Thoughts about Memory Management on Bare Metal, pt. 1

Static hashing and hashmaps

A hashmap is a really neat data structure: it's an associative array where input keys are used to look up locations in memory easily. These keys are put through a hashing function, transforming them into a hash index or hash code, and this hash will point to where the memory is stored in the corresponding target array. Since with fixed-width input data hashing will 'always' take the same amount of operations, most hashmap designs will feature amortised constant O(1) access, though in practice this isn't really the case.

Since a typical hashmap will not run in an environment where each possible key has a unique location corresponding to it, some kind of hash colision mitigation is unavoidable (thus the average hashing process is not an injective operation), and since allocating the entire space is also frequently uneconomic reallocation can end up being necessary at many points (and, remember, reallocation and dynamic memory stuff is undesirable in bare metal).

The issue here is that we aren't really allowed to grow and shrink at will, and should aim to take up as much memory as possible; that is, the initial storage allocation should aim to give the subsystem the maximum amount of memory it would need during its whole runtime. This becomes the memory ceiling of the datastructure. The hashmap, then, would either have to be statically allocated in the flash binary, or will have to be malloc()'d at startup and never freed.

This still leaves the question of colisions open.

Let's add more context. As I mentioned before, I started thinking about all of these things in the context of developing a BASIC-like running on the ESP32, and so some structures and requirements tend to emerge spontaneously without me having to do much deciding. In a typical BASIC, variables are stored onto a stack or on a table and then every time they're referenced the interpreter trawls this structure (O(n) as a function of table size) to find the variable, and if it's not present it pushes it onto the structure (e.g. in Microsoft BASIC for the 6502 you can use variables without declaring them, which automatically implicitly declares them there). This trawl is repeated every time a variable is referenced, absolutely nuking performance. It's not like it's much of a space-saving thing, either: MS-BASIC used a weird 5-byte format for floating point data (fine), as well as integers (what) that were treated as 16-bit numbers (what?) with 24 padding bits (what!?), plus two bytes for the name, meaning that each variable took up seven bytes of space.

Arrays, as far as I know, need 4+2n bytes of bookkeeping on top of their actual memory footprint: 1 for the name, 2 for the address, 1 for the number of dimensions, and 2n for the length of the dimensions for n dimensions [6] give or take. As you'll probably recognise, arrays go onto the heap of the BASIC, but it's important to note that once you DIM/declare an array, it can't be deallocated or resized (for details, see here), which is a recurring theme in the low-power space. More modern BASICs like the beautiful QB64 allow resizing and reallocating arrays as enabled by running on top of a fat OS that can handle moving a lot of memory around for them [7] without having to think too much about it themselves.

