Repository navigation
XorBinaryFuse silent failure #49
Description
Activity
@vprus Your blog at https://vladimirprus.com/blog/ seems to be missing an RSS feed.
I have a local patch to add an exception, so yes, can turn that into a PR.
If you're OK with AI-assisted, but human-checked PRs, I can ask Copilot to review other implementations for the same issue as well, let me know.
Nevermind, there seems to be 3 such places, will provide a PR shortly.
Just for context, this path should NEVER happen. If it does, it is a bug. So yeah, generating an exception is a good way to handle it.
I don't really understand the underlying math, but I had around 50K strings, so I assumed that String.hashCode.toLong, while imperfect, should still work. Apparently, it did not, and my naive attempt to rehash it into 64-bit did not help either.
@vprus It is almost certainly the case that you have collisions. The Java implementation is a bit naive, but what we do with the other implementations is to prune the duplicates. I'll create a PR on this topic.
That should not happen with 50K strings if you have good hashing. But that's not good:
String.hashCode.toLong. I think Google's Guava library must have good hash functions.So, essentially, it fails because of a bug, and the bug is the use of an excessively weak hashing.
Yes, you are correct. There were two strings with the same hashCode. Using either xxhash or String.hashCode.toLong+distinct worked for me.
Thanks for your help!
There is code in XorBinaryFuse8
https://github.com/FastFilter/fastfilter_java/blob/master/fastfilter/src/main/java/org/fastfilter/xor/XorBinaryFuse8.java#L201
that appears to silently fail, and fill the fingerprint array with 0xFF.
Then, the code in mayContain goes like this:
that essentially becomes
or
or
In other words, mayContain will now return false most inputs, generating false negatives.
I would suggest that this behaviour is catastrophic in practical code, and a better approach would be to modify the code to through an exception.