c++ - 使用双包装类进行位操作(C++，clang)修复性能下降

Question

我的问题是“我能否编写一个 bitset 类型的类，它既可以与内部 unsigned 和 dynamic_bitset 内部表示一起使用，又不会失去独有的 unsigned bitset 类的性能？”

为了提供一些上下文，我正在尝试创建一个类，它充当一个位集，在其中实现我需要的频繁操作。此类的初稿在内部使用无符号长整型表示。

但是，在某些情况下我需要超过 64 位或 128 位，这将需要使用 boost 的动态位集，或使用无符号长整数数组作为内部表示。

现在，我的初稿与仅使用裸无符号长整型(为我的编译器使用 -O3 标志)的代码一样高效。而且我完全意识到，在使用动态位集的情况下，我无法保持这种性能。但是，我只想使用我的类编写一次我的算法，而不是编写一个具有无符号表示的代码和一个使用动态位集的代码。所以我创建了一个 bitsetwrapper 类，它有一个指向抽象位集的指针，它可以是具有内部无符号长位集的位集或具有内部动态位集的位集。它应指向哪个派生类，然后由您需要使用的位数决定。

这样我就永远不必担心使用指向抽象类的指针，因为它们被限制在我的包装器中。一个例子:

    class BitsetBase{}
    class UnsignedBitset : public BitsetBase{
            unsigned long representation;
    }
    class DynamicBitsetBitset : public BitsetBase{
            dynamic_bitset<> representation;
    }

    class BitsetWrapper{
        *BitsetBase bitset;
    }

现在我遇到了一些性能问题，到目前为止我还没有完全解决这些问题。

初始性能基准如下(相对比较):

    Unsinged long code : 1s
    UnsingedBitset code : 1s
    BitsetWrapper code (using UnsingedBitset) : 4s

为了给您一些额外的背景信息，在所有 3 个实例中都制作了许多拷贝。这就是导致 BitsetWrapper 增加到 4s 的原因。因为在我最初的尝试中，我使用“new”来初始化 Bitset 实例。

现在我设法通过在外部初始化 UnsingedBitset 并将它们作为参数传递给我的包装器构造函数来完全规避 new。
产生显着的性能 boost 。

    Unsinged long code : 1s
    UnsingedBitset code : 1s
    BitsetWrapper code (using UnsingedBitset) : 2.4s

然而，达到 1s 性能至关重要。我很惊讶 UnsignedBitset 版本具有与原始 Unsigned 长代码相同的性能。我的猜测是编译器可以以某种方式优化它，但不能再对“双重”包装器进行优化。有谁知道为什么性能如此糟糕，以及是否有其他方法可以解决我的问题？ (ps.我也试过 boost::variant 这也慢了 3 倍)

代码示例:

    for(1000000 loops){                
        AnyClass bitset(random_input) 
        while(!bitset.equalsZero()){
            bitset.removeLeastSignificantBit()
            AnyClass bitset2 = bitset
            bitset2.invert()
            while(!bitset2.equalsZero()){
                result += bitset2.someManipulation();
            }
        }
    }

把问题问的更清楚。我是否有可能围绕一个表示创建一个包装器，如果与具有固定无符号长表示的包装器相比，内部表示是无符号长整数，它可以在内部选择它应该使用的表示(基于某些参数)而不会损失性能。

调用的代码示例是:

    void invert(){
            representation = ~representation;
    )

(无性能损失)然后会变成:

   void invert(){
       bitset_instance->invert();
   }

在 Bitset 包装器中(性能损失)。

Answer 1

没有看到更多代码，我只能推测，但虚函数调用和间接的成本可能超过位操作的成本。如果每个位翻转都是通过虚函数调用完成的，那么这尤其可以想象。这是最有可能的，因为您消除了分配作为额外的性能开销——但同样，可以肯定的是，人们需要更多地了解您的使用模式。

您真的需要灵 active 吗？如果你想去除抽象，有一些可能性:

1. 使用dynamic_bitset一直。
2. 使用其他实现方式，例如 std::vector<bool> (很可能不会比 1 更高效)
3. 使用不同的调度机制。如果您知道编译时的情况，模板是一个显而易见的选择。其他运行时机制(if/else、switch)最有可能产生与虚拟函数相同的性能。

附言不确定它是否只是为了简洁而被省略，但多态基类应该有一个虚拟析构函数。如果您在堆栈上分配它们并只传递指针，这甚至是一个很好的做法。