IGNITE-1917: Simplifying schema.
Project: http://git-wip-us.apache.org/repos/asf/ignite/repo Commit: http://git-wip-us.apache.org/repos/asf/ignite/commit/678314fe Tree: http://git-wip-us.apache.org/repos/asf/ignite/tree/678314fe Diff: http://git-wip-us.apache.org/repos/asf/ignite/diff/678314fe Branch: refs/heads/ignite-1917 Commit: 678314fe20112e3ffd98f8e2537519bad312a433 Parents: 8200031 Author: vozerov-gridgain <voze...@gridgain.com> Authored: Tue Nov 17 18:13:20 2015 +0300 Committer: vozerov-gridgain <voze...@gridgain.com> Committed: Tue Nov 17 18:13:20 2015 +0300 ---------------------------------------------------------------------- .../internal/portable/PortableSchema.java | 191 ++++++++++++++++- .../portable/PortableSchemaIntIntMap.java | 214 ------------------- 2 files changed, 183 insertions(+), 222 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/ignite/blob/678314fe/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 f970290..7738ae5 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 @@ -38,14 +38,23 @@ public class PortableSchema implements Externalizable { /** Order returned if field is not found. */ public static final int ORDER_NOT_FOUND = -1; + /** Minimum sensible size. */ + private static final int MAP_MIN_SIZE = 32; + + /** Empty cell. */ + private static final int MAP_EMPTY = 0; + /** Inline flag. */ private boolean inline; /** IDs depending on order. */ private int[] ids; - /** Map form field ID to order. */ - private PortableSchemaIntIntMap idToOrder; + /** ID-to-order data. */ + private int[] idToOrderData; + + /** ID-to-order mask. */ + private int idToOrderMask; /** ID 1. */ private int id0; @@ -103,8 +112,6 @@ public class PortableSchema implements Externalizable { id5 = iter.hasNext() ? iter.next() : 0; id6 = iter.hasNext() ? iter.next() : 0; id7 = iter.hasNext() ? iter.next() : 0; - - idToOrder = null; } else { inline = false; @@ -116,7 +123,7 @@ public class PortableSchema implements Externalizable { for (int i = 0; i < fieldIds.size(); i++) ids[i] = fieldIds.get(i); - idToOrder = new PortableSchemaIntIntMap(ids); + initializeMap(ids); } } @@ -204,8 +211,33 @@ public class PortableSchema implements Externalizable { return ORDER_NOT_FOUND; } - else - return idToOrder.get(id); + else { + int idx = (id & idToOrderMask) << 1; + + int curId = idToOrderData[idx]; + + if (id == curId) // Hit! + return idToOrderData[idx + 1]; + else if (curId == MAP_EMPTY) // No such ID! + return ORDER_NOT_FOUND; + else { + // Unlikely collision scenario. + for (int i = 2; i < idToOrderData.length; i += 2) { + int newIdx = (idx + i) % idToOrderData.length; + + assert newIdx < idToOrderData.length - 1; + + curId = idToOrderData[newIdx]; + + if (id == curId) + return idToOrderData[newIdx + 1]; + else if (curId == MAP_EMPTY) + return ORDER_NOT_FOUND; + } + + return ORDER_NOT_FOUND; + } + } } /** {@inheritDoc} */ @@ -270,8 +302,129 @@ public class PortableSchema implements Externalizable { for (int i = 0; i < size; i++) ids[i] = in.readInt(); - idToOrder = new PortableSchemaIntIntMap(ids); + initializeMap(ids); + } + } + + /** + * Parse values. + * + * @param vals Values. + * @param size Proposed result size. + * @return Parse result. + */ + private static ParseResult parse(int[] vals, int size) { + int mask = maskForPowerOfTwo(size); + + int totalSize = size * 2; + + int[] data = new int[totalSize]; + int collisions = 0; + + for (int order = 0; order < vals.length; order++) { + int id = vals[order]; + + 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; + } + + /** + * Initialize the map. + * + * @param vals Values. + */ + private void initializeMap(int[] vals) { + int size = Math.max(nextPowerOfTwo(vals.length) << 2, MAP_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); + } + + idToOrderData = finalRes.data; + idToOrderMask = maskForPowerOfTwo(idToOrderData.length / 2); } /** @@ -320,4 +473,26 @@ public class PortableSchema implements Externalizable { return new PortableSchema(schemaId, fields); } } + + /** + * Result of map parsing. + */ + private static class ParseResult { + /** Data. */ + private int[] data; + + /** Collisions. */ + private int collisions; + + /** + * Constructor. + * + * @param data Data. + * @param collisions Collisions. + */ + private ParseResult(int[] data, int collisions) { + this.data = data; + this.collisions = collisions; + } + } } http://git-wip-us.apache.org/repos/asf/ignite/blob/678314fe/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 deleted file mode 100644 index 8b8f7cf..0000000 --- a/modules/core/src/main/java/org/apache/ignite/internal/portable/PortableSchemaIntIntMap.java +++ /dev/null @@ -1,214 +0,0 @@ -/* - * 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; - -/** - * 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(int[] vals) { - int size = Math.max(nextPowerOfTwo(vals.length) << 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(int[] vals, int size) { - int mask = maskForPowerOfTwo(size); - - int totalSize = size * 2; - - int[] data = new int[totalSize]; - int collisions = 0; - - for (int order = 0; order < vals.length; order++) { - int id = vals[order]; - - 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; - } - } -}