Repository navigation
XorBinaryFuse silent failure #49
Description
There is code in XorBinaryFuse8
that appears to silently fail, and fill the fingerprint array with 0xFF.
Then, the code in mayContain goes like this:
byte f = fingerprint(hash)
f ^= fingerprints[h0] ^ fingerprints[h1] ^ fingerprints[h2];
return (f & 0xff) == 0;
that essentially becomes
f ^= 0xFF ^ 0xFF ^ 0xFF
return (f & 0xff) == 0;
or
f ^= 0xFF;
return (f & 0xFF) == 0;
or
return (f == 0xFF)
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.
Activity
lemire commentedon Jan 19, 2026
@vprus Good point. Would you consider providing a pull request?
lemire commentedon Jan 19, 2026
@vprus Your blog at https://vladimirprus.com/blog/ seems to be missing an RSS feed.
vprus commentedon Jan 19, 2026
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.
vprus commentedon Jan 19, 2026
Nevermind, there seems to be 3 such places, will provide a PR shortly.
vprus commentedon Jan 19, 2026
Created #50
lemire commentedon Jan 19, 2026
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.
vprus commentedon Jan 19, 2026
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.
lemire commentedon Jan 19, 2026
@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.
vprus commentedon Jan 19, 2026
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!