Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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
add comment

2 Answers

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
add comment

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
add comment

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.