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

71–80 of 87 posts

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

#71

Post by PoignardAzur »

It's a neat trick, but I think a linked list (with the very specific layout where nodes are allocated in order) is the only situation where this trick could possibly be useful?

And I think it only works if Spectre mitigations are disabled anyway?

What the trick does is replace sequential fetches (where each fetch address depends on the result of the previous fetch because, well, linked lists) with parallel fetches. It takes the minimum fetch-to-fetch latency from a L1 cache hit (roughly 3 cycles IIRC) to a cycle or less (most CPUs can do multiple parallel fetches per cycle).

If your data is stored in a vector or a B-tree, accesses are already parallel by default and you'll never need this trick.

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

#72

Post by bee_rider »

gus_massa wrote: post #48
bee_rider wrote: post #39

Earlier quoted context omitted.

How sparse is your matrix?

In the last case they were like 100x100, but only two rows or columns were not zero, so only 2% full. We were using einsums to multiply them with 4D arrays, and I solved the problem writing some code with @guvectorize. In al old case they like 1000x1000, like a block checkboard where one of the colors had only 0, so like 50% full, but the blocks had different sizes. It was an old project in Fortran, and we used a "fo…

Neat. That’s fairly sparse. I’m 0% surprised to hear that small sparse matrices haven’t got as existing code out there, seems like a good excuse to roll your own :)

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

#73

Post by pkhuong »

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.

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

#74

Post by spockz »

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…

If this would be possible for an application, does it not make more sense to use SIMD instructions at that point?

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

#75

Post by gpderetta »

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.

Went for the speculation example, stayed for the interrupt-atomic memory copy. Great article.

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

#76

Post by gpderetta »

spockz wrote: post #74
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…

If this would be possible for an application, does it not make more sense to use SIMD instructions at that point?

You want to use SIMD and multiple accumulators. In fact not only you want to use as many accumulators as the number of SIMD ALUs, as SIMD operations are usually longer latency you usually unroll SIMD loops for software pipelining, using more accumulators to break loop carried dependencies.

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

#77

Post by gpderetta »

kaba0 wrote: post #69
12_throw_away wrote: post #49

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

Depend what you mean by official. There are likely more compilers implementing GCC vector extensions than there are rust compilers.

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

#78

Post by [deleted] »

trealira wrote: post #53
metadat wrote: post #51

Earlier quoted context omitted.

Makes sense, thanks! I'm still curious how this compiles down to faster ASM than a check for null.

CPUs can execute arithmetic instructions fast, because we've been trying to execute sequential instructions faster for years. One way to do this is to create a pipeline: while the result of one instruction is being calculated, start reading the next; when the result is being written to a register, you're executing the previous one. Bottlenecks are introduced by dependencies, like if an instruction modifies one regist…

[deleted]

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

#79

Post by xxpor »

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)?

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

#80

Post by johnbcoughlin »

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)?

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)
Post reply on HN