You are viewing a plain text version of this content. The canonical link for it is here.
Posted to issues@commons.apache.org by GitBox <gi...@apache.org> on 2022/07/29 15:19:45 UTC
[GitHub] [commons-collections] aherbert commented on a diff in pull request #320: Collections 824: Optimize SimpleHasher.forEachIndex and SimpleHasher name change
aherbert commented on code in PR #320:
URL: https://github.com/apache/commons-collections/pull/320#discussion_r933241690
##########
src/main/java/org/apache/commons/collections4/bloomfilter/EnhancedDoubleHasher.java:
##########
@@ -129,24 +126,60 @@ public IndexProducer indices(final Shape shape) {
@Override
public boolean forEachIndex(IntPredicate consumer) {
Objects.requireNonNull(consumer, "consumer");
- int bits = shape.getNumberOfBits();
- /*
- * Essentially this is computing a wrapped modulus from a start point and an
- * increment. So actually you only need two modulus operations before the loop.
- * This avoids any modulus operation inside the while loop. It uses a long index
- * to avoid overflow.
- */
- long index = mod(initial, bits);
+ final int bits = shape.getNumberOfBits();
+ // Enhanced double hashing:
+ // hash[i] = ( h1(x) + i*h2(x) + (i*i*i - i)/6 ) mod bits
+ // See: https://en.wikipedia.org/wiki/Double_hashing#Enhanced_double_hashing
+ //
+ // Essentially this is computing a wrapped modulus from a start point and an
+ // increment and an additional term as a tetrahedral number.
+ // You only need two modulus operations before the loop. Within the loop
+ // the modulus is handled using the sign bit to detect wrapping to ensure:
+ // 0 <= index < bits
+ // 0 <= inc < bits
+ // The final hash is:
+ // hash[i] = ( h1(x) - i*h2(x) - (i*i*i - i)/6 ) wrapped in [0, bits)
+
+ int index = mod(initial, bits);
int inc = mod(increment, bits);
- for (int functionalCount = 0; functionalCount < shape.getNumberOfHashFunctions(); functionalCount++) {
-
- if (!consumer.test((int) index)) {
- return false;
+ final int k = shape.getNumberOfHashFunctions();
+ if (k>bits) {
Review Comment:
`k > bits`
##########
src/main/java/org/apache/commons/collections4/bloomfilter/Hasher.java:
##########
@@ -52,5 +55,14 @@ public interface Hasher {
* @param shape the shape of the desired Bloom filter.
* @return the iterator of integers
*/
- IndexProducer uniqueIndices(Shape shape);
+ default IndexProducer uniqueIndices(Shape shape) {
+ return new IndexProducer() {
Review Comment:
The functional interface can return a lambda:
```java
return consumer -> {
Objects.requireNonNull(consumer, "consumer");
return Hasher.this.indices(shape).forEachIndex(IndexFilter.create(shape, consumer));
};
```
##########
src/main/java/org/apache/commons/collections4/bloomfilter/EnhancedDoubleHasher.java:
##########
@@ -58,50 +59,46 @@ private static long toLong(byte[] byteArray, int offset, int len) {
}
/**
- * Constructs the SimpleHasher from a byte array.
+ * Constructs the EnhancedDoubleHasher from a byte array.
* <p>The byte array is split in 2 and each half is interpreted as a long value.
* Excess bytes are ignored. This simplifies the conversion from a Digest or hasher algorithm output
* to the two values used by the SimpleHasher.</p>
- * <p><em>If the second long is zero the default increment is used instead.</em></p>
* @param buffer the buffer to extract the longs from.
* @throws IllegalArgumentException is buffer length is zero.
- * @see #getDefaultIncrement()
*/
- public SimpleHasher(byte[] buffer) {
+ public EnhancedDoubleHasher(byte[] buffer) {
if (buffer.length == 0) {
throw new IllegalArgumentException("buffer length must be greater than 0");
}
int segment = buffer.length / 2;
Review Comment:
Since length will be positive you could use a bit shift here: `int segment = buffer.length >>> 1`
The conversion to long is not easy to explain and the javadoc is missing details. After dividing in half, up to the first 8 bytes from each half are used to construct a long. The bytes are interpreted in big-endian order but if the buffer is less than 8 bytes then zeros are effectively prepended at the start.
This is a non-standard zero fill behaviour (true big-endian number after the BE):
```
// big-endian order with zero filling start
a -> a BE: a0000000
ab -> ab BE: ab000000
abcdefg -> abcdefg BE: abcdefg0
abcdefgh -> abcdefgh BE: abcdefgh
// Now ignoring the end as we reached 8 bytes
abcdefghi -> abcdefgh
abcdefghij -> abcdefgh
```
This is basically not achieving the same as:
```Java
// copy (with zero-fill) at least 8 bytes from the offset
return ByteBuffer.wrap(
Arrays.copyOfRange(byteArray, offset, offset + Math.max(len, 8)))
.order(ByteOrder.BIG_ENDIAN)
.getLong();
```
If you keep it the same then note that the `toLong` method can avoid an addition inside the loop by using a start-end iteration:
```java
private static long toLong(byte[] byteArray, int offset, int len) {
long val = 0;
final int end = offset + Math.min(len, Long.BYTES);
for (int i = offset; i < end; i++) {
val <<= 8;
val |= (byteArray[i] & 0xff);
}
return val;
}
```
The bytes could be interpreted as little-endian:
```java
private static long toLong(byte[] byteArray, int offset, int len) {
long val = 0;
final int end = offset + Math.min(len, Long.BYTES);
int shift = 0;
for (int i = offset; i < end; i++) {
val |= (byteArray[i] & 0xff) << shift;
shift += 8;
}
return val;
}
```
Using the little endian is easier to explain as the bytes are cut in half and up to 8 bytes from each is read as a long in little endian order.
Using little-endian, or the current code, both create smaller numbers when needing zero fill. Only a true big-endian read will create a large number.
### Thoughts on the hasher input:
Note that it is worse to create smaller numbers for the increment and start point. If the start is smaller than the number of bits in a filter then hashing will start at the same point when the size increases; likewise the increment will be the same if it remains smaller than the number of bits in the filter and so the first few indices will be the same if the number of bits changes (but is still larger than the increment). In a worse case scenario with small start and increments for all items, hashing may not create indices that fill the full region within a much larger filter. Imagine hashers created with a single byte for the start and increment (bounded to 255) with a filter size of 30000 and number of hash functions as 5. Ignoring the tetrahedral addition (a maximum of 20 for k=5) the max index is 255 * 4 + 255 = 1275, this covers 4.25% of the filter. This also ignores the negative wrapping but the behaviour is the same, some bits cannot be reached.
So this needs to be avoided as the filter probability assumptions will be void. If the start and increment are larger than the number of bits then the modulus will create a 'random' position and increment within the size. However if limited to only 1 byte then you still only have 255 possible start positions even though randomly spread. So use big-endian numbers does not help. What matters is the number of bits of entropy in the start and increment. If there are more than 4 bytes to create the long (little-endian) the numbers will be expected to exceed the maximum size of a filter (limited to a 32-bit int).
This behaviour could be noted in the javadoc. It is recommended to create a hasher using at least twice the number of random bytes as the number of non-zero bytes in the shape number of bits:
```java
2 * Math.ceil(Integer.highestOneBit(shape.getNumberOfBits()) / 8.0)
```
That is quite verbose. To simplify then assume a max size shape and recommend that a hasher is not constructed with fewer than 8 bytes of entropy through the `byte[]` constructor, or the 4 bytes of entropy for each argument to the `long, long` constructor; and then update to interpret the bytes as little-endian.
##########
src/main/java/org/apache/commons/collections4/bloomfilter/Shape.java:
##########
@@ -186,20 +186,6 @@ public double estimateN(int cardinality) {
return -(m / k) * Math.log1p(-c / m);
}
- /**
Review Comment:
This was from a previous documented factory. If you are happy that this is covered by the class javadoc then fine. I think the factory method names can be implied to use the standard variable names, but it is not explicitly documented.
Note: Unrelated - why is shape comparable? I thought this was previously discussed as unnecessary. I cannot find a Jira ticket for this. The method is not tested to return a specific order; its only usage in the package is in the equals function.
##########
src/test/java/org/apache/commons/collections4/bloomfilter/IncrementingHasher.java:
##########
@@ -0,0 +1,110 @@
+/*
+ * 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.commons.collections4.bloomfilter;
+
+import java.util.Objects;
+import java.util.function.IntPredicate;
+
+/**
+ * To be used for testing only.
Review Comment:
You could transfer the javadoc from the old SimpleHasher to here. At least then the method is explained.
##########
src/test/java/org/apache/commons/collections4/bloomfilter/IncrementingHasher.java:
##########
@@ -0,0 +1,110 @@
+/*
+ * 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.commons.collections4.bloomfilter;
+
+import java.util.Objects;
+import java.util.function.IntPredicate;
+
+/**
+ * To be used for testing only.
+ */
+class IncrementingHasher implements Hasher {
+
+ /**
+ * The initial hash value.
+ */
+ private final long initial;
+
+ /**
+ * The value to increment the hash value by.
+ */
+ private final long increment;
+
+ /**
+ * Constructs the IncrementingHasher from 2 longs. The long values will be interpreted as unsigned values.
+ * <p><em>If the increment is zero the default increment is used instead.</em></p>
+ * @param initial The initial value for the hasher.
+ * @param increment The value to increment the hash by on each iteration.
+ * @see #getDefaultIncrement()
Review Comment:
NA
##########
src/test/java/org/apache/commons/collections4/bloomfilter/IncrementingHasher.java:
##########
@@ -0,0 +1,110 @@
+/*
+ * 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.commons.collections4.bloomfilter;
+
+import java.util.Objects;
+import java.util.function.IntPredicate;
+
+/**
+ * To be used for testing only.
+ */
+class IncrementingHasher implements Hasher {
+
+ /**
+ * The initial hash value.
+ */
+ private final long initial;
+
+ /**
+ * The value to increment the hash value by.
+ */
+ private final long increment;
+
+ /**
+ * Constructs the IncrementingHasher from 2 longs. The long values will be interpreted as unsigned values.
+ * <p><em>If the increment is zero the default increment is used instead.</em></p>
+ * @param initial The initial value for the hasher.
+ * @param increment The value to increment the hash by on each iteration.
+ * @see #getDefaultIncrement()
+ */
+ IncrementingHasher(long initial, long increment) {
+ this.initial = initial;
+ this.increment = increment;
+ }
+
+ /**
+ * Performs a modulus calculation on an unsigned long and an integer divisor.
+ * @param dividend a unsigned long value to calculate the modulus of.
+ * @param divisor the divisor for the modulus calculation.
+ * @return the remainder or modulus value.
+ */
+ static int mod(long dividend, int divisor) {
Review Comment:
Duplicate of `EnhancedDoubleHasher.mod`. Since that method (which is tested) is package-private then just call that.
##########
src/main/java/org/apache/commons/collections4/bloomfilter/EnhancedDoubleHasher.java:
##########
@@ -21,14 +21,15 @@
/**
* A Hasher that implements combinatorial hashing as as described by
- * <a href="https://www.eecs.harvard.edu/~michaelm/postscripts/tr-02-05.pdf">Krisch and Mitzenmacher</a>.
+ * <a href="https://www.eecs.harvard.edu/~michaelm/postscripts/tr-02-05.pdf">Krisch and Mitzenmacher</a> using the enhanced double hashing technique
+ * described in the wikipedia article <a href="https://en.wikipedia.org/wiki/Double_hashing#Enhanced_double_hashing">Double Hashing</a>.
* <p>
* Common use for this hasher is to generate a byte array as the output of a hashing
Review Comment:
`Common use for this hasher is to generate bit indices from a byte array output of ...`
##########
src/main/java/org/apache/commons/collections4/bloomfilter/EnhancedDoubleHasher.java:
##########
@@ -129,24 +126,60 @@ public IndexProducer indices(final Shape shape) {
@Override
public boolean forEachIndex(IntPredicate consumer) {
Objects.requireNonNull(consumer, "consumer");
- int bits = shape.getNumberOfBits();
- /*
- * Essentially this is computing a wrapped modulus from a start point and an
- * increment. So actually you only need two modulus operations before the loop.
- * This avoids any modulus operation inside the while loop. It uses a long index
- * to avoid overflow.
- */
- long index = mod(initial, bits);
+ final int bits = shape.getNumberOfBits();
+ // Enhanced double hashing:
+ // hash[i] = ( h1(x) + i*h2(x) + (i*i*i - i)/6 ) mod bits
+ // See: https://en.wikipedia.org/wiki/Double_hashing#Enhanced_double_hashing
+ //
+ // Essentially this is computing a wrapped modulus from a start point and an
+ // increment and an additional term as a tetrahedral number.
+ // You only need two modulus operations before the loop. Within the loop
+ // the modulus is handled using the sign bit to detect wrapping to ensure:
+ // 0 <= index < bits
+ // 0 <= inc < bits
+ // The final hash is:
+ // hash[i] = ( h1(x) - i*h2(x) - (i*i*i - i)/6 ) wrapped in [0, bits)
+
+ int index = mod(initial, bits);
int inc = mod(increment, bits);
- for (int functionalCount = 0; functionalCount < shape.getNumberOfHashFunctions(); functionalCount++) {
-
- if (!consumer.test((int) index)) {
- return false;
+ final int k = shape.getNumberOfHashFunctions();
+ if (k>bits) {
+ for (int j = k; j > 0;) {
+ // handle k > bits
+ final int block = Math.min(j, bits);
+ j -= block;
+ for (int i = 0; i < block; i++) {
+ if (!consumer.test(index)) {
+ return false;
Review Comment:
This line has no coverage.
The last commit to Codecov failed. I reran the job to see if it was a glitch. You can do the same locally using:
```Java
mvn test jacoco:report
open target/site/jacoco/org.apache.commons.collections4.bloomfilter/EnhancedDoubleHasher.java.html
```
##########
src/test/java/org/apache/commons/collections4/bloomfilter/AbstractHasherTest.java:
##########
@@ -78,12 +81,40 @@ public void testHashing(int k, int m) {
@Test
public void testUniqueIndex() {
- // create a hasher that produces duplicates with the specified shape.
- // this setup produces 5, 17, 29, 41, 53, 65 two times
- Shape shape = Shape.fromKM(12, 72);
- Hasher hasher = new SimpleHasher(5, 12);
- Set<Integer> set = new HashSet<>();
- assertTrue(hasher.uniqueIndices(shape).forEachIndex(set::add), "Duplicate detected");
- assertEquals(6, set.size());
+ // @formatter:off
+ /*
+ * The probability of a collision when
Review Comment:
Is there a reference for this?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@commons.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org