←back to thread

Indices, not Pointers

(joegm.github.io)
102 points vitalnodo | 4 comments | 02 Sep 25 23:21 UTC | HN request time: 0.603s | source
Show context
10000truths ◴[03 Sep 25 01:55 UTC] No.45111473[source]▶
There are a couple other advantages that are unstated in the article, yet very important from a software design perspective:

1) Indices are a lot more portable across different environments than pointers. They can be serialized to disk and/or sent over the network, along with the data structure they refer to. Pointers can't even be shared between different processes, since they're local to an address space by design.

2) Indices enable relocation, but pointers restrict it. A struct that stores a pointer to itself cannot be trivially moved/copied, but a struct containing an integer offset into itself can. A live pointer to an object pool element prevents the object pool from being safely moved around in memory, but an index into the object pool does not impose such restriction.

replies(3): >>45112164 #>>45112905 #>>45114542 #
1. cma ◴[03 Sep 25 04:04 UTC] No.45112164[source]▶
Data memory-dependent prefetchers like in Apple's newer chips I think only work with full pointers and not offsets, so it could be a decent perf hit.
replies(3): >>45112323 #>>45112400 #>>45113187 #
2. astrange ◴[03 Sep 25 04:44 UTC] No.45112323[source]▶
Indices can be much smaller than pointers (which are 8 bytes), so they have plenty of cache advantages of their own which can make up for that.
3. ◴[03 Sep 25 05:05 UTC] No.45112400[source]▶
4. whstl ◴[03 Sep 25 07:32 UTC] No.45113187[source]▶
Still depends. If the indices are pointing to a dense, flat, contiguous array, it will still be faster than following pointers into scattered heap allocations, with or without prefetching, because of how CPU caching works.