Repository: ignite Updated Branches: refs/heads/ignite-1917 df518bdbd -> cbfd19a4d
IGNITE-1917: Added fast ID resolution. Project: http://git-wip-us.apache.org/repos/asf/ignite/repo Commit: http://git-wip-us.apache.org/repos/asf/ignite/commit/6e773a0d Tree: http://git-wip-us.apache.org/repos/asf/ignite/tree/6e773a0d Diff: http://git-wip-us.apache.org/repos/asf/ignite/diff/6e773a0d Branch: refs/heads/ignite-1917 Commit: 6e773a0d02d761243f83f832aeae9910c3e9e6ac Parents: df518bd Author: vozerov-gridgain <voze...@gridgain.com> Authored: Tue Nov 17 13:11:29 2015 +0300 Committer: vozerov-gridgain <voze...@gridgain.com> Committed: Tue Nov 17 13:11:29 2015 +0300 ---------------------------------------------------------------------- .../internal/portable/PortableSchema.java | 14 +- .../portable/PortableSchemaIntIntMap.java | 217 +++++++++++++++++++ 2 files changed, 226 insertions(+), 5 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/ignite/blob/6e773a0d/modules/core/src/main/java/org/apache/ignite/internal/portable/PortableSchema.java ---------------------------------------------------------------------- diff --git a/modules/core/src/main/java/org/apache/ignite/internal/portable/PortableSchema.java b/modules/core/src/main/java/org/apache/ignite/internal/portable/PortableSchema.java index 86ca5f8..0c49451 100644 --- a/modules/core/src/main/java/org/apache/ignite/internal/portable/PortableSchema.java +++ b/modules/core/src/main/java/org/apache/ignite/internal/portable/PortableSchema.java @@ -47,6 +47,8 @@ public class PortableSchema implements Externalizable { /** Map with ID to order. */ private HashMap<Integer, Integer> idToOrder; + private PortableSchemaIntIntMap fastIdToOrder; + /** IDs depending on order. */ private ArrayList<Integer> ids; @@ -108,6 +110,7 @@ public class PortableSchema implements Externalizable { id7 = iter.hasNext() ? iter.next() : 0; idToOrder = null; + fastIdToOrder = null; } else { inline = false; @@ -123,6 +126,8 @@ public class PortableSchema implements Externalizable { ids.add(fieldId); idToOrder.put(fieldId, i); } + + fastIdToOrder = new PortableSchemaIntIntMap(idToOrder); } } @@ -210,11 +215,8 @@ public class PortableSchema implements Externalizable { return ORDER_NOT_FOUND; } - else { - Integer order = idToOrder.get(id); - - return order != null ? order : ORDER_NOT_FOUND; - } + else + return fastIdToOrder.get(id); } /** {@inheritDoc} */ @@ -283,6 +285,8 @@ public class PortableSchema implements Externalizable { ids.add(fieldId); idToOrder.put(fieldId, i); } + + fastIdToOrder = new PortableSchemaIntIntMap(idToOrder); } } http://git-wip-us.apache.org/repos/asf/ignite/blob/6e773a0d/modules/core/src/main/java/org/apache/ignite/internal/portable/PortableSchemaIntIntMap.java ---------------------------------------------------------------------- diff --git a/modules/core/src/main/java/org/apache/ignite/internal/portable/PortableSchemaIntIntMap.java b/modules/core/src/main/java/org/apache/ignite/internal/portable/PortableSchemaIntIntMap.java new file mode 100644 index 0000000..f554b30 --- /dev/null +++ b/modules/core/src/main/java/org/apache/ignite/internal/portable/PortableSchemaIntIntMap.java @@ -0,0 +1,217 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to You under the Apache License, Version 2.0 + * (the "License"); you may not use this file except in compliance with + * the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package org.apache.ignite.internal.portable; + +import java.util.Map; + +/** + * Map for fast access to field order by ID. + */ +// TODO: IGNITE-1917: Inline into schema. +public class PortableSchemaIntIntMap { + /** Minimum sensible size. */ + private static final int MIN_SIZE = 32; + + /** Empty cell. */ + private static final int EMPTY = 0; + + /** Data. */ + private final int[] data; + + /** Mask for index calculation. */ + private final int mask; + + /** + * Constructor. + * + * @param vals Values. + */ + public PortableSchemaIntIntMap(Map<Integer, Integer> vals) { + int size = Math.max(nextPowerOfTwo(vals.size()) << 2, MIN_SIZE); + + assert size > 0; + + ParseResult finalRes; + + ParseResult res1 = parse(vals, size); + + if (res1.collisions == 0) + finalRes = res1; + else { + ParseResult res2 = parse(vals, size * 2); + + // Failed to decrease aom + if (res2.collisions == 0) + finalRes = res2; + else + finalRes = parse(vals, size * 4); + } + + data = finalRes.data; + + mask = maskForPowerOfTwo(data.length / 2); + } + + /** + * Get order. + * + * @param id ID. + * @return Order. + */ + public int get(int id) { + int idx = (id & mask) << 1; + + int curId = data[idx]; + + if (id == curId) // Hit! + return data[idx + 1]; + else if (curId == EMPTY) // No such ID! + return PortableSchema.ORDER_NOT_FOUND; + else { + // Unlikely collision scenario. + for (int i = 2; i < data.length; i += 2) { + int newIdx = (idx + i) % data.length; + + assert newIdx < data.length - 1; + + curId = data[newIdx]; + + if (id == curId) + return data[newIdx + 1]; + else if (curId == EMPTY) + return PortableSchema.ORDER_NOT_FOUND; + } + + return PortableSchema.ORDER_NOT_FOUND; + } + } + + /** + * Parse values. + * + * @param vals Values. + * @param size Proposed result size. + * @return Parse result. + */ + private static ParseResult parse(Map<Integer, Integer> vals, int size) { + int mask = maskForPowerOfTwo(size); + + int totalSize = size * 2; + + int[] data = new int[totalSize]; + int collisions = 0; + + for (Map.Entry<Integer, Integer> val : vals.entrySet()) { + int id = val.getKey(); + int order = val.getValue(); + + assert id != 0; + + int idIdx = (id & mask) << 1; + + if (data[idIdx] == 0) { + // Found empty slot. + data[idIdx] = id; + data[idIdx + 1] = order; + } + else { + // Collision! + collisions++; + + boolean placeFound = false; + + for (int i = 2; i < totalSize; i += 2) { + int newIdIdx = (idIdx + i) % totalSize; + + if (data[newIdIdx] == 0) { + data[newIdIdx] = id; + data[newIdIdx + 1] = order; + + placeFound = true; + + break; + } + } + + assert placeFound : "Should always have a place for entry!"; + } + } + + return new ParseResult(data, collisions); + } + + /** + * Get next power of two which greater or equal to the given number. + * This implementation is not meant to be very efficient, so it is expected to be used relatively rare. + * + * @param val Number + * @return Nearest pow2. + */ + private static int nextPowerOfTwo(int val) { + int res = 1; + + while (res < val) + res = res << 1; + + if (res < 0) + throw new IllegalArgumentException("Value is too big to find positive pow2: " + val); + + return res; + } + + /** + * Calculate mask for the given value which is a power of two. + * + * @param val Value. + * @return Mask. + */ + private static int maskForPowerOfTwo(int val) { + int mask = 0; + int comparand = 1; + + while (comparand < val) { + mask |= comparand; + + comparand <<= 1; + } + + return mask; + } + + /** + * Result of map parsing. + */ + private static class ParseResult { + /** Data. */ + public int[] data; + + /** Collisions. */ + public int collisions; + + /** + * Constructor. + * + * @param data Data. + * @param collisions Collisions. + */ + public ParseResult(int[] data, int collisions) { + this.data = data; + this.collisions = collisions; + } + } +}
