3 ms·

This seems like a complicated way to speed up a linear scan. What's the advantage of this approach over just sorting the strings and doing a binary search, whic

This seems like a complicated way to speed up a linear scan. What's the advantage of this approach over just sorting the strings and doing a binary search, which is log N? (Not a naive binary search using strcmp, but the trick where you find the lower and upper bounds given index 0, refine it using index 1, etc. until your input is exhausted.)

SomeHacker44 8y ago
He was only searching 16 strings. The overhead of a binary search on such a small N would likely overwhelm the algorithmic improvements of moving from an O(N) to O(log N) implementation.
- ridiculous_fish 8y ago
  The table is optimized for 16 strings, but there's a reference to "linear scanning an array of string tables" so I thought the total input was larger. Anyways the size of the set is important information.
trentnelson 8y ago
Sorting the strings by length, or lexicographical? Length sort wouldn't work for the prefix-oriented nature of the comparisons. Lexicographical sorting and a binary search involves pointer chasing, and doesn't provide any way to fast-path the negative match lookup. If I'm getting called a trillion times on a hot-path, but only a million of those times I'm receiving a module name (search string) I'm interested in, then it behooves me to have the fastest negative match logic possible. As it stands, the final assembly version can negative match in about 6 cycles, prefix match in about 14 cycles, and worst-case false-positive negative match (where three strings need to be compared, but there is no match) in 21 cycles. The CPI for the final routine is reported as around 0.266, which is pretty close to the optimal of 0.25. I think you'd struggle to meet that performance with anything that relies on pointer chasing. I do comment on the likelihood of a log(n)-based algorithm overtaking performance when the data set is large enough here: http://trent.me/is-prefix-of-string-in-table/#other-applications http://trent.me/is-prefix-of-string-in-table/#other-applicat... This particular use case wasn't intended for prefix matching against large data sets though, and thus, wasn't optimized for that.
- ridiculous_fish 8y ago
  Ok, I see further down the article does describe some of the assumptions: short strings, very small set size, optimized for negative matching. Some constructive feedback: move that information up to the "Goal" section, maybe with a motivating example. The fact that the set size is <= 16 is important to know before discussing cycle counts.
  - teraflop 8y ago
    It's in the third paragraph of the article: > A SIMD-friendly C structure called STRING_TABLE was derived. It is optimized for up to 16 strings, ideally of length less than or equal 16 characters.
    - ridiculous_fish 8y ago
      I understood this to mean that the input would be processed in chunks of 16 (as is common with SIMD), not that the total input size was <= 16.
xenadu02 8y ago
Chasing pointers is cache death. Many theoretically optimal algorithms have been struck down by the God of Memory Latency. eg, If you measure it, tree performance will often be much improved by storing slightly less than one cache line's worth of data at each node. The CPU can pipeline and predict the shit out of the linear search at each node to the point that all the theoretical O(1) or O(log N) lookups in the world get demolished by a CS101 scan of the array. This makes a relatively good general use cache aware data structure because small collections tend to fit into a single cache line while large data structures have relatively few pointers to chase. Of course as the OP demonstrates, optimizing for your specific use case can yield even more dramatic improvements.
- trentnelson 8y ago
  Heh, “predict the shit out of”, I like that.

SomeHacker44 8y ago

He was only searching 16 strings. The overhead of a binary search on such a small N would likely overwhelm the algorithmic improvements of moving from an O(N) to O(log N) implementation.

ridiculous_fish 8y ago
The table is optimized for 16 strings, but there's a reference to "linear scanning an array of string tables" so I thought the total input was larger. Anyways the size of the set is important information.

trentnelson 8y ago

Sorting the strings by length, or lexicographical? Length sort wouldn't work for the prefix-oriented nature of the comparisons. Lexicographical sorting and a binary search involves pointer chasing, and doesn't provide any way to fast-path the negative match lookup. If I'm getting called a trillion times on a hot-path, but only a million of those times I'm receiving a module name (search string) I'm interested in, then it behooves me to have the fastest negative match logic possible. As it stands, the final assembly version can negative match in about 6 cycles, prefix match in about 14 cycles, and worst-case false-positive negative match (where three strings need to be compared, but there is no match) in 21 cycles. The CPI for the final routine is reported as around 0.266, which is pretty close to the optimal of 0.25. I think you'd struggle to meet that performance with anything that relies on pointer chasing. I do comment on the likelihood of a log(n)-based algorithm overtaking performance when the data set is large enough here: http://trent.me/is-prefix-of-string-in-table/#other-applications http://trent.me/is-prefix-of-string-in-table/#other-applicat... This particular use case wasn't intended for prefix matching against large data sets though, and thus, wasn't optimized for that.

ridiculous_fish 8y ago
Ok, I see further down the article does describe some of the assumptions: short strings, very small set size, optimized for negative matching. Some constructive feedback: move that information up to the "Goal" section, maybe with a motivating example. The fact that the set size is <= 16 is important to know before discussing cycle counts.
- teraflop 8y ago
  It's in the third paragraph of the article: > A SIMD-friendly C structure called STRING_TABLE was derived. It is optimized for up to 16 strings, ideally of length less than or equal 16 characters.
  - ridiculous_fish 8y ago
    I understood this to mean that the input would be processed in chunks of 16 (as is common with SIMD), not that the total input size was <= 16.

xenadu02 8y ago

Chasing pointers is cache death. Many theoretically optimal algorithms have been struck down by the God of Memory Latency. eg, If you measure it, tree performance will often be much improved by storing slightly less than one cache line's worth of data at each node. The CPU can pipeline and predict the shit out of the linear search at each node to the point that all the theoretical O(1) or O(log N) lookups in the world get demolished by a CS101 scan of the array. This makes a relatively good general use cache aware data structure because small collections tend to fit into a single cache line while large data structures have relatively few pointers to chase. Of course as the OP demonstrates, optimizing for your specific use case can yield even more dramatic improvements.

trentnelson 8y ago
Heh, “predict the shit out of”, I like that.