Use optimized implementation of bloom filter

[ozgrakkurt]

Hey!

I implemented https://github.com/ozgrakkurt/sbbf-rs.

It is an implementation of parquet bloom filters, I checked it against the implementation at parquet2 and it produces same output.

I would like to integrate it here if it makes sense to do.

A big problem with it may be that it has different implementations including a aarch64::neon which wouldn't get tested on GitHub CI.

[tustvold]

Do you have any performance benchmark results you could share?

[ozgrakkurt]

I added it to the benchmarks here: crepererum-oss/pdatastructs.rs#126.

[ozgrakkurt]

@tustvold added benchmark against parquet2 implementation on the repo can you run it if you have time?

I ran it on an aarch64 cpu and these are the results I get:

INSERT
parquet2 -> 76 ns
sbbf-rs -> 3.5ns

CONTAINS (this seems to be dominated by hashing time and dynamic dispatch in sbbf-rs, also seems like the compiler optimizes the code in parquet2 pretty well)
parquet2 -> 3.4 ns
sbbf-rs -> 2.8 ns

CONTAINS (without hashing and dynamic-dispatch in sbbf-rs, requires modifying library a little specifically for aarch64 since all aarch64 cpus support `neon` SIMD instructions, don't want to release with this optimization since not sure if it is worth complicating the code)
parquet2 -> 1.9 ns
sbbf-rs -> 500 ps

couldn't bench the parquet implementation since the struct for bloom filter seemed non-trivial to construct

[ozgrakkurt]

Added parquet impl by copy-pasting the bloom_filter file

results on mac m1:

results on VPS (x86_64) with 1 gb ram and 1vcore cpu: