Realistic model of memory allocation/deallocation cost

Question

When doing complexity analysis, they never account for the costs of memory allocation/deallocation on the heap. In particular, this is the case for the announced complexities of the operations on containers.

But allocation/deallocation does not come for free and unfortunately is implementation-dependent. Furthermore, one may suspect that the costs are dependent on the whole allocation/deallocation history, via fragmentation. To me, this seems a grey area of the characterization of algorithms, and I believe that in some cases this hidden cost could invalidate low complexity claims such as O(1) or amortized O(1).

So I wonder if there are reasonable models of the complexity of real heap management systems that reflect the behavior of those commonly implemented with compilers. Is there a better answer than "this is implementation dependent" ?

Or another way to ask the question: is it justified to ignore these costs ?

---

Note that I am aware of the post What is the time complexity of memory allocation assumed to be?, but I expect a more concrete answer.

Answer 1

I do believe it is justified to ignore these costs. If we care about actual running time in practice, I expect that there are other factors that are ignored in asymptotic running time that often have a bigger influence -- memory hierarchy and caching particularly comes to mind. In theoretical runtime analysis we treat a random lookup into memory as the same cost as a single arithmetic operation, but in practice it can be 100x slower. I think it'd be rare to find situations where memory allocation overhead causes an 100x increase in runtime.

There are ways to achieve at most a $O(\log n)$ time slowdown, where $n$ is the total amount of memory available. For instance, you can emulate "page tables" in software. Build a mapping from (object id, offset) to an address, and store this mapping in a binary tree. Now accessing the $j$th byte of object with id $i$ can be done by looking up $(i,j)$ in the mapping, and then accessing memory there. Allocating a $k$-byte object can be done by picking a new object id, then finding any $k$ free bytes in memory, and adding $k$ mappings to the binary tree. You can keep track of which bytes are free using a bitmap. Deallocation is also simple; you remove $k$ mappings from the binary tree. In practice, you probably want to use page granularity rather than byte granularity, and round up object allocations to be a multiple of the page size.

I would be surprised to find any problem where taking memory management into account in the running time analysis changes the ultimate time complexity to solve the problem.

Most of the common algorithms use fixed-size objects. For those algorithms, it is straightforward to build a memory allocator where allocation and deallocation can be done in $O(1)$ time. For instance, you can have a doubly linked list of empty objects; allocation removes one from the list, and deallocation inserts it back onto the list.

Answer 2

This question feels more like benchmarking than algorithm analysis to me. That's not to say that there aren't algorithmic considerations.

Consider a multiprocessing environment with different threads all allocating, sharing, and deallocating objects. Each CPU could allocate from its own arena, or there could be a pool of arenas and each allocation could be taken from one that no other CPUs are using. However, an object must be returned to the arena from which it came. This means that deallocation is more likely to suffer from contention and cache locality issues than allocation.

Unmapping a segment of memory from the address space of a process is a $O(\log n)$ operation where $n$ is the number of blocks mapped, since every operating system that I'm aware of uses balanced binary trees for the segment map. (There was an old version of Solaris which used a linked list until system programmers complained about the performance!)

However, mapping a segment, where the programmer doesn't care where it's mapped to, on a 64-bit OS, is probably an $O(1)$ operation, since the kernel probably appends to the tree. Once again, deallocation is likely to be more expensive than allocation.