How to allocate memory
Many programmers use malloc() and free() and pay no more mind to "allocating memory", but I often find 2-20× speed improvements by rethinking memory usage, so it is something I usually want to examine when joining a distressed project.
The first step, is to stop allocating "memory", and start allocating specific somethings else. Consider the usage pattern:
Pages are allocated from the operating system, are fixed size, and are not a particularly useful fixed size
Stacks grow and shrink at one end, and you can usually have one or two
Arrays (growable contiguous space) have a type and a length, and the most common allocation operations are to copy and to extend (append), with "slicing" being common enough that it is worth optimising.
Objects (fixed size heaps) on the other hand, do not grow.
There are other common data structures (like hash tables) that resist a good memory allocation strategy. We can usually find another data structure (like a trie) which is faster and better that we can find a good memory allocation strategy for.
One major limitation of malloc (and even the best implementations like jemalloc and dlmalloc) is that they try to use a single allocator for each data structure. This is a mistake: A huge performance gain can be had by using a separate allocator for each of your data structures — or rather, for each of your data usage patterns.
And yet you can still start with malloc if you wrap your use of it by length. Wrapping malloc in this way does not mean:
... continue reading