That's basically what I've done at work on my embedded project.<p>Object pools, with indices and generations. Way, way easier than meddling with raw pointers, cheaper than shared_ptr/weak_ptr and no clean-up required when deleting stuff because the stored generation won't match the new object's generation. You can even make that default-constructible if you increment the generation on instantiation too (so that only even generations are alive) and hide it all behind high-level abstractions with C++.<p>Though my knowledge of these techniques come from 2000s video game architectures, as games like GTA: Vice City are known to use it.
This article reminds me (on the surface, this is deeper than my experience) of how the recent Goose language orients things.<p>I never worked with it but I seem to recall the old original Mac API's (Pascal based) used "handles" a lot to solve the issue of being able for the system to move allocations and memory out from under a program without it knowing, as a "pointer to pointer to <thing>". I was poring over those manuals in ~1988/1989 with visions of being a full-time Mac developer in my head.
Your memory is correct.<p>The early Macintoshes used the Motorola MC68000 CPU, which lacked an MMU. (Not sure if external MMUs were available then, but in any case Macs didn't have one). And the onboard memory was tiny even for the time (128_K_ for the smaller models).<p>So the memory management user API was designed to let the system move memory blocks around at will. "Resources" (discrete data blocks such as menu definitions, icons, even code segments, all with static content IIRC) could even be freed entirely, then reloaded from floppy disk when needed again.<p>To make this work, your code would lock a handle before dereferencing it into a pointer to the memory block, then unlock it when finished accessing it. As an application developer it didn't really feel like a burden or hassle, just another minor thing to remember, and it did the job.<p>I have my doubts as to how this approach would scale to the larger and more complex software of today, but it would be an interesting experiment.<p><a href="https://en.wikipedia.org/wiki/Classic_Mac_OS_memory_management" rel="nofollow">https://en.wikipedia.org/wiki/Classic_Mac_OS_memory_manageme...</a><p>EDIT: The Mac's memory API was a bit more complex than I remembered. But it was all part of being a Mac developer back then - <i>everything</i> on the Mac was new and different. For many of us, it felt like the future had arrived. (Maybe not so much the case for those coming from LISP machines and the like).<p><a href="https://archive.org/details/inside-macintosh-1992-1994/1992-memory/mode/2up" rel="nofollow">https://archive.org/details/inside-macintosh-1992-1994/1992-...</a>
My PhD thesis is on this topic, and I had an ASPLOS paper on handle based memory support in unmanaged languages (C/C++) through LLVM a few years ago: <a href="https://nickw.io/papers/asplos24-alaska.pdf" rel="nofollow">https://nickw.io/papers/asplos24-alaska.pdf</a><p>The overhead we saw there is suprisingly just from instruction and branch overhead from using software handles - I have ongoing work to do it in hardware and the overheads are <i>much</i> lower.
Note that the terminology in this article is somewhat non-standard. I usually think of a handle as a pointer-to-a-pointer: it adds another level of indirection so that memory allocator can move objects in memory without needing knowledge of all outstanding pointers. IIRC the classic Mac Toolbox (~1990) used them extensively, and that concept seems to be what your Ph.D thesis is about.<p>The objects discussed in this article would probably be better called "descriptors". They're very much analogous to file descriptors in UNIX: the API returns an integer index into a table, which contains the actual data being referenced. The memory address of the table or its members remains opaque to calling code, and there is no way to access outside the bounds of the table.
I made a real attempt to program this way in my C++ project (largely due to this article), and personally I found it extremely cumbersome because you have to carry the owner of this resource everywhere you want to use the handle. That itself can worsen the performance when it's in different functions, it made generic programming hard and such code has to be more template heavy, and it was difficult to refactor.<p>But this was a very low level project, and I suspect Floooh was probably thinking more of end-user applications.
Sounds like a misunderstanding/misusage? I'm thinking that the handles are to be opaque indicies, think typed variation of void pointers or filehandles in classic C api's. Thus, the handle is subsystem specific and it owns _all_ resources of a type, thus you're not meant to know or be able to send the "owner", it's merely a way to have a reference to something you use.
I’m not sure how applicable this is today. It is quite hard to beat jemalloc, especially for small allocations, which it handles essentially the same way a hand coded pool or arena would anyway.
If using 32bit handles, you save 4 bytes per reference compared to pointers. If your application uses a lot of references, this can add up (in total memory use).<p>I have a few applications with lots of tree structures, where this makes a meaningful difference.
I’ve worked on game engines and what he’s describing is still very common<p>I don’t know about outside that world though
Nice approach! I did something similar in my recent project (even if it was not C++). But I didin't bother handling overflow of generation counter, since for my purposes 32 bits were more than enough.
I remember back in the day in Windows C++ programming everything was a HANDLE memory is probably not serving me, but they were all really just void* renamed. And you use them with various win32 functions I guess to keep things straight. I don't miss those days.
> but they were all really just void* renamed<p>The good thing is that all of these can and have been quite neatly put into RAII[1] or some memory arena with custom deleters which use the Win32 functions. One <i>could</i> manually `delete` those handles, but there be dragons. Vulkan does something similar; everything is a VkSomething handle. They <i>may</i> just be pointers directly exposed by the driver, but even so, users are explicitly supposed to use vkDeleteSomething functions to delete them.<p>[1]: <a href="https://github.com/microsoft/wil" rel="nofollow">https://github.com/microsoft/wil</a>
Famously Win16 API required locking memory allocations to be able to access them by a pointer. Unlocked allocations could be moved by the OS.
A nice analysis of large-scale programming techniques that go beyond the novice version of "OO Sux" to the almost secret<p><a href="https://en.wikipedia.org/wiki/AoS_and_SoA" rel="nofollow">https://en.wikipedia.org/wiki/AoS_and_SoA</a><p>and why game engines use entity-component systems, analytical databases are column-oriented, etc. That is, the classical organization of "objects" as structures has a lot of overhead when you're doing heavy work. For instance java reifies objects with a big header, a monitor lock, and other stuff that really adds up if you, say, are writing a chess engine and need to maintain transposition tables. And even if you are in C++ and there is a lot less overhead, AoS still has bad mechanical sympathy compared to SoA.
my API always use handels, not because i design them that way, but in every iteration they get more and more handles
The most popular program of all time which used the concept of "Handles are the better pointers" -- is/was the Microsoft Windows series of operating systems (from a little company called Microsoft, in Seattle).<p>You have have heard of it (or them!)<p>You see, in that OS, individual windows (as GUI elements and "Operating System Objects") were not pointers, but <i>Handles!</i><p>Every other OS-controlled object (Bitmaps, Brushes, Fonts, Device Contexts, etc.) were also <i>Handles!</i><p>You see, Application Programmers (for normal applications, not Ring 0 device drivers) -- were <i>never</i> given direct pointer access to OS internal data structures!<p>Instead the OS handed out <i>Handles</i> for different OS-managed objects to application code that asked for them, allocated and managed the memory they used during their lifetime, and disposed of the memory so allocated when the application using them had completed or terminated.<p>Unix/Linux is similar -- except that the application programmer typically gets what's called a "File Handle" (because "everything's a file" under Unix/Linux...)<p>But generally speaking (and yes, there are exceptions like mmap() on Unix/Linux and ring-0 drivers on Windows) the application programmer never manages the memory allocation or disposal themselves, they never use direct pointers for these objects, they go through an OS proxy to that OS structure, that proxy is called a "handle", and it moves the proper responsibility for memory allocation/deallocation of the resource to the OS, away from the programmer.<p>Compare and contrast this with the use of handles (as proxies) and the concept of "Encapsulation" (from Object Oriented programming, but equally applicable here) in codebases where you have a central Senior developer who writes the central code in a language like C or C++, full of pointers, complex data structures, complex dynamic memory allocation/deallocation, etc., and you have regular developers who write code via the use of Handles around that central code, i.e., that central code does not expose pointers or direct memory -- instead it exposes an API or functions where regular programmers request handles, and subsequently pass the handles with additional API calls to the central codebase to gain functionality for whatever object or objects are represented by the handle.<p>(You can also compare this to obtaining a token/cookie from a web API, then passing that token/cookie on subsequent requests with different additional parameters to different endpoints on a single website's API to gain different functions related to the use of the back end object or objects that that token/cookie is related to...)<p>Also, I should point out that while replacing pointers with handles in code may make a programming a little bit slower, it also allows the handle allocation code to save/update a list of allocations. Hybrid code could replace pointer operations with handle allocation in a test/debug codebase, then replace it again with native pointer operations in a release codebase (faster, once all the bugs are worked out). A handle allocator is a powerful tool to check for memory allocation errors in code if it's programmed correctly... Allocate the same handle twice -- have your handle allocation code can check for that, and raise an immediate exception! Forget to free it at the end of use? Raise an exception for that! It's a great way to find bugs in pointer code!<p>Anyway, great article!<p>Related:<p><a href="https://en.wikipedia.org/wiki/Encapsulation_(computer_programming)" rel="nofollow">https://en.wikipedia.org/wiki/Encapsulation_(computer_progra...</a><p><a href="https://en.wikipedia.org/wiki/Pointer_(computer_programming)" rel="nofollow">https://en.wikipedia.org/wiki/Pointer_(computer_programming)</a>
Lovely long-form comment, a joy to read. The way you explain the concept of "handles" as an abstraction useful in a whole class of situations.<p>> Any problem in computer science can be solved with another level of indirection.<p><a href="https://en.wikipedia.org/wiki/Fundamental_theorem_of_software_engineering" rel="nofollow">https://en.wikipedia.org/wiki/Fundamental_theorem_of_softwar...</a><p>An entire operating system conceptualized as a hierarchy of handles.<p>- Windows, GUI elements, "OS objects"<p>- Bitmaps, Brushes, Fonts, Device Contexts<p>- File system namespace - Objects as file descriptors - <a href="https://en.wikipedia.org/wiki/Everything_is_a_file" rel="nofollow">https://en.wikipedia.org/wiki/Everything_is_a_file</a><p>- Memory handles to manage allocation and freeing without directly handling pointers<p>- APIs, token/cookie, authenticated requests - and functions<p>It's about encapsulation, and designing the <i>interface between objects</i>.<p>How handles are like functions, makes me think. A function is a form of indirection, and it can be seen as a handle or interface with defined types of inputs and outputs.<p>And the useful of handles/proxies in testing. Yes, it solves the same question as "dependency injection" but in a more functional style. You pass in a handle with well-defined types of vaues, which can be treated the same way by functions whether the handle operates with a local test database or the actual production one. It's being able to have multiple implementations, or instances, with the same interface.
>Lovely long-form comment, a joy to read. The way you explain the concept of "handles" as an abstraction useful in a whole class of situations.<p>Well thank you very much! I appreciate the kind sentiment!<p>> Any problem in computer science can be solved with another level of indirection.<p>Indeed! I forgot to include this part when writing, it was "at the tip of my consciousness" but I couldn't recall that exact text exactly, so I didn't include it -- but you nailed it!:<p>><a href="https://en.wikipedia.org/wiki/Fundamental_theorem_of_software_engineering" rel="nofollow">https://en.wikipedia.org/wiki/Fundamental_theorem_of_softwar...</a><p>>An entire operating system conceptualized as a hierarchy of handles.<p>It's quite the concept isn't it!<p>Incidentally, if you look at the Assembly compiler output of any "Object-Oriented" programming language (i.e., C++, ObjectPascal, etc.), you will notice that it is generating what looks like normal Assembly functions for non-Object-Oriented programming languages (C, Pascal, etc.), <i>except that</i> each function is getting passed an additional first parameter (typically as EAX on 32-bit x86 systems, RAX on 64-bit x86 systems), and that first parameter is actually a pointer to the "Object" in memory (pointer to a data structure that comprises the "Object" in memory -- since Assembler has no concept of higher-level programming language Objects!), but it's function is to allow a flat traditional function to operate on the data (and call associated related "object" functions (via another level of pointer indirection)) -- well, it's the same <i>principle</i> as a Handle (that of "Indirection": <a href="https://en.wikipedia.org/wiki/Indirection" rel="nofollow">https://en.wikipedia.org/wiki/Indirection</a>) in effect!<p>>It's about encapsulation, and designing the interface between objects.<p>Indeed!<p>>How handles are like functions, makes me think. A function is a form of indirection, and it can be seen as a handle or interface with defined types of inputs and outputs.<p>Exactly!<p>>And the useful of handles/proxies in testing. Yes, it solves the same question as "dependency injection" but in a more functional style.<p>You get "dependency injection" virtually for free!<p>>You pass in a handle with well-defined types of vaues, which can be treated the same way by functions whether the handle operates with a local test database or the actual production one. It's being able to have multiple implementations, or instances, with the same interface.<p>Yes! And (added bonus!) it <i>decouples</i> the handle using program (client) from the handle serving program (server!). That is, the code is not as strongly linked "bind/bound together" as code using raw pointers, and can be separated across boundaries (across processes on a single machine, across the internet on multiple machines) if the data is <i>marshalled</i> (fancy term for if the data of the variable which contains the integer value for the Handle is moved from point A to point B, wherever point A and B are, i.e., HTTP(S) request + JSON or XML or BSON or other structured data exchange format...)<p>Anyway, thank you again for your kind sentiments!
This sounds a lot like ECS—or at least, how ECS systems handle memory for the components.
They always have been, and Win32 extensively uses HANDLE with some underlying restrictions. I remember reading up that certain numeric allocation buckets in HANDLE corresponded to the type of underlying resource (ie. Nth bits mean <this resource>), but it has been too long to remember the details.
there are serious downsides to this, its a tradeoff and I wouldn't say they are "better pointers". There are definitely cases where it can work (e.g. uniform objects that either rapidly create/destroy or all die at a boundary). This is usually the case with a "simple memory model" domain like games, rendering, etc. All the work starts and ends at a request, frame, or scene.<p>But for anything else, handles can be trouble.<p>First, you're obviously paying indirection tax on EVERY lookup. Logic like `x->foo` becomes `memory_allocator.objects[x->index]->foo`. You're also paying the generation counter tax (assuming you want any kind of safety). So you also have to do something like this:<p><pre><code> if (x->index < 0 || x->index > memory_allocator.objects.size()) { // panic? }
auto *ref = memory_allocator.objects[x->index];
if (!ref) { // panic? }
if (ref->generation != x->generation) { /// panic? }
return *ref;
</code></pre>
Next, you have type bloat. Hopefully you are making type-safe versions of all these indices so you can't just use an aribtrary index into any kind of array right? Ok well that means now you have double the types (one index type per pointer type). Ok maybe not the worst, just a lot of boilerplate everywhere. Prepare for a lot of this:<p><pre><code> struct Handle { uint64_t index; uint64_t generation }
typedef PlayerHandle Handle;
</code></pre>
Handles are also a lot bigger. If you're memory constrained, adding an additional 16-32 bytes per pointer allocation is painful. For my programming lang I have a single test file that contains 300K AST nodes, that would be another 9.6MB to parse a single file for handles alone, for noticeably slower performance (300K+ indirections and cache misses).<p>Next, you have the issue of resizing your memory array. You now are in "write your own garbage collector" land. You want to consolidate 50% of the memory that is suddenly free? Well you need to change every index to point the new compacted range (expensive and complex), or manage a free list which potentially increases the memory requirement, and adds complexity, cache coherence issues, etc. Do your memory lists grow indefinitely? Do you need to think about having separate lists for short lived and long lived (generational GC style)? Managing lifespan of objects all sharing one backing storage when the indexes are just integers strewn about is actually _harder_ than doing the same with pointers (just use compacting GC already).<p>Then there's the issue of object pools. You want your data to live in arrays. Do you put all objects into one master array? You lose cache coherence / iteration speed, and type safety (unless you really bloat and start adding type info to every entry). If you use different arrays for each you might end up with dozens of arrays, one per type, and also their free lists. Now you need a way to manage the lifespans and scope of all these object pools. Suddenly, you've reinvented malloc / free and segfault signals.<p>Or you could just wisely use pointers...
> First, you're obviously paying indirection tax on EVERY lookup<p>It's not true for typical use-cases, when objects aren't processed one by one, but in bulk.<p>> Next, you have type bloat<p>What's the problem? Do you pay a special tax each time you need create a new type?<p>> Prepare for a lot of this<p>That's not how it's done in C++. You typically have a template for handle types, so that <i>PlayerHandle</i> is just <i>Handle<Player></i>.<p>> Handles are also a lot bigger.<p>The article mentions, that handles are typically smaller than pointers. A pointer is 8 bytes (on 64-bit machines), but handles can be smaller if not so many objects are needed to be created.<p>> Next, you have the issue of resizing your memory array.<p>There is only problematic to resize it down, which is almost never needed.<p>> dozens of arrays<p>> manage the lifespans and scope of all these object pools<p>It's not a problem. Each subsystem owns its arrays and destroys them only when the subsystem itself is destroyed.
Yes, there are ways to workaround / minimize these problems, but again, it mostly works for simple systems (like games). Sure, if you process everything "in bulk" so that you don't have complex lifespans and/or indirection, then it is easy. But if you already have everything "in bulk" and aren't worried about lifespans, and already freeing in bulk, why do you need handles again?<p>Same for other responses. Great, you can just implement a lifespan array in every subsystem. If your sub systems are very simple (e.g. single Entity component is the only thing you're allocating in a game, maybe Resource as well), then sure, its simple. Not sure what it's buying you, since you apparently are also freeing all entities and scene elements at once too. But for a complex system where there are many types of objects (dozens or hundreds), and where lifespans are complex (some short, some long), then having "every system implement its own pool" adds a lot of complexity. Then not only would you want type-safety with a Handle<Object> for every type of object, but also some kind of affinity for the sub-system which currently manages that lifespan (unless you just have a single Pool for every object type, which re-introduces the lifespan issues).<p>Again, other responses I'll lump into "sounds like for simple systems it isn't substantially more difficult than pointers". I guess if it has a meaningful performance tradeoff, then it might be worth it (where a simple free list or using system malloc would be too expensive).<p>If you say you don't need many objects, so counters can be small, and you never need to resize the handles array, so indexes are valid, and you don't have lots of object types, and don't have lots of subsystems, and lifespans are purely scoped to subsystem lifespans, and don't mind type bloat all over your interfaces, then it sounds like handles are a perfect fit. I'm trying to imagine what's so bad about using pointers in such a simple system, and what we're "solving" (e.g. just &memory_array[next_index++]).
[flagged]