Beating the L1 cache with value speculation (2021)

Post by metadat » Sat, Jul 13, 2024, 1:24 AM UTC

trealira wrote: post #50

metadat wrote: post #47

Earlier quoted context omitted.

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]; // Ta…

Post by trealira » Sat, Jul 13, 2024, 1:42 AM UTC

metadat wrote: post #51

trealira wrote: post #50

Earlier quoted context omitted.

> 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]; // Ta…

Makes sense, thanks! I'm still curious how this compiles down to faster ASM than a check for null.

Post by trealira » Sat, Jul 13, 2024, 2:01 AM UTC

metadat wrote: post #54

trealira wrote: post #53

Earlier quoted context omitted.

CPUs can execute arithmetic instructions fast, because we've been trying to execute sequential instructions faster for years. One way to do this is to create a pipeline: while the result of one instruction is being calculated, start reading the next; when the result is being written to a register, you're executing the previous one. Bottlenecks are introduced by dependencies, like if an instruction modifies one regist…

This jives with my understanding of pipelining architecture and speculative execution, thank you for connecting the dots! Seriously cool to understand why that line works better. It seems unfortunate the compiler isn't able to realize "no further assignments are ever performed on node->next, it is side-effect dependency free, optimize the spec exec accordingly". Though, how often would this be the case in a real-worl…

Post by WantonQuantum » Sat, Jul 13, 2024, 3:11 AM UTC

ahoka wrote: post #21

candiddevmike wrote: post #13

Earlier quoted context omitted.

It's impressive that it doesn't have a mobile view and still looks great.

What? It looks horrible.

Post by WantonQuantum » Sat, Jul 13, 2024, 4:02 AM UTC

  #include 
  #include 

  typedef struct Node {
    int value;
    struct Node *next;
  } Node;

  Node *head = NULL;
  Node *tail = NULL;

  int main(int argc, char **argv) {

    // Allocate some nodes
    for (int i = 0; i value = rand();
      new_node->next = NULL;
      if (tail == NULL) {
        head = tail = new_node;
      } else {
        tail->next = new_node;
        tail = new_node;
      }
    }

    // Print their locations in memory
    for (Node *current = head; current->next != NULL; current = current-> next) {
      printf("%p\n", current);
    }
  }