SIMD без SIMD, или ищем на С почти в два раза быстрее чем на С++

Прочитал статьи про комбинаторную кодогенерацию на С++ в контексте линейного поиска в базе данных: Возможности оптимизации в языках C и C++ и Скорости разработки и исполнения не достижимые на С. Попробуем достигнуть скоростей разработки и исполнения на C?

После того, как я запустил компиляцию С++ кода из второй статьи, мне стало интересно — успею ли я написать аналог на С, который будет работать быстрее, пока код… компилируется? Не успел, код скомпилировался через 5 минут, а аналог на С писался все 15.

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

Задача решается в два этапа:
1. Давайте научимся заменять операции сравнения чем-нибудь более простым, например сложением и битовыми операциями
2. Давайте научимся комбинировать несколько операций из 1 вместе, бесплатно.

Итак, пункт первый. Есть значение b и диапазон [a, c], надо посчитать a <= b и b <= c. Без сравнений. Пусть для определенности a, b, c неотрицательные и помещаются в 7 бит — т.е. от 0 до 127.

Нетрудно заметить, что выражение (128 — a) + b гарантированно помещается в 8 бит; более того, 8-ой бит результата равен 1 тогда и только тогда когда a <= b. Например, если a = 0, то в значении выражения 128 + b 8-ой бит всегда 1; если a = 1, то в значении выражения 127 + b 8-ой бит равен 1 если b равен 0 или 1, и так далее.

Результат сравнения b и с получается почти так же — выражение (127 — c) + b помещается в 8 бит, и 8-ой бит результата равен 0 тогда и только тогда когда b <= c.

Итак, ура! Вместо того, чтобы считать a <= b, мы с вами будем считать ((128 — a) + b) & 128. Казалось бы, зачем?..

Пункт второй. У битовых операций есть прекрасное свойство, которое все знают — одной инструкцией можно сделать сразу очень много однотипных битовых операций. Год кажется уже 2013, уже даже процессор без SSE днем с огнем не сыщешь, так что будем считать что уж 64-то бита — точно можно.

Не все знают, что похожее прекрасное свойство есть и у арифметических операций — если быть аккуратным и предварительно подготовить данные. Например, пусть у нас есть 32-битная арифметика, и 4 пары семибитных беззнаковых чисел. Смотрите, как их можно сложить:

1. Добавляем к каждому числу лишний старший бит, который инициализируем нулем:
aaaaaaa -> 0aaaaaaa

2. 4 группы по 8 битов записываем последовательно:
0aaaaaaa0bbbbbbb0ccccccc0ddddddd

3. Два получившихся 32-битных числа складываем; получаем 4 8-битных результата сложения в 32-битном числе.

4. Если хочется 7-битной арифметики, то биты переноса можно обнулить.

Сразу становится ясно, что нужно сделать в искомой задаче:

1. Выкладываем данные в 64-битном регистре так, чтобы у каждого значения был лишний старший бит. Случайно получилось так что пример из статьи влезает с такой укладкой в 62 бита — осталось место для одного однобитного поля!

struct T_cash_account_row {     unsigned reserved0:1;      unsigned code:20;			// 0 - 1000000     unsigned carry_code:1;  	unsigned gender:1;			// 0 - 1     unsigned carry_gender:1;  	unsigned age:7;			    // 0 - 100	     unsigned carry_age:1;      unsigned reserved1:1;  	unsigned amount_of_money:20;// 0 - 1000000     unsigned carry_amount_of_money:1;  	unsigned height:9;			// 0 – 300     unsigned carry_height:1; }; 

Внимание, тут используется знание порядка укладки bit fields в конкретном компиляторе; на самом деле надо заменить структуру на unsigned long long и укладывать туда значения через битовые операции, но для этого пришлось бы менять референсный код. Код стал чуть менее кроссплатформенным чем он был, это лечится.

2. Заранее генерируем два слагаемых из чисел наподобие (128 — a) и (128 — 1 — c) из примера выше. Вместо 128 подставляем ширину каждого поля в битах. Чтобы не сойти с ума, используем макросы.

#define FILL(enum, field, bits) \     if (range_filters->use_filter[enum]) { \         begin_add.field = (1 << bits) - range_filters->begin.field; \         begin_add.carry_##field = range_filters->begin.field == 0; \         end_add.field = (1 << bits) - 1 - range_filters->end.field; \         mask_add.carry_##field = 1; \     } 

Обращаю внимание на заполнение carry_field для begin — битовые поля оперируют арифметикой без доп. расширенного бита, так что если begin = 0, то нужно заполнить само поле нулем, и carry_field единицей. Если вместо битовых полей использовать unsigned long long и битовые операции, то можно просто писать (1 << bits) — begin.

3. Складываем 64-битное число, в котором уложены наши поля, с двумя контрольными слагаемыми; получаем нужную нам информацию в битах переноса

        unsigned long long value = *(unsigned long long*)&array_ptr[i];          unsigned long long begin_result = (value + begin_add_i) ^ mask_add_i;         unsigned long long end_result = value + end_add_i; 

В этом кусочке кода мы злостно нарушили strict aliasing (и черт с ним), а также заменили 1 в битах переноса на 0.

4. Проверяем, что все интересные нам биты переноса (те, которые должны учитываться фильтром) равны 1 после первого сложения и 0 после второго.

        if (((begin_result | end_result) & mask_add_i) == 0) 

Поскольку мы заменили 1 на 0, то достаточно проверить что все интересные нам биты равны нулю.

5. Измеряем производительность, получаем прирост почти в 2 раза по сравнению с С++ кодом, который компилируется 5 минут.

Microsoft (R) C/C++ Optimizing Compiler Version 17.00.50727.1 for x64  Generated rows: 100000000 C-search took 0.778000 seconds. C++-optimized search took 0.307000 seconds. C-optimized-search took 0.171000 seconds. 

И на всякий случай код целиком. Компилируется в MSVC с ключиком /TP (потому что не C89, ни до моих изменений ни после), и в gcc без ключиков (случайность).

Разумеется, так измерять производительность нельзя.
Разумеется, мне повезло с 62 битами (а автору оригинальной статьи повезло с 4000 вариантами).
Но выводы каждый пусть сделает для себя сам.

Напоследок хочется отметить, что — кажется — настоящее решение для production будет использовать SoA укладку данных — вместо массива структур использовать по одному массиву для каждого поля (с, например, битовой упаковкой). Тогда во-первых можно экономить на количестве данных, прочитанных при linear scan, во-вторых не нужна compile-time комбинаторика, в-третьих кода писать меньше, в-четвертых количество полей и структуру запроса проще менять динамически. Еще разумеется настоящее решение для production будет использовать (о, ужас) платформенно-зависимый SIMD.