5

2 つの非常に大きな一連の要素があり、2 番目は最初の 100 倍の大きさです。最初の系列の各要素に対して、2 番目の系列には 0 個以上の要素があります。これは、2 つのネストされたループで走査および処理できます。しかし、最初の配列の各メンバーに一致する要素の量が予測できないため、処理が非常に遅くなります。

2 番目の一連の要素の実際の処理には、論理 AND (&) と人口カウントが含まれます。

Cを使用して適切な最適化を見つけることができませんでしたが、最初のシリーズの各要素に対してインラインasmを実行し、rep * mov *などを実行してから、おそらく次のバッファーで、2番目のシリーズの一致するバイトのバッチ処理を行うことを検討しています1MBとか。しかし、コードはかなり厄介になります。

誰かがより良い方法を知っていますか? C が優先されますが、x86 ASM も OK です。どうもありがとう！

問題を単純化したサンプル/デモ コード。わかりやすくするために、最初のシリーズは「人」、2 番目のシリーズは「イベント」です。(元の問題は実際には 100m と 10,000m のエントリです!)

#include <stdio.h>
#include <stdint.h>

#define PEOPLE 1000000    //   1m
struct Person {
    uint8_t age;   // Filtering condition
    uint8_t cnt;   // Number of events for this person in E
} P[PEOPLE]; // Each has 0 or more bytes with bit flags

#define EVENTS 100000000  // 100m
uint8_t P1[EVENTS]; // Property 1 flags
uint8_t P2[EVENTS]; // Property 2 flags

void init_arrays() {
    for (int i = 0; i < PEOPLE; i++) { // just some stuff
        P[i].age = i & 0x07;
        P[i].cnt = i % 220; // assert( sum < EVENTS );
    }
    for (int i = 0; i < EVENTS; i++) {
        P1[i]    = i % 7;  // just some stuff
        P2[i]    = i % 9;  // just some other stuff
    }
}

int main(int argc, char *argv[])
{
    uint64_t   sum = 0, fcur = 0;

    int age_filter = 7; // just some

    init_arrays();      // Init P, P1, P2

    for (int64_t p = 0; p < PEOPLE ; p++)
        if (P[p].age < age_filter)
            for (int64_t e = 0; e < P[p].cnt ; e++, fcur++)
                sum += __builtin_popcount( P1[fcur] & P2[fcur] );
        else
            fcur += P[p].cnt; // skip this person's events

    printf("(dummy %ld %ld)\n", sum, fcur );

    return 0;
}

gcc -O5 -march=native -std=c99 test.c -o test
4

7 に答える 7

4

平均して 1 人あたり 100 アイテムを取得するため、一度に複数のバイトを処理することで処理を高速化できます。インデックスの代わりにポインターを使用するためにコードを少し再配置し、1 つのループを 2 つのループに置き換えました。

uint8_t *p1 = P1, *p2 = P2;
for (int64_t p = 0; p < PEOPLE ; p++) {
    if (P[p].age < age_filter) {
        int64_t e = P[p].cnt;
        for ( ; e >= 8 ; e -= 8) {
            sum += __builtin_popcountll( *((long long*)p1) & *((long long*)p2) );
            p1 += 8;
            p2 += 8;
        }
        for ( ; e ; e--) {
            sum += __builtin_popcount( *p1++ & *p2++ );
        }
    } else {
        p1 += P[p].cnt;
        p2 += P[p].cnt;
    }
}

私のテストでは、これによりコードが 1.515 秒から 0.855 秒に高速化されました。

于 2012-11-14T04:56:30.280 に答える
2

ニールによる答えは、年齢でソートする必要はありません。ところで、これは良い考えです -

2 番目のループに穴がある場合 (そのアイデアをサポートするために元のソース コードを修正してください)、一般的な解決策は次のcumsum[n+1]=cumsum[n]+__popcount(P[n]&P2[n]);
とおりです 。sum+=cumsum[fcur + P[p].cnt] - cumsum[fcur];

いずれにせよ、計算上の負担は EVENTS*PEOPLE ではなく、単に EVENTS の順序のようです。いずれにしても、条件を満たしている連続したすべての人に対して内部ループを呼び出すことにより、何らかの最適化を行うことができます。


sums (_popcounts(predicate[0..255]))実際に最大 8 個の述語がある場合、すべてのfor each people を個別の配列 C[256][PEOPLE]に事前計算することは理にかなっています。これはメモリ要件 (ディスク上?) を約 2 倍にしますが、検索を 10GB+10GB+...+10GB (8 つの述語) から 200MB の 1 つのストリーム (16 ビット エントリを想定) にローカライズします。

p(P[i].age < condition && P[i].height < cond2) の確率によっては、累積合計を計算する意味がなくなる場合があります。多分そうでないかもしれません。おそらく、一度に 8 人か 16 人の SSE 並列処理だけで十分でしょう。

于 2012-11-13T19:15:02.030 に答える
2

まったく新しいアプローチは、ROBDDを使用して各人物/各イベントの真理値表をエンコードすることです。まず、イベント テーブルが非常にランダムでない場合、またはビッグナム乗算の真理値表などの病理学的関数で構成されていない場合、最初に関数の圧縮を達成し、次に真理値表の算術演算を圧縮形式で計算できます。 . 各サブツリーはユーザー間で共有でき、2 つの同一のサブツリーの各算術演算は 1 回だけ計算する必要があります。

于 2012-11-14T06:44:03.533 に答える
1

サンプル コードが問題を正確に反映しているかどうかはわかりませんが、次のように書き直すことができます。

for (int64_t p = 0; p < PEOPLE ; p++)
    if (P[p].age < age_filter)
        fcur += P[p].cnt;

for (int64_t e = 0; e < fcur ; e++)
    sum += __builtin_popcount( P1[e] & P2[e] );
于 2012-11-11T00:08:49.197 に答える
0

私は gcc -O5 について知りません (ここには文書化されていないようです)、私の gcc 4.5.4 で gcc -O3 here とまったく同じコードを生成するようです (ただし、比較的小さなコード サンプルでのみテストされています)。

達成したい内容によっては、-O3 は -O2 より遅くなる場合があります。

あなたの問題と同様に、実際のアルゴリズムよりもデータ構造について考えることをお勧めします。データが便利な方法で表現されていない限り、適切なアルゴリズム/コードの最適化で問題を解決することに集中するべきではありません。

単一の基準（ここでは、例では年齢）に基づいて大量のデータをすばやく切り取りたい場合は、ソートされたツリーのバリアントを使用することをお勧めします。

于 2012-11-13T16:59:42.370 に答える
0

ブランチの予測ミス (他の回答では見られない) に取り組むために、コードは次のようになります。

#ifdef MISPREDICTIONS
if (cond)
    sum += value
#else
mask = - (cond == 0);  // cond: 0 then -0, binary 00..; cond: 1 then -1, binary 11..
sum += (value & mask); // if mask is 0 sum value, else sums 0
#endif

データの依存関係があるため、完全に無料というわけではありません (スーパースカラー CPU を考えてください)。しかし、ほとんど予測不可能な状況では通常、10 倍のブーストが得られます。

于 2012-11-14T14:05:23.860 に答える
0

実際のデータ (年齢、カウントなど) が実際に 8 ビットである場合、計算にはおそらく多くの冗長性があります。この場合、処理をルックアップ テーブルに置き換えることができます。8 ビット値ごとに 256 の可能な出力があり、計算の代わりにテーブルから計算されたデータを読み取ることができる場合があります。

于 2012-11-14T05:15:56.510 に答える