5 ms·

Beating the L1 cache with value speculation (2021)

47 points by shoo 1y ago

signa11 1y ago
https://news.ycombinator.com/item?id=45499965 https://news.ycombinator.com/item?id=45499965
hshdhdhehd 1y ago
I am new to this low level, but am I right in understanding this works because he uses a linked list but often it is contiguous in memory so you guess the next element is contiguous and if it is the branch predictor predicts you are right and saves going to cache and breaking the pipeline. However I imagine you'd also get the same great performance using an array?
- vlovich123 1y ago
  Yes, as he noted the trick is of limited value in practice
- kazinator 1y ago
  Consecutive linked list nodes can occur when you bump allocate them, and in particularly if you have a copying garbage collector which ensures that bump allocation takes place from blank slate heap areas with no gaps. Idea: what if we implement something that resembles CDR coding, but doesn't compact the cells together (not a space-saving device). The idea as is that when we have two cells A and B such that A->cdr == B, and such that A + 1 == B, then we replace A->cdr with some special constant which says the same thing; indicates that A->cdr is equivalent to A + 1. Then, I think, we could have a very simple, stable and portable form of the trick in the article: while (node) { value += node->value; if (node->next == NEXT_IS_CONSECUTIVE) next = node + 1; else next = node->next; node = next; } The branch predictor can predict that the branch is taken (our bump allocator ensures that is frequently the case), and go straight to next = node + 1. When in the speculatively executed alternative path, the load of node->next completes and is not equal to the magic value, then the predicted path is canceled and we gret node->next. This doesn't look like something that can be optimized away, because we are not comparing node->next to node + 1; there is no tautology there.
- bjornsing 1y ago
  Yes. But I don’t think the OP is suggesting this as an alternative to using an array. As I read / skimmed it the linked list is just a simplified example. You can use this trick in more complex situations too, eg if you’re searching a tree structure and you know that some paths through the tree are much more common than others.
stinkbeetle 1y ago
Data speculation is a CPU technique too, which Apple CPUs are known to implement. Apparently they can do stride detection when predicting address values. Someone with a M >= 2 might try the code and find no speedup with the "improved" version, and that it's already iterating faster than L1 load-to-use latency.
- bjornsing 1y ago
  But that works on a different level, right? At least as I understand it data speculation is about prefetching from memory into cache. This trick is about using the branch predictor as an ultra-fast ”L0” cache you could say. At least that’s how I understand it.
  - stinkbeetle 1y ago
    This is doing value speculation in software, using the branch predictor. The hardware of course does do that and instead uses different tables for deriving a predicted value, and misprediction will be detected and flushed in a slightly different way. But the effect on the main sequence of instructions in the backend will be quite similar. In neither case is it a "prefetch" as such, it is actually executing the load with the predicted value and the result will be consumed by other instructions, decoupling address generation from dependency on previous load result.
    - bjornsing 1y ago
      Yeah that’s sort of how I understand the OP too: The CPU will execute speculatively on the assumption that the next element in the linked list is consecutive in memory, so it doesn’t have to wait for L1 cache. It needs to check the real value in L1 of course, but not synchronously.
- adrian_b 1y ago
  Value prediction and address prediction are very different things. Address prediction for loads and stores, by detecting various kinds of strides and access patterns, is done by most CPUs designed during the last 25 years and it is used for prefetching the corresponding data. This is as important for loads and stores as branch prediction for branches. On the other hand, value prediction for loads is done by very few CPUs and for very restricted use cases, because in general it is too costly in comparison with meager benefits. Unlike for branch direction prediction and branch target prediction, where the set from which the predicted value must be chosen is small, the set from which to choose the value that will be returned by a load is huge, except for very specific applications, e.g. which repeatedly load values from a small table. The application from the parent article is such a very special case, because the value returned by the load can be computed without loading it, except for exceptional cases, which are detected when the loaded value is different from the pre-computed value.
rini17 1y ago
Won't it introduce risk of invalid memory access when the list isn't contiguous? And if it always is contiguous then why not use array instead. Smells like contrived example.
- imtringued 1y ago
  Yeah this use case is pretty contrived. Even a simple unrolled linked list would beat his implementation.
