Module xalloc::bitmap

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 allocations	Tlsf (bytes)	BitmapAloc (bytes)
1,024	0	1,118	128
	1	1,174	128
	256	15,454	128
	1,024	58,462	128
65,536	0	1,118	8,192
	1	1,174	8,192
	1,024	58,462	8,192
	65,536	3,671,134	8,192

Performance

The allocation throughput is roughly the same as of jemalloc.

Structs

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