Beating the L1 cache with value speculation

That depends on the allocator you use. If you allocate your nodes from an arena that belong to the list, the resulting layout is usually pretty good.

Are you familiar with Donald Knuth's "Dancing Links" ??

Its a covering-problem solver (NP-complete) that uses linked lists highly-efficiently. All nodes are "statically allocated" (at least, with respect to the algorithm), because the covering-problem takes up a constant amount of space.

The linked-list "Dances", pointing at other nodes to represent which combination of covers are attempted. So any link could potentially point to any other link later in its list. However, the number of nodes themselves is constant and set before the algorithm runs.

As such, the linked-list is fully X1->X2->X3->X4... at the start of the algorithm. (where X1, X2, X3 are contiguously allocated in memory). If X3 is proven to "not be a good guess" for our covering problem, then it is cut out of the linked list (X1->X2->X4).

All links remain in order, and are ordered on a 2-dimensions (So not only X1->X2->X3... but also X1->Y1->Z1...). Where X, Y and Z are the compound-elements trying to cover locations 1, 2, 3, ...

------------

Most simple malloc implementations also have the free-list as a simple linked-list that is in fact, ordered in memory. (The first node in the free-list is the lowest numbered RAM spot, while the final node in the free-list is in the highest-numbered RAM spot).

The FAT32 linked-list across a hard drive is also nicely ordered (and when it isn't, the user will perform "defragmentation" to reorder the list and optimize the hard drive).

-----------

IMO, the "nicely ordered Linked List" is uncommon, but... common enough that its worth discussion. And sure, maybe we don't use FAT32 filesystems today very often, but that's the technology I used growing up lol. I know the methodology works!!

It's fairly standard for a compacting GC to rearrange lists this way, because memory latency was a concern even back in the 80s.

If you're using linked lists in a language without a compacting GC, then you almost certainly want something else instead.

If you're using them in a language with one, then you still usually want something else, but at least the cost isn't as high. Also you might be using Haskell or something, where other constraints make data-structures like arrays painful to use.

You can get help from the allocator. For example jemalloc has an experimental API called "batch allocation" where it returns a list of allocations of the same size, and it makes its best effort to make them contiguous (not guaranteed though): https://github.com/jemalloc/jemalloc/blob/12cd13cd418512d9e7...

The idea is that you may have a data structure that you want to be able to modify (in which case you need to free individual nodes) but in most cases you do not.

Then you could use batch allocation, and pair it with this optimization.

It's extremely common in Lisp. Linked lists are the natural data structure of Lisp and in most modern programs they rarely get modified. Common Lisp provides vectors for greater efficiency but they might be less necessary in many programs if this trick works.

Given the nature of branch prediction, I’d expect it would still help dramatically in the case where the list was almost entirely sequential, which seems a bit more plausible.

I could imagine behaviors like this happening with object pools, though it does still feel a bit contrived.

In the field of high performance processor microarchitecture, one goal is to increase performance by executing a maximum number of instructions in parallel (increase IPC). For this purpose we identify dependencies between instructions. We identify 4 types of dependencies between instruction registers: Read after Write (RaW), Read after Read (RaR), Write after Read (WaR) and Write after Write (WaW). (the same kind of dependencies exist with memory)

Among these dependencies some are caused by the reduced number of registers, with more registers they can be removed, this is called false dependencies. 3 of these 4 dependencies are false dependencies: RaR, WaR, WaW. And with register renaming techniques we can eliminate these dependencies and therefore increase IPC.

Only the Read after Write (RaW) dependency remains and it really determines what can be executed in parallel or not in modern machines. The whole point of value speculation is to break the RaW dependency to increase IPC.

The papers you quoted cover value speculation in hardware, while the article covers value speculation in software.

The possibilities and gains relative to these 2 approaches differ since: in software we can predict a whole expression, while in hardware we can only predict a static value (or a pattern of values). But in hardware it doesn't require any particular effort at compile time and it doesn't increase the code size.

I recently spoke with one of the researchers you mentioned (who deals with value speculation in hardware) and he acknowledged that the performance gain is currently quite low relative to the amount of hardware to be added.

But maybe the research in hardware value speculation will lead to a higher performance gain? Maybe in software there are more realistic gains? Maybe even a mix of hardware and software can make the value speculation powerful?

Imagine an instruction `predict <rd>, <r1>, <r2>` where rd takes the value of r1 but the processor is allowed to use the value of r2 as a value prediction

  while (node) {
    value += node->value;
    next = node->next;

So it is the same thing.

That looks weird, why would you need to test if two values are equal if you’re going to assign them to be equal anyway?

Personally, I prefer to just use the RDTSC assembly instruction (Read TimeStamp Counter), which provides the 64-bit number of clocks your core has ticked.

Both Windows and Linux provide more robust timers (in particular: if your thread takes longer than 10ms, there's a chance your thread will sleep to give other threads a shot at the CPU). So if you're timing something longer than 10ms, you probably want to use OS timers instead.

-------------

There were a few programs where I couldn't add rdtsc easily to the code (in particular: I was trying to test something so fast that rdtsc took up the bulk of the time). In these cases, I went into the BIOS, disabled "turbo" on my CPU, locking my computer to 3.4GHz.

From there, I took the Windows timer and measured 1-billion events, and then divided by 3.4-Billion (3.4GHz == 3.4-billion clocks per second).

---------

I don't know the specific methodology that the blogpost used. But there's many easy ways to do this task.

Some tools you can do this with:

The perf command line utility, the perf_event_open system call, the libpapi high level API, pmc.h on FreeBSD (IIRC).

Now, some more clever analysis: These can tell you the why rather than the what, they collect the same information but can present it graphically and compute TMAM statistics for example (Top-down microarchitecture analysis method).

vTune, Intel Advior, AMD uProf, and a few others. vTune is the best for x86, but only supports Intel fully.

The program is reading perf events.

The code is at https://gist.github.com/bitonic/78887f5d3238bab5e31f3c5a41d4...

Not necessarily. After putting a lot of brain grease into writing the code, it will probably work just fine.

But it will lead to a bunch of serious "WTF!?" situations when other people look at the code and/or are supposed to make changes at a later point.

And possibly stuff breaking in spectacular ways after introducing "minor cleanup" patches. Or some weird performance regressions, after touching completely unrelated code that might affect the temporal order of the memory allocations in questions, and so on...

Besides improving performance, doing this kind of trickery in production code will probably also improve your job security.

Why? Most of the time these predictions help you.

Compilers are 'just' graph transformations applied to code which probably leads to improved performance.

A compiler can therefore optimize away unnecessary loads/stores, or recognize implicit parallelism and transform a loop into a SIMD loop.

But a compiler will not change the logic of your code or add extra steps.

For a compiler to properly do the optimization detailed here would require it to have knowledge of runtime execution/memory access patterns. This might be done through profile-guided optimization, or by providing hints like __builtin_expect.

That said, compilers are not magic boxes. Relying on your compiler for optimal codegen has diminishing returns as you approach the point where microarchitectural details start making a difference. Most people don't get to that point, so it's rarely an issue.

This is not a 'static' optimization. It relies on knowledge that the compiler cannot decide by looking at the code (whether the linked list is _mostly_ laid out continuously).

It might still be a very useful optimization in a JIT runtime. If your loop variable keeps increasing the same amount after every lookup, maybe rewrite the loop to add speculation...

The code relies on information not present in the program - "this linked list consist mostly of nodes sequentially arranged".

If you could express that in your programming language, then yes, the compiler could optimize it. One could argue that the "weird" if statement is just that hint.

And is it useful? It depends. There are plenty of situations where doubling your throughput is worth a lot of effort. There've been situations in my career where I've spent a month or two to shave a cycle or two. It's rare. But when you need it, you want the biggest bag of tricks you can bring, because it really matters :)

The compiler deduces that even though the statement `node = next` is inside an `if`, it is more general, so it removes both `node++` and the `if`.

There are some restricted form of value prediction in the wild: Indirect branch prediction is fairly common; so is alias prediction that will speculate whether two data addresses (at least one if which is a store) do not alias; AMD memory renaming also makes assumptions around stack addresses; outside of these special cases I'm not aware on any cpu that will actually generally speculate actual values or address.

On relaxed memory model machines naive value prediction would break dependency ordering (i.e. memory order consume), so things get very complicated.