ビット単位で大きなデータチャンクをループする最速の方法は何ですか

StackOverflow https://stackoverflow.com/questions/418266

質問

バイト単位のバイナリデータのメモリブロックを実行しています。

現在、私は次のようなことをしています：

for (i = 0; i < data->Count; i++)
{   
    byte = &data->Data[i];
    ((*byte & Masks[0]) == Masks[0]) ? Stats.FreqOf1++; // syntax incorrect but you get the point.
    ((*byte & Masks[1]) == Masks[1]) ? Stats.FreqOf1++;
    ((*byte & Masks[2]) == Masks[2]) ? Stats.FreqOf1++;
    ((*byte & Masks[3]) == Masks[3]) ? Stats.FreqOf1++;
    ((*byte & Masks[4]) == Masks[4]) ? Stats.FreqOf1++;
    ((*byte & Masks[5]) == Masks[5]) ? Stats.FreqOf1++;
    ((*byte & Masks[6]) == Masks[6]) ? Stats.FreqOf1++;
    ((*byte & Masks[7]) == Masks[7]) ? Stats.FreqOf1++;
}

マスクの場所：

for (i = 0; i < 8; i++)
{
    Masks[i] = 1 << i;
}

（ループやインライン関数でなんとか高速に処理できなかったので、書きました。）

この最初のループを改善する方法についての提案はありますか？私は少し理解するのにかなり不慣れです。

これはやるべきことのように思えるかもしれません。しかし、私は圧縮アルゴリズムを実装しています。ちょうど一部にアクセスするビットが欲しいのです。

ありがとう！

PS：これはVisual Studio 2008コンパイラに含まれています。そのため、提案がそのコンパイラに適用されるといいでしょう。

PPS：2つのカウントをインクリメントする必要がないことに気付きました。 1つで十分です。次に、最後の合計ビットとの差を計算します。 しかし、それはただ数えることに特有です。本当に早くしたいのはビット抽出です。

編集： 前方に持ってきたルックアップテーブルのアイデアは素晴らしいです。 私はタイトルで間違った質問をしたことを理解しています。 結局、私がしたいことはビットを数えるのではなく、各ビットにできるだけ速くアクセスするからです。

別の編集： データ内の1ビットだけポインタを進めることは可能ですか？

別の編集： これまでのすべての回答をありがとう。

次のステップで実装したいのは、コンテキストを分析しない、洗練されていないバイナリ算術コーダーです。それで、私は今のところ単一ビットにのみ興味があります。最終的にはコンテキスト対応BACになりますが、後で使用します。

1バイトの代わりに4バイトを処理するオプションがあります。しかし、32ビットを超えるループも同様にコストがかかりますね？

役に立ちましたか？

解決

あなたがやろうとしていることを本当に理解していませんでした。ただし、ビットマップのビットにアクセスしたいだけの場合は、次の（テストされていない!!!）関数を使用できます。

#include <stddef.h>

_Bool isbitset(unsigned char * bitmap, size_t idx)
{
    return bitmap[idx / 8] & (1 << (idx % 8)) ? 1 : 0;
}

void setbit(unsigned char * bitmap, size_t idx)
{
    bitmap[idx / 8] |= (1 << (idx % 8));
}

void unsetbit(unsigned char * bitmap, size_t idx)
{
    bitmap[idx / 8] &= ~(1 << (idx % 8));
}

void togglebit(unsigned char * bitmap, size_t idx)
{
    bitmap[idx / 8] ^= (1 << (idx % 8));
}

編集： OKしたがって、上記のランダムアクセス関数を使用するのではなく、1ワードのデータ全体を一度に読み取ります。

好きな符号なし整数型を使用できますが、アーキテクチャのワードサイズに対応する可能性が高いものを選択する必要があります。 stdint.h の uint_fast32_t を使用します：

uint_fast32_t * data = __data_source__;
for(; __condition__; ++data)
{
    uint_fast32_t mask = 1;
    uint_fast32_t current = *data;
    for(; mask; mask <<= 1)
    {
        if(current & mask)
        {
            // bit is set
        }
        else
        {
            // bit is not set
        }
    }
}

内部ループから、ビットを次のように設定できます

*data |= mask;

ビットを設定解除

*data &= ~mask;

そしてビットをトグル

*data ^= mask;

警告：ビッグエンディアンアーキテクチャでは、コードが予期しない動作をする可能性があります！

