Быстрые фильтры цветка в C-64-битных Ints, High Frequency Initialize/Query/Destroy cyle

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

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

Каждые 50 мс я получаю два набора (W, R) 64-битных int. Мне нужно найти пересечение между 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 ответа

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

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

******** table[65536] = {0};
void clear()
{
 memset(table, 0, sizeof(table));
}
uint16_t hash(******** 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(******** ele)
{
 uint16_t h = hash(ele);
 while (table[h])
 ++h;
 table[h] = ele;
}
int find(******** ele) 
{
 int res = 0;
 uint16_t h = hash(ele);
 while (table[h] != ele)
 {
 if (!table[h])
 return 0;
 ++h;
 }
 return 1;
}

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


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

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

Если у вас есть ~ 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);
 ...
}

Ожидаемое время выполнения?

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

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

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

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

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

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

Счастливый взлом!

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

  • Overkill, но вы можете ускорить операцию очистки и пересечения с помощью векторных инструкций SIMD (например, SSE).
  • Возможно, вы сможете использовать другие свойства данных. Например, если есть какое-либо сходство между каждым массивом вызова R и W, вы можете превратить алгоритм грубой силы в инкрементный алгоритм, хотя вам, возможно, придется использовать счетные фильтры цветения.
  • В зависимости от коэффициента загрузки и повторяемости самих элементов вам может не понадобиться очищать растровые изображения на каждой итерации. Вам нужно только очистить их, когда вы, наконец, получите непустое пересечение (затем перезапустите add() s и intersect().)
  • Ваш размер проблемы здесь не нужен, но если у вас есть миллионы элементов, вы можете разделить входные списки R и W на подсписок, передать их на несколько ядер, создать частные копии BF для R и W, затем сверните (OR) BF (R) s и BF (W) s вместе.


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

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

licensed under cc by-sa 3.0 with attribution.