非常に大きな配列のランダムアクセスを最適化する方法はありますか(現在 を使用していますuint8_t
が、何がより良いのかを尋ねています)
uint8_t MyArray[10000000];
配列内の任意の位置の値が
- 0または1のために95%すべてのケースにおいて、
- 2で4%事例、
- 間3そして255他の1%ケースは?
では、この用途に配列よりも優れたものはありますかuint8_t
? 配列全体をランダムな順序でループするには、できるだけ高速にする必要がありますが、これは RAM 帯域幅に非常に大きな負荷をかけるため、複数のスレッドが異なる配列に対して同時にこれを実行すると、現在のところ RAM 帯域幅全体がすぐに飽和状態になります。
5% を除くほぼすべての値が 0 または 1 になることがわかっているのに、このような大きな配列 (10 MB) を持つのは非常に非効率だと感じたので質問しています。配列内のすべての値の 95% が実際には 8 ビットではなく 1 ビットしか必要としない場合は、メモリ使用量がほぼ 1 桁削減されます。これに必要な RAM 帯域幅を大幅に削減し、結果としてランダム アクセスも大幅に高速化する、よりメモリ効率の高いソリューションが必要であるように思われます。
ベストアンサー1
思いつく単純な可能性としては、一般的なケースでは値ごとに 2 ビットの圧縮配列を保持し、(idx << 8) | value)
その他のケースでは値ごとに 4 バイト (元の要素インデックスの場合は 24 ビット、実際の値の場合は 8 ビット) のソートされた配列を保持することです。
値を検索するときは、まず2bpp配列を検索します(O(1))。0、1、または2が見つかった場合は、それが必要な値です。3が見つかった場合は、セカンダリ配列で検索する必要があります。ここでは、バイナリ検索を実行して、索引関心のある部分を 8 左シフトし (O(log(n)、n は小さいので 1% になるはずです)、4 バイトのものから値を抽出します。
std::vector<uint8_t> main_arr;
std::vector<uint32_t> sec_arr;
uint8_t lookup(unsigned idx) {
// extract the 2 bits of our interest from the main array
uint8_t v = (main_arr[idx>>2]>>(2*(idx&3)))&3;
// usual (likely) case: value between 0 and 2
if(v != 3) return v;
// bad case: lookup the index<<8 in the secondary array
// lower_bound finds the first >=, so we don't need to mask out the value
auto ptr = std::lower_bound(sec_arr.begin(), sec_arr.end(), idx<<8);
#ifdef _DEBUG
// some coherency checks
if(ptr == sec_arr.end()) std::abort();
if((*ptr >> 8) != idx) std::abort();
#endif
// extract our 8-bit value from the 32 bit (index, value) thingie
return (*ptr) & 0xff;
}
void populate(uint8_t *source, size_t size) {
main_arr.clear(); sec_arr.clear();
// size the main storage (round up)
main_arr.resize((size+3)/4);
for(size_t idx = 0; idx < size; ++idx) {
uint8_t in = source[idx];
uint8_t &target = main_arr[idx>>2];
// if the input doesn't fit, cap to 3 and put in secondary storage
if(in >= 3) {
// top 24 bits: index; low 8 bit: value
sec_arr.push_back((idx << 8) | in);
in = 3;
}
// store in the target according to the position
target |= in << ((idx & 3)*2);
}
}
あなたが提案したような配列の場合、最初の配列には 10000000 / 4 = 2500000 バイト、2 番目の配列には 10000000 * 1% * 4 B = 400000 バイトが必要になります。つまり、2900000 バイト、つまり元の配列の 3 分の 1 未満になり、最も使用される部分はすべてメモリ内にまとめて保持されるため、キャッシュに適しています (L3 に適合する可能性もあります)。
24 ビットを超えるアドレス指定が必要な場合は、「セカンダリ ストレージ」を微調整する必要があります。これを拡張する簡単な方法は、256 要素のポインタ配列を使用して、インデックスの上位 8 ビットを切り替え、上記のように 24 ビットのインデックス付きソート済み配列に転送することです。
クイックベンチマーク
#include <algorithm>
#include <vector>
#include <stdint.h>
#include <chrono>
#include <stdio.h>
#include <math.h>
using namespace std::chrono;
/// XorShift32 generator; extremely fast, 2^32-1 period, way better quality
/// than LCG but fail some test suites
struct XorShift32 {
/// This stuff allows to use this class wherever a library function
/// requires a UniformRandomBitGenerator (e.g. std::shuffle)
typedef uint32_t result_type;
static uint32_t min() { return 1; }
static uint32_t max() { return uint32_t(-1); }
/// PRNG state
uint32_t y;
/// Initializes with seed
XorShift32(uint32_t seed = 0) : y(seed) {
if(y == 0) y = 2463534242UL;
}
/// Returns a value in the range [1, 1<<32)
uint32_t operator()() {
y ^= (y<<13);
y ^= (y>>17);
y ^= (y<<15);
return y;
}
/// Returns a value in the range [0, limit); this conforms to the RandomFunc
/// requirements for std::random_shuffle
uint32_t operator()(uint32_t limit) {
return (*this)()%limit;
}
};
struct mean_variance {
double rmean = 0.;
double rvariance = 0.;
int count = 0;
void operator()(double x) {
++count;
double ormean = rmean;
rmean += (x-rmean)/count;
rvariance += (x-ormean)*(x-rmean);
}
double mean() const { return rmean; }
double variance() const { return rvariance/(count-1); }
double stddev() const { return std::sqrt(variance()); }
};
std::vector<uint8_t> main_arr;
std::vector<uint32_t> sec_arr;
uint8_t lookup(unsigned idx) {
// extract the 2 bits of our interest from the main array
uint8_t v = (main_arr[idx>>2]>>(2*(idx&3)))&3;
// usual (likely) case: value between 0 and 2
if(v != 3) return v;
// bad case: lookup the index<<8 in the secondary array
// lower_bound finds the first >=, so we don't need to mask out the value
auto ptr = std::lower_bound(sec_arr.begin(), sec_arr.end(), idx<<8);
#ifdef _DEBUG
// some coherency checks
if(ptr == sec_arr.end()) std::abort();
if((*ptr >> 8) != idx) std::abort();
#endif
// extract our 8-bit value from the 32 bit (index, value) thingie
return (*ptr) & 0xff;
}
void populate(uint8_t *source, size_t size) {
main_arr.clear(); sec_arr.clear();
// size the main storage (round up)
main_arr.resize((size+3)/4);
for(size_t idx = 0; idx < size; ++idx) {
uint8_t in = source[idx];
uint8_t &target = main_arr[idx>>2];
// if the input doesn't fit, cap to 3 and put in secondary storage
if(in >= 3) {
// top 24 bits: index; low 8 bit: value
sec_arr.push_back((idx << 8) | in);
in = 3;
}
// store in the target according to the position
target |= in << ((idx & 3)*2);
}
}
volatile unsigned out;
int main() {
XorShift32 xs;
std::vector<uint8_t> vec;
int size = 10000000;
for(int i = 0; i<size; ++i) {
uint32_t v = xs();
if(v < 1825361101) v = 0; // 42.5%
else if(v < 4080218931) v = 1; // 95.0%
else if(v < 4252017623) v = 2; // 99.0%
else {
while((v & 0xff) < 3) v = xs();
}
vec.push_back(v);
}
populate(vec.data(), vec.size());
mean_variance lk_t, arr_t;
for(int i = 0; i<50; ++i) {
{
unsigned o = 0;
auto beg = high_resolution_clock::now();
for(int i = 0; i < size; ++i) {
o += lookup(xs() % size);
}
out += o;
int dur = (high_resolution_clock::now()-beg)/microseconds(1);
fprintf(stderr, "lookup: %10d µs\n", dur);
lk_t(dur);
}
{
unsigned o = 0;
auto beg = high_resolution_clock::now();
for(int i = 0; i < size; ++i) {
o += vec[xs() % size];
}
out += o;
int dur = (high_resolution_clock::now()-beg)/microseconds(1);
fprintf(stderr, "array: %10d µs\n", dur);
arr_t(dur);
}
}
fprintf(stderr, " lookup | ± | array | ± | speedup\n");
printf("%7.0f | %4.0f | %7.0f | %4.0f | %0.2f\n",
lk_t.mean(), lk_t.stddev(),
arr_t.mean(), arr_t.stddev(),
arr_t.mean()/lk_t.mean());
return 0;
}
(コードとデータは常に Bitbucket で更新されます)
上記のコードは、投稿で指定された OP のとおりに分散されたランダム データを 10M 要素の配列に設定し、データ構造を初期化して次の処理を実行します。
- データ構造を使用して1000万要素のランダム検索を実行します
- 元の配列に対しても同じことを行います。
(シーケンシャル検索の場合、配列が常に圧倒的に勝ることに注意してください。これは、最もキャッシュに適した検索であるためです)
最後の 2 つのブロックは 50 回繰り返され、時間が計測されます。最後に、各タイプのルックアップの平均と標準偏差が計算され、スピードアップ (lookup_mean/array_mean) とともに出力されます。
私は上記のコードを-O3 -static
Ubuntu 16.04 の g++ 5.4.0 ( 、いくつかの警告付き) でコンパイルし、いくつかのマシンで実行しました。ほとんどのマシンは Ubuntu 16.04 を実行していますが、一部は古い Linux、一部は新しい Linux を実行しています。この場合、OS はまったく関係ないと思います。
CPU | cache | lookup (µs) | array (µs) | speedup (x)
Xeon E5-1650 v3 @ 3.50GHz | 15360 KB | 60011 ± 3667 | 29313 ± 2137 | 0.49
Xeon E5-2697 v3 @ 2.60GHz | 35840 KB | 66571 ± 7477 | 33197 ± 3619 | 0.50
Celeron G1610T @ 2.30GHz | 2048 KB | 172090 ± 629 | 162328 ± 326 | 0.94
Core i3-3220T @ 2.80GHz | 3072 KB | 111025 ± 5507 | 114415 ± 2528 | 1.03
Core i5-7200U @ 2.50GHz | 3072 KB | 92447 ± 1494 | 95249 ± 1134 | 1.03
Xeon X3430 @ 2.40GHz | 8192 KB | 111303 ± 936 | 127647 ± 1503 | 1.15
Core i7 920 @ 2.67GHz | 8192 KB | 123161 ± 35113 | 156068 ± 45355 | 1.27
Xeon X5650 @ 2.67GHz | 12288 KB | 106015 ± 5364 | 140335 ± 6739 | 1.32
Core i7 870 @ 2.93GHz | 8192 KB | 77986 ± 429 | 106040 ± 1043 | 1.36
Core i7-6700 @ 3.40GHz | 8192 KB | 47854 ± 573 | 66893 ± 1367 | 1.40
Core i3-4150 @ 3.50GHz | 3072 KB | 76162 ± 983 | 113265 ± 239 | 1.49
Xeon X5650 @ 2.67GHz | 12288 KB | 101384 ± 796 | 152720 ± 2440 | 1.51
Core i7-3770T @ 2.50GHz | 8192 KB | 69551 ± 1961 | 128929 ± 2631 | 1.85
結果は...まちまちです!
- 一般的に、これらのマシンのほとんどでは、何らかの高速化が実現されているか、少なくとも同等です。
- 配列が「スマート構造」検索よりも優れている 2 つのケースは、大量のキャッシュがあり、特に忙しくないマシンの場合です。上記の Xeon E5-1650 (15 MB キャッシュ) は夜間ビルド マシンで、現在はまったくアイドル状態です。Xeon E5-2697 (35 MB キャッシュ) は、アイドル状態のときにも高性能計算を行うマシンです。これは理にかなっています。元の配列は巨大なキャッシュに完全に収まるため、コンパクトなデータ構造は複雑さを増すだけです。
- 「パフォーマンス スペクトル」の反対側には、アレイの方がわずかに高速ですが、NAS に搭載されている質素な Celeron があります。このマシンのキャッシュは非常に小さいため、アレイも「スマート構造」もまったく収まりません。キャッシュが十分に小さい他のマシンのパフォーマンスも同様です。
- Xeon X5650 は、かなりビジーなデュアルソケット仮想マシン サーバー上の仮想マシンであるため、ある程度の注意が必要です。名目上は十分な量のキャッシュがあるものの、テスト中にまったく関係のない仮想マシンによって何度もプリエンプトされる可能性があります。