4

我想以一种不会影响性能的方式将一个大的 bitset 与一个较小的 bitset 连接起来。目前，我的应用程序仅在以下代码中花费了 20% 的 cpu 时间：

boost::dynamic_bitset<> encode(const std::vector<char>& data)
{
    boost::dynamic_bitset<> result;

    std::for_each(data.begin(), data.end(), [&](unsigned char symbol)
    {
        for(size_t n = 0; n < codes_[symbol].size(); ++n)
            result.push_back(codes_[symbol][n]); // codes_[symbol][n].size() avarage ~5 bits
    });
    return result;
}

我读过这篇文章，它提出了一个解决方案，不幸的是这对我不起作用，因为目标位集和源位集的大小之间的大小差异非常大。

有任何想法吗？

如果使用 boost::dynamic_bitset 无法有效地做到这一点，那么我愿意接受其他建议。

4

3 回答 3

1

这是因为您一直在使用push_back()，但实际上，您已经提前知道了大小。这意味着大量的冗余复制和重新分配。你应该先调整它的大小。此外，您不必push_back()每个值 - 您应该可以使用某种形式的insert()（我实际上并不知道它的确切接口，但我认为append()是名称）一次插入整个目标向量，这应该会好很多。

此外，您将留下dynamic_bitsetas unsigned long ，但据我所知，您实际上只是插入unsigned char其中。改变它可以让你的生活更轻松。

我也很好奇什么类型codes_是 - 如果它是 amap你可以用 a 替换它vector，或者事实上，因为它的静态大小最大（256 个条目是 a 的最大值unsigned char），一个静态数组。

于 2011-04-23T19:51:29.950 回答
0

我之前尝试过在性能代码中使用 boost bitset 并且感到失望。我深入研究了一下，得出结论我最好实现自己的位缓冲类，尽管我忘记了让我确信 boost 的类永远不会很快的细节（我确实检查了程序集产生）。

我仍然不知道构建位缓冲区/位集/位流或任何您想调用它们的最快方法是什么。一位同事正试图找出这个相关的问题，但在撰写本文时，它仍在等待一个好的答案。

于 2011-04-23T18:29:15.120 回答
0

我写了自己的 bitset 类。我感谢任何改进建议。我将尝试研究 SSE，看看那里是否有任何有用的东西。

通过我非常粗略的基准测试，我获得了 11 倍的性能提升，同时一次添加 6 位。

class fast_bitset
{
public:
    typedef unsigned long block_type;
    static const size_t bits_per_block = sizeof(block_type)*8;

    fast_bitset() 
        : is_open_(true)
        , blocks_(1)
        , space_(blocks_.size()*bits_per_block){}

    void append(const fast_bitset& other)
    {
        assert(!other.is_open_);

        for(size_t n = 0; n < other.blocks_.size()-1; ++n)
            append(other.blocks_[n], bits_per_block);
        append(other.blocks_.back() >> other.space_, bits_per_block - other.space_);
    }

    void append(block_type value, size_t n_bits)
    {
        assert(is_open_);
        assert(n_bits < bits_per_block);

        if(space_ < n_bits)
        {
            blocks_.back() = blocks_.back() << space_;
            blocks_.back() = blocks_.back() | (value >> (n_bits - space_));
            blocks_.push_back(value);
            space_ = bits_per_block - (n_bits - space_);
        }
        else
        {
            blocks_.back() = blocks_.back() << n_bits;
            blocks_.back() = blocks_.back() | value;
            space_ -= n_bits;
        }
    }

    void push_back(bool bit)
    {
        append(bit, 1);
    }

    bool operator[](size_t index) const
    {
        assert(!is_open_);

        static const size_t high_bit = 1 << (bits_per_block-1);
        const size_t block_index = index / bits_per_block;
        const size_t bit_index = index % bits_per_block;
        const size_t bit_mask = high_bit >> bit_index;
        return blocks_[block_index] & bit_mask;
    }

    void close()
    {
        blocks_.back() = blocks_.back() << space_;
        is_open_ = false;
    }

    size_t size() const
    {
        return blocks_.size()*bits_per_block-space_;
    }

    const std::vector<block_type>& blocks() const {return blocks_;}

    class reader
    {
    public:
        reader(const fast_bitset& bitset) 
            : bitset_(bitset)
            , index_(0)
            , size_(bitset.size()){}
        bool next_bit(){return bitset_[index_++];}
        bool eof() const{return index_ >= size_;}
    private:
        const fast_bitset& bitset_;
        size_t index_;
        size_t size_;
    };

private:
    bool is_open_;
    std::vector<block_type> blocks_;
    size_t space_;
};
于 2011-04-23T20:55:36.607 回答