previousupnext

4.1 Compartment Area Implementation

For memory allocations requests up to 4 KB, LeapHeap applies the algorithm of 3.1 Bitmap Algorithm to the data structures of 2.1 Compartment Area Data Structure, as detailed in this section.

The implementation runs the LeapHeap bitmap algorithm using 32-bit words (Intel dwords) and allows up to five bitmap tiers, so that the absolute maximum number of cells in a compartment is 2 to the power 25.

Thread-based bit preference is used at the highest bitmap tier. Each thread has a preferred bit number distinct from that of other threads (up to 32 theads). The allocator checks whether the value of the preferred bit is zero; if so it navigates the regions of the lower tiers corresponding to that bit; if not it reverts to looking for any free bit in the top tier. This heuristic gives LeapHeap much of the locality advantage of the thread-private heap, mentioned in section 1.2.2 Private Heaps and Locality. Unfortunately this benefit comes with a large RAM penalty.

A separate commit bitmap, one bit per 4 KB page, lets the allocator track which cells are underlain by pagefile memory. The allocator calls the NT kernel to commit fresh memory one or two pages at a time, as necessary.

The are 512 sizeclasses at 8-byte intervals, covering cells from eight bytes up to 4 KB in length. When LeapHeap runs under its default settings, compartments map one-to-one with sizeclasses, and for simplicity this arrangement is often assumed in other places in this guide; however is is perfectly possible to have one compartment cover several sizeclasses. The allocator rounds the requested size up to the cell size of the nearest compartment that can hold it. All cells allocated are 8-byte aligned.

The three Intel machine instructions cited in 3.1 Bitmap Algorithm, namely Bit Test and Set (BTS), Bit Test and Reset (BTR) and Bit Test and Complement (BTC), are not in fact used by the implementation. It so happens that they do not record the content of the whole word that they modify, a feature essential for detecting full to not-full transitions. Instead LeapHeap uses:

The default LeapHeap is arranged so that the smaller-celled compartments have more bitmap tiers than the larger-celled. Allocations of sizes from 1 to 64 bytes are covered by compartments with four tiers, having an aggregate memory (address range) demand of 288 MB. From there, three-tier compartments extend up to 384-byte cells, using a further 285 MB. Two-tier compartments handle allocations between 385 bytes and 2 KB, requiring 248 MB. The remaining compartments up to the 4 KB threshold are mainly single-tier (32 cells) and between them consume 24 MB of memory, giving a total of 845 MB of address range.