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

31–40 of 87 posts

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

#31

Post by pfedak »

mwkaufma wrote: post #26

The optimization is the linear memory layout of the nodes -- value speculation is decoration.

The example is poorly chosen in terms of practicality for this reason, but otherwise, no, this is a poor summary that misses something interesting.

The memory layout isn't changing in the faster versions, and there are no additional cache misses. It's easy to convince yourself that the only difference between the naive linked list and assuming linear layout is the extra pointer load - but TFA shows this is false! The execution pipeline incurs extra costs, and you can influence it.

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

#32

Post by gergo_barany »

xiphias2 wrote: post #25
rostayob wrote: post #22

Earlier quoted context omitted.

gpderetta is right -- test/cmp + jump will get fused. uiCA is a very nice tool which tries to simulate how instructions will get scheduled, e.g. this is the trace it produces for sum3 on Haswell, showing the fusion: https://uica.uops.info/tmp/75182318511042c98d4d74bc026db179_... .

It's cool, I would love to have this for ARMv8 Mac

The LLVM project has a tool called llvm-mca that does this. Example: https://gcc.godbolt.org/z/7zcova1ce

The version in the Compiler Explorer wouldn't work on AArch64 without an -mcpu flag and I didn't know what to pass, so I copied -mcpu=cyclone from https://djolertrk.github.io/2021/11/05/optimize-AARCH64-back.... You'd have to look up the correct one for your Mac's CPU.

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

#33

Post by kevin_thibedeau »

account42 wrote: post #17
dmoy wrote: post #14

Earlier quoted context omitted.

Well in the articles case, it's the linked list `next` pointers: https://mazzo.li/posts/value-speculation.html#value-speculat... In a happy case, those will be laid out sequentially in memory so you can guess the value of the pointer easily. (That said your comment still stands, since using linked lists in the first place is much more rare). But I suppose there's probably a lot of other domains where you might have a…

Not only are linked lists rare, they are also mainly useful exactly in situations where you cannot guarantee a (even mostly) linear allocation order.

Memory pools are commonly allocated in a contiguous block and sliced into nodes placed onto a free list. They will be sequential until the pattern of allocations mixes them up.

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

#34

Post by gergo_barany »

bobmcnamara wrote: post #3

The nodes are adjacent.

The nodes are adjacent in sum1.

The nodes are adjacent in sum2, and sum2 executes more instructions than sum1, and sum2 is faster than sum1.

The nodes are adjacent in sum3, and sum3 executes more instructions than sum1, and sum3 is faster than sum1.

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

#35

Post by scottlamb »

sfink wrote: post #29
oersted wrote: post #28

I enjoyed the read and it taught me new things, I just wish that the reference example would have some minimal practical value. I don’t think there is any reasonable scenario where you would be using a linked list but the memory is contiguous most of the time.

It's not that unlikely. - Create the list in some weird order. You know you're going to traverse it a bunch, so you sort it. - The list is in creation order, and creation is in allocation order. Once in a while you go back and insert or delete a small handful of nodes, hence the linked list. - There is a natural sort order that you can make contiguous, but you support relatively rare alternative orderings and optimiz…

Yeah, this layout of a linked list within one big allocation seems like a niche thing at best.

* I tend to default to a simple vector because it's denser, more CPU cache friendly, less pointer chasy.

* If I really wanted a linked list to avoid occasional expensive ops, I probably would want to be able to grow it without reallocation (much less touching up all the old pointers), so they might all be in separate allocations, and most general-purpose memory allocators won't give me the nice sequential-ness.

* And then I'd probably end up with an unrolled linked list (probably the same thing you're describing as a "segmented array"?), which would reduce the pointer chasing and also make better use of the memory bandwidth through better density, so it'd outperform this trick.

* I guess if I really wanted to be able to reorder stuff within a vector cheaply but was still comfortable with the amortized constant time for growth, I might have represent the links as indices within the vector (or in a parallel vector). It'd be useful then. Maybe something like a linked hash map too. But if those ops are common, the 100% accurate prediction of this benchmark is way too optimistic. Could sort it sometimes as you mentioned, but that seems even more niche and fussy.

There might be other cases of this trick that I'm more likely to use than this data structure, but I'm scratching my head to think of them.

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

#36

Post by Remnant44 »

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 dependencies and execute multiple accumulations each cycle.

This technique is similar in concept, but even more general. Put the "guess" in the registers and run with it, relying on a second instruction within a branch to correct the guess if its wrong. Assuming your guess is overwhelmingly accurate... this lets you unlock the width of modern cores in code that otherwise wouldn't present a lot of ILP!

Clever.

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

#37

Post by Remnant44 »

mwkaufma wrote: post #26

The optimization is the linear memory layout of the nodes -- value speculation is decoration.

The linear node layout is not the point at all.

It's serving two purposes here:

1) Providing us with a correct "guess" of what the next node is. 2) Ensuring that in all cases we're running from the L1 cache.

In real world code, you'd be correct -- getting things to run out of L1/L2 is the most important attribute. This is specifically about a micro-optimization that allows you to beat the obvious code even when running completely from cache!

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

#38

Post by saagarjha »

account42 wrote: post #17
dmoy wrote: post #14

Earlier quoted context omitted.

Well in the articles case, it's the linked list `next` pointers: https://mazzo.li/posts/value-speculation.html#value-speculat... In a happy case, those will be laid out sequentially in memory so you can guess the value of the pointer easily. (That said your comment still stands, since using linked lists in the first place is much more rare). But I suppose there's probably a lot of other domains where you might have a…

Not only are linked lists rare, they are also mainly useful exactly in situations where you cannot guarantee a (even mostly) linear allocation order.

The point here is that this isn't guaranteed, it's that it is likely. And as the other commenters mention, it's likelier than you think.

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

#39

Post by bee_rider »

gus_massa wrote: post #11
IshKebab wrote: post #6

Neat trick. Though it seems unlikely to be very useful in practice. How often are you going to know the probably value of a pointer without knowing the actual value? I would guess it's pretty rare. Interesting anyway!

It's possible to have a "sparse" matrixes where most of the values are 0 and only a few are not null. So you can guess 0 and cross your fingers. (There are libraries that implement sparse matrixes in a more memory efficient way. I needed them for a program in Python, but I'm not an expert in Python. I found a few ways, but they are only useful for big matrixes with very few coeficients and have other restrictions to…

How sparse is your matrix?

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

#40

Post by mistercow »

It’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 reads as a kind of “hybrid mode”.

Post reply on HN