1

我目前正在评估是否应该使用单个大型位集或多个 64 位无符号长整数 (uint_64) 来存储大量位图信息。在这种情况下，位图表示几 GB 内存页面的当前状态（脏/非脏），并且有数千个条目。

我正在执行的工作要求我能够查询和更新脏页，包括在两个脏页位图之间执行 OR 操作。

为了清楚起见，我将执行以下操作：

  • 从文件导入位图，并与现有位图执行按位或运算
  • 计算汉明权重（计算设置为 1 的位数，表示脏页数）
  • 重置/清除一点，将其标记为更新/清理
  • 检查位的当前状态，以确定它是否干净

看起来对 C++ 位集执行按位运算很容易，并且很容易计算汉明权重。但是，我想这里没有魔法——CPU 只能对它可以存储在寄存器中的尽可能多的字节执行按位操作——所以 bitset 使用的例程可能与我自己实现的例程相同。汉明权重可能也是如此。

此外，将位图数据从文件导入位集看起来很难看——我需要多次执行位移，如此处所示。我想考虑到我将使用的位集的大小，这会对性能产生负面影响。当然，我想我可以只使用许多小的位集，但这可能没有任何优势（其他可能易于实现）。

一如既往，任何建议都会被采纳。谢谢！

4

3 回答 3

1

数千位听起来并不多。但也许你有数百万。

我建议您编写代码，就好像您通过抽象它具有理想的实现一样（首先使用更容易编码的任何实现，忽略任何性能和内存要求问题）然后尝试几种替代的特定实现来验证（通过测量它们）哪个表现最好。

您甚至没有考虑过的一种解决方案是使用 Judy 数组（特别是 Judy1 数组）。

于 2012-09-18T03:04:16.530 回答
1

听起来您有一个非常具体的一次性应用程序。就我个人而言，我从未使用过 bitset，但据我所知，它的优势在于它可以像一个布尔数组一样被访问，并且能够像向量一样动态增长。

据我所知，你真的不需要其中任何一个。如果是这种情况，并且如果填充位集是一场戏剧，我会倾向于自己做，因为分配一大堆整数并对其进行位操作确实非常简单。

鉴于有非常具体的要求，您可能会从进行自己的优化中受益。访问原始位数据对此至关重要（例如，使用预先计算的单个字节的汉明权重表，如果有空闲内存，甚至可以使用两个字节）。

我一般不提倡重新发明轮子......但是如果您有特殊的优化要求，最好针对这些调整您的解决方案。在这种情况下，您要实现的功能非常简单。

于 2012-09-18T02:11:54.983 回答
1

我想如果我是你，我可能会省去任何 DIY 的麻烦并使用boost::dynamic_bitset。他们在功能方面涵盖了所有基础，包括可用于文件 IO 的流运算符重载（或仅以unsigned ints 形式读取数据并使用它们的转换，请参阅他们的示例）和count汉明权重的方法。Boost 至少受到 Sutter 和 Alexandrescu 的高度评价，他们在头文件中做所有事情——没有链接，只有#include适当的文件。此外，与标准库不同bitset，您可以等到运行时指定位集的大小。

编辑： Boost 似乎确实允许您需要的快速输入读取。 dynamic_bitset提供以下构造函数：

template <typename BlockInputIterator>
dynamic_bitset(BlockInputIterator first, BlockInputIterator last,
               const Allocator& alloc = Allocator());

底层存储是 s 的一个std::vector（或几乎相同的东西）Block，例如uint64s。std::vector因此，如果您以 a of s 的形式读取位图uint64，则此构造函数会将它们直接写入内存而无需任何位移。

于 2012-09-18T02:16:56.090 回答