Оптимизация поиска при выборе кампании

[PkXwmpgN]

При начальной инициализации данных, количество элементов массиве 10 миллионов

int nels = 10;
int campaigns = 1000000;
int *values = (int *) malloc(sizeof(int) * campaigns * nels);

Инициализируются, только первый миллион

for (int i = 0; i < campaigns; i++) {
    values[i] = rand() % 256;
}

Можете пояснить ваш первый тест с массивом. Зачем там, два цикла и 10 миллионов операций умножения и сложения?

Почему не так, например

for(int i = 0, size = compaign * nels; i < size; ++i)
{
    if(values[i] == references)
    {
        // если нужен индекс компании i / nels
        // если нужен индекс ограничения i % nels
    }
}

[saterenko]

По инициализации я ошибся, исправил, спасибо.

По первому тесту главный момент — это break во внутреннем цикле, что позволяет выйти из цикла при нахождении нужного значения и не перебирать все. Попробовал полный перебор, как вы предложили, время увеличилось в 2 раза.

[PkXwmpgN]

А вы с -O3 собрали? И еще вопрос, вы запускаете тесты все сразу друг за другом из одной прогаммы?

[saterenko]

Да, с опцией -O3. Да, все тесты последовательно в одной программе. Собственно вот программа: https://github.com/saterenko/labs/blob/master/bit_limits/test.c

[robert_ayrapetyan]

Вы всегда так код пишите (int-ы, uint64_t и константы (64) в одной функции)?

[saterenko]

Не могу сказать, у меня нет статистики за всё время, пока я программирую на C ))) Можно более конкретный вопрос, что именно тут не устроило, учитывая, что это одноразовая программа для проведения тестов, где int-а заведомо достаточно, uint64_t оптимален для хранения битовых масок (если не заморачиваться SSE, AVX и т.п.), а использование 64 вместо sizeof(uint64_t) * 8 ни чем не грозит, потому как мы используем именно 64-битное число?

[robert_ayrapetyan]

Окончательно проснувшись понял, что коммент был не в тему, извините…

Перенес последний тест в начало, чтоб ничего не влияло, но и тут у меня он всегда возвращает:

test #4 bitmaps 2, found: 382858, clocks: 0, sec: 0.000000
(это на 10 млн. кампаний)

Только на 50 млн. появлятся:
test #4 bitmaps 2, found: 1919263, clocks: 1, sec: 0.007812

Главное потом вовремя остановить, дважды система (16Гб памяти) выедала весь своп и приходилось кнопкой действовать.

Добавлю еще, что у нас похожая задача, и важно соблюсти последовательность проверок. Например, по юзерагенту фильруются, допустим, 45% кампаний, а по гео — 10%, важно поставить проверку гео после юзерагента, чтоб вообще не проверять ненужные.

[saterenko]

Видимо вы перенесли тест, а заполнение масок перенести забыли. Я убрал первые три теста, на 1М записей показывает:

test #4 bitmaps 2, found: 38565, clocks: 172, sec: 0.000172

В случае с битовыми масками последовательность проверок не имеет значения, потому как для каждой проверки надо будет провести операцию AND по всей маске. Но не все операции можно реализовать через битовые маски, поэтому имеет смысл сначала провести все возможнные проверки через них, а потом остальные, например, те же проверки по юзерагенту. Это уже зависит от ресурсоёмкости каждой проверки.

[robert_ayrapetyan]

Да нет, не забыл. Вот ваш оригинальный тест (на 1 млн.):
test #1 bruteforce, found: 38281, clocks: 1, sec: 0.007812
test #2 set, found: 38281, clocks: 4, sec: 0.031250
test #3 bitmaps, found: 38281, clocks: 0, sec: 0.000000
test #4 bitmaps 2, found: 38281, clocks: 0, sec: 0.000000

Вот на 10 млн.:
test #1 bruteforce, found: 382858, clocks: 10, sec: 0.078125
test #2 set, found: 382858, clocks: 31, sec: 0.242188
test #3 bitmaps, found: 382858, clocks: 1, sec: 0.007812
test #4 bitmaps 2, found: 382858, clocks: 0, sec: 0.000000

И только на 50 млн. появляется отличная от нуля цифра:
test #4 bitmaps 2, found: 1919263, clocks: 1, sec: 0.007812

[saterenko]

Вот только последний тест: https://github.com/saterenko/labs/blob/master/bit_limits/test2.c
Результат:
test #4 bitmaps 2, found: 38565, clocks: 170, sec: 0.000170

[old_bear]

> Как работает процессор, какие есть SSE, AVX и тому подобные инструкции, как устроен кеш — эти знания позволяют ускорить работу программы, часто существенно. Но красивый алгоритм может ускорить работу на порядки.

Может я что-то не так понял, но похоже что __builtin_ffsll компилируется в довольно известную в узких кругах asm-инструкцию bsf. Так что тут тоже речь идёт про знание того, как работает процессор, которое и помогает выбирать оптимальный алгоритм.