6 ms·
The prime here is needlessly small, I believe-- which will inflate the false positive rate. It's using 64-bit registers and 64-bit multiplies, so the prime cou
by nullc 5y ago
The prime here is needlessly small, I believe-- which will inflate the false positive rate. It's using 64-bit registers and 64-bit multiplies, so the prime could be 0xfffffffffffffb. For 32-bit registers and multiplies the prime could be 0xfffffd.
I'm guessing it's using an overly small value because it's based on java code and java is a little brain-damaged about unsigned numbers. :)
You could get a better use of your comparison register by using the syndrome of BCH code over GF(256)-- e.g. the full 64-bits for a 64-bit register instead of 56, though given how fast multipliers are these days using a prime modulus is probably fastest (in hardware or maybe in SIMD a characteristic-2 BCH code would almost certainly be faster and better!).
The code here also has the issues that permutations of the characters of the needle will match-- this may fairly bad performance for some plausible inputs. A BCH code would be less bad in that respect.
With the right choice of BCH code, you could be guaranteed that any false positive would differ in at least X characters out of Y, if Y is equal to or less than your window size, that may reduce the amount of comparisons you do for false positives (mostly interesting for very small hashes, I suppose).
- gopalv 5y ago> though given how fast multipliers are these days using a prime modulus They are really fast on a single thread, but at least on Xeons I use the mul and modulo seems to have a weak spot with thread parallelism though. To fix a set of threading scaling issue with LIKE "%pattern%" SQL queries (something like TPC-H Query13), I spent a week digging through the algorithms which work better when all the threads are doing the same thing. I narrowed down on BoyerMooreHorspool[1] as the algorithm which doesn't seem to be hit by other threads running the same algorithm (of course, everything utf-8 matching turns unicode char patterns into exact byte lookups). [1] - https://github.com/apache/hive/blob/master/storage-api/src/java/org/apache/hadoop/hive/ql/exec/vector/expressions/StringExpr.java#L307 https://github.com/apache/hive/blob/master/storage-api/src/j...
- nullc 5y ago> and modulo If the modulo is a compile time constant it should get converted into a multiply. If its not, for whatever reason the performance will be less than amazing.
- ithkuil 5y agoThere is a trick to turn a modulo info a multiplication even if it's not known at compile time: https://lemire.me/blog/2016/06/27/a-fast-alternative-to-the-modulo-reduction/ https://lemire.me/blog/2016/06/27/a-fast-alternative-to-the-...
- turminal 5y agoThe blog post you linked is about fair range mapping. I don't see how that applies to the problem of computing a modulo while avoiding expensive cpu instructions.
- nullc 5y agoYeah, that is inapplicable. This is the relevant reference: Arch D. Robison, "{N}-bit Unsigned Division via {N}-bit Multiply-Add" (2005) https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.512.2627&rep=rep1&type=pdf https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.51...
- hawk_ 5y ago> mul and modulo seems to have a weak spot with thread parallelism is that only with hyperthreading enabled or mul/modulo affect other unrelated cores as well?
- uyt 5y agoImplementation-wise, if you multiply two 64 bit numbers you need to hold the result in a __int128 before taking the mod which makes it less portable.
- nullc 5y agoThe larger prime I gave is 56 bits for that reason. It will not overflow 64 bits. (-- unless I've messed something up, of course!)
- vbezhenar 5y agoUnsigned numbers are usable in Java, they just require a bit more care.