他のヒント

おそらく最速の方法は、バイト値とそのバイトに設定されているビット数のルックアップテーブルを作成することです。少なくとも、Googleでインタビューしたときの答えでした。

ビット関連のものについては、次のリンクを参照してください。ビット調整ハック

各バイト値（256）をその中の1の数にマップするテーブルを使用します。 （0の数は（8-1の数）です）。次に、バイトを反復処理し、複数のルックアップと比較の代わりに、各バイトに対して単一のルックアップを実行します。例：

int onesCount = 0;
for (i = 0; i < data->Count; i++)
{   
    byte = &data->Data[i];
    onesCount += NumOnes[byte];
}
Stats.FreqOf1 += onesCount;
Stats.FreqOf0 += (data->Count * 8) - onesCount;

事前計算済みのルックアップテーブルを使用できます。例：

static int bitcount_lookup[256] = { ..... } ; /* or make it a global and compute the values in code */

...

for( ... ) 
   byte = ... 
   Stats.FreqOf1 += bitcount_lookup[byte];

32ビット整数の1ビットをカウントする方法を以下に示します（Javaの Integer.bitCount（i）メソッドに基づく）：

unsigned bitCount(unsigned i) {
    i = i - ((i >> 1) & 0x55555555);
    i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
    i = (i + (i >> 4)) & 0x0f0f0f0f;
    i = i + (i >> 8);
    i = i + (i >> 16);
    return i & 0x3f;
}

したがって、データをintにキャストし、4バイト単位で前進できます。

ここでは、単一の32ビット値で簡単に作成しましたが、ビット数に合わせて調整するのは難しくありません。

int ones = 0;
int x = 0xdeadbeef;
for(int y = 0;y < 32;y++)
{
    if((x & 0x1) == 0x1) ones++;
    x = (x >> 1);
}

printf("%x contains %d ones and %d zeros.\n", x, ones, 32-ones);

ただし、プロセスの値を変更することに注意してください。保持する必要があるデータに対してこれを行う場合は、まずそのコピーを作成する必要があります。

__ asmでこれを行うと、おそらくより良い、おそらくより高速な方法になりますが、コンパイラがどれだけうまく最適化できるかについて言うのは難しいです...

検討する各ソリューションには、それぞれに欠点があります。ルックアップテーブルまたはビットシフター（私のような）には、両方とも欠点があります。

ラリー

ttobiass-インライン関数は、あなたが話しているようなアプリケーションでは重要ですが、留意する必要があるものがあることに留意してください。インラインコードのパフォーマンスを CAN することができます。いくつか覚えておいてください。

  • デバッグモードのインラインは存在しません。 （強制しない限り）
  • コンパイラは、適切と思われる関数をインライン化します。多くの場合、関数をインライン化するように指示すると、まったく実行されない場合があります。 __forceinlineを使用している場合でも。インライン化の詳細については、MSDNを確認してください。
  • 特定の関数のみをインライン化することもできます。たとえば、再帰関数をインライン化することはできません。

C / C ++言語のプロジェクト設定とコードの構築方法から最高のパフォーマンスを得ることができます。この時点で、ヒープ操作とスタック操作、呼び出し規則、メモリのアライメントなどを理解することが重要です。

これがあなたの質問に正確に答えているわけではないことはわかっていますが、パフォーマンスと、最高のパフォーマンスを得る方法について言及しています。これらは重要です。

リンクワゴンに参加するには： カウントビット

これが時期尚早な最適化のケースではなく、本当に最後のフェムト秒ごとに絞り出す必要がある場合は、おそらく各バイト値のビットカウントを一度に入力する256要素の静的配列を使用する方が良いでしょう、

  

Stats.FreqOf1 + = bitCountTable [byte]

そしてループが完了したら：

  

Stats.FreqOf0 =（（data-＆gt; Count * 8）-Stats.FreqOf1）

美しいコードには、このためのさまざまなテクニックに関する章全体があります。 （ほとんど）Googleブックで読むことができますここから開始。

ビットを抽出するより高速な方法は次のとおりです。

bitmask= data->Data[i];

while (bitmask)
{
    bit_set_as_power_of_two= bitmask & -bitmask;
    bitmask&= bitmask - 1;
}

ビットセットをカウントするだけの場合、キャッシュごとのLUTは高速ですが、この回答のリンク。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top