You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@datasketches.apache.org by "jmalkin (via GitHub)" <gi...@apache.org> on 2024/05/31 05:31:58 UTC
[PR] Common bitarray (datasketches-java)
jmalkin opened a new pull request, #567:
URL: https://github.com/apache/datasketches-java/pull/567
Refactored BloomFilter's `BitArray` class to make it common across filters. That involved making it public, so all the methods in the abstract base class now have a javadoc.
BitArray now has `getBits(index, numBits)` and `setBits(index, numBits, value)` (where the max size is 64 bits) as well as `assignBit(index, value)`. The QuotientFilter has been updated to use this class, and the old Bitmap wrapping some legacy CERN code has been removed.
Opening this against the reviewed branch, but we probably then want to merge back into quotient-filter after that?
--
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: commits-unsubscribe@datasketches.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org
Re: [PR] Common bitarray (datasketches-java)
Posted by "c-dickens (via GitHub)" <gi...@apache.org>.
c-dickens commented on code in PR #567:
URL: https://github.com/apache/datasketches-java/pull/567#discussion_r1622173486
##########
src/test/java/org/apache/datasketches/filters/quotientfilter/QuotientFilterTest.java:
##########
@@ -158,30 +166,32 @@ static public void OverflowTest() {
* and the program exits, indicating a test failure.
*/
@Test
- static public void testQuotientFilterInsertionAndIteration() {
+ public void testQuotientFilterInsertionAndIteration() {
int bits_per_entry = 8;
int num_entries_power = 4;
//int num_entries = (int)Math.pow(2, num_entries_power);
//int fingerprint_size = bits_per_entry - 3;
QuotientFilter qf = new QuotientFilter(num_entries_power, bits_per_entry);
- qf.insert(0, 2, false);
- qf.insert(0, 3, false);
- qf.insert(0, 3, false);
- qf.insert(0, 4, false);
- qf.insert(0, 15, false); // last slot in the filter
- qf.insert(0, 16, false); // outside the bounds
+ qf.insert(0x1F, 0, false);
+ qf.insert(0x1F, 2, false);
+ qf.insert(0x1F, 3, false);
+ qf.insert(0x1F, 3, false);
+ qf.insert(0x1F, 4, false);
+ qf.insert(0x1F, 15, false); // last slot in the filter
+ qf.insert(0x1F, 16, false); // outside the bounds
qf.pretty_print() ;
Iterator it = new Iterator(qf);
- int[] arr = new int[] {2, 3, 3, 4, 15};
+ //int[] arr = new int[] {2, 3, 3, 4, 15};
Review Comment:
remove commented line as the correct array is defined below?
--
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: commits-unsubscribe@datasketches.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org
Re: [PR] Common bitarray (datasketches-java)
Posted by "jmalkin (via GitHub)" <gi...@apache.org>.
jmalkin commented on code in PR #567:
URL: https://github.com/apache/datasketches-java/pull/567#discussion_r1622807094
##########
src/main/java/org/apache/datasketches/filters/common/BitArray.java:
##########
@@ -0,0 +1,302 @@
+/*
+ * 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.datasketches.filters.common;
+
+import static org.apache.datasketches.common.Util.LS;
+
+import org.apache.datasketches.common.SketchesArgumentException;
+import org.apache.datasketches.memory.Buffer;
+import org.apache.datasketches.memory.Memory;
+import org.apache.datasketches.memory.WritableMemory;
+
+/**
+ * This class holds an array of bits suitable for use in a Bloom Filter
Review Comment:
Fixed and added a little more context on max size.
(Marking as resolved when I fix locally, before committing)
--
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: commits-unsubscribe@datasketches.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org
Re: [PR] Common bitarray (datasketches-java)
Posted by "jmalkin (via GitHub)" <gi...@apache.org>.
jmalkin commented on code in PR #567:
URL: https://github.com/apache/datasketches-java/pull/567#discussion_r1622807984
##########
src/main/java/org/apache/datasketches/theta/Sketches.java:
##########
@@ -79,15 +79,32 @@ public static int getMaxAnotBResultBytes(final int maxNomEntries) {
}
/**
- * Ref: {@link Sketch#getMaxCompactSketchBytes(int)}
- * @param numberOfEntries Ref: {@link Sketch#getMaxCompactSketchBytes(int)},
- * {@code numberOfEntries}
- * @return Ref: {@link Sketch#getMaxCompactSketchBytes(int)}
- */
+ * Returns the maximum number of storage bytes required for a CompactSketch with the given
+ * number of actual entries. Note that this assumes the worse case of the sketch in
Review Comment:
Didn't even mean to pull this in. I think I inadvertently pulled form the main branch -- I thought I fetched and switches to the quantiles-filter branch! But will fix.
--
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: commits-unsubscribe@datasketches.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org
Re: [PR] Common bitarray (datasketches-java)
Posted by "jmalkin (via GitHub)" <gi...@apache.org>.
jmalkin commented on code in PR #567:
URL: https://github.com/apache/datasketches-java/pull/567#discussion_r1622810716
##########
src/test/java/org/apache/datasketches/filters/quotientfilter/QuotientFilterTest.java:
##########
@@ -158,30 +166,32 @@ static public void OverflowTest() {
* and the program exits, indicating a test failure.
*/
@Test
- static public void testQuotientFilterInsertionAndIteration() {
+ public void testQuotientFilterInsertionAndIteration() {
int bits_per_entry = 8;
int num_entries_power = 4;
//int num_entries = (int)Math.pow(2, num_entries_power);
//int fingerprint_size = bits_per_entry - 3;
QuotientFilter qf = new QuotientFilter(num_entries_power, bits_per_entry);
- qf.insert(0, 2, false);
- qf.insert(0, 3, false);
- qf.insert(0, 3, false);
- qf.insert(0, 4, false);
- qf.insert(0, 15, false); // last slot in the filter
- qf.insert(0, 16, false); // outside the bounds
+ qf.insert(0x1F, 0, false);
+ qf.insert(0x1F, 2, false);
+ qf.insert(0x1F, 3, false);
+ qf.insert(0x1F, 3, false);
+ qf.insert(0x1F, 4, false);
+ qf.insert(0x1F, 15, false); // last slot in the filter
+ qf.insert(0x1F, 16, false); // outside the bounds
qf.pretty_print() ;
Iterator it = new Iterator(qf);
- int[] arr = new int[] {2, 3, 3, 4, 15};
+ //int[] arr = new int[] {2, 3, 3, 4, 15};
Review Comment:
Had modified the test during debugging but clearly didn't roll it all back. Can remove the addition of item 0 but keeping the fingerprints as `0x1F` since it was much easier to debug when actually setting something!
--
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: commits-unsubscribe@datasketches.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org
Re: [PR] Common bitarray (datasketches-java)
Posted by "jmalkin (via GitHub)" <gi...@apache.org>.
jmalkin merged PR #567:
URL: https://github.com/apache/datasketches-java/pull/567
--
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: commits-unsubscribe@datasketches.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org
Re: [PR] Common bitarray (datasketches-java)
Posted by "c-dickens (via GitHub)" <gi...@apache.org>.
c-dickens commented on code in PR #567:
URL: https://github.com/apache/datasketches-java/pull/567#discussion_r1622146327
##########
src/main/java/org/apache/datasketches/theta/Sketches.java:
##########
@@ -79,15 +79,32 @@ public static int getMaxAnotBResultBytes(final int maxNomEntries) {
}
/**
- * Ref: {@link Sketch#getMaxCompactSketchBytes(int)}
- * @param numberOfEntries Ref: {@link Sketch#getMaxCompactSketchBytes(int)},
- * {@code numberOfEntries}
- * @return Ref: {@link Sketch#getMaxCompactSketchBytes(int)}
- */
+ * Returns the maximum number of storage bytes required for a CompactSketch with the given
+ * number of actual entries. Note that this assumes the worse case of the sketch in
Review Comment:
worse --> worst
--
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: commits-unsubscribe@datasketches.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org
Re: [PR] Common bitarray (datasketches-java)
Posted by "c-dickens (via GitHub)" <gi...@apache.org>.
c-dickens commented on code in PR #567:
URL: https://github.com/apache/datasketches-java/pull/567#discussion_r1622024424
##########
src/main/java/org/apache/datasketches/filters/common/BitArray.java:
##########
@@ -0,0 +1,302 @@
+/*
+ * 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.datasketches.filters.common;
+
+import static org.apache.datasketches.common.Util.LS;
+
+import org.apache.datasketches.common.SketchesArgumentException;
+import org.apache.datasketches.memory.Buffer;
+import org.apache.datasketches.memory.Memory;
+import org.apache.datasketches.memory.WritableMemory;
+
+/**
+ * This class holds an array of bits suitable for use in a Bloom Filter
Review Comment:
minor - but I think that this line should be changed if we use it in Quotient Filter as well.
--
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: commits-unsubscribe@datasketches.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org