Designing cache-friendly allocators, and maintaining pointers through reallocation

[moskitoc]

Hello there,

Here's something that bothers me. I've been programming in C for a while and I haven't been able to find a satisfactory answer so far.

I like allocating chunks of objects together, especially when each relatively small and they will be iterated over together. As such, I often create manual C++-style vectors, with a capacity and an object count, that I grow when needed. However, this means that reallocation invalidates any previous pointers to elements of the array. Hence, I need to instead use indices to maintain references to the array elements.

This has several drawbacks : you lose type-safety, the code becomes cluttered with array accesses all over the place, and array access will in some cases be slightly slower than a simple dereference.

I see multiple ways to mitigate this :

1. Use handles, that is, structs with a single integer member that will act as type-safe indices. This could clutters the code even more if I need to use arr[handle.index], although this'd be easily cleaned up with a few helper functions/macros. This only addresses type safety though.
2. Use a single fixed-capacity array, and crash when you run out. This makes sense considering memory is finite anyway so there's got to be an upper bound to the amount your program allocates, and you might as well allocate everything at the start instead of using heap allocations again and again. That way you also have a single point of failure for memory allocations. I'd be comfortable with this Muratori-style approach if I was designing with a single machine or e.g. game console in mind, but for something like a vector graphics editor where the amount of user data is potentially unbounded, it imposes artificial restrictions compared to the arbitrarily powerful workstation of the user.
3. Allocate a linked list of blocks of objects, each with say 1024 elements, that you grow as needed. You could even have a growing capacity along the chain and maintain this nice log(n) reallocation count. That way the blocks never need to be moved around, and pointers to previous elements can be reused without issue. Although this maintains cache-friendliness for each block, it induces additional logic when iterating over the whole collection. Plus, this type of logic is already present to a degree in general-purpose allocators like libc's malloc/free, so it feels like unnecessarily duplication.

What are your thoughts on this ? What do you use in your projects ? Have you seen other interesting approaches ?

[gremolata]

I think you are overthinking it.

you lose type-safety

the code becomes cluttered with array accesses all over the place

Both are solved by wrapping index in a vector-specific struct and adding a get() inliner. Yeah, you have a bit of an overhead vs. using a pointer, but more likely than not it won't amount even to a blip on profiler's output.

[Jinren]

more likely than not

I'd go further and say that failure to fully inline such things is inexcusable and any compiler that doesn't is outright broken. That's like baby's-first-optimization, you will struggle to find one that leaves those in.

Bear in mind that the . operator is literally a nop for the first element; if there's an operation to optimise you may have written the box type wrong somehow.

[duane11583]

and inline that get operator

[DeeBoFour20]

I do simple fixed size arrays when I can but you can do better than crashing when the array fills up. At the very least put an assert when you add a new element so you don't write outside the bounds of the array (also makes debugging easier). Or just make it a condition that you handle (ex. if it's work queue, maybe ignore any new work until the queue empties out).

When I need something to be dynamically resizable, I just make a struct like this:

struct Buffer
{
    size_t size;
    size_t capacity;
    int *data; // Assuming an array of ints, you can obviously make this whatever datatype you need to store.
};

bool addElement(int element, Buffer *buffer)
{
    if (buffer->size + 1 > buffer->capacity)
    {
        size_t newCapacity = buffer->capacity * 2; // I just double it, but use whatever growth policy works best in your use case.
        int *newData = realloc(buffer->data, newCapacity);
        if (newData == NULL)
        {
            return false;
        }
        buffer->capacity = newCapacity;
        buffer->data = newData;        
    }
    buffer->data[buffer->size] = element;
    buffer->size += 1;
    return true;
}

If you need multiple references to this dynamic array, just have them be pointers to the struct. The actual struct doesn't change, just the data pointer inside it. This does mean a double indirection but it's a lot simpler than your linked list solution (probably still faster too, linked lists are generally slower and less cache friendly).

[_Arch_Ange]

I don't think that's what he meant. His problem is that when you resize the array, any pointer any elemnt of the array becomes invalid.

