4 ms·

One of the effects first noticed in CS papers maybe 20 years ago is that binary heaps should NOT start from the beginning of a cache line, which is what most pr

by puzzle 9y ago

One of the effects first noticed in CS papers maybe 20 years ago is that binary heaps should NOT start from the beginning of a cache line, which is what most programmers would assume would be a wise thing to do. We're always told to align to cache boundaries. If you don't move the root node to the end of a cache line (or at least toward the middle, depending on line size and node size), traversing the heap will touch more lines, since the sibling nodes you need to compare will often/always be in separate cache lines.

mini_marcel 9y ago
Hi! I'm sure I misunderstand your comment, but correct me if I'm wrong. For instance, if each item has a size of 64B (for N=7), which is the size of a cache line, then whatever the position of the first element into the first cache line, the next item will necessary be located into the next cache line. Did I miss something?
- puzzle 9y ago
  In a binary heap, there's a single root, but after that, there are pairs of nodes. In your case, the item has the same size of a cache line, so things are not too bad. During traversal, you'll always read two whole lines for each pair of nodes. You could still worry about the CPU cache's n-way associativity, but either that requires a lot of control over memory allocation layout or it will provide diminishing returns. Anyway, the interesting case is when items are smaller than a line. Look at an array-based implementation of a heap: https://en.m.wikipedia.org/wiki/Binary_heap#Heap_implementation https://en.m.wikipedia.org/wiki/Binary_heap#Heap_implementat... Root is item 0. Assume it's aligned to a multiple of 64 bytes and you have two 32-byte items per line. When comparing array items 1&2, 3&4, 6&7, etc., notice how the two items are always in different cache lines. Item 1 is in the same line as item 0, not item 2. You're always crossing the line boundary. If the root were at item 1 in the same array (or, equivalently, item 0 in case the array started at a multiple of 64, plus an offset of 32), then each pair would be always in the same cache line. In case it wasn't clear, I was pointing out a similar phenomenon with other data structures; it wasn't about linked lists.
  - mini_marcel 9y ago
    Ok yes!! This is perfectly clear now, thanks. I didn't know, very interesting and a smart optimisation of cache lines use! I've also read that the processors are able to ask words (of a cache line) in different orders, and so ask for hot words first. It may help a little if this kind of structure was not aligned in an optimized fashion. Doesn't work for HW prefetch, though.

by puzzle 9y ago

mini_marcel 9y ago

Hi! I'm sure I misunderstand your comment, but correct me if I'm wrong. For instance, if each item has a size of 64B (for N=7), which is the size of a cache line, then whatever the position of the first element into the first cache line, the next item will necessary be located into the next cache line. Did I miss something?

puzzle 9y ago
In a binary heap, there's a single root, but after that, there are pairs of nodes. In your case, the item has the same size of a cache line, so things are not too bad. During traversal, you'll always read two whole lines for each pair of nodes. You could still worry about the CPU cache's n-way associativity, but either that requires a lot of control over memory allocation layout or it will provide diminishing returns. Anyway, the interesting case is when items are smaller than a line. Look at an array-based implementation of a heap: https://en.m.wikipedia.org/wiki/Binary_heap#Heap_implementation https://en.m.wikipedia.org/wiki/Binary_heap#Heap_implementat... Root is item 0. Assume it's aligned to a multiple of 64 bytes and you have two 32-byte items per line. When comparing array items 1&2, 3&4, 6&7, etc., notice how the two items are always in different cache lines. Item 1 is in the same line as item 0, not item 2. You're always crossing the line boundary. If the root were at item 1 in the same array (or, equivalently, item 0 in case the array started at a multiple of 64, plus an offset of 32), then each pair would be always in the same cache line. In case it wasn't clear, I was pointing out a similar phenomenon with other data structures; it wasn't about linked lists.
- mini_marcel 9y ago
  Ok yes!! This is perfectly clear now, thanks. I didn't know, very interesting and a smart optimisation of cache lines use! I've also read that the processors are able to ask words (of a cache line) in different orders, and so ask for hot words first. It may help a little if this kind of structure was not aligned in an optimized fashion. Doesn't work for HW prefetch, though.