Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Most programs can be quite casual about heap allocation, even to the extent that functional programming languages prefer to allocate new objects than modify old ones, and let the garbage collector worry about freeing things.

In embedded programming, the silent sector, however, there are many applications where you can't use heap allocation at all, due to memory and hard real-time constraints; the number of objects of each type that will be handled is part of the specification, and everything is statically allocated.

Games programming (at least with those games that are ambitious about pushing the hardware) sometimes falls in between: you can use dynamic allocation, but there are enough memory and soft real-time constraints that you can't treat the allocator as a black box, let alone use garbage collection, so you have to use custom allocators. This is one of the reasons C++ is still widely used in the games industry; it lets you do things like http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2007/n2271.html

What other domains are in that in-between territory? Where, apart from games, are custom allocators heavily used?

share|improve this question
1  
Some OSes use a slab allocator which provides object caching but can also be used to reduce processor cache conflict misses by mapping members of an object to different sets for a modulo 2**N indexed cache (both by having multiple instances in a contiguous memory and by variable padding within the slab). Cache behavior can be more important than allocation/free speed or memory use in some cases. – Paul A. Clayton Apr 3 '13 at 0:34

Any time you have an application which has a performance-intensive critical path, you should be concerned how you treat memory. Most end-user client-side applications don't fall into this category because they are primary event-driven and most events come from interactions with the user, and that doesn't have that many (if any at all) performance constraints.

However, a lot of back-end software should have some focus on how the memory is handled because a lot of that software can scale up to handle higher number of client, larger number of transactions, more data sources.... Once you start pushing the limits, you can start analyzing how your software users memory and write custom allocation schemes tailored to your software rather than rely on a completely generic memory allocator that was written to handle any imaginable use case.

To give you few examples... in my first company I worked on a Historian package, software responsible for collecting/storing/archiving of process control data (think of a factory, nuclear power plant or oil refinery with 10's of millions of sensors, we'd store that data). Any time we analyzed any performance bottleneck that prevented the Historian from processing more data, most of the time the problem was in how the memory was handled. We've gone through great lengths to make sure malloc/free were not called unless they were absolutely necessary.

In my current job, I work on surveillance video digital recorder and analysis package. At 30 fps, each channel receives a video frame every 33 milliseconds. On the hardware we sell, we can easily record a 100 channels of video. So that's another case to make sure that in the critical path (network call => capture components => recorder management software => storage components => disk) there isn't any dynamic memory allocations. We have a custom frame allocator, which contains fixed-size buckets of buffers and uses LIFO to reuse previously allocated buffers. If you need 600Kb of storage, you might end up with 1024Kb buffer, which waste space, but because it is tailored specifically for our use where each allocation is very short-lived, it works out very well because the buffer is used, free and reused for next channel without any calls to heap API.

In the type of applications I described (moving lots of data from A to B and handling large numbers of client requests) going to the heap and back is a major source of CPU performance bottlenecks. Keeping heap fragmentation to a minimum is a secondary benefit, however as far as I can tell most modern OSes already implement low-fragmentation heaps (at a minimum I know Windows does, and I would hope others do as well). Personally, in 12+ years working in these types of environments, I've seen CPU usage issues related to heap quite frequently, while never once have I seen a system that actually suffered from fragmented heap.

share|improve this answer

Another area where you might want a custom allocator is to prevent heap fragmentation. Over time your heap may allocate small objects fragmented throughout the heap. If your program can't keep heap memory together, when your program goes to allocate a larger object, it has to claim more memory from the system as it can't find a free block in between your existing, fragmented heap (too many small objects are in the way). Your program's total memory usage will increase over time, and you will consume additional pages of memory unnecessarily. So this is a pretty big issue for programs that are expected to run over long periods of time (think databases, servers, etc etc).

Where, apart from games, are custom allocators heavily used?

Facebook

Check out jemalloc that Facebook is starting to use to improve their heap performance and decrease fragmentation.

share|improve this answer
    
Right. However, a copying garbage collector neatly solves the problem of fragmentation, doesn't it? – rwallace Dec 16 '11 at 21:06

My weird background covers image/video processing, game engines, large-scale servers, search engines, and VFX software (ex: raytracers, mesh decimators, sculptors, particle systems, etc) and all of them used custom allocators to speed things up. The need for custom allocators has kind of followed my entire career.

