5

私のアプリケーションでは、CPU 時間の 20% がビット リーダーによるビット ( ) の読み取りに費やされskipています。次のコードを高速化する方法を知っている人はいますか? 任意の時点で、20 を超える有効なビットは必要ありません (これが、状況によっては を使用できる理由ですfast_skip)。

ビットはビッグ エンディアン順で読み取られるため、バイト スワップが必要になります。

class bit_reader
{   
    std::uint32_t* m_data;
    std::size_t    m_pos;
    std::uint64_t  m_block;

public:
    bit_reader(void* data)
        : m_data(reinterpret_cast<std::uint32_t*>(data))
        , m_pos(0)
        , m_block(_byteswap_uint64(*reinterpret_cast<std::uint64_t*>(data)))
    {
    }

    std::uint64_t value(std::size_t n_bits = 64)
    {               
        assert(m_pos + n_bits < 64);

        return (m_block << m_pos) >> (64 - n_bits);
    }

    void skip(std::size_t n_bits) // 20% cpu time
    {
        assert(m_pos + n_bits < 42);

        m_pos  += n_bits;

        if(m_pos > 31)
        {
            m_block = _byteswap_uint64(reinterpret_cast<std::uint64_t*>(++m_data)[0]);
            m_pos  -= 32;
        }
    }   

    void fast_skip(std::size_t n_bits)
    {
        assert(m_pos + n_bits < 42);
        m_pos  += n_bits;
    }   
};

ターゲット ハードウェアは x64 です。

4

7 に答える 7

2

以前のコメントから、ハフマン/算術符号化されたストリームを JPEG で解凍していることがわかります。

  • skip()value()インライン化できるほど単純です。コンパイラーがシフトレジスターとバッファーポインターをレジスターにずっと保持する可能性があります。ここと呼び出し元で修飾子を使用してすべてのポインターを作成するとrestrict、ハフマンデコードの結果をビットバッファーに書き込まないことをコンパイラーに伝えることで、さらに最適化できるようになります。
  • 各ハフマン/アーティメティック シンボルの平均長は短いため、8 回中 7 回までは 64 ビット シフト レジスタを補充する必要はありません。コンパイラに分岐予測のヒントを与えることを調査します。
  • JPEG ビットストリーム内のシンボルが 32 ビットを超えることはまれです。これにより、さらなる最適化が可能になりますか?
  • 重いパスである非常に論理的な理由の 1 つskip()は、それを頻繁に呼び出していることです。ここでは、すべてのビットではなく、シンボル全体を一度に消費していますよね? シンボルとテーブル ルックアップで先頭の 0 または 1 をカウントすることで実行できる巧妙なトリックがいくつかあります。
  • ストリーム内の次のビットが LSB になるようにシフト レジスタを配置することを検討してください。これにより、シフトが回避されます。value()
于 2012-08-07T22:18:24.867 に答える
1

64 ビットのシフトは絶対にお勧めできません。多くの CPU では、シフトは低速な操作です。コードをバイト アドレッシングに変更することをお勧めします。これにより、最大 8 ビットのシフトが制限されます。

多くの場合、ビット自体は必要ありませんが、ビットが存在するかどうかを確認する必要があります。これは、次のようなコードで実行できます。

    if (data[bit_inx/64] & mask[bit_inx % 64])
    {
        ....
    }
于 2012-08-07T21:38:12.630 に答える
0

これは私が試した別のバージョンですが、パフォーマンスは向上しませんでした。

class bit_reader
{   
public:     
    const std::uint64_t* m_data64;
    std::size_t          m_pos64;
    std::uint64_t        m_block0;
    std::uint64_t        m_block1;


    bit_reader(const void* data)
        : m_pos64(0)
        , m_data64(reinterpret_cast<const std::uint64_t*>(data))
        , m_block0(byte_swap(*m_data64++))
        , m_block1(byte_swap(*m_data64++))
    {
    }

    std::uint64_t value(std::size_t n_bits = 64)
    {               
        return __shiftleft128(m_block1, m_block0, m_pos64)  >> (64 - n_bits);
    }

    void skip(std::size_t n_bits)
    {
        m_pos64 += n_bits;

        if(m_pos64 > 63)
        {
            m_block0 = m_block1;
            m_block1 = byte_swap(*m_data64++);
            m_pos64  -= 64;
        }
    }   

    void fast_skip(std::size_t n_bits)
    {
        skip(n_bits);
    }   
};
于 2012-08-08T13:41:16.397 に答える
0

それが原因であるかどうか、および _byteswap_uint64 の基になる実装がどのように見えるかはわかりませんが、byteorder に関する Rob Pike の記事を読む必要があります。たぶんそれがあなたの答えです。

要約: エンディアン性は、しばしば想定されるほど問題ではありません。また、バイト オーダー スワッピングの実装には、しばしば問題が伴います。しかし、簡単な代替手段があります。

[編集]私はより良い理論を持っています。以下の私のコメントから貼り付けました：エイリアシングかもしれません。64 ビット アーキテクチャは、データを 64 ビットで整列するのが大好きです。整列境界を越えて読み取ると、かなり遅くなります。(++m_data)[0]x64 は 64 ビットでアラインされてreinterpret_castいるuint32_t*ため、それが原因である可能性がありuint64_t*ます。

于 2012-08-07T21:40:31.947 に答える
-2

可能であれば、複数のパスでこれを行うのが最善です。複数の実行を最適化し、違反を減らすことができます。

一般的には、行うのが最善です

const uint64_t * arr = data;

for(uint64_t * i = arr; i != &arr[len/sizeof(uint64_t)] ;i++)
{
     *i = _byteswap_uint64(*i); 
     //no more operations here
}
// another similar for loop

このようなコードは実行時間を大幅に短縮できます

最悪の場合、キャッシュ ミスを最小限に抑え、RAM からのデータの単一ロードを維持するために、100k ブロックの実行のように実行できます。

あなたの場合、ストリーミングの方法でそれを行いますが、低速のデータソースからの低メモリと高速応答を維持するのに適していますが、速度には適していません。

于 2012-08-07T22:21:08.520 に答える