[HN Gopher] Beating the L1 cache with value speculation (2021)
___________________________________________________________________
Beating the L1 cache with value speculation (2021)
Author : nickdevx
Score : 148 points
Date : 2024-07-11 20:17 UTC (1 days ago)
(HTM) web link (mazzo.li)
(TXT) w3m dump (mazzo.li)
| bobmcnamara wrote:
| The nodes are adjacent.
| gergo_barany wrote:
| 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.
| mnw21cam wrote:
| The article states that the CPU has a limit of 4 instructions per
| cycle, but the sum2 method issues 5 instructions per cycle.
| Presumably one of them (maybe the increment) is trivial enough to
| be executed as a fifth instruction.
| gpderetta wrote:
| some nominally 4-wide intel cpus can execute 5 or 6
| instructions per cycle when macrofused. For example a cmp and a
| conditional jXX can be macrofused.
| rostayob wrote:
| 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_...
| .
| xiphias2 wrote:
| It's cool, I would love to have this for ARMv8 Mac
| gergo_barany wrote:
| 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.
| IshKebab wrote:
| 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!
| Bootvis wrote:
| It might be useful in cases where you pre-allocate a large
| array which you don't randomly access and whose structure
| doesn't change much but sometimes it does. Then you could
| either reallocate the array and pay a (large) one time cost or
| use this trick.
| gus_massa wrote:
| 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 get an improved speed. I finaly gave
| up and used a normal np matrixes.)
| bee_rider wrote:
| How sparse is your matrix?
| bell-cot wrote:
| Bigger-picture, this method amounts to manually assisted
| speculative execution. And it's not about knowing the not-yet-
| loaded _value_ , but about knowing what will (very likely)
| happen as a consequence of that value.
| dmoy wrote:
| 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
| performance critical loop where some hacky guessing might work.
| account42 wrote:
| Not only are linked lists rare, they are also mainly useful
| exactly in situations where you cannot guarantee a (even
| mostly) linear allocation order.
| gpderetta wrote:
| the optimization could be vaguely interesting if you are
| implementing a lisp (or some other list heavy language) and
| don't want to perform too aggressive non-local
| optimizations to optimize the layout of lists.
| twoodfin wrote:
| As I recall, at least one of the Lisp machine Lisps used
| a bit in the cons pair to declare if the cdr (tail
| element) was immediately following.
|
| EDIT: https://en.wikipedia.org/wiki/CDR_coding
| kevin_thibedeau wrote:
| 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.
| kazinator wrote:
| Garbage collection is good at consolidating swaths of
| adjacent free objects into ordered allocation.
| saagarjha wrote:
| 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.
| kazinator wrote:
| The Linux kernel is full of links, and so are many
| (probably most) C programs in the GNU/Linux userland.
| gpderetta wrote:
| In principle a compiler via JIT or PGO could do this
| optimization automatically.
| queuebert wrote:
| I appreciate the elegant blog design. Reminds me of Edward
| Tufte's books.
| candiddevmike wrote:
| It's impressive that it doesn't have a mobile view and still
| looks great.
| ahoka wrote:
| What? It looks horrible.
| AnthOlei wrote:
| Ha, I think this site is styled by a single-sheet CSS called
| Tufte.css
| notpushkin wrote:
| I don't think it is. In Tufte CSS, sidenotes are implemented
| using float: right [1], while here CSS Grid is used instead.
|
| [1]: https://github.com/edwardtufte/tufte-
| css/blob/957e9c6dc3646a...
| gpderetta wrote:
| Nice article!
|
| Incidentally, value speculation (or prediction) is a way to break
| causality in concurrent memory models.
| Atharshah wrote:
| I will change my game level
| mwkaufma wrote:
| The optimization is the linear memory layout of the nodes --
| value speculation is decoration.
| pfedak wrote:
| 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.
| mistercow wrote:
| I think a more practical example might have been to have a
| mostly contiguous list with a few discontinuous nodes
| inserted randomly in the middle. That's more like a real
| case, and exercises the advantages of linked lists over
| simple arrays, but should still perform well, since there
| would only be a few value speculation misses.
| Remnant44 wrote:
| 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!
| metadat wrote:
| In case your knowledge of the mechanics of `struct' vs `typedef
| struct' in C are rusty like mine, here are nice refreshers:
|
| https://stackoverflow.com/a/23660072
|
| https://stackoverflow.com/a/1675446
| oersted wrote:
| 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.
| sfink wrote:
| 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
| optimize for the natural order.
|
| Then again, I pretty much agree with you. I think it's a clever
| trick, but I can't come up with a time when I would use it.
| Largely that's probably because if the memory is contiguous
| most of the time, then you should probably be using a vector
| instead. You can insert/remove by shifting stuff around to
| handle the rare cases that require the linked list. If
| performance cliffs are a problem, you can mitigate with a
| segmented array.
| scottlamb wrote:
| 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.
| oersted wrote:
| I do think there are examples out there for this value
| prediction trick that could make sense, which is why I was a
| bit frustrated by the example they chose.
|
| Someone mentioned sparse vectors for example, where you are
| guessing 0 rather than pointer++. Anytime where a value is
| somewhat predictable this could come in handy.
| Remnant44 wrote:
| 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.
| mistercow wrote:
| 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".
___________________________________________________________________
(page generated 2024-07-12 23:00 UTC)