Custom heap allocators

Question

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?

Answer 1

Video processing, VFX, operating systems, etc. Often people overuse them though. The data structure and allocator need not be separated to achieve efficient allocation.

For example, it's introducing a lot of extra complexity to split efficient tree node allocation in an octree away from the octree itself and rely on an external allocator. It's not necessarily a violation of SRP to fuse these two concerns together and make it the responsibility of the octree to allocate many nodes at once contiguously, as doing that does not increase the number of reasons to change. It may, practically speaking, decrease it.

In C++, for example, one of the retarded side effects of having standard containers rely on an external allocator has made linked structures like std::map and std::list considered almost useless by the C++ community, since they're benchmarking them against std::allocator while these data structures allocate one node at a time. Of course your linked structures are going to perform poorly in that case, but things would have turned out so much differently if efficient allocation of nodes for linked structures was considered a data structure's responsibility rather than an allocator's. They might still use a custom allocation for other reasons like memory tracking/profiling, but to rely on the allocator to make linked structures efficient while trying to allocate nodes one-at-a-time makes all of them, by default, extremely inefficient, which would be okay if it came with a well-known caveat that linked structures now need a custom allocator, like free list, to be reasonably efficient and avoid triggering cache misses left and right. Far more practically applicable might have been something like std::list<T, BlockSize, Alloc>, where BlockSize indicates the number of contiguous nodes to allocate at once for the free list (specifying 1 would effectively lead to std::list as it is now).

But there is no such caveat, which then leads to a whole community of blockheads echoing a cult mantra that linked lists are useless, e.g.

Answer 2

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.

Answer 3

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.