c++ - 扫描位数组以获取多位模式

Question

我正在编写一个由位图(uint8_t 数组)支持的内存分配器，目前当出现分配请求时，我会按顺序从 0 到 n 位扫描位图并搜索空间可以满足要求。 (位 1 表示页面已使用，0 表示页面空闲)现在不是一次一位地搜索空间，有没有技术可以更快地扫描整个数组？即，如果收到 3 页内存的请求，我想一次性搜索数组中的 000 模式，最好不要循环？

PS:我没有使用 std::bitset，因为它不适用于我正在使用的编译器。 AFAIK 也不允许我搜索多个位。

编辑:位被打包成一个字节 uint8_t 有 8 页(每个位 1)编码在其中。

Answer 1

要扫描一个空白页，您可以一次循环一个完整字节的位数组，并检查它是否小于 255。如果小于 255，则至少有一个零位。更好的做法是一次扫描 32 位或 64 位(无符号整数)，然后缩小 uint 内的搜索范围。

要优化一点，您可以使用零位跟踪第一个字节(并在释放页面时更新该位置)。一旦您分配了该空闲页面，这可能会产生误报，但至少下次扫描可以从那里开始而不是从头开始。

如果您愿意以 2 的幂(取决于您的数据结构)对齐较大的 block ，则可以优化对多个页面的扫描。例如，要分配 8 页，您只需扫描一个完整的字节是否为零:

1 page: scan for any zero bit (up to 64 bits at a time)
2 pages: scan for 2 zero bits at bit position 0,2,4,6
3-4 pages: scan for zero nibble (for 3 pages, the fourth would be available for 1 page then)
5-8 pages: scan for an empty byte

for each of the above, you could first scan 64 bits at a time.

这样，您就不必担心(或检查)byte/uint32/uint64 边界处的重叠零范围。

对于每种类型，可以保留/更新第一个空闲 block 的起始位置。