Comment by ncruces
1 year ago
Here, it's often the opposite.
These algorithms are basically brute force with very little setup, and can become quadratic for large, periodic needles.
String search algorithms that avoid quadratic behaviour (and may even be sublinear) have an higher cost setup that explores needle structure
What? It all depends on the sizes of the strings. Hardware benchmarks, for each significant hardware µarchitectures, must be done on combinations of string sizes in order to know "when" the SIMD setup code is worth it.
Often the setup code is not worth it, even the SIMD complexity is not bringing enough performance in many use cases (basically, kept for niche applications, little lib statically linked for those).
Did you look at the algorithm 1? The setup code is a pair of splats. There's no consideration for alignment, it works with unaligned data just fine. So what do you mean? What threshold would you expect for it to be worth it (assuming it's useful at all)?
Dude, I cannot be more explicit than that.
That said, when you work on such code, use assembly, C code is for reference (have a look at dav1d av1 decoder).
3 replies →