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

41–50 of 87 posts

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

#41

Post by mistercow »

pfedak wrote: post #31
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…

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.

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

#42

Post by kazinator »

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 Linux kernel is full of links, and so are many (probably most) C programs in the GNU/Linux userland.

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

#43

Post by kazinator »

kevin_thibedeau wrote: post #33
account42 wrote: post #17

Earlier 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.

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.

Garbage collection is good at consolidating swaths of adjacent free objects into ordered allocation.

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

#44

Post by oersted »

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…

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.

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

#45

Post by bee_rider »

Hmm. What do we think about the alternative guess that the address of the next node’s value field is the next address after our current node’s value field memory address? This is, I guess, essentially a guess that we’re pointing at sequential elements of a big array, which sort of begs the question “why not just use an array?” But I’m wonder if a slightly permuted array is not so unusual, or at least might come up occasionally.

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

#46

Post by mistercow »

bee_rider wrote: post #45

Hmm. What do we think about the alternative guess that the address of the next node’s value field is the next address after our current node’s value field memory address? This is, I guess, essentially a guess that we’re pointing at sequential elements of a big array, which sort of begs the question “why not just use an array?” But I’m wonder if a slightly permuted array is not so unusual, or at least might come up oc…

I feel like there are a number of data structures that you might initially set up (or load in) in some preferred contiguous order, which will still remain largely contiguous after modification, so that you get a good tradeoff between cheap operations and fast traversal. You’d then have the option to do partial defragmentation at convenient times, without having to have a convoluted hybrid data structure. But it’s definitely something you’d do in specific critical cases after a lot of analysis.

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

#47

Post by metadat »

mistercow wrote: post #40

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 rea…

That is amazing, isn't it?

I want to understand, in:

  uint64_t sum5(Node *node) {
    uint64_t value = 0;
    Node *next = NULL;
    for (; node; node = node->next) {
      for (;;) {
        value += node->value;
        if (node + 1 != node->next) {
          break;
        }
        node++;
      }
    }
    return value;
  }
How is this magic:

        if (node + 1 != node->next) {
          break;
        }
Better than the more intuitive:

        if (node->next == null) {
          break;
        }
Also.. why is `node + 1' even a valid comparison? (Please forgive my rusty C/C++, college was awhile ago)

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

#48

Post by gus_massa »

bee_rider wrote: post #39
gus_massa wrote: post #11

Earlier quoted context omitted.

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?

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 "for"(do) for the blocks and another inside each block.

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

#49

Post by 12_throw_away »

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?

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

#50

Post by trealira »

metadat wrote: post #47
mistercow wrote: post #40

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 rea…

That is amazing, isn't it? I want to understand, in: uint64_t sum5(Node *node) { uint64_t value = 0; Node *next = NULL; for (; node; node = node->next) { for (;;) { value += node->value; if (node + 1 != node->next) { break; } node++; } } return value; } How is this magic: if (node + 1 != node->next) { break; } Better than the more intuitive: if (node->next == null) { break; } Also.. why is `node + 1' even a valid com…

> Also.. why is `node + 1' even a valid comparison here?

In C and C++, when you add 1 to a pointer, you actually make it point to the next object of that size in memory, e.g. if I have a pointer to a 4-byte integer at address 0x8000, incrementing it will make it point to address 0x8004.

Because arrays are contiguous chunks of memory, you can use this to iterate through arrays.

  int array[50];
  int *p = &array[0]; // Take the address of the first array element
  int sum = 0;
  for (int i = 50; i != 0; i--) {
      sum += *p;
      p++; // Point to the next element
  }
After this loop, p will be equal to &array[50], which is one past the last element of the array, because the loop will have run 50 times, and p is incremented once per loop.

What OP did is allocate an array of linked list nodes, and test to see if the next linked list node was actually just the next array element.

Post reply on HN