4 ms·

Moving away from pointers and using a shared pool of handles with integer indexes will introduce a whole new array of issues. A plain int carries no information

Moving away from pointers and using a shared pool of handles with integer indexes will introduce a whole new array of issues. A plain int carries no information about the validity of the object behind that handle because they are carried around as copies, not references. I remember debugging a regression with UNIX network sockets where valid connections were being killed, and the bug was only triggered under heavy load. Deadlines were approaching and as a desperate measure I did the exact opposite the article suggests: 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. The culprit was a double-close that normal debugging tools such as Valgrind could not find but my unorthodox refactoring did. Later I've learnt to love UUID's whenever performance allows. They're not pointers so they don't introduce memory handling issues and they can be easily tracked in e.g. distributed data pipelines and logging systems.

throwaway894345 6y ago
> 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.
- bluetomcat 6y ago
  In C world yes, in C++ world no, because of weak_ptr.
  - asdfasgasdgasdg 6y ago
    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.
    - codr7 6y ago
      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.
      - asdfasgasdgasdg 6y ago
        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.
      - benibela 6y ago
        >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
        asdfasgasdgasdg 6y ago
        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.
        benibela 6y ago
        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
edflsafoiewq 6y ago
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.
bluetomcat 6y ago
> 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?
- rightbyte 6y ago
  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.
  - bluetomcat 6y ago
    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.
  - wtetzner 6y ago
    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.
    - TeMPOraL 6y ago
      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.
magicalhippo 6y ago
> 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: [...]"
AnIdiotOnTheNet 6y ago
> 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.
- bluetomcat 6y ago
  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.
- kazinator 6y ago
  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.
  - andolanra 6y ago
    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.
    - deleted 6y ago
      [deleted]
coldtea 6y ago
>A plain int carries no information about the validity of the object So, just like a pointer then?
kazinator 6y ago
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.

throwaway894345 6y ago

> 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.

bluetomcat 6y ago
In C world yes, in C++ world no, because of weak_ptr.
- asdfasgasdgasdg 6y ago
  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.
  - codr7 6y ago
    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.
    - asdfasgasdgasdg 6y ago
      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.
    - benibela 6y ago
      >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
      - asdfasgasdgasdg 6y ago
        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.
        benibela 6y ago
        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

edflsafoiewq 6y ago

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.

bluetomcat 6y ago

> 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?

rightbyte 6y ago
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.
- bluetomcat 6y ago
  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.
- wtetzner 6y ago
  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.
  - TeMPOraL 6y ago
    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.

magicalhippo 6y ago

> 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: [...]"

AnIdiotOnTheNet 6y ago

> 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.

bluetomcat 6y ago
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.
kazinator 6y ago
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.
- andolanra 6y ago
  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.
  - deleted 6y ago
    [deleted]

coldtea 6y ago

>A plain int carries no information about the validity of the object So, just like a pointer then?

kazinator 6y ago

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.