4 ms·

An integer which references another data location is a pointer. This project only replaces system pointers with home grown pointers

8372049 3y ago
I think in this context, "pointer-free" is meant to imply (spatial) locality of reference, no additional memory allocations, address-independent and presumably memory safety (but I didn't read the code and may be wrong about the last one).
huhtenberg 3y ago
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.
nine_k 3y ago
It's not exactly so right on the hardware level. Many architectures, including the ubiquitous x64, have an ability to add a direct offset to a memory-access operation (like mov), or efficiently compute the address with an offset and element size (like lea). This removes an extra pointer deteference, which may be hugely expensive. With a cache-friendly structure like array, the one dereference you may need for the array access has a high chance to be served from L2 or L1, saving you a lot of clocks, because RAM has huge latency.
naasking 3y ago
This is typically referred to as a handle rather than a pointer. Handles can permit more flexibility than pointers.
nilamo 3y ago
> An integer which references another data location is a pointer. A more useful, storage/serializable friendly, pointer perhaps.

8372049 3y ago

I think in this context, "pointer-free" is meant to imply (spatial) locality of reference, no additional memory allocations, address-independent and presumably memory safety (but I didn't read the code and may be wrong about the last one).

huhtenberg 3y ago

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.

nine_k 3y ago

It's not exactly so right on the hardware level. Many architectures, including the ubiquitous x64, have an ability to add a direct offset to a memory-access operation (like mov), or efficiently compute the address with an offset and element size (like lea). This removes an extra pointer deteference, which may be hugely expensive. With a cache-friendly structure like array, the one dereference you may need for the array access has a high chance to be served from L2 or L1, saving you a lot of clocks, because RAM has huge latency.

naasking 3y ago

This is typically referred to as a handle rather than a pointer. Handles can permit more flexibility than pointers.

nilamo 3y ago

> An integer which references another data location is a pointer. A more useful, storage/serializable friendly, pointer perhaps.