[Высокая производительность, Ненормальное программирование, C] FizzBuzz по-сениорски
Автор
Сообщение
news_bot ®
Стаж: 6 лет 9 месяцев
Сообщений: 27286
- Добрый день, я на интервью на позицию старшего разработчика.- Здравствуйте, давайте начнем с небольшого теста, пока я ваше CV смотрю. Напишите программу, которая выводила бы числа от 1 до, скажем, миллиарда, притом если число кратно трем, то вместо числа выводится Fizz, если кратно пяти, то Buzz, а если и трем, и пяти, то FizzBuzz.Серьезно, FizzBuzz? Задачка для начальной школы, на сениорскую позицию? Ну ладно.Я достаю свой верный лаптоп, и пишу такой код:
#include <stdio.h>
#define LIMIT 1000000000
int main(void) {
for (int i = 1; i <= LIMIT; i++) {
if (0 == i % 3) {
if (0 == i % 5) {
printf("FizzBuzz\n");
} else {
printf("Fizz\n");
}
} else if (0 == i % 5) {
printf("Buzz\n");
} else {
printf("%d\n", i);
}
}
return 0;
}
Запускаю программу, она себе бежит, но не так чтобы сильно быстро, через 3 с чем-то минуты, после первого миллиона, я ее прерываю и быстренько высчитываю, что весь процесс займет больше двух суток. Да, наверно надо было включить буферизацию, это бы несколько ускорило, но это не спасет, лучше просто перенаправить вывод в файл, что я и делаю, и через 41.5 секунду у меня есть красивенький файл на 7.5 гигов.- Вам не кажется, что можно побыстрее? - спрашивает интервьюер.- Да ладно, основное время занимает I/O, 7.5 гигов записать — не шутка, даже на SSD.- А давайте перенаправим вывод в /dev/null.- Без проблем. Через минуту:- Как это — 39.5 секунд? То есть весь I/O занимает 2 секунды, а все остальное время — мой код?- Да, так получается. Это не самая медленная реализация, на каждой итерации два сравнения и один printf, я часто вижу вариант с тремя сравнениями и двумя printf’ами. Для джуниора, я бы сказал, это даже хорошо. А вот для сениора ...Это было больно, но, пожалуй, заслужено. Ладно, я тебе покажу, кто тут джуниор.- Сейчас сделаю побыстрее.- Попробуйте. Только объясняйте, что вы делаете.- Видите, что у нас тут есть паттерн — каждые 3*5, то есть 15 итераций цикла логика полностью повторяется. Тогда можно переделать цикл:
for (i = 1; i < LIMIT - 15; i += 15) {
printf( "%d\n" // 1
"%d\n" // 2
"Fizz\n" // 3
"%d\n" // 4
"Buzz\n" // 5
"Fizz\n" // 6
"%d\n" // 7
"%d\n" // 8
"Fizz\n" // 9
"Buzz\n" // 10
"%d\n" // 11
"Fizz\n" // 12
"%d\n" // 13
"%d\n" // 14
"FizzBuzz\n", // 15
i, i+1, i+3, i+6, i+7, i+10, i+12, i+13);
}
- Если раньше на каждые 15 чисел у нас приходилось 15 сравнений переменной цикла и два if’а в теле цикла, то есть в общей сложности 45 сравнений, а каждое сравнение — это потенциальная проблема с branch prediction’ом, то теперь одно. Да и вызовов printf’а стало в 15 раз меньше. Одна только проблема — цикл не дойдет ровно до миллиарда, а только до 999999990 (макс число, кратное 15 и меньшее миллиарда), так что оставим старый цикл, но только для обработки хвоста, то есть последних 10 значений (это практически не влияет на производительность).После всех изменений получился такой код.- И что у нас со временем получается?- Если вывод в файл, то 22.5 секунды, если в /dev/null – 20.2Интервьюер доволен, похоже, чего-то такого он от меня и ожидал. Но … зря он про джуниора сказал.- Я думаю, что это не предел.- В самом деле? А что тут можно еще оптимизировать?- Я уменьшил количество вызовов printf’а в 15 раз, но при этом сами эти printf’ы стали тяжелее. Да и вообще printf сам по себе тяжелый, из-за своей мощности — это ведь фактически виртуальная машина со своим языком, полным по Тьюрингу, на нем даже крестики-нолики писали. В данной ситуации используется лишь небольшая часть возможностей printf, так что можно его заменить на что-то свое, более легкое:
#define NUM cur += myitoa(num++, cur)
#define FIZZ do { memcpy(cur, "Fizz\n", 5); cur += 5; num++; } while (0)
#define BUZZ do { memcpy(cur, "Buzz\n", 5); cur += 5; num++; } while (0)
#define FIZZBUZZ do { memcpy(cur, "FizzBuzz\n", 9); cur += 9; } while (0)
void print(int num) {
static char wrkbuf[CHUNK_SIZE];
char *cur = wrkbuf;
NUM;
NUM;
FIZZ;
NUM;
BUZZ;
FIZZ;
NUM;
NUM;
FIZZ;
BUZZ;
NUM;
FIZZ;
NUM;
NUM;
FIZZBUZZ;
fwrite(wrkbuf, cur - wrkbuf, 1, stdout);
}
- Можно, конечно, использовать уже готовую itoa, но это нестандартная функция, не везде есть, да и она слишком универсальная, поскольку поддерживает разные системы счисления, а у нас только десятичная система - упрощаем все, что можно. Ну и, конечно, в главном цикле просто вызываем print(i) вместо длинного printf’а.Получается такой код.Я подхожу к доске и рисую табличку с результатами запусков:ВариантВывод в файлВывод в /dev/nullВремя (сек)Относ наивнойОтнос предыдущейВремя (сек)Относ наивнойОтнос предыдущейнаивная41.4291x-39.6501x-оптимизация цикла22.5461.83x1.83x20.1511.97x1.97xотказ от printf12.5633.30x1.80x8.7714.52x2.30x- В принципе на вывод в файл можно особо не смотреть — там какое-то время съедается на I/O, и оно плавает, так что лучше ориентироваться на время без I/O.Я стираю ту часть, где про вывод в файл.- Итого ускорение в 4 с половиной раза.Интервьюер смотрит с уважением. Похоже, интервью я прошел, можно сворачиваться, да и интервьюер уже бумаги начинает складывать. Но я еще не закончил.- Я знаю, как можно еще ускорить.- Серьезно?- Абсолютно. Я до этого использовал чисто технические способы ускорения, а ведь можно еще и алгоритмически улучшить. Смотрите, что будет напечатано, когда мы вызываем, например, print(150000001) и следующий за ним print(150000016):
150000001\n150000002\nFizz\n150000004\nBuzz\nFizz\n150000007\n150000008\nFizz\nBuzz\n150000011\nFizz\n150000013\n150000014\nFizzBuzz\n
150000016\n150000017\nFizz\n150000019\nBuzz\nFizz\n150000022\n150000023\nFizz\nBuzz\n150000026\nFizz\n150000028\n150000029\nFizzBuzz\n
^^ ^^ ^^ ^^ ^^ ^^ ^^ ^^
- Отличия всего в 16 байтах, а программа всю строку пересобирает с нуля. Можно просто менять байты на месте. Правда, заранее неизвестно, сколько десятичных разрядов надо поменять, так что это потребуется вычислить — сравнить два буфера, и определить, где они отличаются. Это, пожалуй, тяжеловатая задача, но у нас есть, — я делаю театральную паузу — векторные инструкции и интринсики для них!Я не озвучиваю, но подразумеваю, что джуниор такого бы не придумал. В этот момент понимаю, что интервьюер тоже.Открываю Intel’овскую страницу с интринсикамии нахожу там нужные векторные функции для работы с 16-байтными векторами. У меня тут максимум 10-байтные, но их можно добить нулями до 16, не проблема. И да, 16-байтные вектора — это SSE инструкции, никакой AVX-512 тут не нужен, мой 4-летний мобильный проц это точно потянет.Получаю такой кусок с жирными и вкусными интринсиками:
unsigned int diff = 0xFFFF & ~_mm_movemask_epi8(_mm_cmpeq_epi8(
_mm_load_si128((__m128i const *)prev_first_number),
_mm_load_si128((__m128i const *)last_number)));
unsigned int diff_pos = 16 - _tzcnt_u32(diff); // number of changed digits
Быстрая проверка flags в /proc/cpuinfo – нужные для выбранных мной интринсиков SSE2(еще со времен Pentium 4) и BMI1(появился в Haswell’ах) в CPU есть, все должно работать.Запускаю тот код, что получился, смотрю уже только вывод в /dev/null и обновляю табличку:ВариантВремя (сек)Относительно наивнойОтносительно предыдущейнаивная39.6501x-оптимизация цикла20.1511.97x1.97xотказ от printf8.7714.52x2.30xпереиспользование буфера4.4908.83x1.95xЕще почти в 2 раза ускорились! А по сравнению с начальным вариантов так вообще почти в 9. Жаль, до 10 раз не дотянул.- Ну все, наверно теперь уже хватит. Это уже вполне по-сениорски.Во взгляде интервьюера читается облегчение.- Скорее всего, мы вплотную подошли к пределу того, что можно выжать из однопоточной программы, - говорю я, медленно подвисая к концу фразы. Как же я об этом раньше не подумал! - Я ведь еще многопоточность не попробовал!Интервьюер, похоже, начинает чего-то опасаться, и старается как-то незаметно переползти на соседний стул, поближе к выхожу из переговорки, но ему сильно мешают подлокотники. Пофиг, не надо было меня провоцировать!- Я буду выделять каждому рабочему потоку кусок числового поля, и этот поток будет возвращать готовый буфер для своего куска, а главный поток будет печатать эти буферы, соблюдая порядок:
for (int j = 0; j < THREAD_COUNT; j++) {
thread_pool[j].start_num = i;
thread_pool[j].count = NUMS_PER_THREAD;
thread_pool[j].buf = malloc(BUFFER_SIZE);
pthread_create(&thread_pool[j].id, NULL, worker, (void *)&thread_pool[j]);
i += NUMS_PER_THREAD;
}
int active_threads = THREAD_COUNT;
int max = LIMIT / 15 * 15;
for (int j = 0; active_threads; j = (j+1) % THREAD_COUNT) {
pthread_join(thread_pool[j].id, NULL);
fwrite(thread_pool[j].buf, thread_pool[j].buflen, 1, stdout);
if (max - i > NUMS_PER_THREAD) {
thread_pool[j].start_num = i;
pthread_create(&thread_pool[j].id, NULL, worker, (void *)&thread_pool[j]);
i += NUMS_PER_THREAD;
} else if (max > i) {
thread_pool[j].start_num = i;
thread_pool[j].count = max - i + 1;
pthread_create(&thread_pool[j].id, NULL, worker, (void *)&thread_pool[j]);
i += max - i + 1;
} else {
free(thread_pool[j].buf);
active_threads--;
}
}
- У меня двухядерный проц с гипертредингом, так что четыре рабочих потока одновременно будет оптимально, пока главный поток занимается выводом, один рабочий поток не используется, так что в любой момент времени максимум 4 потока активны. Конечно, стоит поэксперементировать с размером куска, который дается на обработку — в идеале рабочий поток должен обрабатывать свой кусок ровно за то же время, что главный поток выводит данные, тогда никто никого не ждет, все работают на максимальной скорости.Проведя несколько замеров, я остановился на кусках по 3 миллиона чисел — удобное число, кратное 15, и результат хороший.Получился такой код.Запускаю, и обновляю данный в табличке:ВариантВремя (сек)Относительно наивнойОтносительно предыдущейнаивная39.6501x-оптимизация цикла20.1511.97x1.97xотказ от printf8.7714.52x2.30xпереиспользование буфера4.4908.83x1.95xмногопоточность1.74822.68x2.57x- Ну вот, я уменьшил время обработки в 22 с лишним раза. И код получился очень даже сениорский — умный алгоритм, многопоточность, интринсики опять же. Как считаете?Я отвернулся от доски и увидел, что в переговорке я один. Через стеклянную стенку переговорки я разглядел интервьюера, который что-то быстро говорил секретарю, показывая пальцем в мою сторону. Он что, вызывает охрану? Похоже, что мне тут больше не рады.Я быстро закрыл лаптоп и покинул офис. Почему-то мне так и не перезвонили.Все тесты делались на Dell Latitude 7480 с i7-7600U 2.8 Ghz, 16 Gb памяти, SSD и OpenSUSE Leap 15.1 с kernel’ом 4.12.14, каждый тест не менее 10 раз, выбиралось наименьшее значение. При компиляции использовались флаги -O3 -march=native -pthreadВсе варианты кода производят одинаковый результат, когда вывод направлен в файл, то есть работают корректно. Код доступен в этом репо.
===========
Источник:
habr.com
===========
Похожие новости:
- [Финансы в IT] Reddit-ралли спасло от долгов кинотеатры AMC
- [Математика, Учебный процесс в IT, Физика] Личный опыт: как мы готовили курс по компьютерному моделированию в бакалавриате Нового физтеха
- [Периферия, Здоровье, Киберспорт] Гигиена труда оператора ЭВМ (МКМ)
- [Open source, Алгоритмы, Параллельное программирование] Динамика потокового вычислителя
- Mozilla свернула разработку проектов Voice Fill и Firefox Voice
- Доступны дистрибутивы Clonezilla Live 2.7.1 и GParted Live 1.2.0
- [Ненормальное программирование, Программирование, Java, API, C#] Вы всё ещё ловите исключения? Тогда мы к вам
- [Настройка Linux, Системное администрирование, Серверное администрирование, Резервное копирование] Настраиваем Restic с systemd на Linux
- [IT-эмиграция, Карьера в IT-индустрии] Паста, пицца, мама миа! Переезд разработчика в Италию
- [Информационная безопасность, CTF] HackTheBox. Прохождение Worker. Работаем с SVN. Используем Azure DevOps для захвата хоста
Теги для поиска: #_vysokaja_proizvoditelnost (Высокая производительность), #_nenormalnoe_programmirovanie (Ненормальное программирование), #_c, #_si (си), #_fizzbuzz, #_optimizatsija (оптимизация), #_intervju (интервью), #_sobesedovanie (собеседование), #_vysokaja_proizvoditelnost (
Высокая производительность
), #_nenormalnoe_programmirovanie (
Ненормальное программирование
), #_c
Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете голосовать в опросах
Вы не можете прикреплять файлы к сообщениям
Вы не можете скачивать файлы
Текущее время: 23-Ноя 00:48
Часовой пояс: UTC + 5
Автор | Сообщение |
---|---|
news_bot ®
Стаж: 6 лет 9 месяцев |
|
- Добрый день, я на интервью на позицию старшего разработчика.- Здравствуйте, давайте начнем с небольшого теста, пока я ваше CV смотрю. Напишите программу, которая выводила бы числа от 1 до, скажем, миллиарда, притом если число кратно трем, то вместо числа выводится Fizz, если кратно пяти, то Buzz, а если и трем, и пяти, то FizzBuzz.Серьезно, FizzBuzz? Задачка для начальной школы, на сениорскую позицию? Ну ладно.Я достаю свой верный лаптоп, и пишу такой код: #include <stdio.h>
#define LIMIT 1000000000 int main(void) { for (int i = 1; i <= LIMIT; i++) { if (0 == i % 3) { if (0 == i % 5) { printf("FizzBuzz\n"); } else { printf("Fizz\n"); } } else if (0 == i % 5) { printf("Buzz\n"); } else { printf("%d\n", i); } } return 0; } for (i = 1; i < LIMIT - 15; i += 15) {
printf( "%d\n" // 1 "%d\n" // 2 "Fizz\n" // 3 "%d\n" // 4 "Buzz\n" // 5 "Fizz\n" // 6 "%d\n" // 7 "%d\n" // 8 "Fizz\n" // 9 "Buzz\n" // 10 "%d\n" // 11 "Fizz\n" // 12 "%d\n" // 13 "%d\n" // 14 "FizzBuzz\n", // 15 i, i+1, i+3, i+6, i+7, i+10, i+12, i+13); } #define NUM cur += myitoa(num++, cur)
#define FIZZ do { memcpy(cur, "Fizz\n", 5); cur += 5; num++; } while (0) #define BUZZ do { memcpy(cur, "Buzz\n", 5); cur += 5; num++; } while (0) #define FIZZBUZZ do { memcpy(cur, "FizzBuzz\n", 9); cur += 9; } while (0) void print(int num) { static char wrkbuf[CHUNK_SIZE]; char *cur = wrkbuf; NUM; NUM; FIZZ; NUM; BUZZ; FIZZ; NUM; NUM; FIZZ; BUZZ; NUM; FIZZ; NUM; NUM; FIZZBUZZ; fwrite(wrkbuf, cur - wrkbuf, 1, stdout); } 150000001\n150000002\nFizz\n150000004\nBuzz\nFizz\n150000007\n150000008\nFizz\nBuzz\n150000011\nFizz\n150000013\n150000014\nFizzBuzz\n
150000016\n150000017\nFizz\n150000019\nBuzz\nFizz\n150000022\n150000023\nFizz\nBuzz\n150000026\nFizz\n150000028\n150000029\nFizzBuzz\n ^^ ^^ ^^ ^^ ^^ ^^ ^^ ^^ unsigned int diff = 0xFFFF & ~_mm_movemask_epi8(_mm_cmpeq_epi8(
_mm_load_si128((__m128i const *)prev_first_number), _mm_load_si128((__m128i const *)last_number))); unsigned int diff_pos = 16 - _tzcnt_u32(diff); // number of changed digits for (int j = 0; j < THREAD_COUNT; j++) {
thread_pool[j].start_num = i; thread_pool[j].count = NUMS_PER_THREAD; thread_pool[j].buf = malloc(BUFFER_SIZE); pthread_create(&thread_pool[j].id, NULL, worker, (void *)&thread_pool[j]); i += NUMS_PER_THREAD; } int active_threads = THREAD_COUNT; int max = LIMIT / 15 * 15; for (int j = 0; active_threads; j = (j+1) % THREAD_COUNT) { pthread_join(thread_pool[j].id, NULL); fwrite(thread_pool[j].buf, thread_pool[j].buflen, 1, stdout); if (max - i > NUMS_PER_THREAD) { thread_pool[j].start_num = i; pthread_create(&thread_pool[j].id, NULL, worker, (void *)&thread_pool[j]); i += NUMS_PER_THREAD; } else if (max > i) { thread_pool[j].start_num = i; thread_pool[j].count = max - i + 1; pthread_create(&thread_pool[j].id, NULL, worker, (void *)&thread_pool[j]); i += max - i + 1; } else { free(thread_pool[j].buf); active_threads--; } } =========== Источник: habr.com =========== Похожие новости:
Высокая производительность ), #_nenormalnoe_programmirovanie ( Ненормальное программирование ), #_c |
|
Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете голосовать в опросах
Вы не можете прикреплять файлы к сообщениям
Вы не можете скачивать файлы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете голосовать в опросах
Вы не можете прикреплять файлы к сообщениям
Вы не можете скачивать файлы
Текущее время: 23-Ноя 00:48
Часовой пояс: UTC + 5