Module xalloc::bitmap

source ·
Expand description

Free space bitmap-based external memory allocator.

This allocator uses a simple bitmap to track the allocation state, and relies on a naïve bit scan for allocation.

Memory Overhead

Since it uses a bitmap to track free space, it consumes a memory proportional to the size of the heap. The memory consumption is estimated to be roughly size / 8 bytes, where size is the size of the heap measured by the number of allocation units.

BitmapAlloc does not store information about individual allocated regions by itself. Therefore, BitmapAlloc would be preferred when the number of allocations is quite high and each allocation is very small (preferably, just one allocation unit).

The following table shows the memory overhead comparison between Tlsf and BitmapAlloc with a varying number of allocations (assuming the heap is fully occupied).

size# of allocationsTlsf (bytes)BitmapAloc (bytes)
1,02401,118128
11,174128
25615,454128
1,02458,462128
65,53601,1188,192
11,1748,192
1,02458,4628,192
65,5363,671,1348,192

Performance

The allocation throughput is roughly the same as of jemalloc.

Structs

Free space bitmap-based external memory allocator.
A handle type to a region allocated in a BitmapAlloc.