Быстрые фильтры Блума в C-64bit Ints, высокочастотный цикл Initialize/Query/Destroy

Вы хотите, чтобы это было просто. Поскольку вы имеете дело с небольшим количеством элементов, и они представляют собой 64-битные целые числа (которые быстро сравниваются на 32-битной машине и молниеносно на 64-битной). В качестве первого шага я бы использовал хеш-таблицу из 64 000 элементов. Когда вы вставляете, сделайте 16-битный «хэш» 64-битного целого числа, объединив каждую из 16-битных частей вместе, чтобы получить индекс таблицы. Если это недостаточно быстро, профилируйте его, чтобы узнать, почему.

Это звучит не так сексуально, как делать что-то с фильтрами Блума. Но на самом деле вы имеете дело только с целыми числами размером 8K. Вот код, который я набросал прямо сейчас (не пытался его компилировать). Вероятно, это довольно быстро, если предположить случайное распределение вставленных чисел, и это не сработает, если какая-либо из вставок равна 0.

uint64_t table[65536] = {0};

void clear()
{
    memset(table, 0, sizeof(table));
}

uint16_t hash(uint64_t val)
{
    assert(ele != 0);
    uint16_t *parts = (uint16_t*)&ele;
    uint16_t h = 0x5AA5;
    h = h * 131 + parts[0];
    h = h * 131 + parts[1];
    h = h * 131 + parts[2];
    h = h * 131 + parts[3];
    return h;
}

void insert(uint64_t ele)
{
    uint16_t h = hash(ele);
    while (table[h])
        ++h;
    table[h] = ele;
}

int find(uint64_t ele) 
{
    int res = 0;
    uint16_t h = hash(ele);
    while (table[h] != ele)
    {
        if (!table[h])
            return 0;
        ++h;
    }
    return 1;
}

Вам понадобится лучшее разрешение коллизий, если ваши вставки не распределены случайным образом. Возможно, вы также могли бы придумать лучший метод хеширования.

Если я тебя понимаю:

1. Вы будете реализовывать каждый фильтр Блума как растровое изображение размера N.
2. Вы предполагаете хеш-функцию, которая равномерно распределяет элементы.

Если у вас есть ~ 1000 элементов, вы должны задать размер битового набора фильтра Блума, чтобы был установлен только некоторый допустимый коэффициент загрузки из них, возможно, в среднем 1 из 8, чтобы поддерживать низкий уровень ложных срабатываний пересечения набора. Тем не менее, вы всегда можете получить несколько ложных срабатываний. Например, при пересечении наборов фильтров Блума вы можете получить ложные срабатывания, когда set1 = { e1 } и set2 = { e2 }, e1 != e2, set1 intersect set2 = { }, но bf(set1) interesect bf(set2) <> {}. Обратите внимание, что вы никогда не получите ложноотрицательных результатов — если bf(set1) intersect bf(set2) = {}, то обязательно set1 intersect set2 = {}.

Я думаю, что ваш алгоритм должен формировать BF как для R, так и для W, а затем пересекать их как можно больше битов за раз, как показано в варианте 2 ниже.

Быстрый взлом, ржавый C:

const unsigned N = 1024 * 8;
const unsigned BPW = 8 * sizeof ulong;
typedef unsigned long ulong;
typedef struct BF { ulong bits[N/BPW]; } BF;