- pkhuong 1y ago
  > Won't it introduce risk of invalid memory access no.

47 points by shoo 1y ago

https://news.ycombinator.com/item?id=45499965 https://news.ycombinator.com/item?id=45499965

I am new to this low level, but am I right in understanding this works because he uses a linked list but often it is contiguous in memory so you guess the next element is contiguous and if it is the branch predictor predicts you are right and saves going to cache and breaking the pipeline. However I imagine you'd also get the same great performance using an array?

vlovich123 1y ago
Yes, as he noted the trick is of limited value in practice
kazinator 1y ago
Consecutive linked list nodes can occur when you bump allocate them, and in particularly if you have a copying garbage collector which ensures that bump allocation takes place from blank slate heap areas with no gaps. Idea: what if we implement something that resembles CDR coding, but doesn't compact the cells together (not a space-saving device). The idea as is that when we have two cells A and B such that A->cdr == B, and such that A + 1 == B, then we replace A->cdr with some special constant which says the same thing; indicates that A->cdr is equivalent to A + 1. Then, I think, we could have a very simple, stable and portable form of the trick in the article: while (node) { value += node->value; if (node->next == NEXT_IS_CONSECUTIVE) next = node + 1; else next = node->next; node = next; } The branch predictor can predict that the branch is taken (our bump allocator ensures that is frequently the case), and go straight to next = node + 1. When in the speculatively executed alternative path, the load of node->next completes and is not equal to the magic value, then the predicted path is canceled and we gret node->next. This doesn't look like something that can be optimized away, because we are not comparing node->next to node + 1; there is no tautology there.
bjornsing 1y ago
Yes. But I don’t think the OP is suggesting this as an alternative to using an array. As I read / skimmed it the linked list is just a simplified example. You can use this trick in more complex situations too, eg if you’re searching a tree structure and you know that some paths through the tree are much more common than others.

stinkbeetle 1y ago

Data speculation is a CPU technique too, which Apple CPUs are known to implement. Apparently they can do stride detection when predicting address values. Someone with a M >= 2 might try the code and find no speedup with the "improved" version, and that it's already iterating faster than L1 load-to-use latency.

bjornsing 1y ago
But that works on a different level, right? At least as I understand it data speculation is about prefetching from memory into cache. This trick is about using the branch predictor as an ultra-fast ”L0” cache you could say. At least that’s how I understand it.
- stinkbeetle 1y ago
  This is doing value speculation in software, using the branch predictor. The hardware of course does do that and instead uses different tables for deriving a predicted value, and misprediction will be detected and flushed in a slightly different way. But the effect on the main sequence of instructions in the backend will be quite similar. In neither case is it a "prefetch" as such, it is actually executing the load with the predicted value and the result will be consumed by other instructions, decoupling address generation from dependency on previous load result.
  - bjornsing 1y ago
    Yeah that’s sort of how I understand the OP too: The CPU will execute speculatively on the assumption that the next element in the linked list is consecutive in memory, so it doesn’t have to wait for L1 cache. It needs to check the real value in L1 of course, but not synchronously.
adrian_b 1y ago
Value prediction and address prediction are very different things. Address prediction for loads and stores, by detecting various kinds of strides and access patterns, is done by most CPUs designed during the last 25 years and it is used for prefetching the corresponding data. This is as important for loads and stores as branch prediction for branches. On the other hand, value prediction for loads is done by very few CPUs and for very restricted use cases, because in general it is too costly in comparison with meager benefits. Unlike for branch direction prediction and branch target prediction, where the set from which the predicted value must be chosen is small, the set from which to choose the value that will be returned by a load is huge, except for very specific applications, e.g. which repeatedly load values from a small table. The application from the parent article is such a very special case, because the value returned by the load can be computed without loading it, except for exceptional cases, which are detected when the loaded value is different from the pre-computed value.

rini17 1y ago

Won't it introduce risk of invalid memory access when the list isn't contiguous? And if it always is contiguous then why not use array instead. Smells like contrived example.

imtringued 1y ago
Yeah this use case is pretty contrived. Even a simple unrolled linked list would beat his implementation.
pkhuong 1y ago
> Won't it introduce risk of invalid memory access no.