Фильтры быстрого цветения в C-64bit Ints, высокочастотная инициализация / запрос / уничтожение cyle - PullRequest
3 голосов
/ 04 декабря 2010

Мне нужна реализация фильтра Блума, для части большого проекта. Весь проект находится на C (и только на C! Нет C ++), и, к сожалению, я не смог найти ни одной достойной реализации фильтра Блума на основе C (за исключением реализации проверки концепции).

Требования к фильтру Блума:
1. Модуль, содержащий фильтр Блума, работает каждые 50 мс .
Весь модуль должен завершиться в течение 5-6 мс,
это означает, что весь код фильтра Блума должен быть выполнен менее чем за 3 мс .
2. Элементы являются 64-битными целыми числами
3. Всего у меня менее 8 тыс. Элементов (включая вставки / запросы)
Обычный случай - несколько сотен вставок в фильтр и 1000-1500 запросов.

Каждые 50 мс я получаю два набора (W, R) 64-битных целых. Мне нужно найти пересечение между W & R, полученным в эту эпоху (IOW, фильтр Блума должен начинаться заново для каждой эпохи). Код ниже показывает общий поток управления

sleep(50ms)
...module code..
clear(bloomfilter) /* basically a memset(0) on bloomfilter bitmap */
W = getListW()
for each entry in W
  insert(bloomfilter, entry)
R = getListR()
for each entry in R
   if (present(bloomfilter, entry))
      ..do something with entry..
..rest of module code..

Теперь я видел несколько работ, в которых утверждается, что они выполняют операции быстрого фильтра Блума для очень больших наборов данных. Но мои требования разные. Мне нужен быстрый посев (вставка W) и быстрый запрос. Хэш-функции являются еще одной проблемой. Я не могу позволить себе такие хеш-функции, как SHA1, из-за нехватки времени.

Ответы [ 3 ]

3 голосов
/ 04 декабря 2010

Вы хотите, чтобы все было просто.Поскольку вы имеете дело с небольшим количеством элементов, и они представляют собой 64-битные целые числа (которые быстро сравниваются на 32-битной машине и молниеносно на 64-битной).В качестве первого снимка я бы выбрал хеш-таблицу из 64К элементов.Когда вы вставляете, сделайте 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;
}

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

2 голосов
/ 04 декабря 2010

Если я вас понимаю:

  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 ulongs, и эти маленькие растровые изображения находятся на TOS и должны легко вписываться в L1 $, и, во всяком случае, иметь большую пространственную локализацию;
  2. добавляет 100-1000 элементов к BFR, например. ~ 1000 встроенных вызовов add, некоторых сдвигов и хранилищ;
  3. проверяет попадание 100-1000 элементов BFR, например ~ 1000 встроенных вызовов попаданий, некоторых битовых сдвигов, масок, тестов;
  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) s и BF (W) s вместе.
0 голосов
/ 08 мая 2011

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

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

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...