После написания первой статьи про FizzBuzz (которая неожиданно для меня стала выбором редакции на Технотексте 2021) у меня появлялись мысли о том, что можно бы еще ускорить, но все время было не до того. И тут мне прилетает перчатка.
Так что пришлось расчехлить верный GCC, чтобы помериться кодом с @ChePeter.
Пара замечаний перед тем, как окунуть руки в код:
-
@ChePeter сравнивал быстродействие своего решения с не самым быстрым моим решением. Но, как я понял, на i5-9400 нет поддержки BMI1, поэтому вариант customprint2 действительно самый быстрый из тех, которые работают на этом процессоре
-
код от "пенсионера" заставил вспомнить выражение из 1983 года: "The determined Real Programmer can write FORTRAN programs in any language". Могу только сказать, что такой код вряд ли пройдет ревью
-
“Ну и распараллеливать тут нечего, создание потоков съест больше времени процессора, чем собственно вычисления” – я полностью не согласен с этим утверждением. Как раз эта задача довольно хорошо параллелится, и в случае моего предыдущего захода многопоточность сразу дала прирост в более чем в 2.5 раза
Задача остается прежняя, но добавляется ограничение – не использовать интринсики. Код “пенсионера” на моем компьютере (вывод перенаправлен в /dev/null) отрабатывает за 2.337 сек, значит это время мне надо побить. Но на самом деле я хочу “влезть” в секунду – в прошлый раз мне не хватило каких-то 51 миллисекунд. Но тогда у меня были интринсики, сейчас попробую обойтись без них.
Поскольку интринсики исключены, переиспользование буфера становится не столь эффективным, то есть будем собирать буфер каждый раз с нуля. Но и тут есть, где разгуляться.
Оптимизация переделки числа в строку
В предыдущем варианте я использовал свой аналог функции itoa, и она в цикле делила число на 10. Цикл – плохо, деление – плохо, выкидываем на фиг и то, и другое, заменяем lookup таблицей. Поскольку у нас есть ограничение в миллиард (на самом деле 999999990, как самое больше кратное 15 число до миллиарда), нам нужно уметь работать с 9-значными числами, таблица в миллиард 10-байтных строк будет огромная, не годится. Тогда можно делить число на две части, в этом случае хватает таблицы для 5-значных чисел, то есть 100000 6-байтных строк, это уже терпимо, но еще не очень. Однако, если мы будет за один проход обрабатывать не 15 чисел, а 30, то последняя цифра числа будет определяться его порядковым номером в 30-числовой серии, и тогда нам достаточно переводить в строку 8-значное число, а раз мы делим его на две части, то это будет два lookup’а по таблице из 10000. А поскольку каждая часть у нас получается 4 байта, нам удобно хранить их не как строки, а как 32-битные int'ы, и это нам впоследствии пригодится. Получаем таблицу в 40K, которая отлично влезает в любой кэш, значит можно рассчитывать, что поиск по такой таблице будет летать.
Благодаря тому, что последнюю цифру числа нам определять не надо, а серия у нас из 30 чисел, поиск по таблице нужно делать только 3 раза за серию, когда переключаются десятки. Приятный побочный эффект. К тому же мы можем почти полностью избавиться от деления – мы просто инкрементируем младшую часть числа, и проверяем, не надо ли сделать перенос. Одним выстрелом уложим целое стадо (стаю? косяк?) зайцев.
Снижение числа вызовов функций
В предыдущих версиях FizzBuzz довольно активно использовались функции стандартной библиотеки, и в первую очередь memcpy(). Я уверен, что memcpy() работает очень быстро и использует доступные векторные инструкции, но в нашей задаче надо постоянно копировать небольшие буферы – от 4 до 10 байт, что можно спокойно уложить в пару инструкций присваивания вместо того, чтобы вызывать функцию. Поскольку C не позволяет присваивать массивы, нужно все буферы переделать в int’ы фиксированного размера. Тут, конечно, создает проблемы little endian на x86, придется очень сильно думать над порядком байтов в этих "числах", но оно того стоит.
Разные типы worker’ов
Новая методика переделки числа в строку будет работать только для 9-значных чисел, которые составляют 90% нашего числового поля. Можно еще сделать отдельный вариант для 8-значных чисел, это закроет еще 9%, а оставшийся процент можно обрабатывать более медленным, но зато универсальным обработчиком. Но это означает, что нужно иметь возможность для разных диапазонов чисел задавать разные обработчики. Это немного усложнит менеджер задач, но без этого нельзя будет реализовать новые идеи, не отказываясь от многопоточности.
Даже не считая двух lookup таблиц на 10000 и на 1000 чисел (на big endian можно было бы обойтись и одной, на little endian это потребует дополнительных плясок, которые неминуемо ударят по производительности), кода стало заметно больше, так что я приведу только самый важный кусок – worker’а, который обрабатывает 9-значные числа (то есть 90% числового поля):
#define FIZZ do { *((uint64_t *)cur) = 0x0a7a7a6946; cur += 5; } while (0)
#define BUZZ do { *((uint64_t *)cur) = 0x0a7a7a7542; cur += 5; } while (0)
#define FIZZBUZZ do { *((uint64_t *)cur) = 0x7a7a75427a7a6946; cur += 8; *((uint8_t *)cur) = 0x0a; cur++; } while (0)
#define FIZZ_BUZZ do { *((uint64_t *)cur) = 0x7a75420a7a7a6946; cur += 8; *((uint16_t *)cur) = 0x0a7a; cur += 2; } while (0)
#define BUZZ_FIZZ do { *((uint64_t *)cur) = 0x7a69460a7a7a7542; cur += 8; *((uint16_t *)cur) = 0x0a7a; cur += 2; } while (0)
#define DIGIT(A) do {*cur = A; cur++; *cur = 'n'; cur ++; } while (0)
#define NUM do {*((uint32_t *)cur) = high; cur += 4; *((uint32_t *)cur) = low; cur += 4; } while (0)
#define NORM do { l++; if (l >= 10000) { l -= 10000; h += 1; high = table10K[h]; } low = table10K[l]; } while(0)
void *fast9(void *arg) {
struct thread_data *data = (struct thread_data *)arg;
char *cur = data->buf;
int first_digits = data->first / 10;
int h = first_digits / 10000; // decimal digits 1-4
int l = first_digits % 10000; // decimal digits 5-8
uint32_t high = table10K[h];
uint32_t low = table10K[l];
for (int i = data->first; i <= data->last; i += 30) {
NUM; DIGIT('1'); // 1
NUM; DIGIT('2'); // 2
FIZZ; // 3
NUM; DIGIT('4'); // 4
BUZZ_FIZZ; // 5, 6
NUM; DIGIT('7'); // 7
NUM; DIGIT('8'); // 8
FIZZ_BUZZ; // 9, 10
NORM;
NUM; DIGIT('1'); // 11
FIZZ; // 12
NUM; DIGIT('3'); // 13
NUM; DIGIT('4'); // 14
FIZZBUZZ; // 15
NUM; DIGIT('6'); // 16
NUM; DIGIT('7'); // 17
FIZZ; // 18
NUM; DIGIT('9'); // 19
BUZZ_FIZZ; // 20, 21
NORM;
NUM; DIGIT('2'); // 22
NUM; DIGIT('3'); // 23
FIZZ_BUZZ; // 24, 25
NUM; DIGIT('6'); // 26
FIZZ; // 27
NUM; DIGIT('8'); // 28
NUM; DIGIT('9'); // 29
FIZZBUZZ; // 30
NORM;
}
data->buflen = cur - data->buf;
pthread_exit(NULL);
}
Загадочные хексовые константы – это слова Fizz и Buzz в разных вариантах, представленные в виде little endian чисел.
Полный исходник тут.
Результат
Ну и самое главное – получилось ли уделать “пенсионера”?
$ time ./multithreaded2 >/dev/null
real 0m0.692s
user 0m2.659s
sys 0m0.033s
Да, более чем в 3 раза быстрее. И удалось войти в секунду, притом с огромным запасом. Что интересно, я обновил данные по всем тестам и теперь даже multithreaded отлично входит в секунду (но новый вариант все равно быстрее). Не знаю, то ли это заслуга более нового kernel'а (5.17 вместо 4.12) или более нового gcc (11.3 вместо 7.5).
Автор:
qrdl
