Hineman A Bit-Parallel Search Algorithm for Allocating Free Space To appear in

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 ef i-cient 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 implementa-tion show that these techniques lead to a 14 times in-crease 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 processox As processors mature, registers become widel; and the degree of bit-level paral-lelism increases, which makes the peqormance improve-ments of our search algorithm more substantial.