You do have to take care of the ABA problem - if you access memory using an index that became invalid before and another object is using instead, you will have some weird hard-to-debug logic errors (worse than use-after-free, since even Valgrind can't save you). To prevent this you need another generational counter to store along with your id (which is either incremented for every usage or assigned a random hash)

▲

adrian_b 5 days ago | parent [-]

This matters only for shared data structures. It is irrelevant for thread-local data.

For shared data structures, you have more to worry about, so regardless if you use indices or pointers you must use either atomic operations or means to ensure exclusive access to the entire data structure or means to detect the need for retries when using optimistic accesses.

▲

kazinator 5 days ago | parent [-]

Well, solving/mitigating the ABA ambiguity can debug use-after-free errors in single-threaded programs also. Because when a pointer A is freed to B, and then recycled again for a new object, we can make it into a different pointer A' (e.g. with a tagging scheme). So then when the old A pointer copies are lingering around, we can tell they are invalid due to having the wrong tag.

Solving ABA is probably a point in favor of indices (if we are working in a higher level language) because their type supports the bit operations for tagging. However, some hardware has support for hardware tagging for pointers. E.g. ARM; Android uses it.

▲

adrian_b 5 days ago | parent [-]

With indices what you say can be implemented trivially, much simpler than with pointers, by always incrementing a reallocated index (i.e. an index extracted from the free list) with the array size and always addressing the array with the indices modulo the array size.

With the array size chosen to be a power of two, this adds negligible overhead in time and no overhead in space.

▲

duped 5 days ago | parent [-]

That's equivalent to packing two counters into one.

	▲	adrian_b 5 days ago \| parent [-]
		True.