Analytics

FizzBuzz по-сениорски


      FizzBuzz по-сениорски

— Добрый день, я на интервью на позицию старшего разработчика.

— Здравствуйте, давайте начнем с небольшого теста, пока я ваше 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("FizzBuzzn");
            } else {
                printf("Fizzn");
            }
        } else if (0 == i % 5) {
            printf("Buzzn");
        } else {
            printf("%dn", 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( "%dn"          // 1
                "%dn"          // 2
                "Fizzn"        // 3
                "%dn"          // 4
                "Buzzn"        // 5
                "Fizzn"        // 6
                "%dn"          // 7
                "%dn"          // 8
                "Fizzn"        // 9
                "Buzzn"        // 10
                "%dn"          // 11
                "Fizzn"        // 12
                "%dn"          // 13
                "%dn"          // 14
                "FizzBuzzn",   // 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, "Fizzn", 5); cur += 5; num++; } while (0)
#define BUZZ do { memcpy(cur, "Buzzn", 5); cur += 5; num++; } while (0)
#define FIZZBUZZ do { memcpy(cur, "FizzBuzzn", 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.429

1x

39.650

1x

оптимизация цикла

22.546

1.83x

1.83x

20.151

1.97x

1.97x

отказ от printf

12.563

3.30x

1.80x

8.771

4.52x

2.30x

— В принципе на вывод в файл можно особо не смотреть — там какое-то время съедается на I/O, и оно плавает, так что лучше ориентироваться на время без I/O.

Я стираю ту часть, где про вывод в файл.

— Итого ускорение в 4 с половиной раза.

Интервьюер смотрит с уважением. Похоже, интервью я прошел, можно сворачиваться, да и интервьюер уже бумаги начинает складывать. Но я еще не закончил.

— Я знаю, как можно еще ускорить.

— Серьезно?

— Абсолютно. Я до этого использовал чисто технические способы ускорения, а ведь можно еще и алгоритмически улучшить. Смотрите, что будет напечатано, когда мы вызываем, например, print(150000001) и следующий за ним print(150000016):

150000001n150000002nFizzn150000004nBuzznFizzn150000007n150000008nFizznBuzzn150000011nFizzn150000013n150000014nFizzBuzzn
150000016n150000017nFizzn150000019nBuzznFizzn150000022n150000023nFizznBuzzn150000026nFizzn150000028n150000029nFizzBuzzn
       ^^         ^^               ^^                     ^^         ^^                     ^^               ^^         ^^ 

— Отличия всего в 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.650

1x

оптимизация цикла

20.151

1.97x

1.97x

отказ от printf

8.771

4.52x

2.30x

переиспользование буфера

4.490

8.83x

1.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.650

1x

оптимизация цикла

20.151

1.97x

1.97x

отказ от printf

8.771

4.52x

2.30x

переиспользование буфера

4.490

8.83x

1.95x

многопоточность

1.748

22.68x

2.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

Все варианты кода производят одинаковый результат, когда вывод направлен в файл, то есть работают корректно. Код доступен в этом репо.

Related posts

Как я заработал 1 000 000 $ без опыта и связей, а потом потратил их, чтобы сделать свой переводчик

admin

Опасные мифы о клещах

admin

Главная причина, почему все-таки Linux

admin

Leave a Comment