In my experience (though I'm sure everyone's mileage will vary wildly) the last 3 were actually the most demanding from an allocator standpoint: more than games and image/video processing, possibly counter-intuitively.

Nevertheless, some of the memory allocators I've personally applied were probably at the peak of me being guilty of "premature optimization". Especially earlier in my career, I reached for them way too often. There are often alternatives to using them that don't have us reaching around data structures and data types.

Custom Allocator Needs

With image/video processing, there's a lot of micro-optimization involved since you're often stuck with a linear complexity algorithm processing pixels that cannot possibly do better, so it's all SIMD, multithreading, possibly some loop tiling/blocking, etc. But the critical loopy paths of execution are often processing these big, homogeneous chunks of memory (pixels), so there's not quite as big of a need to get all fancy with memory allocation. The fanciest thing I've done there is to split images into 8x8 tiles so that image/video processing algorithms which need to access neighboring pixels vertically don't suffer as many cache misses with each tile fitting a cache line. That's a memory optimization but didn't require a fancy allocator, just like vector<ImageTile>.

With games, a lot of the data types are often bulkier, and the smaller ones are often aggregated into arrays (making the allocator unnecessary). There's some exceptions like tree-based acceleration structures for frustum culling that benefit from a fixed allocator, but I didn't actually find that many cases that benefited much from a custom allocator in games (though different types of games may benefit a lot). Often with games, I found most memory issues could be solved at the data structure level rather than allocator level. There can also be polygonal meshes involved, but game representations are much simpler than VFX (ex: all polygons can be assumed to be a triangle upfront, or trangulated upfront with quad and n-gon info discarded).

Search engines and servers often cover a lot of non-homogeneous data requests, and often through linked structures (trees in particular, or hash tables with chaining), and linked structures almost always benefit from a fixed allocator or a sequential allocator if the linked structure is built and not modified frequently after. So I find myself and my team using custom allocators a lot there.

Even for data structures which are modified frequently, sometimes it can be quite rewarding to use a simple sequential allocator and just occasionally compact the data structure and purge the previous memory pool -- those kinds of slightly-dirty deferred cleanup solutions (somewhat akin to garbage collection) can do well even if they're not so aesthetically pleasing since they don't free memory right away.

VFX software can be very demanding due to the peskiness of production-style mesh systems (I hate mesh engines). Polygonal meshes make up this complex graph, non-homogeneous structure with dependencies between polygons and vertices, possibly edges in the middle, and all kinds of external data associated from UV maps to weight maps and so forth. It quickly turns into a scenario where we have to flatten away the memory representation with both memory allocators and data structures seeking to allocate more contiguous bits and bytes for efficiency, as well as exploring techniques like this: http://www-etud.iro.umontreal.ca/~blancher/projects/vertex_caching/vertex_caching_eb.pdf.

General-Purpose Allocator

I have attempted at times early on to beat the general-purpose malloc (an allocator with the ability to handle variable-sized chunk requests and free any chunk at any given time) and failed embarrassingly multiple times. I tried chained blocks with associated free bits, buddy allocators, slab allocators, no avail. There were times I got close. One time I thought I beat malloc but it was just for a superficial benchmark which was only timing straight allocation and deallocation. When plugging it into a real-world application, it got slower because it was using more metadata per chunk and paying for it at the memory hierarchy level (page faults, cache misses).

I tried this back when I was really young and optimistic (teenager days ~20 years ago), hoping to solve the world's hunger problems and come up with one glorious memory allocator to rule them all. I failed hard. Someone with more experience than me might actually succeed, and these kinds of deferred solutions using garbage collection and cleaning up in a deferred process sound promising.

I've often toyed with the idea of programs that actually have an extra level of indirection for small objects so that their memory contents can be rearranged on the fly, similar to how the Java garbage collector works. It's been daydream territory for me though, nothing I've ever actually tried and measured, and there's the glaring cost of a need for an additional level of indirection.

My easy solution: don't try to solve the world's hunger problems by coming up with one general-purpose allocator to rule them all. Instead, find the critical hotspots, and apply a degeneralized allocator solution specific to the allocation/deallocation strategies of the hotspot area.

Stack Allocator

This allocator gave me the most trouble of all. I deeply regret ever trying to use it in a wide context.

Yet I noticed often in profiling large-scale, team-based production code that so many objects are often created and destroyed in C++ programs that utilize the heap/free store, even though they have a symmetrical push/pop style pattern of allocation/deallocation that's tied to the call stack. Combining that with profiling sessions that often showed 35% of the time in the software dominated by operator new/malloc made me want to reach for a new kind of allocator that could utilize this kind of push/pop symmetrical allocation/deallocation pattern.

