3 ms·
> 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 modu
by 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?