--- /dev/null
+package org.apache.lucene.facet.taxonomy.writercache.cl2o;
+
+import java.io.BufferedInputStream;
+import java.io.BufferedOutputStream;
+import java.io.DataInputStream;
+import java.io.DataOutputStream;
+import java.io.File;
+import java.io.FileInputStream;
+import java.io.FileOutputStream;
+import java.io.IOException;
+import java.util.Iterator;
+
+import org.apache.lucene.facet.taxonomy.CategoryPath;
+
+/**
+ * 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.
+ */
+
+/**
+ * This is a very efficient LabelToOrdinal implementation that uses a
+ * CharBlockArray to store all labels and a configurable number of HashArrays to
+ * reference the labels.
+ * <p>
+ * Since the HashArrays don't handle collisions, a {@link CollisionMap} is used
+ * to store the colliding labels.
+ * <p>
+ * This data structure grows by adding a new HashArray whenever the number of
+ * collisions in the {@link CollisionMap} exceeds {@code loadFactor} *
+ * {@link #getMaxOrdinal()}. Growing also includes reinserting all colliding
+ * labels into the HashArrays to possibly reduce the number of collisions.
+ *
+ * For setting the {@code loadFactor} see
+ * {@link #CompactLabelToOrdinal(int, float, int)}.
+ *
+ * <p>
+ * This data structure has a much lower memory footprint (~30%) compared to a
+ * Java HashMap<String, Integer>. It also only uses a small fraction of objects
+ * a HashMap would use, thus limiting the GC overhead. Ingestion speed was also
+ * ~50% faster compared to a HashMap for 3M unique labels.
+ *
+ * @lucene.experimental
+ */
+public class CompactLabelToOrdinal extends LabelToOrdinal {
+
+ public static final float DefaultLoadFactor = 0.15f;
+
+ static final char TerminatorChar = 0xffff;
+ private static final int Collision = -5;
+
+ private HashArray[] hashArrays;
+ private CollisionMap collisionMap;
+ private CharBlockArray labelRepository;
+
+ private int capacity;
+ private int threshold;
+ private float loadFactor;
+
+ public int sizeOfMap() {
+ return this.collisionMap.size();
+ }
+
+ private CompactLabelToOrdinal() {
+ }
+
+ public CompactLabelToOrdinal(int initialCapacity, float loadFactor,
+ int numHashArrays) {
+
+ this.hashArrays = new HashArray[numHashArrays];
+
+ this.capacity = determineCapacity((int) Math.pow(2, numHashArrays),
+ initialCapacity);
+ init();
+ this.collisionMap = new CollisionMap(this.labelRepository);
+
+ this.counter = 0;
+ this.loadFactor = loadFactor;
+
+ this.threshold = (int) (this.loadFactor * this.capacity);
+ }
+
+ static int determineCapacity(int minCapacity, int initialCapacity) {
+ int capacity = minCapacity;
+ while (capacity < initialCapacity) {
+ capacity <<= 1;
+ }
+ return capacity;
+ }
+
+ private void init() {
+ labelRepository = new CharBlockArray();
+ try {
+ new CategoryPath().serializeAppendTo(labelRepository);
+ } catch (IOException e) { } //can't happen
+
+ int c = this.capacity;
+ for (int i = 0; i < this.hashArrays.length; i++) {
+ this.hashArrays[i] = new HashArray(c);
+ c /= 2;
+ }
+ }
+
+ @Override
+ public void addLabel(CategoryPath label, int ordinal) {
+ if (this.collisionMap.size() > this.threshold) {
+ grow();
+ }
+
+ int hash = CompactLabelToOrdinal.stringHashCode(label);
+ for (int i = 0; i < this.hashArrays.length; i++) {
+ if (addLabel(this.hashArrays[i], label, hash, ordinal)) {
+ return;
+ }
+ }
+
+ int prevVal = this.collisionMap.addLabel(label, hash, ordinal);
+ if (prevVal != ordinal) {
+ throw new IllegalArgumentException("Label already exists: " +
+ label.toString('/') + " prev ordinal " + prevVal);
+ }
+ }
+
+ @Override
+ public void addLabel(CategoryPath label, int prefixLen, int ordinal) {
+ if (this.collisionMap.size() > this.threshold) {
+ grow();
+ }
+
+ int hash = CompactLabelToOrdinal.stringHashCode(label, prefixLen);
+ for (int i = 0; i < this.hashArrays.length; i++) {
+ if (addLabel(this.hashArrays[i], label, prefixLen, hash, ordinal)) {
+ return;
+ }
+ }
+
+ int prevVal = this.collisionMap.addLabel(label, prefixLen, hash, ordinal);
+ if (prevVal != ordinal) {
+ throw new IllegalArgumentException("Label already exists: " +
+ label.toString('/', prefixLen) + " prev ordinal " + prevVal);
+ }
+ }
+
+ @Override
+ public int getOrdinal(CategoryPath label) {
+ if (label == null) {
+ return LabelToOrdinal.InvalidOrdinal;
+ }
+
+ int hash = CompactLabelToOrdinal.stringHashCode(label);
+ for (int i = 0; i < this.hashArrays.length; i++) {
+ int ord = getOrdinal(this.hashArrays[i], label, hash);
+ if (ord != Collision) {
+ return ord;
+ }
+ }
+
+ return this.collisionMap.get(label, hash);
+ }
+
+ @Override
+ public int getOrdinal(CategoryPath label, int prefixLen) {
+ if (label == null) {
+ return LabelToOrdinal.InvalidOrdinal;
+ }
+
+ int hash = CompactLabelToOrdinal.stringHashCode(label, prefixLen);
+ for (int i = 0; i < this.hashArrays.length; i++) {
+ int ord = getOrdinal(this.hashArrays[i], label, prefixLen, hash);
+ if (ord != Collision) {
+ return ord;
+ }
+ }
+
+ return this.collisionMap.get(label, prefixLen, hash);
+ }
+
+ private void grow() {
+ HashArray temp = this.hashArrays[this.hashArrays.length - 1];
+
+ for (int i = this.hashArrays.length - 1; i > 0; i--) {
+ this.hashArrays[i] = this.hashArrays[i - 1];
+ }
+
+ this.capacity *= 2;
+ this.hashArrays[0] = new HashArray(this.capacity);
+
+ for (int i = 1; i < this.hashArrays.length; i++) {
+ int[] sourceOffsetArray = this.hashArrays[i].offsets;
+ int[] sourceCidsArray = this.hashArrays[i].cids;
+
+ for (int k = 0; k < sourceOffsetArray.length; k++) {
+
+ for (int j = 0; j < i && sourceOffsetArray[k] != 0; j++) {
+ int[] targetOffsetArray = this.hashArrays[j].offsets;
+ int[] targetCidsArray = this.hashArrays[j].cids;
+
+ int newIndex = indexFor(stringHashCode(
+ this.labelRepository, sourceOffsetArray[k]),
+ targetOffsetArray.length);
+ if (targetOffsetArray[newIndex] == 0) {
+ targetOffsetArray[newIndex] = sourceOffsetArray[k];
+ targetCidsArray[newIndex] = sourceCidsArray[k];
+ sourceOffsetArray[k] = 0;
+ }
+ }
+ }
+ }
+
+ for (int i = 0; i < temp.offsets.length; i++) {
+ int offset = temp.offsets[i];
+ if (offset > 0) {
+ int hash = stringHashCode(this.labelRepository, offset);
+ addLabelOffset(hash, temp.cids[i], offset);
+ }
+ }
+
+ CollisionMap oldCollisionMap = this.collisionMap;
+ this.collisionMap = new CollisionMap(oldCollisionMap.capacity(),
+ this.labelRepository);
+ this.threshold = (int) (this.capacity * this.loadFactor);
+
+ Iterator<CollisionMap.Entry> it = oldCollisionMap.entryIterator();
+ while (it.hasNext()) {
+ CollisionMap.Entry e = it.next();
+ addLabelOffset(stringHashCode(this.labelRepository, e.offset),
+ e.cid, e.offset);
+ }
+ }
+
+ private boolean addLabel(HashArray a, CategoryPath label, int hash,
+ int ordinal) {
+ int index = CompactLabelToOrdinal.indexFor(hash, a.offsets.length);
+ int offset = a.offsets[index];
+
+ if (offset == 0) {
+ a.offsets[index] = this.labelRepository.length();
+ try {
+ label.serializeAppendTo(this.labelRepository);
+ } catch (IOException e) {
+ // can't happen - LabelRepository.append() never throws an
+ // exception
+ }
+ a.cids[index] = ordinal;
+ return true;
+ }
+
+ return false;
+ }
+
+ private boolean addLabel(HashArray a, CategoryPath label, int prefixLen,
+ int hash, int ordinal) {
+ int index = CompactLabelToOrdinal.indexFor(hash, a.offsets.length);
+ int offset = a.offsets[index];
+
+ if (offset == 0) {
+ a.offsets[index] = this.labelRepository.length();
+ try {
+ label.serializeAppendTo(prefixLen, this.labelRepository);
+ } catch (IOException e) {
+ // can't happen - LabelRepository.append() never throws an
+ // exception
+ }
+ a.cids[index] = ordinal;
+ return true;
+ }
+
+ return false;
+ }
+
+ private void addLabelOffset(int hash, int cid, int knownOffset) {
+ for (int i = 0; i < this.hashArrays.length; i++) {
+ if (addLabelOffsetToHashArray(this.hashArrays[i], hash, cid,
+ knownOffset)) {
+ return;
+ }
+ }
+
+ this.collisionMap.addLabelOffset(hash, knownOffset, cid);
+
+ if (this.collisionMap.size() > this.threshold) {
+ grow();
+ }
+ }
+
+ private boolean addLabelOffsetToHashArray(HashArray a, int hash, int ordinal,
+ int knownOffset) {
+
+ int index = CompactLabelToOrdinal.indexFor(hash, a.offsets.length);
+ int offset = a.offsets[index];
+
+ if (offset == 0) {
+ a.offsets[index] = knownOffset;
+ a.cids[index] = ordinal;
+ return true;
+ }
+
+ return false;
+ }
+
+ private int getOrdinal(HashArray a, CategoryPath label, int hash) {
+ if (label == null) {
+ return LabelToOrdinal.InvalidOrdinal;
+ }
+
+ int index = CompactLabelToOrdinal.indexFor(hash, a.offsets.length);
+ int offset = a.offsets[index];
+ if (offset == 0) {
+ return LabelToOrdinal.InvalidOrdinal;
+ }
+
+ if (label.equalsToSerialized(labelRepository, offset)) {
+ return a.cids[index];
+ }
+
+ return Collision;
+ }
+
+ private int getOrdinal(HashArray a, CategoryPath label, int prefixLen, int hash) {
+ if (label == null) {
+ return LabelToOrdinal.InvalidOrdinal;
+ }
+
+ int index = CompactLabelToOrdinal.indexFor(hash, a.offsets.length);
+ int offset = a.offsets[index];
+ if (offset == 0) {
+ return LabelToOrdinal.InvalidOrdinal;
+ }
+
+ if (label.equalsToSerialized(prefixLen, labelRepository, offset)) {
+ return a.cids[index];
+ }
+
+ return Collision;
+ }
+
+ /**
+ * Returns index for hash code h.
+ */
+ static int indexFor(int h, int length) {
+ return h & (length - 1);
+ }
+
+ // static int stringHashCode(String label) {
+ // int len = label.length();
+ // int hash = 0;
+ // int i;
+ // for (i = 0; i < len; ++i)
+ // hash = 33 * hash + label.charAt(i);
+ //
+ // hash = hash ^ ((hash >>> 20) ^ (hash >>> 12));
+ // hash = hash ^ (hash >>> 7) ^ (hash >>> 4);
+ //
+ // return hash;
+ //
+ // }
+
+ static int stringHashCode(CategoryPath label) {
+ int hash = label.hashCode();
+
+ hash = hash ^ ((hash >>> 20) ^ (hash >>> 12));
+ hash = hash ^ (hash >>> 7) ^ (hash >>> 4);
+
+ return hash;
+
+ }
+
+ static int stringHashCode(CategoryPath label, int prefixLen) {
+ int hash = label.hashCode(prefixLen);
+
+ hash = hash ^ ((hash >>> 20) ^ (hash >>> 12));
+ hash = hash ^ (hash >>> 7) ^ (hash >>> 4);
+
+ return hash;
+
+ }
+
+ static int stringHashCode(CharBlockArray labelRepository, int offset) {
+ int hash = CategoryPath.hashCodeOfSerialized(labelRepository, offset);
+
+ hash = hash ^ ((hash >>> 20) ^ (hash >>> 12));
+ hash = hash ^ (hash >>> 7) ^ (hash >>> 4);
+
+ return hash;
+ }
+
+ // public static boolean equals(CharSequence label, CharBlockArray array,
+ // int offset) {
+ // // CONTINUE HERE
+ // int len = label.length();
+ // int bi = array.blockIndex(offset);
+ // CharBlockArray.Block b = array.blocks.get(bi);
+ // int index = array.indexInBlock(offset);
+ //
+ // for (int i = 0; i < len; i++) {
+ // if (label.charAt(i) != b.chars[index]) {
+ // return false;
+ // }
+ // index++;
+ // if (index == b.length) {
+ // b = array.blocks.get(++bi);
+ // index = 0;
+ // }
+ // }
+ //
+ // return b.chars[index] == TerminatorChar;
+ // }
+
+ /**
+ * Returns an estimate of the amount of memory used by this table. Called only in
+ * this package. Memory is consumed mainly by three structures: the hash arrays,
+ * label repository and collision map.
+ */
+ int getMemoryUsage() {
+ int memoryUsage = 0;
+ if (this.hashArrays != null) {
+ // HashArray capacity is instance-specific.
+ for (HashArray ha : this.hashArrays) {
+ // Each has 2 capacity-length arrays of ints.
+ memoryUsage += ( ha.capacity * 2 * 4 ) + 4;
+ }
+ }
+ if (this.labelRepository != null) {
+ // All blocks are the same size.
+ int blockSize = this.labelRepository.blockSize;
+ // Each block has room for blockSize UTF-16 chars.
+ int actualBlockSize = ( blockSize * 2 ) + 4;
+ memoryUsage += this.labelRepository.blocks.size() * actualBlockSize;
+ memoryUsage += 8; // Two int values for array as a whole.
+ }
+ if (this.collisionMap != null) {
+ memoryUsage += this.collisionMap.getMemoryUsage();
+ }
+ return memoryUsage;
+ }
+
+ /**
+ * Opens the file and reloads the CompactLabelToOrdinal. The file it expects
+ * is generated from the {@link #flush()} command.
+ */
+ static CompactLabelToOrdinal open(File file, float loadFactor,
+ int numHashArrays) throws IOException {
+ /**
+ * Part of the file is the labelRepository, which needs to be rehashed
+ * and label offsets re-added to the object. I am unsure as to why we
+ * can't just store these off in the file as well, but in keeping with
+ * the spirit of the original code, I did it this way. (ssuppe)
+ */
+ CompactLabelToOrdinal l2o = new CompactLabelToOrdinal();
+ l2o.loadFactor = loadFactor;
+ l2o.hashArrays = new HashArray[numHashArrays];
+
+ DataInputStream dis = null;
+ try {
+ dis = new DataInputStream(new BufferedInputStream(
+ new FileInputStream(file)));
+
+ // TaxiReader needs to load the "counter" or occupancy (L2O) to know
+ // the next unique facet. we used to load the delimiter too, but
+ // never used it.
+ l2o.counter = dis.readInt();
+
+ l2o.capacity = determineCapacity((int) Math.pow(2,
+ l2o.hashArrays.length), l2o.counter);
+ l2o.init();
+
+ // now read the chars
+ l2o.labelRepository = CharBlockArray.open(dis);
+
+ l2o.collisionMap = new CollisionMap(l2o.labelRepository);
+
+ // Calculate hash on the fly based on how CategoryPath hashes
+ // itself. Maybe in the future we can call some static based methods
+ // in CategoryPath so that this doesn't break again? I don't like
+ // having code in two different places...
+ int cid = 0;
+ // Skip the initial offset, it's the CategoryPath(0,0), which isn't
+ // a hashed value.
+ int offset = 1;
+ int lastStartOffset = offset;
+ // This loop really relies on a well-formed input (assumes pretty blindly
+ // that array offsets will work). Since the initial file is machine
+ // generated, I think this should be OK.
+ while (offset < l2o.labelRepository.length()) {
+ // First component is numcomponents, so we initialize the hash
+ // to this
+ int ncomponents = l2o.labelRepository.charAt(offset++);
+ int hash = ncomponents;
+ // If ncomponents is 0, then we are done?
+ if (ncomponents != 0) {
+
+ // usedchars is always the last member of the 'ends' array
+ // in serialization. Rather than rebuild the entire array,
+ // assign usedchars to the last value we read in. This will
+ // be slightly more memory efficient.
+ int usedchars = 0;
+ for (int i = 0; i < ncomponents; i++) {
+ usedchars = l2o.labelRepository.charAt(offset++);
+ hash = hash * 31 + usedchars;
+ }
+ // Hash the usedchars for this label
+ for (int i = 0; i < usedchars; i++) {
+ hash = hash * 31 + l2o.labelRepository.charAt(offset++);
+ }
+ }
+ // Now that we've hashed the components of the label, do the
+ // final part of the hash algorithm.
+ hash = hash ^ ((hash >>> 20) ^ (hash >>> 12));
+ hash = hash ^ (hash >>> 7) ^ (hash >>> 4);
+ // Add the label, and let's keep going
+ l2o.addLabelOffset(hash, cid, lastStartOffset);
+ cid++;
+ lastStartOffset = offset;
+ }
+
+ } catch (ClassNotFoundException cnfe) {
+ throw new IOException("Invalid file format. Cannot deserialize.");
+ } finally {
+ if (dis != null) {
+ dis.close();
+ }
+ }
+
+ l2o.threshold = (int) (l2o.loadFactor * l2o.capacity);
+ return l2o;
+
+ }
+
+ void flush(File file) throws IOException {
+ FileOutputStream fos = new FileOutputStream(file);
+
+ try {
+ BufferedOutputStream os = new BufferedOutputStream(fos);
+
+ DataOutputStream dos = new DataOutputStream(os);
+ dos.writeInt(this.counter);
+
+ // write the labelRepository
+ this.labelRepository.flush(dos);
+
+ // Closes the data output stream
+ dos.close();
+
+ } finally {
+ fos.close();
+ }
+ }
+
+ private static final class HashArray {
+ int[] offsets;
+ int[] cids;
+
+ int capacity;
+
+ HashArray(int c) {
+ this.capacity = c;
+ this.offsets = new int[this.capacity];
+ this.cids = new int[this.capacity];
+ }
+ }
+}
fnp / pylucene.git / blobdiff