This actually gave tremendous benefits since it was such a simple allocator, actually rivaling the native stack in performance and getting better the more it was used (temporal locality at the top of the stack). There were places where I was getting something like 11x performance improvements against real-world operations utilizing it, so it had this very alluring quality and addictive quality to it where it was getting better the more it was used.

My initial mindset was like, "Wowee, I got an infinite ("virtually") stack now that I can use for all temporary objects!" It was again getting to that kind of, "I want to solve the world's hunger problems territory", and it did the trick of making the code quite a faster. operator new/malloc ceased to show up as hotspots completely after that.

Yet, just a few months later, I hated it. The way it was interacting with C++ objects and exception-safety was complex, and it made the code look alien. I was starting to pass it down the call stack everywhere (one thread-local stack allocator), and it was really gross. It did make things go a lot faster, but it also degraded the maintainability and the idiomatic nature of the code to an all-time low.

My easy solution A: Again, stop trying to solve the world's hunger problems. Reach for allocators in increasingly less generalized sections of code, and more sparingly.

My easy solution B: A lot of the excessive heap allocations were coming from structures like teeny vectors and strings being allocated a million times over in a tight loop. This was before we had things like the small string optimization that now comes with some standard implementations.

For that I just ended up coming with an alternate data structure to std::vector and std::string that relied on this underlying data representation:

template <class T, int N>
class SmallVector
{
public:
    // Excluding the complex public interface which was fully standard
    // compliant down to iterators, fill ctor, range ctor,
    // resize, erase, range erase, etc.

    // Returns the nth element.
    T& operator[](int n) {return ptr[n];}

    // Returns the nth element.
    const T& operator[](int n) const {return ptr[n];}

private:
    // Stores an initial capacity of N elements. No additional heap
    // allocation required the capacity exceeds N. Elements are
    // constructed with placement new and destroyed explicitly.
    // I had to use my own aligned storage hack here because this
    // was C++03.
    AlignedStorage<T, N> fixed;

    // Points to 'fixed' initially until capacity exceeds N. Then it
    // points to a dynamically-allocated block.
    T* ptr;

    int cap; // element capacity, initially set to 'N'
    int num; // number of elements
};

Using this kind of structure helped a lot in our cases since we were so often doing these teeny heap allocations as a result of using teeny vectors and strings and such. This one made it so stack allocation could occur provided the capacity was under N, with cases that exceeded N often being very rare-case scenarios.

I now use this just about as much as std::vector for short-lived little teeny sequences that could, 99% of the time, just use the stack.

Sequential Allocator

This allocator never gets old. It's super useful for, say, constructing a tree which is only searched, not modified once built. It tends to improve not only the tree construction as a result of simpler allocation, fewer compulsory cache misses/page faults, but also tends to accelerate search times a little bit due to some improvement in locality of reference (though not by a huge margin).

These allocators are very narrowly-applicable with the "allocate everything sequentially and then purge everything outright at once" strategy, so I never got in trouble with these. I never tried to solve the world's hunger problems with these, i.e. I still use them a lot now as very local implementation details in some very specific, local, critical section of a codebase.

Fixed Allocator

The fixed allocator is the most useful allocator for me out of them all. It never gets old, it never ceases to find utility when I'm dealing with hotspots in places where there is a strong, expressed user need for speed.

My basic implementation of the fixed allocator in C++ has always looked like this:

class FixedAlloc
{
public:
    FixedAlloc(): root_block(0), free_element(0), type_size(0), block_size(0), block_num(0)
    {
    }

    FixedAlloc(int itype_size, int iblock_size): root_block(0), free_element(0), type_size(0), block_size(0), block_num(0)
    {
        init(itype_size, iblock_size);
    }

    ~FixedAlloc()
    {
        purge();
    }

    void init(int new_type_size, int new_block_size)
    {
        purge();
        block_size = max(new_block_size, type_size);
        type_size = max(new_type_size, static_cast<int>(sizeof(FreeElement)));
        block_num = block_size / type_size;
    }

    void purge()
    {
        while (root_block)
        {
            Block* block = root_block;
            root_block = root_block->next;
            free_max(block);
        }
        free_element = 0;
    }

