You are viewing a plain text version of this content. The canonical link for it is here.
Posted to reviews@spark.apache.org by ponkin <gi...@git.apache.org> on 2016/11/17 09:10:43 UTC
[GitHub] spark pull request #15917: SPARK-18252: Using RoaringBitmap for bloom filter...
GitHub user ponkin opened a pull request:
https://github.com/apache/spark/pull/15917
SPARK-18252: Using RoaringBitmap for bloom filters
## What changes were proposed in this pull request?
+ Bloom filter is now using RoaringBitmap as bit vector - to save memory usage
+ Bloom filter is using Murmur 128 bit hash
## How was this patch tested?
All previous tests are valid
Added more accurate test for Byte type
Please review https://cwiki.apache.org/confluence/display/SPARK/Contributing+to+Spark before opening a pull request.
You can merge this pull request into a Git repository by running:
$ git pull https://github.com/ponkin/spark SPARK-18252
Alternatively you can review and apply these changes as the patch at:
https://github.com/apache/spark/pull/15917.patch
To close this pull request, make a commit to your master/trunk branch
with (at least) the following in the commit message:
This closes #15917
----
commit 2cd92c344aabd6cb93a2c14122149f9e2ad1884c
Author: Alexey Ponkin <ap...@luxoft.com>
Date: 2016-11-14T08:06:08Z
SPARK-18252: Using RoaringBitmap for bloom filters
----
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request #15917: SPARK-18252: Using RoaringBitmap for bloom filter...
Posted by srowen <gi...@git.apache.org>.
Github user srowen commented on a diff in the pull request:
https://github.com/apache/spark/pull/15917#discussion_r88455455
--- Diff: common/sketch/src/main/java/org/apache/spark/util/sketch/RoaringBitmapArray.java ---
@@ -0,0 +1,136 @@
+/*
+ * 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.spark.util.sketch;
+
+import org.roaringbitmap.RoaringBitmap;
+
+import java.io.DataInputStream;
+import java.io.DataOutputStream;
+import java.io.IOException;
+import java.util.Arrays;
+
+class RoaringBitmapArray {
+
+ private final RoaringBitmap[] data;
+ private long bitCount; // number of 1`s in bitset
+ private final long numBits; // total number of available bits
+
+ private static int numOfBuckets(long numBits) {
+ if (numBits <= 0) {
+ throw new IllegalArgumentException("numBits must be positive, but got " + numBits);
+ }
+ return (int) Math.ceil(numBits / (double)Integer.MAX_VALUE);
+ }
+
+ private static RoaringBitmap[] initialVector(int numOfBuckets){
--- End diff --
Small style things: space before braces, and after casts, as in a few lines above. Spaces around elements of a for loop, as below.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request #15917: SPARK-18252: Using RoaringBitmap for bloom filter...
Posted by ponkin <gi...@git.apache.org>.
Github user ponkin commented on a diff in the pull request:
https://github.com/apache/spark/pull/15917#discussion_r88460248
--- Diff: common/sketch/src/main/java/org/apache/spark/util/sketch/Murmur3_128.java ---
@@ -0,0 +1,135 @@
+/*
+ * 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.spark.util.sketch;
+
+/**
+ * 128-bit Murmur3 hasher.
+ * Best perfomance is on x86_64 platform
+ * Based on implementation https://github.com/aappleby/smhasher/blob/master/src/MurmurHash3.cpp
+ */
+final class Murmur3_128 {
--- End diff --
In fact the is Murmur hash version which produces 64 - it is called Murmur 2 [Wiki](https://en.wikipedia.org/wiki/MurmurHash), but it is previous version of Murmur, current is Murmur 3 which is faster and give better distribution(Murmur2 has some flaws). Since in bloom filter we always need 1 or more hash functions, creating 128 bit hash(two longs) is pretty good I suppose.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request #15917: SPARK-18252: Using RoaringBitmap for bloom filter...
Posted by ponkin <gi...@git.apache.org>.
Github user ponkin commented on a diff in the pull request:
https://github.com/apache/spark/pull/15917#discussion_r88440366
--- Diff: common/sketch/src/main/java/org/apache/spark/util/sketch/Murmur3_128.java ---
@@ -0,0 +1,135 @@
+/*
+ * 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.spark.util.sketch;
+
+/**
+ * 128-bit Murmur3 hasher.
+ * Best perfomance is on x86_64 platform
+ * Based on implementation https://github.com/aappleby/smhasher/blob/master/src/MurmurHash3.cpp
+ */
+final class Murmur3_128 {
--- End diff --
This decision come from fact that RoaringBitmap supports only int indexes(and can have only Int.MaxValue bits), since we use RoaringBitmap[] to represent vector way larger than Int.MaxValue, we need good hash function to generate long hash values. This implementation is based on [smhasher](https://github.com/aappleby/smhasher/blob/master/src/MurmurHash3.cpp) and [solr implementation](https://github.com/yonik/java_util/blob/master/src/util/hash/MurmurHash3.java) which are both freely available I suppose.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request #15917: SPARK-18252: Using RoaringBitmap for bloom filter...
Posted by srowen <gi...@git.apache.org>.
Github user srowen commented on a diff in the pull request:
https://github.com/apache/spark/pull/15917#discussion_r88455345
--- Diff: common/sketch/src/main/java/org/apache/spark/util/sketch/RoaringBitmapArray.java ---
@@ -0,0 +1,136 @@
+/*
+ * 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.spark.util.sketch;
+
+import org.roaringbitmap.RoaringBitmap;
+
+import java.io.DataInputStream;
+import java.io.DataOutputStream;
+import java.io.IOException;
+import java.util.Arrays;
+
+class RoaringBitmapArray {
--- End diff --
It's certainly worth documenting this in the scaladoc BTW, why the class has to exist.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #15917: SPARK-18252: Using RoaringBitmap for bloom filters
Posted by SparkQA <gi...@git.apache.org>.
Github user SparkQA commented on the issue:
https://github.com/apache/spark/pull/15917
**[Test build #68796 has finished](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/68796/consoleFull)** for PR 15917 at commit [`66f58d1`](https://github.com/apache/spark/commit/66f58d11ecd9d16054619fec94f413fd3b62d9a0).
* This patch **fails Scala style tests**.
* This patch merges cleanly.
* This patch adds no public classes.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #15917: SPARK-18252: Using RoaringBitmap for bloom filters
Posted by lemire <gi...@git.apache.org>.
Github user lemire commented on the issue:
https://github.com/apache/spark/pull/15917
One of the core Roaring authors (@gssiyankai) worked specifically on Roaring and Bloom filters. Any thoughts Gregory?
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #15917: SPARK-18252: Using RoaringBitmap for bloom filters
Posted by SparkQA <gi...@git.apache.org>.
Github user SparkQA commented on the issue:
https://github.com/apache/spark/pull/15917
**[Test build #68782 has started](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/68782/consoleFull)** for PR 15917 at commit [`2cd92c3`](https://github.com/apache/spark/commit/2cd92c344aabd6cb93a2c14122149f9e2ad1884c).
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #15917: SPARK-18252: Using RoaringBitmap for bloom filters
Posted by AmplabJenkins <gi...@git.apache.org>.
Github user AmplabJenkins commented on the issue:
https://github.com/apache/spark/pull/15917
Can one of the admins verify this patch?
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #15917: SPARK-18252: Using RoaringBitmap for bloom filters
Posted by AmplabJenkins <gi...@git.apache.org>.
Github user AmplabJenkins commented on the issue:
https://github.com/apache/spark/pull/15917
Test PASSed.
Refer to this link for build results (access rights to CI server needed):
https://amplab.cs.berkeley.edu/jenkins//job/SparkPullRequestBuilder/68797/
Test PASSed.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request #15917: SPARK-18252: Using RoaringBitmap for bloom filter...
Posted by srowen <gi...@git.apache.org>.
Github user srowen commented on a diff in the pull request:
https://github.com/apache/spark/pull/15917#discussion_r88457983
--- Diff: common/sketch/src/main/java/org/apache/spark/util/sketch/Murmur3_128.java ---
@@ -0,0 +1,135 @@
+/*
+ * 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.spark.util.sketch;
+
+/**
+ * 128-bit Murmur3 hasher.
+ * Best perfomance is on x86_64 platform
+ * Based on implementation https://github.com/aappleby/smhasher/blob/master/src/MurmurHash3.cpp
+ */
+final class Murmur3_128 {
--- End diff --
OK, maybe that makes sense. If bothering with a custom impl, why not 64 bits instead of 128? it would avoid needing a long[2] to take the result?
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request #15917: SPARK-18252: Using RoaringBitmap for bloom filter...
Posted by asfgit <gi...@git.apache.org>.
Github user asfgit closed the pull request at:
https://github.com/apache/spark/pull/15917
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request #15917: SPARK-18252: Using RoaringBitmap for bloom filter...
Posted by srowen <gi...@git.apache.org>.
Github user srowen commented on a diff in the pull request:
https://github.com/apache/spark/pull/15917#discussion_r88456816
--- Diff: common/sketch/src/main/java/org/apache/spark/util/sketch/BloomFilter.java ---
@@ -233,4 +233,5 @@ public static BloomFilter create(long expectedNumItems, long numBits) {
return new BloomFilterImpl(optimalNumOfHashFunctions(expectedNumItems, numBits), numBits);
}
+
--- End diff --
Go ahead and back out this spurious change; there's another newline at the end of the next file
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #15917: SPARK-18252: Using RoaringBitmap for bloom filters
Posted by SparkQA <gi...@git.apache.org>.
Github user SparkQA commented on the issue:
https://github.com/apache/spark/pull/15917
**[Test build #68797 has finished](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/68797/consoleFull)** for PR 15917 at commit [`487da8f`](https://github.com/apache/spark/commit/487da8fbd23f2d861ab10a1faf701696e9ca3967).
* This patch passes all tests.
* This patch merges cleanly.
* This patch adds no public classes.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #15917: SPARK-18252: Using RoaringBitmap for bloom filters
Posted by SparkQA <gi...@git.apache.org>.
Github user SparkQA commented on the issue:
https://github.com/apache/spark/pull/15917
**[Test build #68782 has finished](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/68782/consoleFull)** for PR 15917 at commit [`2cd92c3`](https://github.com/apache/spark/commit/2cd92c344aabd6cb93a2c14122149f9e2ad1884c).
* This patch **fails RAT tests**.
* This patch merges cleanly.
* This patch adds no public classes.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request #15917: SPARK-18252: Using RoaringBitmap for bloom filter...
Posted by srowen <gi...@git.apache.org>.
Github user srowen commented on a diff in the pull request:
https://github.com/apache/spark/pull/15917#discussion_r88455796
--- Diff: common/sketch/src/main/java/org/apache/spark/util/sketch/RoaringBitmapArray.java ---
@@ -0,0 +1,136 @@
+/*
+ * 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.spark.util.sketch;
+
+import org.roaringbitmap.RoaringBitmap;
+
+import java.io.DataInputStream;
+import java.io.DataOutputStream;
+import java.io.IOException;
+import java.util.Arrays;
+
+class RoaringBitmapArray {
+
+ private final RoaringBitmap[] data;
+ private long bitCount; // number of 1`s in bitset
+ private final long numBits; // total number of available bits
+
+ private static int numOfBuckets(long numBits) {
+ if (numBits <= 0) {
+ throw new IllegalArgumentException("numBits must be positive, but got " + numBits);
+ }
+ return (int) Math.ceil(numBits / (double)Integer.MAX_VALUE);
+ }
+
+ private static RoaringBitmap[] initialVector(int numOfBuckets){
+ RoaringBitmap[] vector = new RoaringBitmap[numOfBuckets];
+ for(int i = 0;i<numOfBuckets;i++){
+ vector[i] = new RoaringBitmap();
+ }
+ return vector;
+ }
+
+ RoaringBitmapArray(long numBits) {
+ this(initialVector(numOfBuckets(numBits)), numBits);
+ }
+
+ private RoaringBitmapArray(RoaringBitmap[] data, long numBits) {
+ this.data = data;
+ this.numBits = numBits;
+ long bitCount = 0;
+ for (RoaringBitmap bucket : data) {
+ bitCount += bucket.getCardinality();
+ }
+ this.bitCount = bitCount;
+ }
+
+ /** Returns true if the bit changed value. */
+ boolean set(long index) {
+ int bucketNum = (int)(index / Integer.MAX_VALUE);
+ int bitIdx = (int)(index % Integer.MAX_VALUE);
+ if(!data[bucketNum].contains(bitIdx)) {
+ data[bucketNum].add(bitIdx);
+ bitCount++;
+ return true;
+ }
+ return false;
+ }
+
+ boolean get(long index) {
+ int bucketNum = (int)(index / Integer.MAX_VALUE);
+ int bitIdx = (int) (index % Integer.MAX_VALUE);
+ return data[bucketNum].contains(bitIdx);
+ }
+
+ /** Number of bits */
+ long bitSize() {
+ return numBits;
+ }
+
+ /** Number of set bits (1s) */
+ long cardinality() {
+ return bitCount;
+ }
+
+ /** Combines the two RoaringBitmapArray using bitwise OR. */
+ void putAll(RoaringBitmapArray bitmap) {
+ assert data.length == bitmap.data.length : "RoaringBitmapArray`s must be of equal length when merging";
+ long mergedBitCount = 0;
+ for (int i = 0; i < data.length; i++) {
+ data[i].or(bitmap.data[i]);
+ mergedBitCount += data[i].getCardinality();
+ }
+ this.bitCount = mergedBitCount;
+ }
+
+ void writeTo(DataOutputStream out) throws IOException {
+ out.writeInt(data.length);
+ out.writeLong(numBits);
+ for (RoaringBitmap datum : data) {
+ datum.runOptimize();
+ datum.serialize(out);
+ }
+ }
+
+ static RoaringBitmapArray readFrom(DataInputStream in) throws IOException {
+ int numOfBuckets = in.readInt();
+ long numBits = in.readLong();
+ RoaringBitmap[] data = new RoaringBitmap[numOfBuckets];
+ for (int i = 0; i < numOfBuckets; i++) {
+ data[i] = new RoaringBitmap();
+ data[i].deserialize(in);
+ }
+ return new RoaringBitmapArray(data, numBits);
+ }
+
+ @Override
+ public boolean equals(Object other) {
+ if (this == other) return true;
+ if (other == null || !(other instanceof RoaringBitmapArray)) return false;
+ RoaringBitmapArray that = (RoaringBitmapArray) other;
+ return (this.bitCount == that.bitCount) &&
+ (this.numBits == that.numBits) &&
+ Arrays.equals(data, that.data);
+ }
+
+ @Override
+ public int hashCode() {
+ return Arrays.hashCode(data);
--- End diff --
Is it worth incorporating bitCount, numBits? it's not wrong to omit them, but might be didier.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #15917: SPARK-18252: Using RoaringBitmap for bloom filters
Posted by ponkin <gi...@git.apache.org>.
Github user ponkin commented on the issue:
https://github.com/apache/spark/pull/15917
@srowen It seems like I have fixed all your comments.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #15917: SPARK-18252: Using RoaringBitmap for bloom filters
Posted by AmplabJenkins <gi...@git.apache.org>.
Github user AmplabJenkins commented on the issue:
https://github.com/apache/spark/pull/15917
Merged build finished. Test FAILed.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request #15917: SPARK-18252: Using RoaringBitmap for bloom filter...
Posted by srowen <gi...@git.apache.org>.
Github user srowen commented on a diff in the pull request:
https://github.com/apache/spark/pull/15917#discussion_r88455531
--- Diff: common/sketch/src/main/java/org/apache/spark/util/sketch/RoaringBitmapArray.java ---
@@ -0,0 +1,136 @@
+/*
+ * 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.spark.util.sketch;
+
+import org.roaringbitmap.RoaringBitmap;
+
+import java.io.DataInputStream;
+import java.io.DataOutputStream;
+import java.io.IOException;
+import java.util.Arrays;
+
+class RoaringBitmapArray {
+
+ private final RoaringBitmap[] data;
+ private long bitCount; // number of 1`s in bitset
+ private final long numBits; // total number of available bits
+
+ private static int numOfBuckets(long numBits) {
+ if (numBits <= 0) {
+ throw new IllegalArgumentException("numBits must be positive, but got " + numBits);
+ }
+ return (int) Math.ceil(numBits / (double)Integer.MAX_VALUE);
+ }
+
+ private static RoaringBitmap[] initialVector(int numOfBuckets){
+ RoaringBitmap[] vector = new RoaringBitmap[numOfBuckets];
+ for(int i = 0;i<numOfBuckets;i++){
+ vector[i] = new RoaringBitmap();
+ }
+ return vector;
+ }
+
+ RoaringBitmapArray(long numBits) {
+ this(initialVector(numOfBuckets(numBits)), numBits);
+ }
+
+ private RoaringBitmapArray(RoaringBitmap[] data, long numBits) {
+ this.data = data;
+ this.numBits = numBits;
+ long bitCount = 0;
+ for (RoaringBitmap bucket : data) {
+ bitCount += bucket.getCardinality();
+ }
+ this.bitCount = bitCount;
+ }
+
+ /** Returns true if the bit changed value. */
+ boolean set(long index) {
+ int bucketNum = (int)(index / Integer.MAX_VALUE);
+ int bitIdx = (int)(index % Integer.MAX_VALUE);
+ if(!data[bucketNum].contains(bitIdx)) {
+ data[bucketNum].add(bitIdx);
+ bitCount++;
+ return true;
+ }
+ return false;
+ }
+
+ boolean get(long index) {
+ int bucketNum = (int)(index / Integer.MAX_VALUE);
+ int bitIdx = (int) (index % Integer.MAX_VALUE);
+ return data[bucketNum].contains(bitIdx);
+ }
+
+ /** Number of bits */
+ long bitSize() {
+ return numBits;
--- End diff --
2 space indent everywhere
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #15917: SPARK-18252: Using RoaringBitmap for bloom filters
Posted by AmplabJenkins <gi...@git.apache.org>.
Github user AmplabJenkins commented on the issue:
https://github.com/apache/spark/pull/15917
Test FAILed.
Refer to this link for build results (access rights to CI server needed):
https://amplab.cs.berkeley.edu/jenkins//job/SparkPullRequestBuilder/68796/
Test FAILed.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request #15917: SPARK-18252: Using RoaringBitmap for bloom filter...
Posted by srowen <gi...@git.apache.org>.
Github user srowen commented on a diff in the pull request:
https://github.com/apache/spark/pull/15917#discussion_r88434278
--- Diff: common/sketch/src/test/java/org/apache/spark/util/sketch/Murmur3_128Suite.java ---
@@ -0,0 +1,30 @@
+package org.apache.spark.util.sketch;
--- End diff --
Missing a license
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #15917: SPARK-18252: Using RoaringBitmap for bloom filters
Posted by AmplabJenkins <gi...@git.apache.org>.
Github user AmplabJenkins commented on the issue:
https://github.com/apache/spark/pull/15917
Merged build finished. Test PASSed.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #15917: SPARK-18252: Using RoaringBitmap for bloom filters
Posted by rxin <gi...@git.apache.org>.
Github user rxin commented on the issue:
https://github.com/apache/spark/pull/15917
Please see my comment on the jira ticket. I'm not sure this is a good idea.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #15917: SPARK-18252: Using RoaringBitmap for bloom filters
Posted by srowen <gi...@git.apache.org>.
Github user srowen commented on the issue:
https://github.com/apache/spark/pull/15917
Yes all good points, this is more complex than I had imagined, especially with the good point about needing to support older serialized forms. This may not be worth it, yes.
It would be nice to have just one implementation one way or the other, rather than 2. At the least, it may be fine to improve the existing implementation and punt on the rest.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request #15917: SPARK-18252: Using RoaringBitmap for bloom filter...
Posted by ponkin <gi...@git.apache.org>.
Github user ponkin commented on a diff in the pull request:
https://github.com/apache/spark/pull/15917#discussion_r88439826
--- Diff: common/sketch/src/main/java/org/apache/spark/util/sketch/RoaringBitmapArray.java ---
@@ -0,0 +1,136 @@
+/*
+ * 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.spark.util.sketch;
+
+import org.roaringbitmap.RoaringBitmap;
+
+import java.io.DataInputStream;
+import java.io.DataOutputStream;
+import java.io.IOException;
+import java.util.Arrays;
+
+class RoaringBitmapArray {
--- End diff --
Unfortunately, RoaringBitmap supports only int indexes [javadoc](http://www.javadoc.io/doc/org.roaringbitmap/RoaringBitmap/0.6.27). Since we need to support bloom filters with size more than Int.MaxValue(BitArray supported 64*IntMaxValue) I decided to partition bloom filter with RoaringBitmap[]. Now Bloom filter can be Long.MaxValue large in size(number of bits).
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request #15917: SPARK-18252: Using RoaringBitmap for bloom filter...
Posted by srowen <gi...@git.apache.org>.
Github user srowen commented on a diff in the pull request:
https://github.com/apache/spark/pull/15917#discussion_r88455844
--- Diff: common/sketch/src/main/java/org/apache/spark/util/sketch/RoaringBitmapArray.java ---
@@ -0,0 +1,136 @@
+/*
+ * 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.spark.util.sketch;
+
+import org.roaringbitmap.RoaringBitmap;
+
+import java.io.DataInputStream;
+import java.io.DataOutputStream;
+import java.io.IOException;
+import java.util.Arrays;
+
+class RoaringBitmapArray {
+
+ private final RoaringBitmap[] data;
+ private long bitCount; // number of 1`s in bitset
+ private final long numBits; // total number of available bits
+
+ private static int numOfBuckets(long numBits) {
+ if (numBits <= 0) {
+ throw new IllegalArgumentException("numBits must be positive, but got " + numBits);
+ }
+ return (int) Math.ceil(numBits / (double)Integer.MAX_VALUE);
+ }
+
+ private static RoaringBitmap[] initialVector(int numOfBuckets){
+ RoaringBitmap[] vector = new RoaringBitmap[numOfBuckets];
+ for(int i = 0;i<numOfBuckets;i++){
+ vector[i] = new RoaringBitmap();
+ }
+ return vector;
+ }
+
+ RoaringBitmapArray(long numBits) {
+ this(initialVector(numOfBuckets(numBits)), numBits);
+ }
+
+ private RoaringBitmapArray(RoaringBitmap[] data, long numBits) {
+ this.data = data;
+ this.numBits = numBits;
+ long bitCount = 0;
+ for (RoaringBitmap bucket : data) {
+ bitCount += bucket.getCardinality();
+ }
+ this.bitCount = bitCount;
+ }
+
+ /** Returns true if the bit changed value. */
+ boolean set(long index) {
+ int bucketNum = (int)(index / Integer.MAX_VALUE);
+ int bitIdx = (int)(index % Integer.MAX_VALUE);
+ if(!data[bucketNum].contains(bitIdx)) {
+ data[bucketNum].add(bitIdx);
+ bitCount++;
+ return true;
+ }
+ return false;
+ }
+
+ boolean get(long index) {
+ int bucketNum = (int)(index / Integer.MAX_VALUE);
+ int bitIdx = (int) (index % Integer.MAX_VALUE);
+ return data[bucketNum].contains(bitIdx);
+ }
+
+ /** Number of bits */
+ long bitSize() {
+ return numBits;
+ }
+
+ /** Number of set bits (1s) */
+ long cardinality() {
+ return bitCount;
+ }
+
+ /** Combines the two RoaringBitmapArray using bitwise OR. */
+ void putAll(RoaringBitmapArray bitmap) {
+ assert data.length == bitmap.data.length : "RoaringBitmapArray`s must be of equal length when merging";
+ long mergedBitCount = 0;
+ for (int i = 0; i < data.length; i++) {
+ data[i].or(bitmap.data[i]);
+ mergedBitCount += data[i].getCardinality();
+ }
+ this.bitCount = mergedBitCount;
+ }
+
+ void writeTo(DataOutputStream out) throws IOException {
+ out.writeInt(data.length);
+ out.writeLong(numBits);
+ for (RoaringBitmap datum : data) {
+ datum.runOptimize();
+ datum.serialize(out);
+ }
+ }
+
+ static RoaringBitmapArray readFrom(DataInputStream in) throws IOException {
+ int numOfBuckets = in.readInt();
+ long numBits = in.readLong();
+ RoaringBitmap[] data = new RoaringBitmap[numOfBuckets];
+ for (int i = 0; i < numOfBuckets; i++) {
+ data[i] = new RoaringBitmap();
+ data[i].deserialize(in);
+ }
+ return new RoaringBitmapArray(data, numBits);
+ }
+
+ @Override
+ public boolean equals(Object other) {
+ if (this == other) return true;
+ if (other == null || !(other instanceof RoaringBitmapArray)) return false;
+ RoaringBitmapArray that = (RoaringBitmapArray) other;
+ return (this.bitCount == that.bitCount) &&
+ (this.numBits == that.numBits) &&
--- End diff --
4-space continuation indents
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #15917: SPARK-18252: Using RoaringBitmap for bloom filters
Posted by rxin <gi...@git.apache.org>.
Github user rxin commented on the issue:
https://github.com/apache/spark/pull/15917
Also cc @lemire
Can you take a look at the discussion on the JIRA ticket and chime in? https://issues.apache.org/jira/browse/SPARK-18252
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #15917: SPARK-18252: Using RoaringBitmap for bloom filters
Posted by AmplabJenkins <gi...@git.apache.org>.
Github user AmplabJenkins commented on the issue:
https://github.com/apache/spark/pull/15917
Merged build finished. Test FAILed.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request #15917: SPARK-18252: Using RoaringBitmap for bloom filter...
Posted by srowen <gi...@git.apache.org>.
Github user srowen commented on a diff in the pull request:
https://github.com/apache/spark/pull/15917#discussion_r88440268
--- Diff: common/sketch/src/main/java/org/apache/spark/util/sketch/RoaringBitmapArray.java ---
@@ -0,0 +1,136 @@
+/*
+ * 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.spark.util.sketch;
+
+import org.roaringbitmap.RoaringBitmap;
+
+import java.io.DataInputStream;
+import java.io.DataOutputStream;
+import java.io.IOException;
+import java.util.Arrays;
+
+class RoaringBitmapArray {
--- End diff --
Hm, I see: https://github.com/RoaringBitmap/RoaringBitmap/issues/109
I wonder if it's worth using RoaringBitmap then, but, of course making the improvements we want from RB would take work too, and, removing code helps.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #15917: SPARK-18252: Using RoaringBitmap for bloom filters
Posted by AmplabJenkins <gi...@git.apache.org>.
Github user AmplabJenkins commented on the issue:
https://github.com/apache/spark/pull/15917
Test FAILed.
Refer to this link for build results (access rights to CI server needed):
https://amplab.cs.berkeley.edu/jenkins//job/SparkPullRequestBuilder/68782/
Test FAILed.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request #15917: SPARK-18252: Using RoaringBitmap for bloom filter...
Posted by srowen <gi...@git.apache.org>.
Github user srowen commented on a diff in the pull request:
https://github.com/apache/spark/pull/15917#discussion_r88456006
--- Diff: common/sketch/src/main/java/org/apache/spark/util/sketch/RoaringBitmapArray.java ---
@@ -0,0 +1,136 @@
+/*
+ * 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.spark.util.sketch;
+
+import org.roaringbitmap.RoaringBitmap;
+
+import java.io.DataInputStream;
+import java.io.DataOutputStream;
+import java.io.IOException;
+import java.util.Arrays;
+
+class RoaringBitmapArray {
+
+ private final RoaringBitmap[] data;
+ private long bitCount; // number of 1`s in bitset
--- End diff --
Is it worth maintaining this? it slows down paths like set; is it called frequently enough to cache?
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #15917: SPARK-18252: Using RoaringBitmap for bloom filters
Posted by srowen <gi...@git.apache.org>.
Github user srowen commented on the issue:
https://github.com/apache/spark/pull/15917
Jenkins add to whitelist
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request #15917: SPARK-18252: Using RoaringBitmap for bloom filter...
Posted by srowen <gi...@git.apache.org>.
Github user srowen commented on a diff in the pull request:
https://github.com/apache/spark/pull/15917#discussion_r88434152
--- Diff: common/sketch/src/main/java/org/apache/spark/util/sketch/Murmur3_128.java ---
@@ -0,0 +1,135 @@
+/*
+ * 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.spark.util.sketch;
+
+/**
+ * 128-bit Murmur3 hasher.
+ * Best perfomance is on x86_64 platform
+ * Based on implementation https://github.com/aappleby/smhasher/blob/master/src/MurmurHash3.cpp
+ */
+final class Murmur3_128 {
--- End diff --
Could you explain why we need to add a custom murmurhash implementation? it seems like conceptually we're just swapping bitmaps for bitmapss. What's the license of this code?
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #15917: SPARK-18252: Using RoaringBitmap for bloom filters
Posted by SparkQA <gi...@git.apache.org>.
Github user SparkQA commented on the issue:
https://github.com/apache/spark/pull/15917
**[Test build #68797 has started](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/68797/consoleFull)** for PR 15917 at commit [`487da8f`](https://github.com/apache/spark/commit/487da8fbd23f2d861ab10a1faf701696e9ca3967).
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #15917: SPARK-18252: Using RoaringBitmap for bloom filters
Posted by rxin <gi...@git.apache.org>.
Github user rxin commented on the issue:
https://github.com/apache/spark/pull/15917
@ponkin mind closing the pull request given your findings on https://issues.apache.org/jira/browse/SPARK-18252 ?
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request #15917: SPARK-18252: Using RoaringBitmap for bloom filter...
Posted by ponkin <gi...@git.apache.org>.
Github user ponkin commented on a diff in the pull request:
https://github.com/apache/spark/pull/15917#discussion_r88441043
--- Diff: common/sketch/src/main/java/org/apache/spark/util/sketch/RoaringBitmapArray.java ---
@@ -0,0 +1,136 @@
+/*
+ * 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.spark.util.sketch;
+
+import org.roaringbitmap.RoaringBitmap;
+
+import java.io.DataInputStream;
+import java.io.DataOutputStream;
+import java.io.IOException;
+import java.util.Arrays;
+
+class RoaringBitmapArray {
--- End diff --
well, the main point of this improvement is to save memory - now even filters with few elements acquire space needed for full bloom filter. With this improvement bloom filter size will increase as we insert values in it.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request #15917: SPARK-18252: Using RoaringBitmap for bloom filter...
Posted by ponkin <gi...@git.apache.org>.
Github user ponkin commented on a diff in the pull request:
https://github.com/apache/spark/pull/15917#discussion_r88441473
--- Diff: common/sketch/src/main/java/org/apache/spark/util/sketch/Murmur3_128.java ---
@@ -0,0 +1,135 @@
+/*
+ * 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.spark.util.sketch;
+
+/**
+ * 128-bit Murmur3 hasher.
+ * Best perfomance is on x86_64 platform
+ * Based on implementation https://github.com/aappleby/smhasher/blob/master/src/MurmurHash3.cpp
+ */
+final class Murmur3_128 {
--- End diff --
Well Guava`s implementation is allocating a lot of temp objects(works only with ByteBuffer [source](https://github.com/google/guava/blob/d330fc7f880b49e9d45a44e7650d95a6f7afbe23/guava/src/com/google/common/hash/Murmur3_128HashFunction.java)). So I decided to do standalone implementation - all tests for Hasher are taken from Guava lib.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request #15917: SPARK-18252: Using RoaringBitmap for bloom filter...
Posted by srowen <gi...@git.apache.org>.
Github user srowen commented on a diff in the pull request:
https://github.com/apache/spark/pull/15917#discussion_r88455809
--- Diff: common/sketch/src/main/java/org/apache/spark/util/sketch/RoaringBitmapArray.java ---
@@ -0,0 +1,136 @@
+/*
+ * 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.spark.util.sketch;
+
+import org.roaringbitmap.RoaringBitmap;
+
+import java.io.DataInputStream;
+import java.io.DataOutputStream;
+import java.io.IOException;
+import java.util.Arrays;
+
+class RoaringBitmapArray {
+
+ private final RoaringBitmap[] data;
+ private long bitCount; // number of 1`s in bitset
+ private final long numBits; // total number of available bits
+
+ private static int numOfBuckets(long numBits) {
+ if (numBits <= 0) {
+ throw new IllegalArgumentException("numBits must be positive, but got " + numBits);
+ }
+ return (int) Math.ceil(numBits / (double)Integer.MAX_VALUE);
+ }
+
+ private static RoaringBitmap[] initialVector(int numOfBuckets){
+ RoaringBitmap[] vector = new RoaringBitmap[numOfBuckets];
+ for(int i = 0;i<numOfBuckets;i++){
+ vector[i] = new RoaringBitmap();
+ }
+ return vector;
+ }
+
+ RoaringBitmapArray(long numBits) {
+ this(initialVector(numOfBuckets(numBits)), numBits);
+ }
+
+ private RoaringBitmapArray(RoaringBitmap[] data, long numBits) {
+ this.data = data;
+ this.numBits = numBits;
+ long bitCount = 0;
+ for (RoaringBitmap bucket : data) {
+ bitCount += bucket.getCardinality();
+ }
+ this.bitCount = bitCount;
+ }
+
+ /** Returns true if the bit changed value. */
+ boolean set(long index) {
+ int bucketNum = (int)(index / Integer.MAX_VALUE);
+ int bitIdx = (int)(index % Integer.MAX_VALUE);
+ if(!data[bucketNum].contains(bitIdx)) {
+ data[bucketNum].add(bitIdx);
+ bitCount++;
+ return true;
+ }
+ return false;
+ }
+
+ boolean get(long index) {
+ int bucketNum = (int)(index / Integer.MAX_VALUE);
+ int bitIdx = (int) (index % Integer.MAX_VALUE);
+ return data[bucketNum].contains(bitIdx);
+ }
+
+ /** Number of bits */
+ long bitSize() {
+ return numBits;
+ }
+
+ /** Number of set bits (1s) */
+ long cardinality() {
+ return bitCount;
+ }
+
+ /** Combines the two RoaringBitmapArray using bitwise OR. */
+ void putAll(RoaringBitmapArray bitmap) {
+ assert data.length == bitmap.data.length : "RoaringBitmapArray`s must be of equal length when merging";
+ long mergedBitCount = 0;
+ for (int i = 0; i < data.length; i++) {
+ data[i].or(bitmap.data[i]);
+ mergedBitCount += data[i].getCardinality();
+ }
+ this.bitCount = mergedBitCount;
+ }
+
+ void writeTo(DataOutputStream out) throws IOException {
+ out.writeInt(data.length);
+ out.writeLong(numBits);
+ for (RoaringBitmap datum : data) {
+ datum.runOptimize();
+ datum.serialize(out);
+ }
+ }
+
+ static RoaringBitmapArray readFrom(DataInputStream in) throws IOException {
+ int numOfBuckets = in.readInt();
+ long numBits = in.readLong();
+ RoaringBitmap[] data = new RoaringBitmap[numOfBuckets];
+ for (int i = 0; i < numOfBuckets; i++) {
+ data[i] = new RoaringBitmap();
+ data[i].deserialize(in);
+ }
+ return new RoaringBitmapArray(data, numBits);
+ }
+
+ @Override
+ public boolean equals(Object other) {
+ if (this == other) return true;
+ if (other == null || !(other instanceof RoaringBitmapArray)) return false;
--- End diff --
Use braces, newline for return
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request #15917: SPARK-18252: Using RoaringBitmap for bloom filter...
Posted by srowen <gi...@git.apache.org>.
Github user srowen commented on a diff in the pull request:
https://github.com/apache/spark/pull/15917#discussion_r88440867
--- Diff: common/sketch/src/main/java/org/apache/spark/util/sketch/Murmur3_128.java ---
@@ -0,0 +1,135 @@
+/*
+ * 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.spark.util.sketch;
+
+/**
+ * 128-bit Murmur3 hasher.
+ * Best perfomance is on x86_64 platform
+ * Based on implementation https://github.com/aappleby/smhasher/blob/master/src/MurmurHash3.cpp
+ */
+final class Murmur3_128 {
--- End diff --
Rather than make a new implementation, use Guava's Hashing? Scala and Spark itself already have murmur hash impls but they seem 32-bit only
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request #15917: SPARK-18252: Using RoaringBitmap for bloom filter...
Posted by srowen <gi...@git.apache.org>.
Github user srowen commented on a diff in the pull request:
https://github.com/apache/spark/pull/15917#discussion_r88434426
--- Diff: common/sketch/src/main/java/org/apache/spark/util/sketch/RoaringBitmapArray.java ---
@@ -0,0 +1,136 @@
+/*
+ * 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.spark.util.sketch;
+
+import org.roaringbitmap.RoaringBitmap;
+
+import java.io.DataInputStream;
+import java.io.DataOutputStream;
+import java.io.IOException;
+import java.util.Arrays;
+
+class RoaringBitmapArray {
--- End diff --
Probably a dumb question but why do we need an array of bitmaps? I thought RoaringBitmap was a BitArray counterpart?
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark pull request #15917: SPARK-18252: Using RoaringBitmap for bloom filter...
Posted by ponkin <gi...@git.apache.org>.
Github user ponkin commented on a diff in the pull request:
https://github.com/apache/spark/pull/15917#discussion_r88461735
--- Diff: common/sketch/src/main/java/org/apache/spark/util/sketch/RoaringBitmapArray.java ---
@@ -0,0 +1,136 @@
+/*
+ * 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.spark.util.sketch;
+
+import org.roaringbitmap.RoaringBitmap;
+
+import java.io.DataInputStream;
+import java.io.DataOutputStream;
+import java.io.IOException;
+import java.util.Arrays;
+
+class RoaringBitmapArray {
+
+ private final RoaringBitmap[] data;
+ private long bitCount; // number of 1`s in bitset
--- End diff --
it is only need to calculate expectedFpp (false positive rate) which is not very frequent operation, I agree. will remove
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
[GitHub] spark issue #15917: SPARK-18252: Using RoaringBitmap for bloom filters
Posted by SparkQA <gi...@git.apache.org>.
Github user SparkQA commented on the issue:
https://github.com/apache/spark/pull/15917
**[Test build #68796 has started](https://amplab.cs.berkeley.edu/jenkins/job/SparkPullRequestBuilder/68796/consoleFull)** for PR 15917 at commit [`66f58d1`](https://github.com/apache/spark/commit/66f58d11ecd9d16054619fec94f413fd3b62d9a0).
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org