[解決済み] 非常に大きな配列で、95%の確率で値が0か1である場合のランダムアクセスについて、何か最適化はありますか？

質問

非常に大きな配列のランダムアクセスのための最適化は可能でしょうか？ 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ビットの圧縮配列にしておき、1値4バイトに分離する（元の要素のインデックスが24ビット、実際の値が8ビット、つまり (idx << 8) | value) のように）ソートされた配列を保持することです。

値を調べるときは、まず2bpp配列の検索を行います（O(1)）。0、1、2が見つかれば目的の値、3が見つかれば2次配列で探さなければならないことを意味します。ここでは、バイナリ検索で インデックス を探すためにバイナリサーチを実行します (小さな n で O(log(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 バイト、つまり元の配列の 1/3 以下で、最も使用する部分はすべてメモリ内にまとめて保持されるので、キャッシュに適しています (L3 にも合うかもしれません)。

24 ビット以上のアドレス指定が必要な場合は、"secondary storage" を微調整する必要があります。これを拡張する簡単な方法は、インデックスの上位 8 ビットを切り替えて、上記のように 24 ビットインデックス付きのソート配列に転送する 256 要素ポインター配列を持つことです。

クイックベンチマーク

#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で更新されます)

上のコードは、10M要素の配列にOPの投稿で指定されたランダムなデータを投入し、私のデータ構造を初期化した後、次のようになります。

• 私のデータ構造で 10M の要素のランダムなルックアップを実行します。
• は元の配列を通して同じことをします。

(シーケンシャルルックアップの場合、配列は常に巨大な尺度によって勝利することに注意してください、それはあなたができる最もキャッシュに優しいルックアップだからです)

最後に、各検索の平均と標準偏差が計算され、速度向上 (lookup_mean/array_mean) と共に出力されます。

上記のコードを g++ 5.4.0 でコンパイルしてみました ( -O3 -static といくつかの警告) でコンパイルし、いくつかのマシンで実行しました。それらのほとんどは 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

結果は...散々でした!

1. 一般に、これらのマシンのほとんどで、何らかの速度向上が見られるか、少なくとも同程度の速度があります。
2. 上記の Xeon E5-1650 (15 MB キャッシュ) は夜間構築用のマシンで、現在はかなりアイドル状態です。また、Xeon E5-2697 (35 MB キャッシュ) は高性能計算用のマシンで、同様にアイドル状態のときです。これは理にかなっていて、オリジナルの配列は巨大なキャッシュに完全に収まるので、コンパクトなデータ構造は複雑さを増すだけです。
3. パフォーマンス スペクトラムの反対側では、やはり配列の方がわずかに高速ですが、私の NAS に搭載されている控えめな Celeron は、キャッシュが非常に少なく、配列もスマート構造もまったく入りません。十分に小さいキャッシュを持つ他のマシンも同様のパフォーマンスを発揮します。
4. Xeon X5650 は、かなり忙しいデュアル ソケット仮想マシン サーバー上の仮想マシンであるため、公称では十分な量のキャッシュを持っていますが、テストの間、まったく関係のない仮想マシンによって何度も先取りされた可能性があります。