A bit-parallel search algorithm for allocating free space
Randal C. Burns, W. Hineman · 2002
File systems that allocate data contiguously often use bitmaps to represent and manage free space. Increases in the size of storage to be managed creates a need for efficient algorithms for searching these bitmaps. We present an algorithm that exploits bit-parallelism, examining all bits within a processor word at the same time, to improve search performance. Measurements of our implementation show that these techniques lead to a 14 times increase in the rate at which bitmap pages can be searched on a 64-bit processor. Trace-driven experiments indicate that overall allocation performance increases by a factor of 3 to 6 on a 32-bit processor. As processors mature, registers become wider and the degree of bit-level parallelism increases, which makes the performance improvements of our search algorithm more substantial.