unsigned hash(ulong e) { return foo(e) % N; }
void clear(BF* pbf) { memset(pbf->bits, 0, sizeof(pbf->bits)); }
void add(BF* pbf, ulong e) { unsigned h = hash(e); bf.bits[h/BPW] |= 1 << (h%BPW); }
bool hit(BF* pbf, ulong e) { unsigned h = hash(e); return (bf.bits[h/BPW]>>(h%BPW)) & 1; }
bool intersect(BF* pbfResult, BF* pbf1, BF* pbf2) {
    bool empty = TRUE;
    for (unsigned i = 0; i < N/BPW; i++)
        if ((pbfResult->bits[i] = pbf1->bits[i] & pbf2->bits[i]) != 0)
            empty = FALSE;
    return !empty;
}
void intersectRW(unsigned nr, ulong* r, unsigned nw, ulong* w) {
    BF bfR, bfW, bfIntesection;
    unsigned i;

    clear(&bfR);
    for (i = 0; i < nr; i++)
         add(&bfR, r[i]);

    // variant 1: enumerate elements of W that hit in BF(R)
    for (i = 0; i < nw; i++)
         if (hit(&bfR, w[i]))
             ... w[i] ...

    // variant 2: determine if intersection of BFs is empty and get intersection BF
    clear(&bfW);
    for (i = 0; i < nw; i++)
         add(&bfW, w[i]);
    bool any = intersect(&bfIntersection, &bfR, &bfW);
    ...
}

Ожидаемое время работы?

1. Каждый вызов инициализирует 3 BF по 1 КБ, например. 128 улонгов, и эти маленькие растровые изображения находятся в TOS и должны легко помещаться в L1$, и во всяком случае иметь большую пространственную локальность;
2. добавляет 100-1000 элементов в bfR, например. ~1000 встроенных вызовов add, некоторые битовые сдвиги и сохранения;
3. хит тестирует 100-1000 элементов bfR например. ~1000 встроенных вызовов hit, несколько битовых сдвигов, масок, тестов;
4. или вариант 2, выполняет поэлементное И только для ~ 128 пар улонгов

(Обратите внимание, конечно, что все / и % в приведенном выше коде оптимизированы для сдвигов и масок.)

Всего это может быть несколько десятков тысяч инструкций и несколько тысяч обращений к кешу L1 или L2; с машиной с частотой цикла 2 ГГц я был бы удивлен, если бы после прогрева это заняло более нескольких мс.

Что касается хэш-функций, то вы не сказали нам о распределении этих 64-битных элементов. Если они уже хорошо распределены, вы можете просто свернуть 64-битные до 16-битных с помощью пары сдвигов, xors и маски.

* Любопытный факт сегодняшнего дня — мелкозернистая функция «минимальной перестройки» MS VC++ 4.0 (http://msdn.microsoft.com/en-us/library/kfz8ad09(VS.80).aspx) зависит от блума фильтров в изобилии, но в то время мы никогда не слышали о фильтрах Блума. Скорее, мы думали, что изобрели новый набор данных со структурой данных вероятностного теста на принадлежность... *

Как вы думаете?

Удачного взлома!

Подождите, я забыл упомянуть:

1. Излишне, но вы можете ускорить операцию очистки и пересечения, используя векторные SIMD-инструкции (например, SSE).
2. Вы можете воспользоваться другими свойствами данных. Например, если есть некоторое сходство между массивами R и W каждого вызова, вы можете превратить алгоритм грубой силы в инкрементный алгоритм, хотя вам, возможно, придется использовать подсчитывающие фильтры Блума.
3. В зависимости от коэффициента загрузки и повторяемости самих элементов вам может не понадобиться очищать растровые изображения на каждой итерации. Вам нужно очистить их только тогда, когда вы, наконец, получите непустое пересечение (затем перезапустите add() и intersect().)
4. Размер вашей задачи здесь не нужен, но если бы у вас были миллионы элементов, вы могли бы разделить входные списки R и W на подсписки, передать их нескольким ядрам, построить частные копии BF для R и W, а затем свернуть ( ИЛИ) BF(R) и BF(W) вместе.

У вас есть относительно небольшое количество целых чисел и 3 мс для их обработки.

Достаточно ли быстр ваш процессор, чтобы сделать это простым и отсортировать оба списка? Сортировка должна быть быстрой, так как все удобно помещается в кэш. Просмотр двух списков для поиска пересечения выполняется довольно быстро, и вам никогда не придется беспокоиться о ложных срабатываниях, как при использовании фильтра Блума.