4 ms·

What's the issue with "pointer-chasing"? That it might be inefficient in practice (despite preferable runtime complexity?) due to making poor use of CPU caches?

dragontamer 8y ago
> That it might be inefficient in practice That's basically it. Consider that his algorithm completes 16-searches in 20-cycles, or roughly 5 nanoseconds. A single fetch from main-memory will take 50-nanoseconds, or be ~10x slower than the methodology discussed in this post. Even a fetch from L3 cache is typically 10-nanoseconds, while a fetch from L1 cache is 1ns or ~4-cycles. This SIMD-methodology is incredibly FAST. The "best-case" scenario of this SIMD code is 6-cycles, which is faster than two L1 fetches. (!!!) Note: two L1 fetches would likely go into the reorder buffer and be out-of-ordered into an efficient manner. But... ignore that plz since that destroys the point I'm trying to make. Lol. Still, you can see how repeatedly forcing even L1 fetches would slow down the code, and "pointer chasing" is more likely to fill up the Reorder buffers, since you cannot rely upon prefetchers to pre-fetch the data, or other such tricks of the CPU. Algorithmic complexity means that eventually, the linear / SIMD methodology eventually will be slower with a big-enough dataset. But when looking at small data-sets and optimizing them to the maximum ability (ie: searching 16-strings ASAP), linear / sequential scans are king. Kinda like why insertion sort ends up winning in a lot of small cases over other sorts. CPUs and RAM are incredibly well optimized for sequential data scans.
obl 8y ago
in itself pointer chasing does not mean misusing CPU caches (your dataset could fit in cache and you could be pointer chasing inside it). the main issue that is strictly due to pointer chasing is that you risk having long dependency chains in your instruction stream (address of the load depends on the result of the previous load, the address of which depends on the result of ...). This is pretty bad for a modern CPU since a lot of the speed comes from overlapping independent computations.
trentnelson 8y ago
I think with SIMD type stuff and small data sets (e.g. <=16 strings), conventional big-O complexity analysis can leave a bit to be desired. Similarly, with SIMD and small data sets, you’re going to be faster than anything involving a pointer chasing data structure. Pointers tend to mean branchy-ness; they require more backend resources; they often introduce dependencies that can inhibit out of order pipelines.
Myrmornis 8y ago
To the person who downvoted this: you're using downvotes wrongly. I was asking a question about computer science. Down-voting people who ask questions about computer science is not the way to encourage the sort of conversation we're trying to encourage on HN.

dragontamer 8y ago

> That it might be inefficient in practice That's basically it. Consider that his algorithm completes 16-searches in 20-cycles, or roughly 5 nanoseconds. A single fetch from main-memory will take 50-nanoseconds, or be ~10x slower than the methodology discussed in this post. Even a fetch from L3 cache is typically 10-nanoseconds, while a fetch from L1 cache is 1ns or ~4-cycles. This SIMD-methodology is incredibly FAST. The "best-case" scenario of this SIMD code is 6-cycles, which is faster than two L1 fetches. (!!!) Note: two L1 fetches would likely go into the reorder buffer and be out-of-ordered into an efficient manner. But... ignore that plz since that destroys the point I'm trying to make. Lol. Still, you can see how repeatedly forcing even L1 fetches would slow down the code, and "pointer chasing" is more likely to fill up the Reorder buffers, since you cannot rely upon prefetchers to pre-fetch the data, or other such tricks of the CPU. Algorithmic complexity means that eventually, the linear / SIMD methodology eventually will be slower with a big-enough dataset. But when looking at small data-sets and optimizing them to the maximum ability (ie: searching 16-strings ASAP), linear / sequential scans are king. Kinda like why insertion sort ends up winning in a lot of small cases over other sorts. CPUs and RAM are incredibly well optimized for sequential data scans.

obl 8y ago

in itself pointer chasing does not mean misusing CPU caches (your dataset could fit in cache and you could be pointer chasing inside it). the main issue that is strictly due to pointer chasing is that you risk having long dependency chains in your instruction stream (address of the load depends on the result of the previous load, the address of which depends on the result of ...). This is pretty bad for a modern CPU since a lot of the speed comes from overlapping independent computations.

trentnelson 8y ago

I think with SIMD type stuff and small data sets (e.g. <=16 strings), conventional big-O complexity analysis can leave a bit to be desired. Similarly, with SIMD and small data sets, you’re going to be faster than anything involving a pointer chasing data structure. Pointers tend to mean branchy-ness; they require more backend resources; they often introduce dependencies that can inhibit out of order pipelines.

Myrmornis 8y ago

To the person who downvoted this: you're using downvotes wrongly. I was asking a question about computer science. Down-voting people who ask questions about computer science is not the way to encourage the sort of conversation we're trying to encourage on HN.