7

各ビットを 8 回繰り返してanunsigned charを anに膨らませたいと思います。uint64_t例えば

char -> uint64_t
0x00 -> 0x00
0x01 -> 0xFF
0x02 -> 0xFF00
0x03 -> 0xFFFF
0xAA -> 0xFF00FF00FF00FF00

現在、ビットが設定されているかどうかをテストするためにビットシフトを使用して、これを達成するために次の実装を行っています。

#include <stdint.h>
#include <inttypes.h>   

#define BIT_SET(var, pos) ((var) & (1 << (pos)))

static uint64_t inflate(unsigned char a)
{
    uint64_t MASK = 0xFF;
    uint64_t result = 0;
    for (int i = 0; i < 8; i++) {
        if (BIT_SET(a, i))
            result |= (MASK << (8 * i));    
    }

    return result;
}

しかし、私は C にかなり慣れていないので、このように個々のビットをいじることで、これを行うためのより良い (つまり、より効率的な) 方法があるのではないかと少し考えが変わります。

編集
して追加 OK、テーブル ルックアップ ソリューションを試した後の結果を次に示します。ただし、ルーチンを直接テストしたのではなく、より大きな関数 (正確にはバイナリ行列の乗算) の一部としてテストしたため、結果がどうなるかに影響した可能性があることに注意してください。したがって、私のコンピューターで、100 万の 8x8 行列を乗算し、次のようにコンパイルすると:

  gcc -O2 -Wall -std=c99 foo.c

私は得た

./a.out original
real    0m0.127s
user    0m0.124s
sys     0m0.000s

./a.out table_lookup
real    0m0.012s
user    0m0.012s
sys     0m0.000s

したがって、少なくとも私のマシン (言及すべき仮想マシン 64 ビット Linux Mint) では、テーブル ルックアップ アプローチは約 10 倍のスピードアップを提供するように見えるので、それを答えとして受け入れます。

4

8 に答える 8

7

効率を求めている場合は、ルックアップ テーブルを使用します。256 エントリの静的配列で、それぞれが必要な結果を既に保持しています。上記のコードを使用して生成できます。

于 2013-01-11T09:53:12.153 に答える
6

一部のアーキテクチャ (SSE、Neon) では、このタスクを高速化できる、またはこれを実行するように設計された高速ベクトル操作があります。特別な指示がなければ、推奨されるルックアップ テーブル アプローチは、最も高速で最も移植性があります。

2k サイズが問題になる場合は、並列ベクトル算術演算をシミュレートできます。

static uint64_t inflate_parallel(unsigned char a) {
  uint64_t vector = a * 0x0101010101010101ULL;
  // replicate the word all over qword
  // A5 becomes A5 A5 A5 A5 A5 A5 A5 A5
  vector &= 0x8040201008040201;  // becomes 80 00 20 00 00 04 00 01 <-- 
  vector += 0x00406070787c7e7f;  // becomes 80 40 80 70 78 80 7e 80
                                 // MSB is correct
  vector = (vector >> 7) & 0x0101010101010101ULL;  // LSB is correct
  return vector * 255;                             // all bits correct
}

EDIT : 2^31 反復 (ループ評価を軽減するための 4 回の展開)

time ./parallel            time ./original            time ./lookup
real        0m2.038s       real       0m14.161s       real      0m1.436s
user        0m2.030s       user       0m14.120s       user      0m1.430s
sys         0m0.000s       sys        0m0.000s        sys       0m0.000s

これは約 7 倍のスピードアップですが、ルックアップ テーブルでは約 10 倍のスピードアップが得られます。

于 2013-01-11T10:39:16.880 に答える
3

コードの最適化について心配する前に、コードの機能をプロファイリングする必要があります。

ローカルのコンパイラでは、コードは完全にインライン化され、展開されて、値が不明な場合は8つの定数テスト+または命令に変換され、コンパイル時に値が既知の場合は定数に変換されます。いくつかのブランチを削除することで、おそらくわずかに改善することができますが、コンパイラーはそれ自体で妥当な仕事をしています。

その場合、ループを最適化することは少し無意味です。テーブルルックアップの方が効率的かもしれませんが、コンパイラー自体が最適化を行うのを妨げる可能性があります。