    void* allocate()
    {
        assert(type_size > 0);
        if (free_element)
        {
            void* mem = free_element;
            free_element = free_element->next_element;
            return mem;
        }

        // Create new block (max-aligned malloc).
        void* new_block_mem = malloc_max(sizeof(Block) - 1 + type_size * block_num);
        Block* new_block = static_cast<Block*>(new_block_mem);
        new_block->next = root_block;
        root_block = new_block;

        // Push all but one of the new block's elements to the free pool.
        char* mem = new_block->mem;
        for (int j=1; j < block_num; ++j)
        {
            FreeElement* element = reinterpret_cast<FreeElement*>(mem + j * type_size);
            element->next_element = free_element;
            free_element = element;
        }
        return mem;
    }

    void deallocate(void* mem)
    {
        FreeElement* element = static_cast<FreeElement*>(mem);
        element->next_element = free_element;
        free_element = element;
    }

    void swap(FixedAlloc& other)
    {
        std::swap(free_element, other.free_element);
        std::swap(root_block, other.root_block);
        std::swap(type_size, other.type_size);
        std::swap(block_size, other.block_size);
        std::swap(block_num, other.block_num);
    }

private:
    struct Block
    {
        Block* next;
        char mem[1];
    };
    struct FreeElement
    {
        struct FreeElement* next_element;
    };

    // Disable copying.
    FixedAlloc(const FixedAlloc&);
    FixedAlloc& operator=(const FixedAlloc&);

    struct Block* root_block;
    struct FreeElement* free_element;
    int type_size;
    int block_size;
    int block_num;
};

... typically only used in a single-threaded context. Multithreaded versions use a spinlock variant (again not trying to solve the world's hunger problems in a single allocator).

Data Structures

As shown in the above example with the SmallVector, a lot of times, reaching for a custom allocator is kind of working around your data structures/data types and trying to make them go faster.

Sometimes that's inevitable, our design is already committed to a data structure, or the data structure is so generally useful that it's not worth reinventing another one and just reach around and give it a more efficient allocator (ex: providing a linked structure a fixed allocator).

But there's often data structures that can eliminate the need/temptation for memory pools. For example, an unrolled list might still satisfy all the needs you have of a linked list while providing the spatial locality and cheap, bulk allocation that linked lists typically lack.

I've found lately through tuning that n-ary trees can counter-intuitively work better (at least I have an easier time getting more performance out of them) than binary trees, and n-ary trees don't call so strongly for custom allocators since they have pretty fat nodes already.

Even for cases where we don't use an n-ary tree, we can just store an array (vector, e.g.) of nodes and store indices into them. 32-bit indices cut the memory requirements down to half the size of a pointer on 64-bit, and the array is effectively fulfilling a similar purpose to a memory pool (especially if we reserve capacity in advance).

So there's often ways like this to avoid custom allocators by seeking some different (and sometimes rather exotic) data structures with fatter nodes and such that pack more elements inside of them. When possible, I recommend seeking this solution if you aren't "stuck" with a data structure due to design dependencies.

At the end of the day, all of this is just seeking to make more data fit into a contiguous array of bytes. The fundamental idea of a memory pool is just allocating a big array of bytes and pooling chunks of it to data structures and data types to use. We can avoid reaching around our data types and data structures if they start to resemble this kind of contiguous array form on their own.

Data-Oriented Design

Last but not least, one of the greatest things for me that has mitigated the need for custom allocators is applying a data-oriented mindset. If you're looking at a C++ codebase which wants to allocate teeny abstract objects on the heap for polymorphism, there's often alternate ways to design abstract collections interfaces where the collection can be abstract but the individual elements don't have to be.

An example is AbstractParticleSystem, not vector<unique_ptr<AbstractParticle>>. Polymorphism and opaque types (ex: pimpls) often tempt us to allocate everything in little chunks on the heap. Those little chunks become big chunks that cease to require a custom allocator if we're designing at a bulkier interface level. This also helps for pretty much every other kind of optimization imaginable (more appropriate levels of granularity/coarseness for thread locks, SoA optimizations for sequential vertical access patterns, AoSoA for hybrid random-access and sequential access, multithreading with more appropriately-chunky work for each thread to perform, etc), at the cost of some generality/flexibility.

TL;DR

Anyway, I hope that covers some extra territories where custom allocators might be used, answering the basic question, and hopefully some insight as a result of my adventures (and misadventures) having dealt with custom allocators in all kinds of areas.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.