嵌套循环遍历数组

Question

有2个非常大的系列元素,第二个比第一个大100倍.对于第一个系列的每个元素,第二个系列中有0个或更多元素.这可以通过2个嵌套循环遍历和处理.但是第一个阵列的每个成员的匹配元素数量的不可预测性使得事情变得非常非常缓慢.

第二系列元素的实际处理涉及逻辑和(&)以及人口计数.

我找不到使用C的好的优化,但是我正在考虑使用内联asm,对第一个系列的每个元素执行rep*mov*或类似操作,然后对第二个系列的匹配字节进行批处理,可能在缓冲区中1MB或者其他东西.但是代码会变得非常混乱.

有人知道更好的方法吗？C首选,但x86 ASM也行.非常感谢!

简化问题的示例/演示代码,第一个系列是"人",第二个系列是"事件",为了清楚起见.(最初的问题实际上是100米和10,000米的条目!)

#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

Answer 1

由于平均每人会获得 100 个项目，因此您可以通过一次处理多个字节来加快处理速度。我稍微重新安排了代码，以便使用指针而不是索引，并将一个循环替换为两个循环：

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 秒。