Hacker News Reader

> A plain int carries no information about the validity of the object behind that handle because they are carried around as copies, not references.

A pointer is just an integer index to a byte in memory in most computing architectures.

A pointer is an absolute locator of a byte in the address space of a process, while an integer index implies a certain base (start of the module-private array) and a multiplier (object size).

By using handles, "user code" is freed from having to know the base and the multiplier, which allows for a more compact locator that remains constant in case of base/multiplier changes.

Ah, but that pointer doesn't get re-used on you until you free it, and for that there are strategies like refcounting and GC.

Integers in a small array will get re-used; they have to.

You should probably read the whole article, because it describes strategies for dealing with exactly this problem in the section under Memory safety considerations and then again in the update at the end. The short form is: if you have a bounded size on your array, then you will often have unused bits in your index pointer; you can use these to store a "generation counter", which needs to match the slot. You can now re-use indices, because you can compare the generation of the index (stored in the extra bits) with the generation count in the slot, and if they match, it means that the item has been 'freed' and a new thing is in the slot.

> A plain int carries no information about the validity of the object behind that handle because they are carried around as copies, not references.

The article suggests a handle containing a "plain int" plus a "unique bit pattern", the latter acting like a watermark which is compared to the one in the private array of the corresponding module, preventing dangling accesses.

Apart from rare occasional collisions in the bit pattern causing a false negative on a dangling access, what other issues can be found with this approach?

You are essentially passing an database index key to the getter-function. The only issue I see is that your system has a database integrated into it.

The translation of that key to a memory location should be very straightforward. A few bitwise operations to extract the necessary pieces from the handle, a multiplication of the index, an addition to the private base pointer and there you go. Nothing fancy or CPU-expensive.

I mean, calling it a database might be technically accurate, but is misleading in the sense the it gives the impression that it's a big heavyweight thing. It's not like there's a SQL implementation in there.

You jest, but SQLite run in-memory is a pretty fast database. I'm currently using it for ECS implementation in a little game I'm writing on the side (albeit in Common Lisp, and not yet very performance-heavy).

The reason I went this way is because when writing my third ECS with various access pattern optimizations, I realized I'm hand-implementing database indices - so I may as well plug SQLite for now, nail the interface, and refactor it into Array-of-Struct implementation with handles later.

That's probably not a bad way to think about it - in an application that large, dealing with lots of data, needing high performance, it is effectively an application-specific database.

On the other hand, think about the improved cache footprint from using 2-byte object handles rather than full-size 8-byte pointers. If the "user code" keeps a lot of those handles in sequential structs, that is a huge win.

Oh, sorry, I didn't mean to be disparaging. What I meant was that if the application needs to handle lots of in-memory data, then thinking of it as an in-memory database seems like a great idea. The ECS architecture seems to be pulling in ideas from column oriented databases, there are probably lots of ideas like that which could be repurposed. (Of course there is the other side of that, which is if you can avoid storing lots of data in-memory at all, possibly using an off-the-shelf relational database, then that's a great approach too.)

> A plain int carries no information about the validity of the object behind that handle because they are carried around as copies, not references.

All of this applies to pointers as well.

In C world yes, in C++ world no, because of weak_ptr.

Weak_ptr in C++ only applies to shared_ptr, which is not used for most C++ pointers. Because of the atomic ops done on each copy, in performance sensitive contexts people aren't going to be using it.

Been there, done that.

I was writing an interpreter using shared ptrs all over the place.

Performance was fine until I linked pthreads, at which point it took a nosedive forcing me to refactor the entire project.

No one really tells you this. People will say don't use shared ptrs because they're slow, which is far from the whole truth. They're pretty darn fast as long as you don't enable threading.

I would go a step farther and say that uncontended shared_ptrs are typically fine. The problem comes in when you have shared_ptrs that are frequently copied in more than one thread. That requires synchronizing the shared state across cores, sometimes across NUMA nodes. That's slow.

The same thing goes for mutexes. Modern, uncontended mutexes are very fast. But they can start sucking resources when you're locking them from multiple threads at the same time.

>I was writing an interpreter using shared ptrs all over the place.

I am doing that :/

In Object Pascal it is the standard memory management way. All strings and arrays are reference counted, and so I use it for all my own data structures as well

I have not even added threading and I doubt I will, but the reference counting is already the slowest part

Not sure what the alternative is

You can avoid reference counting overhead by using handles as described in this article. Each object in a slab would have just one reference, and you handles would be indexes into an array of them. Now, after you do that you will be on be hook for making sure you don't accidentally deallocate any of the objects that is currently in use. And it's not guaranteed to be faster. But it is one way to get around this issue.

I do not understand how this would help

It would still need reference counting on the handles to know when the handle is not used anymore and the element in the array can be reused

Without reusing handles it would surely run out of memory. Unless a full GC is used

Shared pointers also defer ownership decisions and lead to memory leaks via cycles which is its own very special level of hell.

> Later I've learnt to love UUID's whenever performance allows.

This is essentially the same as what the article suggests, just with a lot more spare bits for creating unique handles.

"This is where the ‘free bits’ in a handle come in: Let’s say our handles are 16-bits, but we only ever need 1024 items alive at the same time. Only 10 index bits are needed to address 1024 items, which leaves 6 bits free for something else.

If those 6 bits contain some sort of ‘unique pattern’, it’s possible to detect dangling accesses: [...]"

>A plain int carries no information about the validity of the object

So, just like a pointer then?

The problem isn't with the integer indices being by-value, but rather that they are subject to manual memory management. A descriptor can be closed and then replaced by a different object at the same integer value. (Or both can happen atomically with dup2.)

> "I wrapped all the socket calls to only accept pointers to an opaque struct with a single integer and made sure the int was set to a guardian value to indicate invalidation after an error."

This worked because after destroying the descriptor and storing the sentinel value, you didn't destroy the structure.

In production code, that would be a problem. You wouldn't want to leak these wrapper structures, so at some point they would have to be deleted.

And then you're back to the same problem: a structure containing a guardian int is freed while still in use, then the memory is re-allocated to some other purpose, and now the guardian checks are inappropriately testing memory they no longer own.

What works is garbage-collected handles: pointers to objects that wrap a manually-managed resource, but which themselves do not go away while they are referenced.

By the way, POSIX file descriptors could provide a sort of garbage-collected discipline, because they support reference counting. So that is to say, instead of passing around an integer descriptor, you can enforce that dup() must be used by anyone wanting to share the underlying object: everyone must share through their own integer descriptor, not by sharing the integer. Then if five objects or threads or whatever are sharing the same open file, they have five different integers. The object goes away when all five of those contexts separately issue a close on their integer. Nobody closes an integer that they got from somewhere else, always their own dup.

POSIX descriptors also lack the feature described in the article: tag bits. So that is to say, imagine a parallel universe with POSIX descriptors that are not simply non-negative integers clumped close to zero, but have two parts: the integer clumped close to zero, and some bits indicating a generation. For instance suppose descriptor 0x01FC means "generation 0, index 1FC". Then suppose you close(0x01FC) such that the 1FC slot is the lowest available position. Something opens a new descriptor. That results in 0x11FC, not 0x01FC. The generation has incremented. Now suppose a double close happens: another close(0x01FC). The kernel extracts the generation 0, and looks at object 1FC. It sees, hey that thing is generation 1! This is a stale handle! and returns an error.

floooh suggests handles not be plain ints, but also have some bits with a 'unique pattern' (eg. generation counter) for safety checks. This is one of the reasons given for handles being better than pointers.