Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Beating the L1 cache with value speculation (2021)

mazzo.li

Post reply on HN
Print view View original

81–87 of 87 posts

Re: Beating the L1 cache with value speculation (2021)

#81

Post by Remnant44 »

pkhuong wrote: post #73

I see a lot of people asking for a real use case. If you follow the reference chain in the first aside, you'll find this blog post of mine https://pvk.ca/Blog/2020/07/07/flatter-wait-free-hazard-poin... . where we use value speculation to keep MOVS out of the critical path in an interrupt-atomic read sequence for hazard pointers.

Very nice! I was struggling to come up with a realistic real world scenario for value speculation, but this is a perfect example. Any kind of multi-thread/contention related code seems like an ideal target for making a guess-based fast-path corrected by a slow-path consistency check

Re: Beating the L1 cache with value speculation (2021)

#83

Post by WantonQuantum »

kzrdude wrote: post #67
WantonQuantum wrote: post #59

This 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.

Oh yes, you're right!

Re: Beating the L1 cache with value speculation (2021)

#84

Post by [deleted] »

xxpor wrote: post #79
Remnant44 wrote: post #36

It's rare to need to work at this level of optimization, but this is a really neat trick! Modern cores are quite wide - capable of running 6-8 instructions at once, as long as there are no dependencies. Something as simple and common as a summation loop can often be sped up 2-4x by simply having multiple accumulators that you then combine after the loop body; this lets the processor "run ahead" without loop carried d…

>Something as simple and common as a summation loop can often be sped up 2-4x by simply having multiple accumulators that you then combine after the loop body; this lets the processor "run ahead" without loop carried dependencies and execute multiple accumulations each cycle. Shouldn't the compiler be smart enough to figure that out these days (at least if it truly is a straightforward accumulation loop)?

[deleted]

Re: Beating the L1 cache with value speculation (2021)

#86

Post by xxpor »

johnbcoughlin wrote: post #80
xxpor wrote: post #79

Earlier quoted context omitted.

>Something as simple and common as a summation loop can often be sped up 2-4x by simply having multiple accumulators that you then combine after the loop body; this lets the processor "run ahead" without loop carried dependencies and execute multiple accumulations each cycle. Shouldn't the compiler be smart enough to figure that out these days (at least if it truly is a straightforward accumulation loop)?

Such optimizations may be forbidden by the fact that floating point addition is not associative unless you tell the compiler not to worry about that (I believe)

Ah yes, I always forget about the rules with floats. My line of work only ever uses ints.

Re: Beating the L1 cache with value speculation (2021)

#87

Post by account42 »

johnbcoughlin wrote: post #80
xxpor wrote: post #79

Earlier quoted context omitted.

>Something as simple and common as a summation loop can often be sped up 2-4x by simply having multiple accumulators that you then combine after the loop body; this lets the processor "run ahead" without loop carried dependencies and execute multiple accumulations each cycle. Shouldn't the compiler be smart enough to figure that out these days (at least if it truly is a straightforward accumulation loop)?

Such optimizations may be forbidden by the fact that floating point addition is not associative unless you tell the compiler not to worry about that (I believe)

> floating point addition is not associative unless you tell the compiler not to worry about that

Ah yes, fun and safe math optimizations.

Post reply on HN