Ну это очень редкие животные, как единороги. Мне не попадались.
> ИМХО оба навыка важны, как и хард/софтскиллы, например.
Согласен. Но в одних ситуациях важнее одно, а в других — другое. К первому пойдут, когда надо сделать «все красиво», а ко второму, когда надо сделать что-то невозможное.
> Что делать когда варианты перестают влезать не только в 10 байт, но и вообще в AVX512?
Чтобы число в десятичном виде перестало влезать в AVX512, оно должно быть больше 64 байт, то есть 10^64 (здесь ^ — это степень, не XOR). Я не знаю имен для таких чисел, но сочувствую любому, кто решит писать FizzBuzz до 10^64 — ему не суждено увидеть результат :)
Суть статьи была не в том, кто круче, а в том, что если хочется упороться, то для этого почти всегда можно найти какую-то возможность, как-то так.
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'а.
> А время загрузки программы засчитывается к времени выполнения?
Если засекать время, используя time (я именно так делал), то да, будет. Но вся программа не будет сразу грузится в этом случае, Linux мапит куски исполняемого файла в память, отдельно по сегментам, и в данном случае .data будет отдельно замаплен, и будет подгружаться по мере необходимости (ну как page fault случится), при этом будут использоваться скорее всего стандартные 4K-страницы, так что не исключаю, что каждый раз будет читаться с диска 4K, и это будет страшно медленно. Но я все же надеюсь, что тут есть какие-то оптимизации, и можно страницы читать пачками.
Запуск с RAM-диска, конечно, ускорит чтение, но от page fault'ов никуда не уйти, а это опять переключение user space/kernel space, а с недавних пор, спасибо Meltdown и Spectre, это стало очень дорогой операцией.
Для вывода на консоль — имеет, потому как по умолчанию тогда построчная буферизация, в остальных случаях наверно нет.
В любом случае нет смысла городить свою буферизацию, потому что в стандартной библиотеке C она уже есть, максимум — ее надо включить/поменять размер буфера, используя setbuf/setvbuf.
> называет «более простым, предпочтительным» кодом, по сравнению с «запутанным и неоптимальным» оригиналом — то это конец
Ну может не конец, но очень нехорошо, согласен.
> Плох по сравнению с чем именно?
По сравнению с начальным вариантом, где два if'a и один printf на итерацию. Я говорю чисто об алгоритмической сложности, не о лишней переменной и не об использовании comma оператора в таком контексте — это отдельный серьезный грех.
У меня была мысль попробовать блоками не по 15, а, скажем, по 45, чтобы оценить, как это влияет, но было лень столько кода писать :)
Для миллиарда уже было бы проще вообще не дергать printf, а просто подготовить сразу буфер с результатом, и его вывести — это уже выше предлагали. Размер программы вырастает на 7.5 Gb. Кстати, подозреваю, что станет сильно медленнее, так как при чтении .data (через memory-mapped I/O) опять же упираемся в кучу page fault'ов, значит переключения user space/kernel space, а это медленно.
> Про память — не должно бы в неё упираться, потому что всего в районе 5 гбайт/с записи, к тому же линейной — кэш процессора должен порулить тут.
Разве кэш как-то помогает при записи в память? Чтения тут почти нет. 5 Gb/s при общем размере вывода в 7.5 Gb дают около 1.5 сек — очень близко к тому, во что я уперся.
Максимально точное определение работы branch predictor'а :)
А что, в Сбере спрашивают FizzBuzz? Тогда они скоро узнают про интринсики :D
Ну это очень редкие животные, как единороги. Мне не попадались.
> ИМХО оба навыка важны, как и хард/софтскиллы, например.
Согласен. Но в одних ситуациях важнее одно, а в других — другое. К первому пойдут, когда надо сделать «все красиво», а ко второму, когда надо сделать что-то невозможное.
Не стоит рассуждать о вещах, от которых вы столь далеки. Но ничего, обычно мудрость приходит с возрастом.
Чтобы число в десятичном виде перестало влезать в AVX512, оно должно быть больше 64 байт, то есть 10^64 (здесь ^ — это степень, не XOR). Я не знаю имен для таких чисел, но сочувствую любому, кто решит писать FizzBuzz до 10^64 — ему не суждено увидеть результат :)
Суть статьи была не в том, кто круче, а в том, что если хочется упороться, то для этого почти всегда можно найти какую-то возможность, как-то так.
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'а.
Если засекать время, используя time (я именно так делал), то да, будет. Но вся программа не будет сразу грузится в этом случае, Linux мапит куски исполняемого файла в память, отдельно по сегментам, и в данном случае .data будет отдельно замаплен, и будет подгружаться по мере необходимости (ну как page fault случится), при этом будут использоваться скорее всего стандартные 4K-страницы, так что не исключаю, что каждый раз будет читаться с диска 4K, и это будет страшно медленно. Но я все же надеюсь, что тут есть какие-то оптимизации, и можно страницы читать пачками.
Запуск с RAM-диска, конечно, ускорит чтение, но от page fault'ов никуда не уйти, а это опять переключение user space/kernel space, а с недавних пор, спасибо Meltdown и Spectre, это стало очень дорогой операцией.
В любом случае нет смысла городить свою буферизацию, потому что в стандартной библиотеке C она уже есть, максимум — ее надо включить/поменять размер буфера, используя setbuf/setvbuf.
Ну может не конец, но очень нехорошо, согласен.
> Плох по сравнению с чем именно?
По сравнению с начальным вариантом, где два if'a и один printf на итерацию. Я говорю чисто об алгоритмической сложности, не о лишней переменной и не об использовании comma оператора в таком контексте — это отдельный серьезный грех.
Для миллиарда уже было бы проще вообще не дергать printf, а просто подготовить сразу буфер с результатом, и его вывести — это уже выше предлагали. Размер программы вырастает на 7.5 Gb. Кстати, подозреваю, что станет сильно медленнее, так как при чтении .data (через memory-mapped I/O) опять же упираемся в кучу page fault'ов, значит переключения user space/kernel space, а это медленно.
Очень хочется. Спасибо, займусь на досуге.
> Про память — не должно бы в неё упираться, потому что всего в районе 5 гбайт/с записи, к тому же линейной — кэш процессора должен порулить тут.
Разве кэш как-то помогает при записи в память? Чтения тут почти нет. 5 Gb/s при общем размере вывода в 7.5 Gb дают около 1.5 сек — очень близко к тому, во что я уперся.