4

我有一张位图

uint64_t bitmap[10000]

跟踪系统中分配的资源。现在的问题是如何有效地找到该位图中的第一个未设置（零）位？

我知道ffsll(unsigned long long)在 glibc 中可以找到第一个设置位，我假设它使用硬件指令来完成。

要在我的情况下使用此函数，首先我需要初始化数组以将每个位设置为 1，然后在进行资源分配时，我必须线性搜索数组以查找第一个非零字。然后使用 ffsll() 找到第一个设置位。

我怎样才能更快地做到这一点？

更新：我在 x86-64 cpu 上。

4

3 回答 3

5

您可以维护位图树以有效地找到最低位集。在 64 位 CPU 上，您只需拥有 3 的树深度即可跟踪 4096 个 64 位元素——这意味着只需使用三个ffsll调用。

基本上，这是通过将您的数组划分为 64 个字的块并为每个块分配一个 64 位索引来实现的。如果相应的位集字已设置所有位，则设置索引字的位。当您更改位集中的位时，您会调整相应的索引字。

然后，您可以在顶部构建另一个索引数组以形成一棵树。

它需要对每个位更改进行一些额外的工作，但是与您在需要空闲位时不必线性搜索位集所获得的节省相比，额外工作（和存储）的总量可以忽略不计。

于 2013-02-14T02:44:45.687 回答
1

我不确定你怎么会比这快得多，但我愿意被证明是错误的：

uint64_t bitmap[10000];
unsigned int i;
for (i = 0; i < (sizeof(bitmap) / sizeof(*bitmap)) && 0xFFFFFFFFFFFFFFFF == bitmap[i]; ++i);
const int bitInWord = ffsll(bitmap[i]);
const unsigned int firstZeroBit = bitInWord ? i * sizeof(*bitmap) * CHAR_BIT + bitInWord : 0;
于 2013-02-14T02:33:30.440 回答
0

如果您使用的是 32 位 cpu，那么您不想这样做。而是使用 32 位整数数组。数组上的循环会更快。

您也可以将每个值编码为 1 个字节，然后预存储该字节中设置的第一位。因此，当您找到一个并非全部为 0xFFFFFFFF 的整数时，您可以简单地比较字节。如果第一个字节不是 0xFF，那么它就在那个字节中，依此类推。

因此，如果一个字节不是 0xFF，则意味着它是该字节的 255 个可能值之一。每个值都有一个第一位设置。

另一种看待问题的方法是尽可能将其分成块。我不知道你的资源是什么，所以我不能说。

还要考虑在上一次扫描它向前循环的未设置位。如果你存储上一个结果的索引，那么你可以简单地从下一个搜索的相同索引开始。将此索引称为 pos 并每次都使用它。

您还可以在每次将位设置为零时创建一个小的“空闲”索引数组，因此当您的“pos”到达数组末尾时，只需从保存的索引之一重新开始。

换句话说，你真的不想每次都运行这么长的循环。那是您的问题，而不是获得该位的最终说明。使用上面概述的索引跟踪，它会快数百倍。

于 2013-02-14T02:34:23.467 回答