Value speculation is a neat trick. I was also surprised a low-level hack like this worked in a high-level language like OCaml.
Beating the L1 cache with value speculation (2021)
61–70 of 87 posts
Re: Beating the L1 cache with value speculation (2021)
#62Ok… all the comments are pretty nitty gritty obscure. So unless you’re a compiler hacker or HFT assembly dev, where can someone like me learn all this stuff from (besides Intel/Arm manuals, even though the i386 manuals were nice)
Re: Beating the L1 cache with value speculation (2021)
#63Earlier quoted context omitted.
That is amazing, isn't it? I want to understand, in: uint64_t sum5(Node *node) { uint64_t value = 0; Node *next = NULL; for (; node; node = node->next) { for (;;) { value += node->value; if (node + 1 != node->next) { break; } node++; } } return value; } How is this magic: if (node + 1 != node->next) { break; } Better than the more intuitive: if (node->next == null) { break; } Also.. why is `node + 1' even a valid com…
The other person who replied may have already cleared this up for you, but the two conditions you listed mean very different things. The first means “if the next node is not adjacent in memory”, while the second means “if there is no next node.
This is crucially followed by the node++ instruction. As noted elsewhere, this increases the value of the by the , thereby allowing the CPU to execute at the faster of it's memory prefetch / the speculation of the inner code loop execution speed, for as long as the sequence of list nodes is contiguous and sequential.
Re: Beating the L1 cache with value speculation (2021)
#64It’s interesting to me that the final assembly-trick-free version almost no longer looks like a hack. If you commented the inner loop with something like “// Linear scan for adjacent nodes”, the reader gets an OK, if incomplete, intuition for why it’s faster. Even if you don’t know the exact CPU details, if you’re aware that flat arrays usually loop faster than contiguous linked lists, the nested loop immediately rea…
Finding 'the hack' to get the compilers to behave is one of the areas where I'd like to see better warnings (which could get promoted to errors).
while (node) {
value += node->value;
next = node->next;
node++; // Line 101
if (node != next) {
node = next;
}
}
// Compiler warning
// Warning: Lines 101 102 103: always true evaluation combined
while (node) {
while (node) {
value += node->value;
if (node + 1 != node->next) break;
node++;
}
node = node->next;
}Re: Beating the L1 cache with value speculation (2021)
#65Ok… all the comments are pretty nitty gritty obscure. So unless you’re a compiler hacker or HFT assembly dev, where can someone like me learn all this stuff from (besides Intel/Arm manuals, even though the i386 manuals were nice)
Agner Fog's x86 microarchitecture and optimization manuals are a good start.
Re: Beating the L1 cache with value speculation (2021)
#66This got me wondering - it's said that C is based on the lie that all computers have the same architecture as a PDP-11. (At least, I'm pretty sure I remember people saying that). So, are there any programming languages that have updated architectural models, something that takes into account branch prediction, CPU caches, etc?
As far as I am aware, this saying is based on the reasoning behind C types rather than serious compiler considerations. In today's world such cpu-specific concerns are left to the compiler to figure out. I'm sure you could contrive a language where this functionality is exposed, but I'm struggling to come with an example where this would be seriously beneficial across multiple platforms. I strongly suspect that integ…
I guess that’s what intel and amd were relying on, while nvidia let cuda programmers control the gpu cache explicitly.
Re: Beating the L1 cache with value speculation (2021)
#67This is great! Mostly when I think about branch prediction, I'm thinking about the end of a loop so this was a great read. There have been a lot of comments about the example presented being quite artificial and I agree but it is simple enough to help the reader understand what's happening and why it's faster. In fact, it would be fairly common for the nodes in linked lists to be sequential in ram anyway. For example…
That's a controversial part of it. I think that strictly, if the nodes are allocated as part of one array, it is permissible to use current++ to traverse from one to the other. While it would be UB if they are in separate allocations, even if it logically should work all the same way.
Re: Beating the L1 cache with value speculation (2021)
#68Ok… all the comments are pretty nitty gritty obscure. So unless you’re a compiler hacker or HFT assembly dev, where can someone like me learn all this stuff from (besides Intel/Arm manuals, even though the i386 manuals were nice)
Agner Fog's x86 microarchitecture and optimization manuals are a good start.
Optimisation manuals?! Wow that’s the first time I’ve ever heard of them. Thank you!!
Re: Beating the L1 cache with value speculation (2021)
#69This got me wondering - it's said that C is based on the lie that all computers have the same architecture as a PDP-11. (At least, I'm pretty sure I remember people saying that). So, are there any programming languages that have updated architectural models, something that takes into account branch prediction, CPU caches, etc?
Well, C++ has the likely/unlikely attribute to somewhat prefer a branch over the other in the eye of the branch predictor, and C++, Rust and some other low-level languages do have native SIMD support (note: C doesn’t have an official one, just compiler-specific ones. So in this vein it is actually higher level than Rust or C++).
Re: Beating the L1 cache with value speculation (2021)
#70Earlier quoted context omitted.
As far as I am aware, this saying is based on the reasoning behind C types rather than serious compiler considerations. In today's world such cpu-specific concerns are left to the compiler to figure out. I'm sure you could contrive a language where this functionality is exposed, but I'm struggling to come with an example where this would be seriously beneficial across multiple platforms. I strongly suspect that integ…
I guess that’s what intel and amd were relying on, while nvidia let cuda programmers control the gpu cache explicitly.
I can't speak to CUDA or GPUs as I've never had a reason to use either. Perhaps we've finally left the land of the PDP.