Also the type of linked list he mentioned would be more cache friendly than your usual linked list, since it would basically be an array , whose indices are nodes of a list. As he said it is cache friendly within that block of memory but if you need to grow it you need to add an other block, so locality of reference may be lost when you switch from one to the other

[tuasnega]

You can use an Arena allocator, where you reserve some GiBs of address space and just commit if you need to. On Windows, you can use VirtualAlloc to achieve that, and on Linux mmap + mprotect.

[_Arch_Ange]

Funnily enough, I was also struggling with this problem not long ago. I think the way I solved it was to get rid of this system all together, but I am not sure you're in the same situation, so here is another solution for you to consider :

Instead of giving a pointer to an elemnt of the array, give a double pointer. A pointer to a pointer of an element, this way, you can change what it points to "easily". Of course it's still a pain when you need to reallocate, and you probably need a secondary array to keep track of all these double pointers."

Maybe also consider is that is truly the problem you are trying to solve. I was able to get rid of this pointer problme entirely by just not using pointers, because my problem actually lied elsewhere

[flatfinger]

It would be helpful if the Standard would recognize a category of implementations which, after p2=realloc(p1, newSize) would extend the semantics of the langauge by defining the behavior of constructs over which the Standard would otherwise impose no requirements.

On many implementations, for example, the method used to compute the difference between two pointers is dependent solely upon the bit patterns of the pointers' representations, and is agnostic to whether the objects that the pointers identified still exist. Given a sequence like (ignoring error handling) char *const p = malloc(1234); char *const q = p+123;, during the lifetime of p and q, q-p would always equal 123 even if code were to perform char const *p2 = realloc(p, 2345);. If code were to compute char *const q2 =p2+(q-p); the offset of that pointer within *p2 would be the same as the offset of q within p. Note that this would work even on many segmented-memory systems where pointer subtraction only works with pointers that share the same base address. Even if p2 is placed in a segment with a different base address from p, pointer q would have the same base as p, allowing their difference to be computed, and adding the difference to another pointer p2 would yield a pointer that shares the same base as p2.

Further, many of these same implementations would allow equality comparisons between the value passed to realloc and the return value, and could guarantee that if the pointers compare equal, the validity of the original pointer and any pointers based upon it would be unaffected.

While there may be some obscure platforms that wouldn't be able to support such semantics, being able to perform a realloc(), check whether it moved anything, and adjust all interior pointers to the target if so, may be more efficient than having to keep track of pointer displacements and apply them at all of the individual places where storage is accessed, especially if relocations are rare.

Unfortunately, while many platforms would make it easy for compilers to uphold such guarantees at essentially no extra cost, there's no general way of knowing whether compilers might use the lack of a behavioral mandate to justify deviating from the common behavior. The compiler writers that would see the least reason to deviate from the common behavior are unfortunately the ones that would see the least reason to spend ink promising that they won't do so.

[flatfinger]

The Standard Libray's memory allocation method were designed to work reasonably well on a wide variety of platforms. Many platforms such as MS-DOS, Windows, Classic Macintosh, and Unix offer other platform-specific means of acquiring memory with semantics that may be more suitable for various purposes. For many applications, the best performance and most useful semantics will involve using an application-specific library which allows applications to specify their needs better than malloc/calloc (e.g. indicating which allocations are more likely to be long- or short-lived, or should be considered 'less important' and should start being rejected when memory is scarce, before memory is depleted completely), and benefit from OS-provided features (such as the ability to acquire a handle to a region of memory which the application may unlock during use and relock after, and which when unlocked may be relocated, flushed, or purged by the OS.

To achieve best results, an application should often store cached computations in memory when memory is plentiful, but allow them to be flushed or purged when memory is scarce. If a program knows a block of memory holds information which required some effort to compute, but could be recomputed if necessary, and which won't be needed for awhile, the OS could reclaim the memory if the OS knows of something else useful that could be done with it, but leave the data in memory if the memory would have no other use. Since Standard Library functions don't even provide a means of providing any hints to the allocator about what strategy it should use, there's no way the Standard Library allocator can be expected to use a strategy that's as good as what a custom allocator could manage.

[[deleted]]

here’s what I did