1. 46
  1. 12

    This is all good stuff, I can also recommend decoupling handles and storage entirely. Instead of putting the underlying array index in the bottom n bits, you add a hashtable from handle to index.

    The big advantage is that you can tightly pack your data. When you delete an item you swap it with the last element in the array and update the hashtable. Now if you want to perform an operation on every item you just blast over the array. It’s also simpler to expose iteration to the rest of the codebase like this, non-trivial iterators are a pain in C++ and it’s a one liner to hand out a span.

    It also lets you generate handles from outside the system. For example, you can hash asset filenames and use those as handles, then you can pass the handles between the client and server for picking entity models etc and it just works, even better if you add a constexpr hash function :)

    As an aside: people do this in rust too, where it has the additional benefit of hiding your allocations from the borrow checker and amusingly leaves you with the same safety guarantees as rewriting in C++

    1. 5

      Instead of putting the underlying array index in the bottom n bits, you add a hashtable from handle to index.

      The main disadvantage to this is you then need a hashtable lookup for everything, and so you now have two levels of indirection to go through for each access instead of one. The tight packing is not necessarily needed if your data is still mostly-dense, it can be almost as fast to iterate through a hole-y array and skip over the unused entries. It’s a nice tradeoff sometimes, but it is a tradeoff.

      This pattern IS very useful in Rust, its used commonly in gamedev/entity component systems. It’s also nice for stuff like interning strings though. In general I view it as a weird cousin to reference counting; a RC’d pointer is always valid to dereference and you do the safety accounting when you create/destroy pointers, a handle is possibly-invalid and needs no special actions to copy, but you check whether it’s safe when you access it.

      1. 4

        If you’re brave enough you can replace the hash table with a billion element array for a direct lookup from handles to object pointers. The trick is that, thanks to virtual memory, you don’t really consume much physical memory.

        Better have a 64-bit build and small pages though :)

        1. 2

          That link is worth its own submission!

        2. 2

          I did not fully understand the handles.

          is that just a hashmap of

            <unsigned int,T*>

          where ‘the outside’ world uses the ‘key’ of the hash (the unsigned int) in my example ? Or is it something else?

          1. 3

            You got it!

            1. 2

              Not quite.

              It’s more a handle is a uint32_t that is composed of (at least) two bitfields.

              If you have an array to store N items, then you need the B = ciel(log2(N)) bits to store an index into that array.

              So that means you have 32 - B bits to play around and do (other) useful stuff.

              When you want access that element, you have to mask off the high bits and then you have a plain old array index.

              Which you can sanity check against the size of the array.

              So what nifty stuff can you do with those free bits?

              Well a standard problem is use after free.

              You allocate a resource, you free a resource, you still holding a pointer / handle, you forget you have freed the resource, you use it again….. Horrible things happen.

              So you could use the free bits to create a unique id modulo 2^(32-B) that you store in the array and stamp onto the handle.

              When anybody asks for anything to happen with that handle… you check they match and scream if they don’t.

              What you do with those extra bits is up to your imagination…

          2. 4

            I like this technique, I just find it hard to apply to the kind of code I work on, which heavily uses variable-size objects like strings/vectors/maps.

            One way to adapt it is to drop down to byte granularity, so the handles are byte (or word) offsets, not array-of-struct indexes. But obviously you lose a lot of the benefits, especially the easy reuse of array elements — you either end up with a write-once arena, or have to reimplement malloc inside your mini-heap. The biggest remaining benefits are locality of reference and small handles. (I just used this technique last week to implement a string table I know is limited to < 64kb.)

            The article also set off some alarm bells related to concurrency — that “pointers are only valid for a brief period” stuff is a bit hand-wavey and falls apart completely with multi-threading. It actually reminds me of Handles in the old Mac OS (1–9), which were pointers-to-pointers. A derefed Handle would only remain valid until the next call that allocated memory, since the allocator sometimes had to relocate blocks. This was the source of many, many, many troublesome bugs, even in a single-threaded OS.

            1. 2

              One way to adapt it is to drop down to byte granularity, so the handles are byte (or word) offsets, not array-of-struct indexes.

              I think one of the examples (https://github.com/floooh/sokol#sokol_gfxh) does something like this.

            2. 4

              I’ve used this pattern in various places, but as the article said in the update section, you still have “use-after-free” and memory overflow issues, but it just went into different places. If you want to avoid them, you have to implement your own scheme. For example, if you have:

              struct Object {
                int internalArray[100];

              The memory overflow issue can still be:

              objPool[handle].internalArray[102] = 10;

              This will override object at handle + 1.

              The biggest problem to me: your own “handle” scheme cannot incorporate as smoothly to other great tools such as address sanitizers / valgrind (valgrind actually has some hook point to help). And that means unlike usual use-after-free / memory overflow, you cannot discover them with these tools and have to rely on your own.

              1. 1

                I suppose this was to be handled by wrappers that would check the boundaries (maybe with an assert) while adding an element?

                1. 1

                  Depends on what is your wrapper. Your “handle” wrapper can only check boundaries for the objPool array. So the out-of-bound access to internalArray won’t be checked. OTOH, this is well-solved by address sanitizer because the whole struct Object will be surrounded by poison region and such access will trigger runtime error. However, if you allocate them as continuous region, address sanitizer magic won’t happen.

              2. 4

                6 bits for a salt is extremely risky for many workloads that reuse resources. In lock-free programming, 16 bits is sometimes considered a safe-ish choice, but even that may be insufficient depending on the churn of the objects. In high concurrency situations, having a monotonic salt wrap after 64k (16 bits, 6 bits is only 64 and extremely high risk) reuses may lead to use after free issues at extremely high rates. In situations like this, you often benefit from using a combination of immutable resources, epoch based reclamation to prevent use after free and resource reuse before any witnessing threads have completed their operations, and atomic mutation with 16+ bit salts anywhere that EBR can’t be used to avoid ABA.

                1. 2

                  This article is better thought of as a recipe book for a family of solutions rather than a single (superset) solution. Pointers are the best option in some situations. Reread OP until you understand what they are. In the process you’ll also acquire facility in reasoning about when to allocate arrays of objects, operate on indices into the array and maintain additional metadata for memory safety.

                  1. 1

                    I like how malloc() can give you an immutable pointer with associated memory and how it integrates well with stack-allocated memory objects:

                    If the teidious case of string handling, let’s say a getline() loop can fill some struct my_thing for every line :

                    struct my_thing {
                        char *name;
                        char *payload;
                        struct my_thing *next;
                        char buf[];
                    struct my_thing *think = calloc(1, sizeof *my_thing + strlen(line) + 1);
                    memcpy(thing->buf, line, strlen(line));
                    thing->payload = thing->buf;
                    thing->name = strsep(&thing->payload, " \t");
                    thing->next = head;
                    head = thing;

                    So the same malloc() can be used for both the “big buffer” of the structure (of any size you like) and for the linked list.

                    P.S.: I would deduplicate the strlen(line) and check errors for real code though.

                    1. 2

                      This way to use malloc makes me much less sad to make use of it. The buffer size cannot be changed through the life of the program though.

                      I still prefer to use stack allocated structures though, but for string parsing or arbitrary structures, using the stack only is hard!

                      [EDIT: reading further on: having arrays of items of the same type with handles to manage them feels much like something different from both malloc buffers and heap buffers. tool_to_my_belt++

                    2. 1

                      It was a pleasant set of articles to read!

                      I may have a kink for .h only libraries like I saw on the author code bases (static inline… I am still using .c/.h for now though.

                      1. 1

                        In C++ I’ve really enjoyed using entt (https://github.com/skypjack/entt) for managing handle data structures, specifically as an entity-component-system. It implements something similar to the “generations” idea for tracking handle deletions I believe.

                        Stories with similar links:

                        1. Handles are the better pointers via vfoley 1 year ago | 19 points | 5 comments
                        2. Handles are the better pointers via iv 4 years ago | 12 points | 5 comments