Бла-бла-бла


Когда от основной работы начинает пухнуть голова, я люблю переключить контекст и придумать себе задачку, связанную с улучшение работы какого-нибудь алгоритма, оптимизацией. Так как больше 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++) {
        for (int j = 0; j < nels; j++) {
            values[i * nels + j] = 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


P.S.


Спасибо PkXwmpgN за найденную ошибку в инициализации, за-за неё заполнялся не весь массив тестовых данных, а только его десятая часть. После исправления ошибки время выполнения последнего теста увеличилось на порядок, т.е. ускорение по сравнению с полным перебором — 25 раз, глаза на лоб больше не лезут, но тоже впечатляет ;)

Поделиться с друзьями
-->

Комментарии (11)


  1. PkXwmpgN
    10.11.2016 11:21
    +1

    При начальной инициализации данных, количество элементов массиве 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
        }
    }
    


    1. saterenko
      10.11.2016 12:00

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

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


      1. PkXwmpgN
        10.11.2016 12:25

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


        1. saterenko
          10.11.2016 12:33

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


  1. robert_ayrapetyan
    10.11.2016 17:11

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


    1. saterenko
      10.11.2016 17:23

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


      1. robert_ayrapetyan
        11.11.2016 08:04

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

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

        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%, важно поставить проверку гео после юзерагента, чтоб вообще не проверять ненужные.


        1. saterenko
          11.11.2016 10:27

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

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

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


          1. robert_ayrapetyan
            11.11.2016 18:39

            Да нет, не забыл. Вот ваш оригинальный тест (на 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


            1. saterenko
              11.11.2016 18:56

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


  1. old_bear
    11.11.2016 19:44

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

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