于 2013-01-11T10:03:25.553 に答える
2

これに 256 * 8 = 2kB のメモリを費やす場合 (つまり、メモリに関しては効率が低下しますが、必要な CPU サイクルに関してはより効率的になります)、最も効率的な方法は、ルックアップ テーブルを事前に計算することです。 :

static uint64_t inflate(unsigned char a) {
    static const uint64_t charToUInt64[256] = {
        0x0000000000000000, 0x00000000000000FF, 0x000000000000FF00, 0x000000000000FFFF,
        // ...
    };

    return charToUInt64[a];
}
于 2013-01-11T09:59:02.377 に答える
1

@Aki answer と同じテーマのバリエーション。それらのいくつかはここでより優れていますが、コンパイラとターゲットマシンに依存する場合があります (データの依存関係が少ないため、より多くの作業を行うとしても、Aki の機能するスーパースカラー プロセッサにより適しているはずです)。

// Aki Suuihkonen: 1.265
static uint64_t inflate_parallel1(unsigned char a) {
  uint64_t vector = a * 0x0101010101010101ULL;
  vector &= 0x8040201008040201;
  vector += 0x00406070787c7e7f;
  vector = (vector >> 7) & 0x0101010101010101ULL; 
  return vector * 255;
}

// By seizet and then combine: 1.583
static uint64_t inflate_parallel2(unsigned char a) {
    uint64_t vector1 = a * 0x0002000800200080ULL;
    uint64_t vector2 = a * 0x0000040010004001ULL;
    uint64_t vector = (vector1 & 0x0100010001000100ULL) | (vector2 & 0x0001000100010001ULL);
    return vector * 255;
}

// Stay in 32 bits as much as possible: 1.006
static uint64_t inflate_parallel3(unsigned char a) {
    uint32_t vector1 = (( (a & 0x0F)       * 0x00204081) & 0x01010101) * 255;
    uint32_t vector2 = ((((a & 0xF0) >> 4) * 0x00204081) & 0x01010101) * 255;
    return (((uint64_t)vector2) << 32) | vector1;
}

// Do the common computation in 64 bits: 0.915
static uint64_t inflate_parallel4(unsigned char a) {
    uint32_t vector1 =  (a & 0x0F)       * 0x00204081;
    uint32_t vector2 = ((a & 0xF0) >> 4) * 0x00204081;
    uint64_t vector = (vector1 | (((uint64_t)vector2) << 32)) & 0x0101010101010101ULL;
    return vector * 255;
}

// Some computation is done in 64 bits a little sooner: 0.806
static uint64_t inflate_parallel5(unsigned char a) {
    uint32_t vector1 = (a & 0x0F) * 0x00204081;
    uint64_t vector2 = (a & 0xF0) * 0x002040810000000ULL;
    uint64_t vector = (vector1 | vector2) & 0x0101010101010101ULL;
    return vector * 255;
}
于 2013-01-11T12:51:42.690 に答える
0

2 つのマイナーな最適化:
1 つは入力のビットをテストするため (a は破棄されますが、これは問題ではありません)
、もう 1 つはマスクをシフトするためです。

static uint64_t inflate(unsigned char a)
{
    uint64_t mask = 0xFF;
    uint64_t result = 0;
    for (int i = 0; i < 8; i++) {
        if (a & 1)
            result |= mask;
        mask <<= 8;    
        a >>= 1;
    }

    return result;
}

おそらく、「for (int i = 0; i < 8; i++)」ループを「while (a)」ループに置き換えることもできます。ただし、これは右シフト a >>=1 が符号なしで機能する場合にのみ機能します (C 標準では、コンパイラが符号付きまたは符号なしで実行できることを知っている限り)。そうしないと、場合によっては無限ループになります。

編集:
結果を確認するために、両方のバリアントを でコンパイルしましgcc -std=c99 -S source.cた。結果として得られるアセンブラーの出力を一目見ただけで、上記の最適化によって約 2 倍の結果が得られることがわかります。1/3 ビューアの指示。そのほとんどはループ内にあります。

于 2013-01-11T09:57:30.637 に答える