I appreciate the elegant blog design. Reminds me of Edward Tufte's books.
It's impressive that it doesn't have a mobile view and still looks great.
What? It looks horrible.
Beating the L1 cache with value speculation (2021)
21–30 of 87 posts
Re: Beating the L1 cache with value speculation (2021)
#22The 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 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_... .
Re: Beating the L1 cache with value speculation (2021)
#23I will change my game level
Re: Beating the L1 cache with value speculation (2021)
#24I appreciate the elegant blog design. Reminds me of Edward Tufte's books.
Ha, I think this site is styled by a single-sheet CSS called Tufte.css
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...
Re: Beating the L1 cache with value speculation (2021)
#25The 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 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
Re: Beating the L1 cache with value speculation (2021)
#26The optimization is the linear memory layout of the nodes -- value speculation is decoration.
Re: Beating the L1 cache with value speculation (2021)
#27In case your knowledge of the mechanics of `struct' vs `typedef struct' in C are rusty like mine, here are nice refreshers:
Re: Beating the L1 cache with value speculation (2021)
#28I 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.
Re: Beating the L1 cache with value speculation (2021)
#29I 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 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.
Re: Beating the L1 cache with value speculation (2021)
#30Earlier quoted context omitted.
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 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.
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.