search

jonahharris / libcuckoofilter

A C library implementation of a Cuckoo Filter
MIT License
23 stars 9 forks source link

Make it work #3

Closed solardiz closed 3 years ago

solardiz commented 3 years ago

This filter was completely broken since 4b1d866ebc03b403a04f05377f4bda4ff9f85f51, which, while only partially fixing a very real issue, made the indexing inconsistent between add/remove and lookup.

Further, fingerprint value of 0 was allowed as such while also being a magic value used to mark empty entries. This produced occasional false negatives - something a proper Cuckoo filter must never have.

While at it, I also added usage of ASan for tests, a test at requested 92% load factor (somehow even 94% often fails despite the filter is actually larger than requested, indicating there's something imperfect in the filter implementation), and switched away from misuse of posix_memalign() since suitability for a mere uint64_t is guaranteed by simple malloc() and calloc().

The implementation is still far from optimal, and I don't recommend it for actual use, but this PR should make it another valid reference to consider.

There are two other forks that also fixed the off-by-ones and made other changes, but still had bugs preventing the filter from working reliably. I also sent PRs against those: https://github.com/mscastanho/libcuckoofilter/pull/1 https://github.com/avgerin0s/libcuckoofilter/pull/1

jonahharris commented 3 years ago

This library was a PoC and a hack job. Thanks for fixing it up and making it work properly.