search

bits-and-blooms / bloom

Go package implementing Bloom filters, used by Milvus and Beego.
BSD 2-Clause "Simplified" License
2.44k stars 232 forks source link

murmur3 over xxHash? #45

Closed SUP3RIA closed 3 years ago

SUP3RIA commented 6 years ago

Is this matter of licensing issues or are there technical reasons to use murmur3 over xxHash?

a-urth commented 5 years ago

Also interested in that.

lemire commented 3 years ago

Changing the hash function would break existing filters.

If you believe that xxHash would be preferable, please prepare some benchmarks.

I am going to close this issue, please reopen with hard numbers so we can move the discussion forward.

johanneswuerbach commented 2 years ago

I was looking to use the library to write parquet bloom filters and they only support xxhash https://github.com/apache/parquet-mr/blob/5608695f5777de1eb0899d9075ec9411cfdf31d3/parquet-column/src/main/java/org/apache/parquet/column/values/bloomfilter/BloomFilter.java#L32-L46. Would it be an option to make the hash function replaceable so users can provide a custom one?

lemire commented 2 years ago

We can accommodate a new variant, say xxbloom, within the same code base. I do not want to change the default as it would break existing code.

Dynamically assigned hash functions might be hard. First you’d need to make sure it does not harm performance… e.g., by reducing inlining. Second, you’d need to carefully define the interface and the requirements. Third, we want to preserve full backward compatibility.

So the best thing is a new variant…

Pull request invited!