To understand why we need to understand heap organisation in BDWGC. The heap is divided into 4KB sized and aligned blocks, and each block is used for a single object type and size, multiple blocks may be used for each type and size combination. Object types are: pointer-free, normal and uncollectable. Sizes are first rounded up to the nearest 16 bytes (on 64bit systems) then may be rounded up to a higher size so that objects of similar sizes can be allocated together, reducing waste. This arrangement is very convenient, it allows an object’s size to be determined by rounding its pointer to it’s heap block address and inspecting the block’s header, as all the objects on that block will have the same size. Other information is also located in the header including the mark bits.

Allocation is done using free lists, one free list per size and type. If the free list for the desired size and type is empty then the collector will try to get a free block, initialize it and add it to the free list for that size and type. If there are no free blocks, a collection will be triggered. The collector may also perform lazy sweeping, but I’m skipping this detail.

Let’s get an idea of how we’re using the heap. First with a look at the distribution of object sizes, and the number of blocks use for each object size.

Small objects (16 and 48 bytes) dominate the heap. Objects 48 bytes and smaller account for 95% of the objects by count, or 77% by total size. 83% of the heap is usable for objects of this size only. This is not very surprising at least for a language like Mercury where many objects might only be a few words long. For example a cons cell is the most common object (heap attribution profile) and is exactly 16 bytes long.

They also have some of the lowest heap utilisation percentages, this is the percentage of used space within blocks for objects of this size. A low percentage indicates that there is a lot of empty space that can only be used by objects of this size. The question marks indicate that I don’t know how BDWGC stores large objects and do not know the sizes of their heap blocks.

Recall that the program attempted to allocate a 160 byte object. The utilisation of the 160 byte area was 97%, this is an artifact of how I collected the data since I’ve coalesced blocks of different types together in these tables. The program crashed when the collector could not find a block of the correct size and type, and there were no empty blocks that it could initialise for this size and type.

Well, that’s the explanation of why the program crashed, a bit dull. The more interesting story here is what is going on with the small object sizes. We can’t allocate 160 bytes and yet there’s 288MB free, 277MB of which is reserved for objects 48 bytes or smaller! What’s going on with the spare memory in those smaller object blocks?

The first thing to note about these histograms is that I’ve had to scale the graph: For example there are 78,355 blocks with 256 objects in the first graph, you can see a thin bar on the far right of the graph, it extends far beyond the top boarder and scaling the graph and cutting it off was necessary to see the rest of the graph.

Excluding the full blocks, the block utilisation looks like a normal distribution, skewed towards mostly empty blocks for 16 and 32 byte objects, and towards mostly full blocks for 48 byte objects. Blocks for larger objects havn’t been shown they a generally full or close to full. There are no empty blocks for any size category. Presumably they are returned immediately to the free block list when they become free. The following table provides a little more information about block utilisation.

The graphs show that there are a number of blocks with very few 16 and 32 byte objects on them. We know that there are 160 contiguous bytes within these blocks, however they’re totally unavailable for the allocation of 160 byte objects. While there is a single object on a block for a given size, it cannot be used for objects of other sizes. It might be tempting to call this memory "wasted", however it is still available for objects of the correct size. It is however inefficient, Roughly 219MB of memory could be made available to blocks of practically any size if there was no fragmentation within the 16 byte objects.

The simple answer is to use a moving collector. The simplest moving collector, a semi-space copying collector, will use twice as much memory as the program’s working set. While it’s a reasonable GC algorithm it would not help in this particular situation as the original request was to reduce overheads like this. A mark compact collector is a moving collector that would address this specific fragmentation problem. Furthermore it’s easy to imagine keeping the same heap organisation and compacting objects of the same sizes. This can enable the use of a much faster compaction algorithm.

Using a moving collector in an "uncooperative environment" isn’t possible, and doing so for Mercury would be a lot of work. So what can we do with BDWGC?

At YesLogic, we stopped pursuing these ideas and instead recommended that our client did something else, like ran fewer concurrent tasks or purchased more memory. We continue to make changes to Prince itself to reduce memory usage and churn.

In the opening of this article I said that 1.5GB is not a lot by today’s standards for such a task, generating a 1600 page PDF. It’s also true that most developers, most of the time, do not need to worry about memory fragmentation. That being said I’d like to describe two other affects of memory fragmentation.

A modern CPU has multiple layers of memory, while we have multiple gigabytes of slow RAM, we have only megabytes of fast last-level cache and kilobytes of very fast first level cache. Fitting as much information as possible within a smaller amount of memory will increase the chance that other relevant information also being cached, due to its locality. A typical processor has 64 byte cache lines, so this is only true for object sizes less than 64 bytes (assuming they’re aligned). Nevertheless as long as 16 byte objects are the most common this is very relevant. If a 16 byte object is loaded into a cache, but its neighbouring areas are empty, then three quarters of that cache line is wasted.

A similar problem happens at the level of pages (also blocks in BDWGC). These days, due to very large memories, page faults are very rare so many developers will usually assume this is not a problem in practice. This is inaccurate. When the processor translates a virtual memory address into a physical address it does so using page tables configured by the OS. Reading page tables involves reading memory, we know this is slow. A special type of cache called a Translate Look-aside Buffer (TLB) is used to speedup address translation. TLBs are very limited and reducing the number of pages your program needs will improve performance by reducing TLB misses.