|
|
|
|
|
|
by WantonQuantum
712 days ago
|
|
|
This is great! Mostly when I think about branch prediction, I'm thinking about the end of a loop so this was a great read. There have been a lot of comments about the example presented being quite artificial and I agree but it is simple enough to help the reader understand what's happening and why it's faster. In fact, it would be fairly common for the nodes in linked lists to be sequential in ram anyway. For example this code shows that the next node is easy to guess. The nodes do end up exactly in sequence in memory: #include <stdlib.h>
#include <stdio.h>
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 < 100; i++) {
Node *new_node = malloc(sizeof(Node));
new_node->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);
}
}
|
|
|