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("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.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):

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

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


P.S. Мне прилетели очень интересные PRы от некого японца kariya-mitsuru, и там была пара занятных идей, самая главная - заполнять буфер не слева направо, а справа налево, это позволило избавиться от нескольких вызовов memcpy(), что дало заметное ускорение, например, вариант со своим print'ом (без printf) стал быстрее на 31%, вариант с переиспользованием буфера - на 59%.

На основе этого подхода я также переделал многопоточный вариант, и он стал быстрее на 66%, я очень хотел "войти" в секунду, но совсем немного не хватило, каких-то 50 миллисекунд.

В результате таблица выглядит так (с линками на соответствующие реализации):

Вариант

Время (сек)

Относительно наивной

Относительно предыдущей

наивная

39.650

1x

-

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

20.151

1.97x

1.97x

отказ от printf

8.771

4.52x

2.30x

отказ от printf 2 (заполнение буфера справа налево)

6.695

5.92x

1.31x

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

4.490

8.83x

1.49x

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

2.818

14.07x

1.59x

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

1.051

37.73x

2.68x

Similar posts

Ads
AdBlock has stolen the banner, but banners are not teeth — they will be back

More

Comments 301

    +2
    одинаковый результат, когда вывод направлен в файл, то есть работают корректно.

    А это точно означает «корректно»? Может, просто «одинаково неправильно»? :)
      +25
      Я проверял — одинаково правильно :)
      Просто проверять каждый раз 7.5-гиговый файл довольно муторно, я проверил первый, а дальше просто сверял размер и контрольные суммы
      +23
      Но это же только оптимизация по быстродействию. А что с занимаемой памятью, что с размером самой программы, что с нагрузкой на процессор? Ведь оптимизировать можно по разным критериям. А то так можно просто блобом запихнуть результирующий файл в программу и просто записывать его на диск — проверять лень, но возможно выйдет ещё быстрее.
        +37

        Вот да, я ожидал развязку в стиле "мы сделаем всё на шаблонах, чтобы итоговый FizzBuzz вычислился во время компиляции, а работа программы будет заключаться исключительно в том, чтобы вывести строку из секции .data в консоль." :D

          +35
          Но ведь это медленнее — прочитать 7.5GB из .data (с диска), чем на лету сгенерировать.
            –4

            Если структурировать данные, и ввести индексы, то быстро)

              +2
              Самый быстрый способ — это заранее записать файл на диск и сделать к нему жёсткую ссылку.
                +4
                Сделать виртуальную ФС, в которой данные генерятся на лету.
                  +2
                  Нет, задача FizzBuzz не в записи файла на диск, а в генерации потока в stdout. Возможность записи на диск — опциональная.
                    0
                    А я и не предлагаю запись на диск:)
                      +3
                      То есть, программа берёт данные из виртуальной ФС и копирует в stdout? А её запуск сводится к банальной cat? Интересно, действительно интересно.
                        0
                        Именно.
            +3
            Ну если подходить чисто формально, то задачу ставит тот, кто интервьюирует. А он про память ничего не спрашивал — следовательно, требованиям по памяти программа удовлетворяет. Вообще, насколько я понимаю, автор их если и увеличил на второй и последующих итерациях, то не сильно, просто потому, что никаких аллокаций, особенно крупных, в коде не видно.
              +7
              Более-менее используется память в последнем варианте — для каждого потока выделяется буфер в 3M * 119 байт / 15 = 22.7 Mb, для 4 потоков выходит 91 Mb. Все остальные варианты очень скромные по памяти.
                0
                А, ну да — многопоточный вариант наверное съест больше.
              +2
              Если у вас отпимизация по быстродействию то в результате нагрузка на CPU максимальна. Если же процессор простаивает, то значит что то вы недогрузили и перформанс не максимальный.
              Размер программы, соглашусь, критерий независимый, но это не точно :)
                0
                Оффтопик
                ru.wikipedia.org/wiki/%D0%9F%D0%B5%D1%80%D1%84%D0%BE%D1%80%D0%BC%D0%B0%D0%BD%D1%81

                А тут речь про производительность или, может быть, скорость. Как же у меня бомбит от «перфоманса» и «генерации».
                  +1

                  А вы не бомбите.


                  Алсо весьма любопытно, если "перфоманс" ещё куда ни шло (хотя встречается повсеместно), то что не так с генерацией?

                    +1
                    С генерацией в смысле «генерация последовательности» — всё хорошо. Но вот почему-то сейчас это слово используют в значении «поколение» (видимо, надмозг не осилил generation).
                      0

                      В значение "Поколение" оно используется уже у Даля в словаре 1819 года, а как раз-таки смысл "результат глагола 'генерировать'" появился уже после 1950х. Возможно это не такое уж нововведение?

                        0
                        В словаре Даля есть много слов, поменявших свой смысл относительно его словаря. Но это не значит, что, например, слово урод уместно использовать в значении «первенец мужского пола» или «урожай» или задница в значении «наследство»
            +51
            Поставили задачу: «написать FizzBuzz».
            Ожидают результата: «полёт на Марс».
              +9
              А человек построил межзвёздный корабль.
                +6
                Но ему всё равно сказали, мы вам перезвоним.
                  +3
                  и начал тонко тюнить гипердрайв…
                    +1
                    Утюг из Ералаша, улетевший в космос www.youtube.com/watch?v=46IXlSkjLZo
                  +31

                  Любой более менее опытный человек может загрузить любого другого опытного человека узкоспециализированной задача на который первый съел собаку

                    +72

                    Опытный специалист должен не только уметь ускорять алгоритмы, но и понимать, когда пора остановиться и перейти к более важной работе. Возможно, потому и не перезвонили.

                      +4
                      В статье есть и про мотивацию почему автор не остановился вовремя.

                      Для джуниора, я бы сказал, это даже хорошо. А вот для сениора…

                      Это было больно, но, пожалуй, заслужено. Ладно, я тебе покажу, кто тут джуниор.
                        +3

                        Так и запишем: ставит эмоции выше рациональности

                          +2
                          Вопреки распространенному мнению, программисты все же люди, а не роботы, и кое-что человеческое им/нам не чуждо :)
                        +7

                        плюс нежелание остановиться после команды работодателя, с политической точки зрения может расцениваться как вариант деструктивного поведения. (с программной точки зрения это — полное зависание процесса) ;)

                          +4
                        +60
                        А не взяли вас, так как клепать формочки вам было бы скучно
                          +13
                          Скорее потому, что разбирать такой код будет слишком долго и муторно для команды. В итоге, будет потом очень больно увольнять специалиста, написавшего такой код.
                            +13
                            Если нужна прям быстрота-быстрота, то код по-любому будет какой-то такой, кто его ни напиши.
                              +6
                              согласен с предыдущим оратором, просто вызов такого метода нужно сделать как черный ящик и написать все нужные комментарии — тогда будет читаемо.

                              Многие же, к сожалению, думают — раз я такой крутой программист что пишу так, что джуны не понимают — мой код самодокументирующийся. А на самом деле — чем больше опыта, тем проще и понятнее пишешь код.
                                +1

                                Черные ящики на практике обычно оказываются не такими уж и черными, и каждая последующая версия хоть и быстрее но тем сложнее оптимизируется. Что если мы сделаем FizzBuzzFooBar? в превоначальном варианте это ещё два ифа, во втором нужно будет константу менять и заполнять пробелы формата выводом чисел, а про последующие даже думать не хочу. Что делать когда варианты перестают влезать не только в 10 байт, но и вообще в AVX512?


                                Такой код имеет право на жизнь, безусловно, очень крутая статья, свой плюсик я там нарисовал. Но не надо сениора который остановился на первом (втором?) варианте считать хоть чем-то хуже: минимум у него другие интересы, а как максимум он просто смог оценить что решение удовлетворительно и оптимизировать наносекунды ради катастрофического падения простоты кода не нужно

                                  +6
                                  Тут многие комментаторы выступают в роли эдакой крыловской «свиньи под дубом», не осознавая, что они могут писать простой, понятный, красивый, лаконичный и какой там еще код на высокоуровневых языках только потому, что умные «сениоры» уже оптимизировали наносекунды в нужных местах. А вопрос, когда остановиться в оптимизации FizzBuzz, сам по себе ответа не имеет — это ж не реальная задача с практической ценностью, это чистая условность в рамках интервью, кандидату как бы говорят: «Давай, абстрагируйся от факта, что это не нужно, забудь, что это можно за минуту нагуглить и покажи нам, как ты можешь.»
                                    0
                                    А вопрос, когда остановиться в оптимизации FizzBuzz, сам по себе ответа не имеет

                                    Конечно имеет: когда наш интервьювер улыбнулся и начал переходить к следующим вопросам — это и был момент оптимальной производительности/читаемости. А когда он начал уползать сторону двери — уже сильно сильно ушли в сторону неоптимального решения.


                                    В общем, понятное дело, что автор просто поделился о том как круто можно занютить физзбазз, в такой вот форме собеса с шутейками, но если вообразить что такое могло быть в реальности то имеем что вопросы "а зачем?" вполне обоснованы. Если воспринимать это как фон для "оптимизируем физзбазз в 5 этапов" тогда конеш вопросов никаких быть не может — круто пишем, простор для оптимизаций — широк.




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

                                      +1
                                      «Идентичен вылизанному плюсокоду» — это «вылизанному» в том смысле, что память вручную разложена, чтобы влезать в кэши CPU, алгоритмы перепидарашены, чтобы предсказатель ветвлений не фейлил, интринсики и вот это вот все? Откровенно говоря, с трудом в это верится, а в то, что при этом код на Хаскеле остался нормальным кодом на Хаскеле, не превратившись в ужасающий «С++ на Хаскеле», не верится вовсе.
                                        0
                                        вручную разложена, чтобы влезать в кэши CPU, алгоритмы перепидарашены, чтобы предсказатель ветвлений не фейлил, интринсики и вот это вот все?

                                        Вот это всё, да.


                                        Хаскеле, не превратившись в ужасающий «С++ на Хаскеле», не верится вовсе.

                                        Ну, продакшн код увы показать не смогу, остается только поверить в эти цифры (из внутренней презы с бенчами разных вариантов):


                                        img


                                        Сравнивается: говнокод на Java, нормальный код на Java, оптимизированный хаскель, оптимизированный раст

                                          0
                                          думаю оптимизированная джава тоже была бы 2-5 сек
                                            0

                                            Ну я не эксперт в джаве, можете подскажете как в джаве:


                                            1. указать что вот через у этого интерфейса ровно две реализации, Причем чаще будет реализация А чем реализация Б (и на неё в IF нужно проверять в первую очередь)
                                            2. указать какая ветка ифа более вероятна чтобы компилятор её поставил первый и не нужно было делать лишний джамп в большинстве случаев, например в расте: if likely(some_condition()) { ... } else { ... }
                                            3. как указать что объекты X,Y,Z обязательно должны быть на стеке?
                                              0
                                              указать что вот через у этого интерфейса ровно две реализации

                                              Вот может как-то так?


                                              https://www.baeldung.com/java-sealed-classes-interfaces#1-sealed-interfaces


                                              указать какая ветка ифа более вероятна чтобы компилятор её поставил первый и не нужно было делать лишний джамп в большинстве случаев, например в расте: if likely(some_condition()) {… } else {… }

                                              https://www.baeldung.com/java-branch-prediction#2-order-of-branches
                                              https://medium.com/swlh/branch-prediction-everything-you-need-to-know-da13ce05787e


                                              По поводу третьего пункта — по-моему никак. Хотя я не гуру JVM :)

                                                0
                                                Вот может как-то так?

                                                Прикольно, один вопрос: использует ли JIT как-то информацию об этом или это просто удобный способ указывать АДТ? Мне кажется что последнее, если есть другая инфа — поделитесь пожалуйста.


                                                https://www.baeldung.com/java-branch-prediction#2-order-of-branches
                                                https://medium.com/swlh/branch-prediction-everything-you-need-to-know-da13ce05787e

                                                Речь как раз о кейсах где бранчпредиктор не справляется и нужно ему помочь. https://doc.rust-lang.org/std/intrinsics/fn.likely.html

                                                  0
                                                  поделитесь пожалуйста

                                                  Я так понимаю, это больше сахарок и на производительность особо не влияет. Впрочем, могу и ошибаться.


                                                  Речь как раз о кейсах где бранчпредиктор не справляется и нужно ему помочь.

                                                  Ну вот что пишут:


                                                  So you should order your branches in the order of decreasing likelihood to get the best branch prediction from a “first encounter”.
                                                    0
                                                    Ну вот что пишут:

                                                    Тут речь не о бранч предикторе вообще. Нас интересует, чтобы JIT код вида


                                                    if (unlikely(something)) {
                                                      add(a, 1);
                                                    }
                                                    else {
                                                      add(b, 2);
                                                    }

                                                    превратил в (псевдокод)


                                                    1: cmp something 1
                                                    2: JE 4
                                                    3: ADD %b 2
                                                    4: ADD %a 1

                                                    А не в


                                                    1: cmp something 1
                                                    2: JNE 4
                                                    3: ADD %b 2
                                                    4: ADD %a 1

                                                    Ну вот пример на годболте: https://godbolt.org/z/1brP6G
                                                    Ассемблер знать не обязательно, обратите мнимание что синий квадратик num + num + num в скомпилированном коде выше красного квадратика num*123 который компилятор поставил за джамп на .LBB0_1


                                                    img


                                                    Видно что компилятор переупорядочил код согласно нашим хинтам чтобы более вероятному бранчу не приходилось делать джамп. Тут вопрос про то в какой код скомпилировалось, ни про какой бранчпредиктор пока не идет речи.

                                                      0

                                                      Немного поигрался с javac/javap, и похоже что описанных вами оптимизаций не происходит при изменении порядка следования веток.
                                                      Возможно, после прогрева JVM таки сделает какие-то оптимизации. Но мне такая магия пока не доступна :(

                                                        0

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

                                                0
                                                (и на неё в IF нужно проверять в первую очередь)

                                                Реализации интерфейсов обычно вообще не проверяют через if.


                                                как указать что объекты X,Y,Z обязательно должны быть на стеке?

                                                Кстати, а как это сделать в хаскеле?

                                                  0
                                                  Кстати, а как это сделать в хаскеле?

                                                  Написать пропозал на 100501-ый экстеншон ghc.


                                                  А вообще в хаскеле нет стека, поэтому вопрос, увы, не имеет смысла.

                                                    0
                                                    А вообще в хаскеле нет стека

                                                    Вот по-этому я и спросил :)
                                                    Вообще, можно стеком считать nurcery, с-но аналогом такой штуки как "аллоцировать на стеке" были бы аннотации для хинтов гц вида: "в этом блоке гц не запускаем", "в этом блоке из nurcery не двигаем" и т.д.

                                                      0
                                                      "в этом блоке гц не запускаем"

                                                      Есть относительно релевантная штука — compact regions — можно один раз заэвалюэйтить терм и собрать мусор в транзитивном замыкании ссылок из соответствующего значения, а потом рассматривать всё значение вместе с транзитивным замыканием как одну большую цельную сущность с точки зрения GC, и внутрь неё при major GC не ходить. С ней хаскельный рантайм дерёт тот же JVM на некоторых задачах.


                                                      Правда, когда я последний раз этой штукой пользовался, она разваливалась на pinned memory (типа Data.Vector или Data.ByteString), но это ерунда.


                                                      Ну и ещё линейные типы же завезли, которые можно рассматривать как хинт компилятору о возможности инплейс-модификации.


                                                      А, кстати, pinned memory ­— это тоже такой хинт, наверное, да. Правда, это уже совсем скучное IO и скорее нужно для FFI.

                                                        0
                                                        Есть относительно релевантная штука — compact regions — можно один раз заэвалюэйтить терм и собрать мусор в транзитивном замыкании

                                                        Да, про это в курсе, но не совсем то. Я говорю несколько о другом сценарии.


                                                        Пусть у нас есть перемещающий сборщик — тогда затраты на сбор мусора пропорционально количеству достижимых данных. Тогда идеально запускать сборщик ровно тогда, когда у нас минимум достижимых данных и максимум недостижимых.
                                                        Далее — допустим у нас есть некоторая ф-я, которая что-то вычисляет — при этом порождает данные в процессе вычисления. Пусть это будет например 11мб данных (числа просто условные). Возвращает ф-я просто одно число, допустим. При этом ф-я вызывается в лупе.
                                                        С-но у нас есть два крайних случая — в первом случае (худшем) сборщик вызывается по триггеру, например, при 21мб заполненной памяти. Это значит что на каждом вызове будет 11мб недоступных данных (на которые нам пофиг) и 10мб доступных (которые сборщик должен обработать).
                                                        Идеальный сценарий — это если сборщик будет вызван непосредственно после вычисления ф-и. Тогда у нас вообще нет достижимых данных, он отрабатывает "мгновенно".
                                                        Вот собственно мы могли бы на этот луп вырубить гц и дергать его непосредственно после каждого вызова ф-и — это бы и дало идеальный сценарий работы.

                                                          0

                                                          Ну так скормите терм с вызовом этой функции compactу. Получите рекурсивную normal form у значения вместе с однократным сбором мусора (если я правильно помню, как работают регионы, и что GC не запускается при вычислении графа в compact).

                                                      0
                                                      > А вообще в хаскеле нет стека, поэтому вопрос, увы, не имеет смысла.

                                                      В C++ стека тоже нет, но я как-то кладу туда переменные…
                                                        +1

                                                        Вы не поняли, в хаскеле его вообще нет в том смысле, в котором он есть в сишке. Скажем так, в контексте хаскеля само понятие "аллокация на стеке" имеет мало смысла.

                                                    0
                                                    указать какая ветка ифа более вероятна чтобы компилятор её поставил первый

                                                    Ну так инвертируйте условие да поменяйте ветки местами. В нормальных IDE это делается одним quick fix-ом. Никакие «хайли лайкли» для этого на фиг не нужны.

                                                      +2
                                                      Где гарантия, что компилятор ветку if ставит likely перед веткой else.
                                                      А что делать с таким кодом:
                                                      int func(int param) {
                                                          if (param < 0) { // unlikely
                                                              // DEBUG_DUMP
                                                              // SHOW_WARNINGS
                                                              // BLA-BLA-BLA
                                                          }
                                                          return param+1;
                                                      }

                                                      тут я хочу, чтоюы всё тело if было сгенерировано где-то в конце сегмента .code и не подгружалось в кеш инструкций. А на входе в функцию на него был условный переход (почти никогда не выполняющийся).
                                                        0
                                                        А что делать с таким кодом:

                                                        Какие с ним могут быть затруднения?
                                                        Если внутри if-а параметр не модифицируется, то точно так же можно инвертировать условие if и засунуть return в блок then, а весь этот DEBUG_DUMP в else.


                                                        Перенести всю отладочную требуху в else будет даже логичнее и удобнее для чтения кода.


                                                        Где гарантия, что компилятор ветку if ставит likely перед веткой else.

                                                        Вот тут я тоже особых гарантий не вижу. Напротив, висит предупреждение о том, что «This is a nightly-only experimental API. (core_intrinsics) intrinsics are unlikely to ever be stabilized».

                                                          0

                                                          Это предупреждение висит у всех нестабилизированных фичей. То что компилятор гарантирует соответствующую компиляцию на поддерживаемых платформах там написано.

                                                        0

                                                        Покажите мне в каком месте спецификации Java гарантируется что компилятор всегда будет генерировать джамп для ветки else?

                                                          0

                                                          JVMS 11 §3.5:


                                                          Most of the Java programming language's other control constructs (if-then-else, do, while, break, and continue) are also compiled in the obvious ways.

                                                          Джамп для ветки else достаточно obvious. Но безопаснее считать, что гарантий нет. У нас там JIT дальше и чёрт знает какие bytecode transofrmers пользователь поназагружал.


                                                          Вот, кстати, при помощи bytecode transofrmation поддержку такой unlikely дичи можно сделать.

                                                  0
                                                  «Идентичен вылизанному плюсокоду» — это «вылизанному» в том смысле, что память вручную разложена, чтобы влезать в кэши CPU, алгоритмы перепидарашены, чтобы предсказатель ветвлений не фейлил, интринсики и вот это вот все?

                                                  Как правило, в таких случаях куда проще генерировать свой ассемблер/LLVM IR/etc вместо того, чтобы вылизывать плюсокод под конкретный компилятор. А генерировать все эти вещи куда проще на хаскеле, чем на плюсах.


                                                  Ну, по крайней мере, в моей продакшен-практике так.

                                                    0
                                                    Не понял, что имеется ввиду под «генерировать свой ассемблер»?
                                                      0

                                                      Примерно то же, что делает условный gcc -S. Ассемблер, конечно, не свой, но генератор вот свой, для своего предметно-специфичного языка.

                                              0
                                              > Что делать когда варианты перестают влезать не только в 10 байт, но и вообще в AVX512?

                                              Чтобы число в десятичном виде перестало влезать в AVX512, оно должно быть больше 64 байт, то есть 10^64 (здесь ^ — это степень, не XOR). Я не знаю имен для таких чисел, но сочувствую любому, кто решит писать FizzBuzz до 10^64 — ему не суждено увидеть результат :)
                                              Суть статьи была не в том, кто круче, а в том, что если хочется упороться, то для этого почти всегда можно найти какую-то возможность, как-то так.
                                                –2
                                                Таки в 64 байта влезает только 10^18 (1.8E+19).
                                                  0
                                                  В буфер длиной 64 байта можно записать строку из 64 девяток, которая будет текстовым десятичным представлением числа 10^64 — 1.
                                                  0-терминатор нас тут не волнует, строковые функции не используются, так что можем использовать все 64 байта.
                                                    0
                                                    Да, действительно, прошу прощения, невнимательно прочитал Ваш комментарий
                                                    +1
                                                    Вы перепутали 64 байта (512 бит) и 64 бита и не заметили «число в десятичном виде».
                                            +12
                                            Сдаётся мне, что не взяли потому что первая пустая формочка была бы получена только через два месяца.
                                              +8
                                              И заменяла бы собой весь сайт:)
                                            0
                                            В реальной жизни программа FizzBuzz написанная Сеньором на собеседовании, скорее всего, выглядела бы еще короче и оптимальнее — «Ciao!»
                                              +8
                                              Почему? Статья отличный пример того, как можно проверять уровень сеньора на простых задачах.
                                                0
                                                Могла бы быть примером, если бы после самой первой итерации был задан вопрос «почему» — по ответу на него с некоторой вероятностью можно было бы предположить, написан код так потому что человек по-другому не умеет (джун) или потому что не оговаривалась необходимость вызывать этот код сколь-нибудь часто и нет смысла городить сложно (сеньор).
                                                Впрочем, в такой версии оно тоже даёт результат — «джун начитанный».
                                              +66

                                              Как я понял, главное при написании FizzBuzz — надёжно заблокировать выход из переговорки.

                                                +11
                                                Не увидел в статье претендента на сеньёра реализацию FizzBuzz на ассемблере (32/64)
                                                с многопоточным использованием. :)

                                                P.S. А, если серьёзно, cтатья просто суперская! Спасибо.
                                                FizzBuzz on rosettacode.org
                                                Ну, и немного отвлечённого Уроки от NeHe на masm64 — программирование задач с OpenGL на ассемблере.

                                                P.P.S. Минусаторы, можете выдохнуть, этот комментарий не для вас!

                                                Пользователи новомодных Фреймворков и языков программирования «курят» нервно в стороне когда вопрос решения задачи «максимально» отзывчив для пользователей и занимает немного в размере результирующего бинарника. :) (imho)
                                                  +6
                                                  «ASM – это чудесно», – думал я когда-то. Но что Вы будете делать со своим кодом лет через 5-10, если половина ноутбуков перейдёт на ARM?
                                                    –4

                                                    как будто на ARM нет ассемблера :)

                                                      +6

                                                      Есть конечно. Что Вы будете делать со всем Вашим кодом, который Вы за эти 5-10 лет написали под x86_64?

                                                        +9

                                                        Переписывать за сеньорскую зарплату!

                                                          –5
                                                          а «минусаторы» считают, что нет :)
                                                            +3

                                                            "Минусаторы", думаю, негодуют из-за того, что вы упорно не понимаете, что дело не в наличии или отсутствии ассемблера.

                                                              –2

                                                              они не понимают иронии. И, видимо, из тех, кто "программист на [%your_programming_language_name%]".
                                                              Смена технологий так сильно пугает, что "фсёпропало"?

                                                                0

                                                                Я за последнее время перепробовал толпу языков, постоянно пишу на трех совершенно разноплановых (шарп, раст, тс), и могу сказать что я лично больше верю в свою возможность сообщить нужную инфу компилятору чтобы он сделал что нужно. Да, я могу возиться с vtune и считать такты, но я никогда не полезу писать ассемблер, а подсуну интринсики/likely/… чтобы компилятор сам сделал то, что мне нужно. И обычно он куда умнее меня, а ещё он никогда* не ошибается.


                                                                Как итог: когда компилятор становится умнее, прогрмма оптимизируется автоматически, под любую платформу собирается максимум с некоторой потерей производительности, а минимум и без неё, потому что быстрый код написанный в таком стиле часто быстрый везде, просто по факту "думали прежде чем писали".


                                                                В общем, каждому своё, какой-нибудь asmbb за верх искусства воспринимать мне тяжело.

                                                            0
                                                            А вы знаете, что сейчас делают с кодом, написанным 10 лет назад на PHP5?
                                                            А с кодом на Delphi?

                                                            Но самое милое конечно это когда заходишь в универ и видишь, как там в виртуалочке запускают твою программу, написанную когда-то на turbo C. :)
                                                              0

                                                              Дописывают. Есть и дельфисты — дальние знакомые. Пыху мигрируют между версиями понемногу. Да..

                                                          +1
                                                          Это точно. И все x86_64 интринсики отправятся туда же. Хотя вроде как у ARM есть какие-то vector extensions. Но переписывать под них по-любому придется.
                                                            +1
                                                            1. Да, у ARM есть neon
                                                            2. Обычно интринсики — это не очень большая часть кода, заменить их гораздо более быстрая задача, чем переписать программу на ASM целиком.

                                                            Но в целом, конечно, векторные инструкции и правда не то место, где портируемость C сильно помогает.

                                                            +2

                                                            https://github.com/DLTcollab/sse2neon


                                                            Некоторые костыли, конечно, но всё сразу с нуля переписывать не потребуется.

                                                              0

                                                              Да тут не только ASM. Тут с высокой вероятностью интринсики ровно так же отлетят в сторону.

                                                              +1
                                                              Получается, претендент пропустил важный первый шаг: поискать готовое решение в Интернет?
                                                                0
                                                                Обычно bottleneck не в таких алгоритмах (в либах — мб, но не в обычном коде). Скорее всего, на событии скрола на 1 пиксель создаются объекты, много вьюшек с прозрачностью одна на одной или блочится главный поток. По крайней мере мы, пользователи нативных мобильных фрэймворков, заточены решать проблемы именно такого класса, т.к. именно в них 99% проблем с производительностью.
                                                                  +8
                                                                  Есть жизнь и за пределами фронт-энда
                                                                    0
                                                                    топикстартер писал про фронт, и я написал про фронт. Да и ваши задачи обычно давно решены, и боттлнек в отсутствии нужного индекса или ненужном джоине, а не в алгоритмах. К сожалению, время велосипедов прошло.
                                                                      +5

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

                                                                        0
                                                                        > Да и ваши задачи обычно давно решены, и боттлнек в отсутствии нужного индекса или ненужном джоине, а не в алгоритмах

                                                                        Не стоит рассуждать о вещах, от которых вы столь далеки. Но ничего, обычно мудрость приходит с возрастом.
                                                                  +26
                                                                  Мне кажется для сениора в такой реализации важно было бы спросить, а зачем это нужно и как используется этот код?
                                                                    +18
                                                                    зачем такие извращения если уже давно есть готовое решение на java? github.com/EnterpriseQualityCoding/FizzBuzzEnterpriseEdition

                                                                    /sarcasmoff
                                                                      –8
                                                                      я бы не позвонил, потому что понял что передо мной обычный сноб, лучше простой парень, чем такой «сеньор-помидор»
                                                                        +36
                                                                        На каждую саркастически-юмористическую статью найдется сеньор-помидор, который верит в реальность и серьёзность происходящего =)
                                                                          +13
                                                                          Тяжело жить без хаба «Юмор».
                                                                        +2
                                                                        Спасибо за задачку, было интересно подумать над ней!

                                                                        Я взял за основу customprint.c (работает примерно 9.2 сек на моей машине), и применил следующие идеи:

                                                                        — Экономить на вызовах fwrite. Для этого процессим числа в блоках, кратных 15. Я остановился на 35000 блоках. Дает небольшой выигрыш.
                                                                        — Поддерживать текущее число в виде строки и эмулировать инкремент. Ускоряет за счет того, мы не всегда итерируемся по всем цифрам текущего числа (гораздо чаще инкрементится только последняя цифра).
                                                                        — Экономить на инкрементах. Для этого заметим, что если после числа мы следующим выведем слово, то можно инкрементить на сразу 2, если два слова — то на 3.
                                                                        — Мелкие микрооптимизации, которые почти ни на что не повлияли (например, полное избавление от деления и взятия по модулю при инкременте)

                                                                        Итоговое решение работает за примерно 3.4 сек на моей машине (ссылка)

                                                                          0
                                                                          > Экономить на вызовах fwrite. Для этого процессим числа в блоках, кратных 15. Я остановился на 35000 блоках. Дает небольшой выигрыш

                                                                          Сомневаюсь, что это дает какой-то выигрыш, поскольку fwrite() уже буферизован. Возможно, если поиграть с размером буфера, используя setvbuf(), можно что-то выиграть, но это какие-то сущие копейки будут.

                                                                          > Поддерживать текущее число в виде строки и эмулировать инкремент. Ускоряет за счет того, мы не всегда итерируемся по всем цифрам текущего числа (гораздо чаще инкрементится только последняя цифра).

                                                                          Примерно эта идея и была использована в reusebuffer.c, только сразу для всего буфера.

                                                                          > Мелкие микрооптимизации, которые почти ни на что не повлияли (например, полное избавление от деления и взятия по модулю при инкременте)

                                                                          В customprint.c нет деления по модулю, я от него избавился шагом раньше, в unrolled.c (ну если не считать обработки хвоста, то его нет смысла хоть как-то оптимизировать, цикл на 10 итераций).
                                                                            0
                                                                            > Сомневаюсь, что это дает какой-то выигрыш, поскольку fwrite() уже буферизован.
                                                                            Я тоже так думал, но был удивлен, когда это дало примерно 1 сек выигрыша. Думаю передавать много маленьких буферов в fwrite хуже, чем буферы побольше.

                                                                            Преверить можно установив константу CHUNK_COUNT в 1.

                                                                            > В customprint.c нет деления по модулю
                                                                            Он был нужен мне в инкременте. Как говорится сам добавил, сам же и соптимизировал.

                                                                              0
                                                                              > Думаю передавать много маленьких буферов в fwrite хуже, чем буферы побольше.

                                                                              По идее не должно, поскольку fwrite буферизует вывод, т.е. далеко не каждый вызов fwrite() приводит к syscall'у write(), который, конечно, довольно дорогой.

                                                                              > Преверить можно установив константу CHUNK_COUNT в 1.

                                                                              Попробую, интересно. Я в процессе своих экспериментов играл с размером буфера, и не обнаружил статистически значимой разницы, то есть стандартного буферу размера BIFSIZ, который используется для (f)printf/(f)puts/fwrite/etc, вполне хватает.
                                                                              Возможно, тут сказывается какая-то разница в параметрах системы.

                                                                              Вы попробуйте вместо этого цикла в 35000 итераций задать буфер в 5 MB через setvbuf — будет ли разница? Если будет, то тогда к fwrite есть вопросы, конечно.

                                                                              Хотя у меня есть одно предположение — буферизация функций стандартной библиотеки обязательно должна быть thread-safe (а у меня ведь все компилируется с -pthread), так что скорее всего для сериализации доступа к единому буферу во всех этих функциях, в т.ч. и в fwrite(), используются mutex'ы, а блокировка/разблокировка mutex'а — это syscall'ы, переход из userspace в kernelspace, и это дорого. Как вариант, можно попробовать скомпилировать этот вариант без -pthread и посмотреть, изменится ли что-то.
                                                                                0
                                                                                Поигрался с размером буфера, никаких изменений не заметил. 5МБ буфера и 1 чанк выдали 4.8 сек, против 3.4 при 35000 чанках. Компиляция без -pthread и замена fwrite на fputs_unlocked тоже ничего не дали.

                                                                                Если что, использовал это:
                                                                                setvbuf(stdout, NULL, _IOFBF, 5242880);

                                                                                  0
                                                                                  Интересный эффект. У меня нет объяснений. Мне сложно представить, что fwrite такой неоптимальный
                                                                              0
                                                                              Про буферизацию: т.е. не имеет смысла в наивном варианте на шагах ветвления заполнять буфер, чтобы потом сделать один вызов printf?
                                                                                0
                                                                                Для вывода на консоль — имеет, потому как по умолчанию тогда построчная буферизация, в остальных случаях наверно нет.
                                                                                В любом случае нет смысла городить свою буферизацию, потому что в стандартной библиотеке C она уже есть, максимум — ее надо включить/поменять размер буфера, используя setbuf/setvbuf.
                                                                            +9
                                                                            История с собеседованием реальная или наложена на идею развития fizzBuzz?
                                                                              +36
                                                                              Ну наконец-то :)

                                                                              История полностью выдуманная, захотелось добавить немного драмы в сухую статью об оптимизации. Просто как-то пришла идея про возможную оптимизацию FizzBuzz через небольшой unrolling цикла, а дальше просто не смог вовремя остановиться (почти как герой статьи).

                                                                              Был еще один вариант, многопоточный с memory-mapped I/O, но он оказался сильно медленнее обычного многопоточного, я думаю, это вызвано тем, что когда маппируешь в память 7.5 гигов, и потом пишешь туда, то количество page fault'ов такое, что их обработка kernel'ом обходится очень дорого. Эта версия косвенно подтверждается тем, что использование huge pages (2M-байтных), вместо стандартных 4K-байтных заметно ускорило процесс, но все равно до обычного многопоточного варианта было далеко.
                                                                                +7
                                                                                Класс! Код читал через раз (ну не программист :), но ваши пояснения логики действий отлично добавляли ясности, ну и драматизма :).
                                                                                Вы не пробовали писать «технологические рассказы»? Ниша имхо свободна, последний раз ощущение схожее с ощущением, возникшим от вашей статьи у меня было от «мне не хватало одного байта» :)
                                                                                  +10
                                                                                  Спасибо :)

                                                                                  > Вы не пробовали писать «технологические рассказы»?
                                                                                  Вы удивитесь, но в числе моих хобби есть и такое. Надеюсь, что когда-то это доберется до публики :)
                                                                                    +5
                                                                                    Как там говорится...«неистово плюсуем!» :)
                                                                                      +4

                                                                                      удивился, прочитав "неистово плюсуем!" в обсуждении текста без кода на C++
                                                                                      :))

                                                                                  0
                                                                                  А можно небольшой гайд об использовании huge pages? Моя упорно не хочит маппить на них. Возможно, я чтото упускаю в системных настройках.
                                                                                    0
                                                                                    Для этого должна быть включена поддержка в kernel'е. В /proc/meminfo надо найти Hugepagesize, и при маппинге использовать именно этот размер.
                                                                                    В mmap'овском man'е написано, как правильно надо задавать флаг с размером huge page, там нужно правильный сдвиг сделать.
                                                                                    0
                                                                                    я думаю, это вызвано тем, что когда маппируешь в память 7.5 гигов, и потом пишешь туда, то количество page fault'ов такое, что их обработка kernel'ом обходится очень дорого.
                                                                                    Конечно, у Linux могут быть свои заморочки (хотя вряд ли), но под macOS, для десятков гигабайт, код:
                                                                                        for(int i = 0; i < LIMIT/NBUF; i++) {
                                                                                            fwrite(buf, 1, sizeof(buf), f);
                                                                                        }
                                                                                    Стабильно немного медленнее кода:
                                                                                        for(char *omap = pa->omap; omap < pa->omap + chunk; omap += pa->step) {
                                                                                            memcpy(omap, pa->buf, pa->szbuf);                  
                                                                                        }
                                                                                    Вариант с mmap(), ясное дело, больше тратит в пользовательском режиме, но существенно меньше тратит в режиме ядра.
                                                                                    Был еще один вариант, многопоточный с memory-mapped I/O, но он оказался сильно медленнее обычного многопоточного, я думаю, это вызвано тем
                                                                                    К гадалке не ходи, проблема в организации многопоточной обработки больших данных, сиречь, в порядке записи.

                                                                                    К примеру, если писать не по столбцам, а по строкам, можно потерять разы.
                                                                                      0
                                                                                      > код… Стабильно немного медленнее кода…

                                                                                      Довольно очевидно, что они не эквиваленты. Для полноты картины надо бы добавить mmap() в начале и munmap() в конце, и они немоментальные. К тому же хочется посмотреть, как делался mmap, с какими флагами — мы же не просто о записи в память говорим.

                                                                                      > К гадалке не ходи, проблема в организации многопоточной обработки больших данных, сиречь, в порядке записи.

                                                                                      Очень странный, ни на чем не основанный вывод.
                                                                                        0
                                                                                        Насчёт «немоментальные», строго говоря, ни munmap() в одном варианте, ни close() в обеих вариантах, не гарантирует записи данных на диск без явного использования fsync() или флага O_DSYNC в open(). В условиях ж не было уточнено, «в файл» или «на диск», наверное, проще на fsync() забить и реализовать в «в файл», а в файле изменения отображаются сразу после записи в отображаемую память и задолго до munmap().

                                                                                        Но! Что гарантировано, так это, что все page fault уже обработаны.

                                                                                        В любом случае, цена open()/map()/munmap()/close(), без синхронизации с диском, — доли процента от записи нескольких гигабайт в память.
                                                                                        К тому же хочется посмотреть, как делался mmap, с какими флагами — мы же не просто о записи в память говорим.
                                                                                        mmap(0, LIMIT*LTXT, PROT_WRITE|PROT_READ, MAP_SHARED|MAP_FILE, f, 0)
                                                                                        Оно ж, конечно, дьявол в деталях, но учебный пример https://habr.com/ru/post/55716/ вполне себе шустро копирует многогигабайтные файлы.

                                                                                        Возможно, для улучшения производительности можно было бы использовать что-то нестандартное, не POSIX, типа MAP_NOCACHE и т.п. Но и так неплохо ж.
                                                                                        > К гадалке не ходи, проблема в организации многопоточной обработки больших данных, сиречь, в порядке записи.

                                                                                        Очень странный, ни на чем не основанный вывод.
                                                                                        Как бы, когда начинали грешить на немасшабируемость подсистемы виртуальной памяти, почти всегда так и оказывалось. 64-бит адресацию для больших баз данных же придумывали, в основном.

                                                                                        Как бы, понятно, если несколько потоков пишут в области с шагом гигабайты, это одно, если с шагом десятки-сотни килобайт, это другое, а если с шагом десятки байт, это третья, самая тяжёлая ситуация.

                                                                                        Попробуйте разделить записи между потоками на 1...250000000, 250000001...500000000, 500000001...750000000 и, 750000001...1000000000.
                                                                                          0
                                                                                          > Попробуйте разделить записи между потоками на 1...250000000, 250000001...500000000, 500000001...750000000 и, 750000001...1000000000.

                                                                                          Именно так и делал (ну, ближайшие кратные 15 брал, конечно). И получал почти на секунду дольше, чем вариант с fwrite, при этом я даже huge page включал при mmap.

                                                                                          Может, на вашей системе нет Meltdown и Spectre mitigations, и переключения user space/kernel space намного быстрее происходят?
                                                                                  0
                                                                                  myitoa можно ускорить, развернуть цикл и писать сразу в выходной буфер вместо копирования
                                                                                    0
                                                                                    Согласен, можно избавиться от лишнего memcpy. Примерно что-то такое реализовано на следующем шаге.
                                                                                      0
                                                                                      Мне тут прилетел PR примерно на это самое, я его только чуть причесал: github.com/qrdl/fizzbuzz/blob/main/customprint2.c
                                                                                      Это дало около 30% прироста скорости, больше, чем я ожидал.
                                                                                      0
                                                                                      Интересно, а есть какие-то операции сверхбыстрого сложения массивов (наложение дампов памяти)?

                                                                                      Если да, наверное, можно попробовать подготовить относительно небольшие дампы (числа по возрастанию добитые пробелами до одного размера, Fizz/Buzz/FizzBuzz, дополнительные десятичные разряды, символы переноса строки). И потом накладывая их друг на друга с правильными смещениями собирать итоговый массив как из конструктора. Или нет?

                                                                                      p.s. Кстати, операцию наложения массивов можно перенести на видеокарту. Вот где простор для оптимизаций))
                                                                                        +3

                                                                                        На самом деле, критерии "синьорности" зависят от компании, и в данном конкретном случае старший разработчик реально будет заниматься микро оптимизациями и выжимать производительность из каждой инструкции, но обычно это немного не так.
                                                                                        На мой взгляд, старший разработчик должен был бы скорее написать код (даже для FizzBuzz), который хоть как-то можно тестировать, расширять и сопровождать. Возможно даже с тестами, документацией и проверками пред- и пост- условий. Только не надо шуток про корпоративную версию FizzBuzz.

                                                                                          +5
                                                                                          Иногда приходит product owner и говорит, что надо сделать вот такую-то штуку минимум в 5 раз быстрее, иначе в ней нет смысла. И тогда начинаются такие танцы с бубном, когда на калькуляторе считаешь, что влезает, а что не влезает в кэш процессора, и где можно избавится от лишнего if'а, чтобы branch prediction не обижать, и всякое такое. И о том, как это поддерживать, будем думать потом. Это тоже одна из сторон жизни, не самая приятная, но это не значит, что ее нет.
                                                                                            +2

                                                                                            Безусловно так может получиться. Я поэтому и написал, что критерии для определения старшего разработчика разнятся от компании к компании.
                                                                                            Основной мой посыл был в любом случае в том, что старший разработчик обычно видит и держит в уме больше деталей связанных с жизненным циклом продукта, его архитектурой и развитием системы. Безусловно, для этого есть другие типы заданий и секции собеседований, но и по FizzBuzz можно многое сказать. Допустим, если я по какой-то странной причине попросил бы кандидата на должность старшего разработчика писать FizzBuzz, меня бы уже очень сильно насторожило что реализация, как в статье, не вынесена в отдельную функцию, да ещё и сверху добавлен макрос (!) с очень общим именем (!!).

                                                                                              +2

                                                                                              Наоборот — самая приятная! :)

                                                                                                +1
                                                                                                Мсье знает толк в извращениях :D
                                                                                            +20
                                                                                            Вы извините, к вам тут зашёл тестировщик и обнаружил, что программа работает корректно не для всех N, а только для N кратных размеру буфера…

                                                                                            Reopened…
                                                                                              +5
                                                                                              Подумал, что надо расширить коммент, а то заминусуют же…

                                                                                              Фразу «Напишите программу, которая выводила бы числа от 1 до, скажем, миллиарда...» надо читать примерно так:
                                                                                              Наши аналитики провели исследование и пришли к выводу, что среднему пользователю будет достаточно вывода в миллиард строк. Поэтому давайте пока в качестве MVP сделаем так, а потом посмотрим на метрики, пособираем обратную связь и по результатам будем решать, как дальше развивать фичу.

                                                                                              А после торжественного выпуска фичи на прод события будут развиваться примерно так:
                                                                                              1. Прибегут пользователи с пожеланиями сделать настраиваемым число выводимых строк. Найдутся те, кому миллиард — это очень много («Для нашего маленького бизнеса за глаза будет достаточно от 1 до 1000»), и будет крупняк, которому подавай вывод в секстильон строк, а то и в два.
                                                                                              2. Прибегут эксплуататоры с вопросом: «А что фича жрет так много ресурсов впустую? Нам говорят, что большинству миллиард строк совсем не нужен, а вы всем так отдаёте!»
                                                                                              3. Прибегут маркетологи со словами: «Ой, фича такая популярная, но жрёт столько ресурсов (эксплуататоры жалуются). Давайте её тарифицировать! Сделаем так, что на бесплатном тарифе будет доступен вывод 1..K строк, на базовом — 1..L строк, а на VIP-тарифе все 1..M строк!»

                                                                                              А ваш код к этим котелкам совсем не готов. Переписывать слишком много придётся…
                                                                                                +3
                                                                                                Есть ещё вероятность, что можно заложиться на все эти кейсы, чтобы в будущем не больно было поддерживать и дорабатывать, а потом фича лежит и не используется вообще никем и никак.
                                                                                                  +1
                                                                                                  Вот полностью согласен. Часто с этим сталкивался, приходилось напоминать людям про ru.wikipedia.org/wiki/YAGNI
                                                                                                  Особенно прикольно, если фичей не будут пользоваться потому, что она слишком тормозная.
                                                                                                    +1

                                                                                                    Во-первых делать расширяемым код под всевозможные будущие хотелки — невозможно.
                                                                                                    Во-вторых это такой же антипаттерн как хардкод одного сценария, я бы назвал его "бесхребетный" код, который состоит из одних адаптеров-стратегий-репозиториев которые из пустого впорожнее переливают с миллиардом никогда не изменяемых опций. Посмотрите на физзбазз на Java из примеров выше — о да, вот уж где можно расширить и изменить что угодно. Явно подготовились к любой хотелке!

                                                                                                0

                                                                                                Вполне, однако, если мы /dev/null пишем, то это легко проверить, и тогда программа выполняется почти мговенно. А если не в /dev/null, то тут время io решает.


                                                                                                Шах и мат.

                                                                                                  +3

                                                                                                  Смотря какие требования. Я бы не стал оптимизировать производительность любой ценой в ущерб читаемости кода.

                                                                                                    –11

                                                                                                    Да, если senior на C (!) пишет такой неоптимальный первый вариант — это повод задуматься.


                                                                                                    Суть FizzBuzz в том, чтобы сразу отсеять тех, кто не умеет писать код.
                                                                                                    А в случае высокого уровня, тех, кто не умеет решить оптимально самую простую задачу, которая оптимально решается "в лоб":


                                                                                                    #include <stdio.h>
                                                                                                    
                                                                                                    int main()
                                                                                                    {
                                                                                                        for (int i = 0, f = 0; i < 1000000000; ++i)
                                                                                                        {
                                                                                                            if (!(i % 3)) printf("F"), f = 1;
                                                                                                            if (!(i % 5)) printf("B"), f = 1;
                                                                                                            if (f) printf("\n"), f = 0;
                                                                                                        }
                                                                                                    }

                                                                                                    Выше — самый простой и очевидный вариант (как раз тот "наивный вариант", от собеседуемого ожидаемый), который даёт (CPU такой же, проверил с Fizz/Buzz, да, там 28 секунд, за счёт длины строк):


                                                                                                    gcc x.c &&  time ./a.out > /dev/null                                                                                                            
                                                                                                    ./a.out > /dev/null  14,83s user 0,12s system 99% cpu 15,031 total

                                                                                                    После этого (при желании — до) senior должен спросить, каковы, собственно, требования к решению, а не заниматься бездумной оптимизацией.
                                                                                                    И только потом уже предлагают оптимизации, которыми являются:


                                                                                                    • Уменьшение совокупного количества системных вызовов.
                                                                                                    • Использование оптимизаций компилятора (как написать код, не мешающий компилятору).
                                                                                                    • Возможные способы алгоритмической оптимизации без сильного ущерба читаемости.

                                                                                                    Дальше — многопоточность с map->reduce.


                                                                                                    Никаких извращений с интринсиками (да ещё и без проверки на этапе выполнения, сработают ли они) делать не стоит, если конечно интервьюер не просит такого явно (а если просит — возможно стоит задуматься, но это зависит от задач, которые вам придётся выполнять).

                                                                                                      +4
                                                                                                      Вы проверили скорость, но не проверили ответ…

                                                                                                      Ваша реализация решает другую задачу: она не печатает пропущенные числа (а должна).
                                                                                                        –8

                                                                                                        Во-первых, это в данном случае, не столь важно: главное то, как должен выглядеть первичный вариант.
                                                                                                        Во-вторых, если вы посмотрите изначальное условие, которое было дано автором в статье, то ничего подобного не увидите (т.е., нет прямого указания на вывод числа, если оно не кратно, хотя возможно предположить из условия, что это подразумевается):


                                                                                                        — Здравствуйте, давайте начнем с небольшого теста, пока я ваше CV смотрю. Напишите программу, которая выводила бы числа от 1 до, скажем, миллиарда, притом если число кратно трем, то вместо числа выводится Fizz, если кратно пяти, то Buzz, а если и трем, и пяти, то FizzBuzz.

                                                                                                        В-третьих, "просто добавьте else" или, например, так:


                                                                                                        ...
                                                                                                            if (f)
                                                                                                            {
                                                                                                                printf("\n");
                                                                                                                f = 0;
                                                                                                                continue;
                                                                                                            }
                                                                                                        
                                                                                                           printf("%d\n", i);
                                                                                                        ...
                                                                                                          +3
                                                                                                          Так добавление else к условию кардинально замедляет выполнение программы.
                                                                                                          На моём железе и с моим gcc (всё собрано с O3) самый простой вариант автора (который первый) работает чуть меньше 35 секунд, а Ваш с continue (и полными строками) — чуть больше 45 секунд, разница больше четверти в пользу авторского простого решения.
                                                                                                            –4

                                                                                                            Да, насчёт замеров вы правы, здесь я ошибся.


                                                                                                            И чисто теоретически, любопытно: видимо, компилятор оптимизирует повторные вычисления (при желании, возможно посмотреть листинг того, что он нагенерил).
                                                                                                            Без оптимизаций авторский вариант у меня выполняется за 70-71с:


                                                                                                             ➭ gcc x.c &&  time ./a.out > /dev/null                                                                                                            
                                                                                                            ./a.out > /dev/null  70,03s user 0,76s system 99% cpu 1:10,94 total

                                                                                                            Мой же с continue за 81с. Автор немного выигрывает за счёт else if, и в таком варианте, я получаю 78 с.:


                                                                                                            ...
                                                                                                                    if (0 == i % 3) printf("Fizz"), f = 1;
                                                                                                                    else if (0 == i % 5) printf("Buzz"), f = 1;
                                                                                                            
                                                                                                                    if (!f)
                                                                                                                    {
                                                                                                                        printf("%d\n", i);
                                                                                                                        continue;
                                                                                                                   }
                                                                                                            
                                                                                                                   printf("\n");
                                                                                                                   f = 0;
                                                                                                            ...

                                                                                                            Но основный выигрыш автор за счёт числа системных вызовов: в случае двойной кратности, он сразу печатает "FizzBuzz", я же всегда делаю отдельный вызов для печати каждого слова.


                                                                                                            И это всё-равно не меняет сути комментария выше.


                                                                                                            Сам первичный код у автора написан запутанно и не оптимально (если хотите формально — у него цикломатическая сложность немного выше, чем нужно, при этом, задача на оптимизацию ещё не стояла).
                                                                                                            И более простой код, пусть и чуть более медленный, предпочтительней.
                                                                                                            Когда же, начинается оптимизация, как я писал в комментарии выше, возможно уменьшать число системных вызовов:


                                                                                                                enum PrintType { pt_none = 0x0, pt_fizz = 0x1, pt_buzz = 0x2, pt_fizzbuzz = 0x3 };
                                                                                                            
                                                                                                                for (int i = 0; i < 1000000000; ++i)
                                                                                                                {
                                                                                                                    switch (!(i % 3) | (!(i % 5) << 1))
                                                                                                                    {
                                                                                                                        case pt_fizz: printf("Fizz\n"); break;
                                                                                                                        case pt_buzz: printf("Buzz\n"); break;
                                                                                                                        case pt_fizzbuzz: printf("FizzBuzz\n"); break;
                                                                                                                        default: printf("%d\n", i); break;
                                                                                                                    }
                                                                                                               }
                                                                                                            

                                                                                                            Результат:


                                                                                                            ➭ gcc x.c &&  time ./a.out > /dev/null                                                                                                            
                                                                                                            ./a.out > /dev/null  69,39s user 0,68s system 99% cpu 1:10,17 total

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

                                                                                                              0
                                                                                                              ./a.out > /dev/null  70,03s
                                                                                                              ./a.out > /dev/null  69,39s

                                                                                                              Теряюсь в догадках — а сработала ли оптимизация?

                                                                                                            +15
                                                                                                            Напишите программу, которая выводила бы числа

                                                                                                            нет прямого указания на вывод числа

                                                                                                            А вы точно синьор?
                                                                                                              +1
                                                                                                              Во-первых, это в данном случае, не столь важно: главное то, как должен выглядеть первичный вариант.

                                                                                                              Мы Вам перезвоним :)
                                                                                                                +1
                                                                                                                нет прямого указания на вывод числа, если оно не кратно, хотя возможно предположить из условия, что это подразумевается


                                                                                                                Напишите программу, которая выводила бы числа от 1 до, скажем, миллиарда
                                                                                                                И как же должно выглядеть более прямое указание?
                                                                                                                  –4
                                                                                                                  И как же должно выглядеть более прямое указание?

                                                                                                                  По крайней
                                                                                                                  Лучше, как явная приписка:


                                                                                                                  "притом если число кратно трем, то вместо числа выводится Fizz, если кратно пяти, то Buzz, а если и трем, и пяти, то FizzBuzz, в ином случае выводится само число".


                                                                                                                  Но да, меня вчера переглючило.
                                                                                                                  Оправдаюсь хотя бы тем, что собеседования обычно не проводят в два часа ночи. :-)

                                                                                                              –2
                                                                                                              Выше — самый простой и очевидный вариант

                                                                                                              За такой "простой и очевидный вариант" следует сразу лицо бить.

                                                                                                                +1
                                                                                                                > За такой «простой и очевидный вариант» следует сразу лицо бить.

                                                                                                                Бить лицо — перебор, но вариант с тремя if'ами и двумя printf'ами на КАЖДУЮ итерацию действительно очень плох, я бы сильно задумался, брать ли такого даже джуниора, потому как его придется слишком много чему учить.
                                                                                                                  +1
                                                                                                                  потому как его придется слишком много чему учить.

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


                                                                                                                  if (!(i % 3)) printf("F"), f = 1;
                                                                                                                  if (!(i % 5)) printf("B"), f = 1;
                                                                                                                  if (f) printf("\n"), f = 0;

                                                                                                                  называет "более простым, предпочтительным" кодом, по сравнению с "запутанным и неоптимальным" оригиналом — то это конец.


                                                                                                                  но вариант с тремя if'ами и двумя printf'ами на КАЖДУЮ итерацию действительно очень плох

                                                                                                                  Плох по сравнению с чем именно? Вопросы оптимизации кода, вообще говоря, это не вопросы сениору, это вопросы мидлу. А сениор от мидла отличается тем, что после просьбы оптимизировать оригинальное решение скажет — "не стану, это не нужно".

                                                                                                                    +1
                                                                                                                    > называет «более простым, предпочтительным» кодом, по сравнению с «запутанным и неоптимальным» оригиналом — то это конец

                                                                                                                    Ну может не конец, но очень нехорошо, согласен.

                                                                                                                    > Плох по сравнению с чем именно?

                                                                                                                    По сравнению с начальным вариантом, где два if'a и один printf на итерацию. Я говорю чисто об алгоритмической сложности, не о лишней переменной и не об использовании comma оператора в таком контексте — это отдельный серьезный грех.
                                                                                                                      0
                                                                                                                      По сравнению с начальным вариантом, где два if'a и один printf на итерацию. Я говорю чисто об алгоритмической сложности

                                                                                                                      А я вам говорил про цикломатическую сложность.
                                                                                                                      Правда, я её неправильно посчитал вчера, так что с этой точки зрения, оба варианта одинаковы (сложность 4).


                                                                                                                      Модифицированная же лучше у варианта switch/case (тут по Маккейбу, 5 из-за цикла):


                                                                                                                      ➭ pmccabe *.c
                                                                                                                      5       5      ...       3if.c: main
                                                                                                                      5       5       ...      orig.c: main
                                                                                                                      3       5       ...      switches.c: main

                                                                                                                      Алгоритмически же они всё-таки O(n), хотя и различаются константой.


                                                                                                                      Но всё же читается проще вариант без вложенных условий, а в таком примере, — это первое, на что бы я обратил внимание.


                                                                                                                      и не об использовании comma оператора в таком контексте — это отдельный серьезный грех.

                                                                                                                      Это вообще не "грех", обычно я его не использую, в данном случае просто нет разницы.

                                                                                                                        +1

                                                                                                                        В одном вы правы точно: насчёт "лишних" вычислений я вчера написал херню, некорректно сравнил время, а также неправильно прикинул цикломатическую сложность.
                                                                                                                        В 2 часа ночи, видимо, лучше хотя бы пытаться заснуть, чем сидеть и что-то делать, когда не спится, т.к. делать не подумав — это не правильно…
                                                                                                                        Ваш пример выглядит сложнее, но он более оптимален, а формально по сложности он с 3if совпадает.

                                                                                                                        0
                                                                                                                        Проблема — когда научить нельзя.

                                                                                                                        И вы это всё увидели по FizzBuzz?


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

                                                                                                                        называет "более простым, предпочтительным" кодом, по сравнению с "запутанным и неоптимальным" оригиналом — то это конец.

                                                                                                                        Не придираясь к запятым, вы хотите сказать, что "вариант с тремя ифами" читается сложнее кода, в котором есть вложенные условия?


                                                                                                                        Вопросы оптимизации кода, вообще говоря, это не вопросы сениору, это вопросы мидлу. А сениор от мидла отличается тем, что после просьбы оптимизировать оригинальное решение скажет — "не стану, это не нужно".

                                                                                                                        Это вопрос не к "мидлу" или "сениору", разница между ними в том, что последний в контексте решения задачи бизнеса понимает, что сказать, и это не обязательно будет "не стану".

                                                                                                                          0
                                                                                                                          Не придираясь к запятым, вы хотите сказать, что "вариант с тремя ифами" читается сложнее кода, в котором есть вложенные условия?

                                                                                                                          Ну конечно!
                                                                                                                          На порядок проще, т.к. в нем вся логика выражена в явном виде. С первого взгляда на код понятно, что как и почему делается, четко виден флоу — нету никакого магического состояния в виде магического эф-а, которое этим флоу управляет и скрывает сам факт наличия условных переходов (вон вы цикломатическую сложность в итоге посчитать не смогли с первого раза правильно — именно из-за этого). С-но код, с управляющими эфами без обоснования просто не проходит нормальное ревью, вот и все.


                                                                                                                          Предсказание работает достаточно хорошо, и в большинстве случаев, конвейер не будет перезагружен.

                                                                                                                          Единственный реальный вариант, на котором предсказания бренчпредиктора работают хорошо — это вариант, при котором у вас подряд много раз одинаковых срабатываний. Ну, примерно как в случае проверки на выход из цикла — если у вас цикл длины 1000, то 999 раз подряд будет "да" и только в конце — "нет".
                                                                                                                          На любых более сложных паттернах конкретный бренч-предиктор конкретного процессора может сработать или не сработать в зависимости от фазы луны.


                                                                                                                          Интересный у вас подход. И как, много людей к вам идут на собеседование? И много уходят с разбитым лицом?

                                                                                                                          Речь, конечно, о том, когда такой код попадает в продакшн.

                                                                                                                            0
                                                                                                                            С первого взгляда на код понятно, что как и почему делается, четко виден флоу — нету никакого магического состояния в виде магического эф-а, которое этим флоу управляет и скрывает сам факт наличия условных переходов

                                                                                                                            Странно, вроде, флаг понятно, где ставится и где сбрасывается, и вся логика "плоская".
                                                                                                                            Ну, видимо, и тут "на вкус и цвет".
                                                                                                                            Учту.


                                                                                                                            вон вы цикломатическую сложность в итоге посчитать не смогли с первого раза правильно — именно из-за этого

                                                                                                                            Нет, я её посчитать не смог, потому что был "не в том состоянии". :-/


                                                                                                                            Единственный реальный вариант, на котором предсказания бренчпредиктора работают хорошо — это вариант, при котором у вас подряд много раз одинаковых срабатываний. Ну, примерно как в случае проверки на выход из цикла — если у вас цикл длины 1000, то 999 раз подряд будет "да" и только в конце — "нет".

                                                                                                                            Это основной вариант, под который он был "заточен", потому и хорошо работает.


                                                                                                                            Речь, конечно, о том, когда такой код попадает в продакшн.

                                                                                                                            Как-бы явно предполагалось и было указано, что это первый вариант для собеседования. Даже, если он не вполне корректный, о продакшне речи не шло. Да и вам не кажется странным заменять ревью кода мордобоем (и что вы будете делать, если программист окажется боксёром)?

                                                                                                                              0
                                                                                                                              Странно, вроде, флаг понятно, где ставится и где сбрасывается, и вся логика "плоская".

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


                                                                                                                              Ну, видимо, и тут "на вкус и цвет".

                                                                                                                              Это никакой не "вкус и цвет", в 2021 не надо экономить на байтах кода и по-этому так писать уже давно не обязательно.


                                                                                                                              Это основной вариант, под который он был "заточен", потому и хорошо работает.

                                                                                                                              Ну да. А остальные варианты просто уже зависят от конкретных реализаций в конкретном процессоре — потому на них и надеяться не стоит.


                                                                                                                              (и что вы будете делать, если программист окажется боксёром)

                                                                                                                              Удар по затылку спасет отца русской демократии.


                                                                                                                              Как-бы явно предполагалось и было указано, что это первый вариант для собеседования. Даже, если он не вполне корректный, о продакшне речи не шло.

                                                                                                                              Окей, окей, но я уверен, что в продакшене вы тоже пишите с эфками :)
                                                                                                                              Если нет — то сорян, конечно.

                                                                                                                        0
                                                                                                                        вариант с тремя if'ами и двумя printf'ами на КАЖДУЮ итерацию действительно очень плох

                                                                                                                        Это самый легко читающийся вариант решения "в лоб". Повторюсь, задачи оптимизировать изначально не стояло.
                                                                                                                        При этом, if — всего-лишь сравнение и переход.


                                                                                                                        И как-бы там вообще не требуется многократное получение остатка через условия, что я и отметил (но это как-то пропустили, заминусовав):


                                                                                                                        flag = (!(i % 3) | (!(i % 5) << 1))
                                                                                                                          +3
                                                                                                                          > При этом, if — всего-лишь сравнение и переход.

                                                                                                                          if — не «всего лишь», это очень дорогая операция в случае, когда branch predictor ошибается, что приводит к перегрузке всего конвейера. Согласно Wiki: Modern microprocessors tend to have quite long pipelines so that the misprediction delay is between 10 and 20 clock cycles en.wikipedia.org/wiki/Branch_predictor

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

                                                                                                                          Вариант со switch'ем действительно интересный, я его еще в том комменте заметил. Тут, конечно, у branch predictor'а шансов угадать почти нет, зато только один раз на цикл, надо будет проверить, какой он даст выигрыш. Сдвиг + ИЛИ + 2 НЕ сильно дешевле одного misprediction'а.
                                                                                                                            0

                                                                                                                            Предсказание работает достаточно хорошо, и в большинстве случаев, конвейер не будет перезагружен.
                                                                                                                            У Intel там совсем не не тривиальный проприетарный алгоритм предсказания.
                                                                                                                            Хотя, конечно, соглашусь, что лишнее условие при оптимизации, стоит убрать.
                                                                                                                            А switch, по сути, такой же if/else if, он в такой же cmp+je/jne выродится, так что бранч предиктор работать будет одинаково, т.к. он про него вообще не знает.


                                                                                                                            Также, начиная с C++-20, к switch/case возможно применять likely/unlikely.
                                                                                                                            Соответственно, в gcc возможно с __builtin_expect (макросами likely/unlikely в C) поэкспериментировать.


                                                                                                                            Выражение же, я так думаю, возможно ещё оптимизировать, надо только подумать, как.
                                                                                                                            Например, заменой div на сложения, используя признаки делимости, которые здесь вспомнили:


                                                                                                                            Признак делимости на 3 в двоичной системе счисления звучит следующим образом: «Число делится на 3 тогда и только тогда, когда сумма его цифр стоящих на четных местах отличается от суммы цифр, стоящих на нечетных местах, на число, делящееся на 3».
                                                                                                                              +2

                                                                                                                              У нас есть программа где скорость работы ВСЕГО приложения на 20% изменяется в лучшую сторону при простановки LIKELY в трёх ифах в разных местах. Так что насчет "Достаточно хорошего предсказания" — бабка надвое сказала.


                                                                                                                              Мерили со статистикой критерионом.

                                                                                                                                +5
                                                                                                                                > бабка надвое сказала

                                                                                                                                Максимально точное определение работы branch predictor'а :)
                                                                                                                                  0

                                                                                                                                  Любопытно… Учту.


                                                                                                                                  критерионом

                                                                                                                                  А киньте ссылку, пожалуйста. Я поискал, и мне оно выдаёт только некий сименсовый комплекс для анализа работы станков. Или это оно?

                                                                                                                                    0

                                                                                                                                    Не оно, но близко (который порт вот этого).

                                                                                                                                      0

                                                                                                                                      Ясно, спасибо. Но, похоже, только для Rust? И оригинал для Haskell...

                                                                                                                                        0

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

                                                                                                                                    0

                                                                                                                                    Бранч предиктор предварительно обучали холостыми запусками программы?

                                                                                                                                      0

                                                                                                                                      мы юзаем критерион: там есть и прогревы, и выкидывания слишком быстрых/слишком медленных кейсов, и многочислвенные прогоны, и статистика с доверительными интервалами… Поверьте, мы нормально замеряли

                                                                                                                                      0

                                                                                                                                      Было бы интересно поковырять дизасм. Возможно, дело не в бранч предикторе, а в том, что компилятор генерирует сильно разный код.


                                                                                                                                      Я не могу поверить в 20% разницы от трёх условных переходов, чинящихся likely-аннотациями, исключительно из-за (мис)предиктов.

                                                                                                                                        0

                                                                                                                                        Компилятор генерирует один и тот же код, я просто немного наврал: 20% разницы было не с лайкли, а с префетчем: https://doc.rust-lang.org/std/intrinsics/fn.prefetch_read_instruction.html


                                                                                                                                        Начал в голове восстанавливать прошедшие события и наткнулся что лайкли мы расставляли позже

                                                                                                                                  0
                                                                                                                                  Я наконец попробовал вариант со switch'ем, и он оказался примерно на 5-7% медленнее наивного, довольно неожиданно. Похоже, компилятор как-то соптимизировал два if'а лучше, чем один switch. Или может это результат того, что в случае со switch'ем branch predictor практически всегда в пролете, а с if'ами все же угадывает иногда.
                                                                                                                                +1
                                                                                                                                За такой "простой и очевидный вариант" следует сразу лицо бить.

                                                                                                                                Интересный у вас подход. И как, много людей к вам идут на собеседование? И много уходят с разбитым лицом?

                                                                                                                              0

                                                                                                                              В вот наконец то, когда последний вариант готов, настала пора заглянуть в performance counters процессора :) Вы, кстати, не смотрели — куда упираетесь? В память упираться вроде рановато.

                                                                                                                                +1
                                                                                                                                Это уже неизвестный мне уровень магии :)
                                                                                                                                Как это посмотреть? Есть какой-то гайд на эту тему?

                                                                                                                                Я подозреваю, что упирается все в память, syscall'ов в результате получается не так много. Кстати, появилась странная мысль попробовать отключить всякие Meltdown и Spectre mitigations в ядре, чтобы переключение user space-kernel space быстрее было, и сравнить.
                                                                                                                                  +1

                                                                                                                                  Intel vTune Amplifier (есть триал), если попроще.
                                                                                                                                  https://github.com/andikleen/pmu-tools — если под линуксом и хочется упороться на-отличненько. Вот статья, с которой можно начать: https://halobates.de/blog/p/262 .


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

                                                                                                                                    0
                                                                                                                                    > хочется упороться на-отличненько

                                                                                                                                    Очень хочется. Спасибо, займусь на досуге.

                                                                                                                                    > Про память — не должно бы в неё упираться, потому что всего в районе 5 гбайт/с записи, к тому же линейной — кэш процессора должен порулить тут.

                                                                                                                                    Разве кэш как-то помогает при записи в память? Чтения тут почти нет. 5 Gb/s при общем размере вывода в 7.5 Gb дают около 1.5 сек — очень близко к тому, во что я уперся.
                                                                                                                                      +1
                                                                                                                                      Разве кэш как-то помогает при записи в память?

                                                                                                                                      Обычно мешает при больших объемах, даже специальные комманды ввели для пересылки данных в обход кэша MOVNTDQ, что бы более эффективно использовать шину памяти.
                                                                                                                                        0
                                                                                                                                        Проблема не в шине, а в том как определить что пересылать…

                                                                                                                                        Юзер спейс тут не причем, можно все в модуле ядра сделать, но не надо использовать стандартную страничную организацию памяти.

                                                                                                                                        Тут дело в умном хеше или мультиплексоре\демультиплесоре, который косвенно должен быть настроен на задачу…
                                                                                                                                0
                                                                                                                                #define FIZZ do { memcpy(cur, «Fizz\n», 5); cur += 5; num++; } while (0)

                                                                                                                                вот тут 3 наверно
                                                                                                                                  +1

                                                                                                                                  здесь 5 — это длина строки “Fizz\n”

                                                                                                                                    +1
                                                                                                                                    Это же сдвиг указателя на буфер. «Fizz\n» таки 5 байт длиной.
                                                                                                                                    0
                                                                                                                                    А как же openmp? Не, до сеньора не дотягивает…
                                                                                                                                      +2
                                                                                                                                      А OpenMP даст выигрыш по сравнению с обычным использованием потоков? Я не знаю, никогда с ним не работал, но мне всегда казалось, это просто еще один уровень абстракции над родными для платформы потоками, и соответственно дополнительные расходы
                                                                                                                                        0
                                                                                                                                        А OpenMP даст выигрыш по сравнению с обычным использованием потоков?


                                                                                                                                        Главный выигрыш openmp в том, что код становится значительно проще, понятней и легче в сопровождении.
                                                                                                                                          0
                                                                                                                                          Это субъективно. Я привык к Pthread'ам, мне они кажутся вполне понятными, особенно когда не надо париться про синхронизацию, как в этом случае.
                                                                                                                                            +2

                                                                                                                                            Вот вы пишете "значительно проще, понятней и легче", а я слышу слово "оверхед" :)

                                                                                                                                        +1
                                                                                                                                        Я отвернулся от доски и увидел, что в переговорке я один. Через стеклянную стенку переговорки я разглядел интервьюера, который что-то быстро говорил секретарю, показывая пальцем в мою сторону. Он что, вызывает охрану? Похоже, что мне тут больше не рады.

                                                                                                                                        А что если всё более прозаично — например, у автора есть привычка вроде «ругать пятиэтажным матом всё вокруг» или «вести себя странно» в момент сосредоточенного обдумывания задачи, чего он сам может не заметить и что на самом деле было причиной такого поведения интервьюера? Вот представьте картину со стороны интервьюера: даёте вы человеку задачу — он задумался, ушел глубоко в свои размышления и внезапно начал задумчиво корчить рожи, грызть листочек, почесывать ногой нос и вообще лезть на потолок. Может интервьюер после увиденного не охрану звал а экзорциста;) Это конечно всё шутка, но хотелось бы отметить — я на своем примере знаю, что когда я слишком сосредоточен, то не отдаю себе отчёт в совершаемых действиях (примеры: пошел налить кофе — насыпал кофе в сахарницу и выбросил кружку в мусорное ведро. Или в процессе обдумывания разгрыз карандаш в щепки с угрожающим выражением лица, и т.п.)
                                                                                                                                          0

                                                                                                                                          хуже, если собеседуемый явным образом начинает проведение определённых ритуалов для погружения в задачу (раскуривает трубку, стучит в бубен, ритмично совершает высокоамплитудные колебания своим телом и т.п.) :)))

                                                                                                                                            +3
                                                                                                                                            Если это дает результат — почему нет :)
                                                                                                                                            Только посадить его отдельно, чтобы джуниоров не пугать.
                                                                                                                                              +5
                                                                                                                                              в комнату с мягкими стенами =)
                                                                                                                                          +5
                                                                                                                                          Все таки от сеньора, на мой взгляд, ожидается совсем другое. Читая эту статью, я ждал что после получения задания FizzBuzz, наш сеньор ПРЕЖДЕ чем начать писать код остановится, и начнет задавать вопросы собеседующему: какие ограничения по производительности, какие ограничения по объему памяти, требования к качеству кода и т.д. В общем — напишет маленькую спецификацию для данной задачи, а потом решит её самым простым подходящим способом.

                                                                                                                                          Знание технических тонкостей, показанные в статье — это конечно замечательно, но по моему не главное в сеньоре.
                                                                                                                                            +3

                                                                                                                                            и сначала напишет тесты и документацию :)

                                                                                                                                              +4
                                                                                                                                              есть жизнь и вне секты «без ТЗ не подходите» :)
                                                                                                                                                0
                                                                                                                                                А на собеседовании откажут по причине: «мы нанимаем сеньора, чтобы он сам всё придумал, а не нас озадачивал»