4 ms·

Oh, please. There are technically correct nitpicks with some merit and there are trivial remarks like yours. It is perfectly clear what "pointer-free" was refe

Oh, please. There are technically correct nitpicks with some merit and there are trivial remarks like yours. It is perfectly clear what "pointer-free" was referring to in the post title.

akoboldfrying 3y ago
It's a legitimate criticism. The claimed benefit of "vector processing is faster than pointer chasing" will materialise only when the most common access pattern is to read or write all node values, since in that case the accessed values are contiguous -- but that's a consequence of the data structure being a struct-of-arrays (instead of the more common array-of-structs), which is wholly independent of the pointers-or-indices question. For any of the (very common) other access patterns, like a preorder traversal, "index-chasing" needs to happen, and that will be exactly as bad as pointer-chasing would be if the entire memory block had been reserved ahead of time in the same way. The only real advantages of indices over pointers are serialisability and ease of debugging.
kitd 3y ago
Is it? Please tell me because I had the same question. From the programmer's PoV, having no pointers gives little to no benefit. From the CPU's PoV, (in c/c++) indices become pointers anyway. Maybe the compiler can optimise more easily, but that's not obvious. Cache coherence is the key goal, but you can do that with pointers easily enough.
- another2another 3y ago
  I haven't looked at the code, but my guess would be that the whole data structure lives in a single chunk of RAM, and the tree is described as offsets to a base address (so probably more compact than with embedded pointers). Of course reading the values at each offset will require constructing a pointer address, but if the whole chunk can fit in the L2 data cache then reading those values at the calculated address will be very fast since the whole data structure is in cache. The aim isn't a compiler optimization, but a runtime on CPU core optimization.

Oh, please. There are technically correct nitpicks with some merit and there are trivial remarks like yours. It is perfectly clear what "pointer-free" was referring to in the post title.

akoboldfrying 3y ago

It's a legitimate criticism. The claimed benefit of "vector processing is faster than pointer chasing" will materialise only when the most common access pattern is to read or write all node values, since in that case the accessed values are contiguous -- but that's a consequence of the data structure being a struct-of-arrays (instead of the more common array-of-structs), which is wholly independent of the pointers-or-indices question. For any of the (very common) other access patterns, like a preorder traversal, "index-chasing" needs to happen, and that will be exactly as bad as pointer-chasing would be if the entire memory block had been reserved ahead of time in the same way. The only real advantages of indices over pointers are serialisability and ease of debugging.

kitd 3y ago

Is it? Please tell me because I had the same question. From the programmer's PoV, having no pointers gives little to no benefit. From the CPU's PoV, (in c/c++) indices become pointers anyway. Maybe the compiler can optimise more easily, but that's not obvious. Cache coherence is the key goal, but you can do that with pointers easily enough.

another2another 3y ago
I haven't looked at the code, but my guess would be that the whole data structure lives in a single chunk of RAM, and the tree is described as offsets to a base address (so probably more compact than with embedded pointers). Of course reading the values at each offset will require constructing a pointer address, but if the whole chunk can fit in the L2 data cache then reading those values at the calculated address will be very fast since the whole data structure is in cache. The aim isn't a compiler optimization, but a runtime on CPU core optimization.