26ビットの符号なし整数の大きな配列

Question

RAMの26ビット変数の大きな配列で作業する必要があります。 32ビットintを使用するには高価です。アクセスは可能な限り速くなければなりません（特に読み取り操作）。
私は以下のスキームに着きました。各26ビットの値は、3つの8ビット値と2ビットに分割されます。

#define N 500000000 
uint8 arr1[N], arr2[N], arr3[N]; 
uint8 arr4[N/4]; 

int read_value(int index) 
{ 
    int a1 = arr1[index];         // bits 0..7 
    int a2 = arr2[index];         // bits 8..15 
    int a3 = arr3[index];         // bits 16..23 
    int a4 = (arr4[index/4] >> (2 * (index % 4))) & 3; // bits 24..25 
    return a1 | (a2 << 8) | (a3 << 16) | (a4 << 24); 
} 

これを行うにはいくつかの方法がありますか？ 27/28/29/30ビットの整数で作業するのにいい方法がありますか？

Answer 1

32ビット整数を使用するには「高価すぎる」と言えば、宇宙的な意味ですか？

あなたがそうだとすれば、私はそこであなたを助ける方法が本当にわかりません。しかし、C/C++の配列は、読み込み速度に関して配列の要素に一定の時間アクセスを提供します（これは、メモリがすでにCPUキャッシュにあると仮定しています;そうでない場合は、より長いです）。したがって、要素0を読み取ることは要素10,000を読み取ることと同じ時間を要する。あなたが持っているコードはこれを遅くするかもしれませんが、私はそれを確実に言うことはできません。

このコードはあなたがしたいことをしなければならないようですが、より多くの領域を占めるにもかかわらず、単純にintの配列を行うのが最も理にかかります。もしこれを絶対にしなければならない場合は、メソッド宣言にinlineを入れて、コンパイラがいつでも展開できるようにしてください。

Answer 2

CPUの演算命令よりもメモリの負荷が大きいので、uint8のような配列は使用しないでください。各要素を読むには何度も費用がかかります。少なくても1つ少ない負荷があるので少なくともuint16の配列を使用してください。

uint16 arr1[N];  // byte 0-15 
uint8 arr2[N];  // byte 16-23 
uint8 arr3[N/4]; // byte 25-26 

これはまだまだ遅いです。速い解決策は、ループ内で一度にすべての13のuint32（または64ビットマシンを実行している場合はuint64）を読み取ってから、16の26ビット整数に抽出します。これらの26ビットintを13個のunint32に格納する方法はたくさんあります。たとえば、各26ビットのintを連続して格納します。

A0 A1 ... A15

または16個の要素のビット0-15、各要素のビット16-23のための次の16のバイト、最後のバイト意志の最初の32のバイトを格納ビット24-25に使用してください。

[0..15] [0..15] ... [0..15] [16-23] [16..23] ... A [16..23] A [24..25] A [24..25] ... A15 [24..25 ]

あなたはテストをしなければならないあなたの場合はt。