While for arrays this trawl is pretty 'cheap' (it's still O(n) but with n ≤ 255), for variables it can get nasty pretty quick (realistically you can input up to 26*36 = 936 variables, but the interpreter can be reading bytecode that would use 'syntactically inappropriate' variable names going into thousands of combinations; a theoretical maximum of around 4000 variables based on memory constraints is an example of such a large number). This is a big performance sink, but solutions to the problem are tough to come up with. I believe that a statically allocated hashmap is in fact a solution to this.

Simply using a 16-bit key, it's possible to effortlessly index into a 64K table without any further adjustments. This would mean that a 2-character name would just point to the address in the code table without requiring any bookkeeping; this would be an example of a 'perfect hashing table'. My first musings, thus, involved using 2 CJK characters as possible variable names. Encoded as UTF-16 and then somewhat adjusted, this means that both are ∈ [0x0000, 0x6bff] which, when concatenated together, produces a ~30-bit key, which would somehow have to be mapped onto a 64K table in some way; every single possible key would have to compete with ~16K other keys for its slot in the table.

The naïve way to resolve this would be to add the top and bottom hanzi together. This is awful, because it'll make a lot of small collisions easy: let's say that we name one variable 女王 ('queen', 0x5973'738B - the sum of the two hanzi is 0xCCFE); it will immediately collide with 王女 ('princess', 0x738B'0x5973). This extends to all anagrams, of which there is a large amount in e.g. Japanese (本日 'today' vs. 日本 'Japan' is another neat example). While it's tempting to tell the user to Never Ever use anagram variable names, I felt that I needed to mitigate this in some way. So, addition is not a good hashing function.

What I did was use a hash prospector to find good 16-bit hashes and incorporate that into the thing. It spat out quite a few functions; what I settled on was the following:

// bias = 0.0049752954186705221
uint16_t hash1(uint16_t x)
{
    x ^= x >> 11;
    x *= 0x104bU;
    x ^= x >> 9;
    x *= 0xcd1bU;
    x ^= x >> 7;
    x *= 0x42a5U;
    x ^= x >> 11;
    x *= 0x258dU;
    x ^= x >> 9;
    return x;
}

// bias = 0.0046809801814303642
uint16_t hash2(uint16_t x)
{
    x ^= x >> 7;
    x *= 0xb257U;
    x ^= x >> 9;
    x *= 0x8829U;
    x ^= x >> 4;
    x *= 0x0af7U;
    x ^= x >> 12;
    x *= 0x504dU;
    x ^= x >> 6;
    return x;
}

Bias here represents how strongly correlated toggling a bit of input is with specific bits of output (low hash, meaning less correlation, is good). These two are chained together, operating on separate halves of the variable name; a simplified code example:

uint16_t hash(uint32_t input)
{
        uint16_t a, b, c;
        a = hash1(input & 0xff'ff);
        b = hash2(input >> 16);
        c = hash1(a ^ b);

        return c;
}

This provides surprisingly decent hash performance. Using a collision measurement script I wrote, I found that for a table of size n, there is on average fewer than n/2 collision events, and that around half of that is a single collision; iteratively adding mitigations shows that after around 50% population, the hash table starts getting more and more collisions, and that beyond around 80% population, the table practically becomes unusable performance-wise; insertion changes from O(1) in a theoretically optimal table to O(n) in a static one. Average-case performance is still pretty good, but worst-case performance isn't good at all. Still, this beats iterating through a table of variables to extract the named one.

To mitigate collisions during insertion, I simply opted for the following simple algorithm:

1. If there is no collision, insert; stop.

2. If there is a collision, rehash c once. If there is no collision, insert; stop.

3. If there is still a collision, increment c = c+1. If there is no collision, insert; stop.

4. If there is still a collision, go to #3

In pseudocode:

bool hash_insert(uint32_t input)
{
        uint16_t a, b, c;
        a = hash1(input & 0xff'ff);
        b = hash2(input >> 16);
        c = hash1(a ^ b);

        if(!collides(c))
        {
                insert_at(c);
                return true;
        }
        else
        {
                c = hash2(c);
                if(!collides(c))
                {
                        insert_at(c);
                        return true;
                }
                else
                {
                        for(int i = 0; i < SIZE; i++)
                        {
                                c = c + 1;

                                if(!collides(c))
                                {
                                        insert_at(c);
                                        return true;
                                }
                        }
                        return false;
                }
        }
}

Of course, c should not be allowed to hit the map out of bounds, but otherwise it's a surprisingly simple principle.

Unfortunately, because we mitigate collisions in this way, a table of names must be maintained separately from the data map, so that indexing into the table will tell us if mitigations were applied or not, so we know whether we've found the variable we want or if it's in another castle ​ in a different memory location. This means the table should have a structure like:

struct entry_t
{
        uint32_t name;          // 4
        uint32_t data;          // +4
};

static entry_t name_table[1024];

The astute reader will notice that this is one byte more than the MS-BASIC variable table, without the performance hit of having to loop through an array to find what we want every time a variable is ever used. Such a table would eat 8K of memory for 1K variables (totalling 4K data) with longer names (four ASCII characters, or 2 CJK characters). It feels a bit like defeat having to still store the name in the thing, but it's essential to disambiguating between two identically hashed names; basically, we're using the name as a way to gauge whether the accessor should do a mitigation or not, without wasting too much space and still preserving some onomastics. As the names are stored as one integer made from concatenated characters, checking whether it's the right name is a simple single-instruction comparsion, and we're avoiding complex string routines that would basically be obligatory with a longer variable name. Checking whether anything's been allocated is also pretty easy: since we know names won't have the highest bit set (remember, we have a ~30-bit key), simply setting the name to 0xffff'ffff ensures that it's easy to check for whether a 'spot' is taken by simply doing if(int32_t(name) < 0) { /* ... */ } without having to worry much. Using a larger table than 1024 is likewise pretty easy to a point: at 16K entries, the table reaches 128K of memory use, which is near our upper static allocation limit and should be avoided.

Slabs and pools

I haven't really dug deep into slab and pooling because we really don't have too much memory to work with in general, so doing stuff in this space would not be quite as efficient as it could be if we had more memory to manage. Generally speaking, slab allocation is most effective when you have an OS that manages memory tightly. Since spinning up and destroying pages can be costly, and finding free memory can sometimes be a chore, the kernel instead allocates a bunch of chunks that can fit a certain object type, and then hands that memory out when requested and reclaims it when freed, all by adjusting a bookkeeping structure that shows which parts of slabs are free to use and which occupied. Freeing and allocating memory in this case is an illusion: it means just rewriting the appropriate part of the bookkeeping table. When something is 'destroyed' or reclaimed in a slab allocator, the object structure is kept cached, so that when another instance is requested there is no set-up involved and the cached object can be returned basically intact. The objects are usually also constructed ahead of time and in one go.

Memory pooling is a similar concept, where a large swath of memory is preallocated and then divided up by a pool allocator. There's bookkeeping and all that jazz, but what separates it from a slab (though neither is really extremely well-defined) is that there are no premade objects in pools, and they can store heterogenous data. It's basically a microcosmos of memory management.

Memory pooling could perhaps work here, but in a way the idea of a memory pool is superfluous because there's no real OS for us to request a lot of memory from and then subdivide it to avoid the overhead because we're that OS and we have to manage the memory we have in this manner anyway. That is, all our memory is in memory pools to begin with. Nobody's there to reclaim leaked memory.

The same principles apply, though: we want to keep a small bookkeeping structure that would indicate which parts of memory are free to use and which are taken.

As there's very little memory to go around, a very light bookkeeping structure would be not just optimal, but really necessary. This is balanced out by the need for space savings and very fine memory granularity. For example, we can assume that the smallest unit of memory that can be handed out like this would be 8 bytes; to keep track of every unit, a 64K memory space would need 8K locations keeping storage status. If we use a bitmap, this means the bookkeeping structure would only have an overhead of 1K (8 locations per byte for 8 bytes of space per location) plus anything on top (like a pointer to the structure and whatnot) that would add a handful of extra bytes. Computationally, this would suck to manage a bit, but if space savings were the main concern this would probably be the way to go. Less fine-grained memory allocation would in turn allow for more metadata in the bookkeeping structure while keeping to the same space concerns: if each space manages 16B of data, then 2 bits per location would allow for a total of 4 states to be stored per item, possibly facilitating things like access control; if each space manages 64B of data, then a full byte is available for this purpose.

Another bookkeeping approach would be to keep a table of what's been allocated, a pointer to it, and the length. Several other approaches (such as a linked list) also exist, and are, in my opinion, all better suited for more memory-rich platforms.

Naïve without dynamicity

Most of the stuff an embedded programme will need will be statically allocated ahead of time anyway. In this case, when I say naïve I mean that there's no magic behind the scenes and nothing is playing musical chairs with the memory. Everything is baked in at compilation time and no deviation is allowed. This is how most of the "important data" will live on the chip anyway. A screen buffer, for example, will be statically allocated as 75K or 150K of RAM with no manager, and resources like fonts or images or sprites or whatnot that would be statically burnt to flash are likewise going to just be this kind of memory: it's basically handling unmanaged, unscoped static memory with bare code-hands. There's nothing to talk about in terms of management here, strictly speaking.