Бла-бла-бла
Когда от основной работы начинает пухнуть голова, я люблю переключить контекст и придумать себе задачку, связанную с улучшение работы какого-нибудь алгоритма, оптимизацией. Так как больше 10 лет я занимаюсь разработкой систем управления рекламой, все мои задачки так же связаны с этой сферой.
В последнее время мои мысли заняты вопросом как увеличить скорость поиска рекламных кампаний по заданным параметрам. Рекламная кампания — это, фактически, набор ограничений, которые надо проверить, чтобы выбрать подходящую под запрос. Пытаясь ускорить полный перебор я дошёл до интринсиков, но достижения нельзя было назвать выдающимися. При этом постоянно было чувство, что я иду не совсем верными путём, что где-то что-то надо перевернуть вверх ногами и скорость увеличится на порядок.
Вчера меня озарило после разговора с Пашей Бейзманом, выступавшим на днях с докладом на HighLoad++. Битовые операции!!! Да, я прекрасно понимаю мощь битовых операций, но я их неправильно готовил 😉 Результаты тестов превзошли мои самые оптимистичные ожидания.
Идея
Один из типов ограничений при выборе кампании — это проверка по вхождению значения в набор. Например, показ кампании может быть ограничен по стране, области, городу, категории и т.п. Первое, что приходит в голову — это дерево со всеми значениями на уровне кампании. Второе — массив значений, если значений в наборе немного (около 10), прямой перебор будет быстре, чем использование деревьев. Для выбора кампании необходимо перебрать все и в каждой из них проверить вхождение заданного значения в набор.
Алгоритм с правильно приготовленными битовыми операциями выглядит следующим образом. Для заданного значения ограничения строим большую битовую маску, размер которой равен количеству кампаний и устанавливаем биты для кампаний, которые старгетированы на данное значение (или нет ограничений заданного типа). Битовые маски помещаем в дерево, где ключом служит значение ограничения. Например, для стран это будет дерево, где ключом является идентификатор страны, а значение — маска с битами, установленными для кампаний, которые можно показывать на эту страну.
С такой структурой очень просто работать. Зная, для какой страны необходимо выбрать кампании, мы выбираем по идентификатору битовую маску и производим операцию AND c масками других ограничений. Очень быстро и красиво.
Тесты
Куда же без тестов производительности… Я тестировал обработку одного ограничения для 1 миллиона кампаний. Для каждой из кампаний было сгенерировано случайным образом ограничение с набором в 10 значений от 0 до 256 (проверки на ошибки выделения памяти и т.п. из кода убраны):
int nels = 10; int campaigns = 1000000; int *values = (int *) malloc(sizeof(int) * campaigns * nels); srand(13); for (int i = 0; i < campaigns; i++) { values[i] = rand() % 256; }
Перебор со значениями в массиве
Пробуем просто перебрать все кампании со всеми ограничениями. Здесь и далее компилируем с опцией -O3.
Тестируем.
clock_t cs, ce; int found_campaigns = 0; int reference = 13; cs = clock(); for (int i = 0; i < campaigns; i++) { for (int j = 0; j < nels; j++) { if (values[i * nels + j] == reference) { found_campaigns++; break; } } } ce = clock(); printf("test #1 bruteforce, found: %d, clocks: %ld, sec: %f\n", found_campaigns, (long) (ce - cs), (double) (ce - cs) / CLOCKS_PER_SEC);
Результат: clocks: 7034, sec: 0.007034.
Перебор со значениями в дереве
Пробуем вместо массива значений ограничения использовать дерево (Judy Arrays).
Pvoid_t *sets = (Pvoid_t) malloc(sizeof(Pvoid_t) * campaigns); memset(sets, 0, sizeof(Pvoid_t) * campaigns); for (int i = 0; i < campaigns; i++) { for (int j = 0; j < nels; j++) { PWord_t pw; JLI(pw, sets[i], values[i * nels + j]); } }
Тестируем.
found_campaigns = 0; cs = clock(); for (int i = 0; i < campaigns; i++) { PWord_t pw; JLG(pw, sets[i], reference); if (pw) { found_campaigns++; } } ce = clock(); printf("test #2 set, found: %d, clocks: %ld, sec: %f\n", found_campaigns, (long) (ce - cs), (double) (ce - cs) / CLOCKS_PER_SEC);
Результат: clocks: 7930, sec: 0.007930.
Перебор 10 значений массива оказался быстрее, чем использование дерева. Тут нет ни чего удивительного, перебор по массиву замечательно утилизирует кеш процессора. Примерное равенство между массивами и деревом было на 12 элементах.
Используем битовые маски
#define SET_BIT(_n, _i) _n[_i / 64] |= 1ULL << (_i % 64) #define CHECK_BIT(_n, _i) _n[_i / 64] & (1ULL << (_i % 64)) PWord_t pw; Pvoid_t pv = (Pvoid_t) 0; int mask_size = sizeof(uint64_t) * (campaigns / 64 + 1); for (int i = 0; i < campaigns; i++) { for (int j = 0; j < nels; j++) { int id = values[i * nels + j]; JLI(pw, pv, id); if (*pw) { uint64_t *mask = (uint64_t *) *pw; SET_BIT(mask, i); } else { uint64_t *mask = (uint64_t *) malloc(mask_size); memset(mask, 0, mask_size); SET_BIT(mask, i); *pw = (Word_t) mask; } } }
Тестируем.
found_campaigns = 0; cs = clock(); JLG(pw, pv, reference); if (pw) { uint64_t *mask = (uint64_t *) *pw; for (int i = 0; i < campaigns; i++) { if (CHECK_BIT(mask, i)) { found_campaigns++; } } } ce = clock(); printf("test #3 bitmaps, found: %d, clocks: %ld, sec: %f\n", found_campaigns, (long) (ce - cs), (double) (ce - cs) / CLOCKS_PER_SEC);
Результат: clocks: 1393, sec: 0.001393.
В 5 раз быстрее чем перебор. Неплохо, но можно лучше.
Ускоряем использование битовых масок
Для ускорения будет использовать встроенную функцию gcc __builtin_ffsll, которая возвращает индекс первого установленого бита.
Тестируем.
found_campaigns = 0; cs = clock(); JLG(pw, pv, reference); if (pw) { uint64_t *mask = (uint64_t *) *pw; for (int i = 0; i < (campaigns / 64 + 1); i++) { uint64_t m = mask[i]; while (m) { int n = __builtin_ffsll(m); m &= ~(1ULL << (n - 1)); found_campaigns++; } } } ce = clock(); printf("test #4 bitmaps 2, found: %d, clocks: %ld, sec: %f\n", found_campaigns, (long) (ce - cs), (double) (ce - cs) / CLOCKS_PER_SEC);
Результат: clocks: 28, sec: 0.000028.
В этом месте мои глаза полезли на лоб. Ускорение в 250 раз по сравнению с полным перебором.
Как работает процессор, какие есть SSE, AVX и тому подобные инструкции, как устроен кеш — эти знания позволяют ускорить работу программы, часто существенно. Но красивый алгоритм может ускорить работу на порядки.
Текст программы можно посмотреть здесь: https://github.com/saterenko/labs/tree/master/bit_limits
ссылка на оригинал статьи https://habrahabr.ru/post/314818/
Добавить комментарий