3 ms·

Is it faster than Boyer Moore?

by _3u10 5y ago

ygra 5y ago
I guess the answer is ... complex. As explained in the linked source for the algorithm (http://0x80.pl/articles/simd-strfind.html#introduction http://0x80.pl/articles/simd-strfind.html#introduction): The main problem with these standard algorithms is a silent assumption that comparing a pair of characters, looking up in an extra table and conditions are cheap, while comparing two substrings is expansive. But current desktop CPUs do not meet this assumption, in particular: • There is no difference in comparing one, two, four or 8 bytes on a 64-bit CPU. When a processor supports SIMD instructions, then comparing vectors (it means 16, 32 or even 64 bytes) is as cheap as comparing a single byte. • Thus comparing short sequences of chars can be faster than fancy algorithms which avoids such comparison. • Looking up in a table costs one memory fetch, so at least a L1 cache round (~3 cycles). Reading char-by-char also cost as much cycles. • Mispredicted jumps cost several cycles of penalty (~10-20 cycles). • There is a short chain of dependencies: read char, compare it, conditionally jump, which make hard to utilize out-of-order execution capabilities present in a CPU. There probably is a trade-off to be made. The more complex algorithms may make sense when the initial setup cost can be amortized and perhaps more things are known about the input and search strings. The dead-simple approach of simply running linearly through the string has no setup cost, can be trivially vectorized and may perform very well for most haystack/needle pairs and thus is probably a good idea for the general algorithm in the library. And in fact, the information that's required to decide whether the more complex algorithms are worth it is perhaps not known to string.IndexOf, so that's probably something that application developers have to decide.
- deleted 5y ago
  [deleted]
- magicalhippo 5y ago
  > And in fact, the information that's required to decide whether the more complex algorithms are worth it is perhaps not known to string.IndexOf, so that's probably something that application developers have to decide. It might not even be known to the application developers or, potentially worse, they might think they know but the program usage evolves and it becomes wrong knowledge. For a JIT'ed language though one could imagine more smartness. In theory the runtime could use a sampling profiler in the background to determine any eligible library functions that are taking a lot of time based on caller. For example, this specific call to IndexOf is taking a lot of time. The runtime could then replace that call to IndexOf with a variant that does some instrumentation, to for example build crude histograms of input lengths and hit locations. Based on this the runtime could replace that call to IndexOf with a version more optimized to the expected parameters. At least this is possible for a JIT'ed language, though surely would be a non-trivial amount of work.
- nickysielicki 5y ago
  One of the most interesting things about the emphasis on algorithms in both CS education and in tech interviews to me is that when you start to look at how people really make high performance software, it rarely comes down to figuring out how to jump from O(n) to O(logn), more often than not it has to do with thinking about memory locality and caching or avoiding branches or fitting the problem into something can be vectorized. Picking the correct algorithm with minimal algorithmic complexity tends to be the easy part. But outside of roles where performance actually matters, you’re probably not going to get asked about these things. And that’s totally reasonable, but why do we ask people about algorithms, then?
  - _3u10 5y ago
    I totally agree. I haven’t actually needed to use Boyer Moore in like 15 years. On another project I got around a 10x speed up by reusing a buffer rather than allocating a new buffer. Cache locality makes a lot more difference than people give it credit for.

Is it faster than Boyer Moore?

by _3u10 5y ago

Is it faster than Boyer Moore?

ygra 5y ago

I guess the answer is ... complex. As explained in the linked source for the algorithm (http://0x80.pl/articles/simd-strfind.html#introduction http://0x80.pl/articles/simd-strfind.html#introduction): The main problem with these standard algorithms is a silent assumption that comparing a pair of characters, looking up in an extra table and conditions are cheap, while comparing two substrings is expansive. But current desktop CPUs do not meet this assumption, in particular: • There is no difference in comparing one, two, four or 8 bytes on a 64-bit CPU. When a processor supports SIMD instructions, then comparing vectors (it means 16, 32 or even 64 bytes) is as cheap as comparing a single byte. • Thus comparing short sequences of chars can be faster than fancy algorithms which avoids such comparison. • Looking up in a table costs one memory fetch, so at least a L1 cache round (~3 cycles). Reading char-by-char also cost as much cycles. • Mispredicted jumps cost several cycles of penalty (~10-20 cycles). • There is a short chain of dependencies: read char, compare it, conditionally jump, which make hard to utilize out-of-order execution capabilities present in a CPU. There probably is a trade-off to be made. The more complex algorithms may make sense when the initial setup cost can be amortized and perhaps more things are known about the input and search strings. The dead-simple approach of simply running linearly through the string has no setup cost, can be trivially vectorized and may perform very well for most haystack/needle pairs and thus is probably a good idea for the general algorithm in the library. And in fact, the information that's required to decide whether the more complex algorithms are worth it is perhaps not known to string.IndexOf, so that's probably something that application developers have to decide.

deleted 5y ago
[deleted]
magicalhippo 5y ago
> And in fact, the information that's required to decide whether the more complex algorithms are worth it is perhaps not known to string.IndexOf, so that's probably something that application developers have to decide. It might not even be known to the application developers or, potentially worse, they might think they know but the program usage evolves and it becomes wrong knowledge. For a JIT'ed language though one could imagine more smartness. In theory the runtime could use a sampling profiler in the background to determine any eligible library functions that are taking a lot of time based on caller. For example, this specific call to IndexOf is taking a lot of time. The runtime could then replace that call to IndexOf with a variant that does some instrumentation, to for example build crude histograms of input lengths and hit locations. Based on this the runtime could replace that call to IndexOf with a version more optimized to the expected parameters. At least this is possible for a JIT'ed language, though surely would be a non-trivial amount of work.
nickysielicki 5y ago
One of the most interesting things about the emphasis on algorithms in both CS education and in tech interviews to me is that when you start to look at how people really make high performance software, it rarely comes down to figuring out how to jump from O(n) to O(logn), more often than not it has to do with thinking about memory locality and caching or avoiding branches or fitting the problem into something can be vectorized. Picking the correct algorithm with minimal algorithmic complexity tends to be the easy part. But outside of roles where performance actually matters, you’re probably not going to get asked about these things. And that’s totally reasonable, but why do we ask people about algorithms, then?
- _3u10 5y ago
  I totally agree. I haven’t actually needed to use Boyer Moore in like 15 years. On another project I got around a 10x speed up by reusing a buffer rather than allocating a new buffer. Cache locality makes a lot more difference than people give it credit for.