Ну это очень редкие животные, как единороги. Мне не попадались.
> ИМХО оба навыка важны, как и хард/софтскиллы, например.
Согласен. Но в одних ситуациях важнее одно, а в других — другое. К первому пойдут, когда надо сделать «все красиво», а ко второму, когда надо сделать что-то невозможное.
> Что делать когда варианты перестают влезать не только в 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 сек — очень близко к тому, во что я уперся.
> Все неподдерживаемые приседания с шага 2 до многопоточности ускорили код в 4 с небольшим раза. Даже с первого наивного варианта — разница в восемь раз. Современные машины, на которых будет выполняться такой код — уж как-нибудь наделены 4 камнями с гипертредингом.
Что значит «неподдерживаемые»? Где? Если на ARMе или до-Haswell'овских Intel'ах (не помню AMD'шную линейку), то да, но герой оптимизировал под конкретный проц в своем конкретном лаптопе. И если будет задача оптимизации какого-то сервиса, например, то это нормально — учитывать, на какой архитектуре этот сервис бежит. Можно было реализовать как простое побайтовое сравнение, но зачем, если есть векторные инструкции? Тем более герой хотел уесть интервьюера, у него была мотивация.
И ускорение чего-то в 4 и 8 раз — это офигенно хороший результат. Я, бывает, на работе бьюсь неделями, чтобы выжать какие-то 10% из сервиса.
> Если в XXI веке человек начинает с микрооптимизации условных переходов и ручной буферизации, его можно смело отправлять обратно в 1980-й год
Одним махом уменьшить кол-во branch инструкций в 45 раз, и количество вызовов printf'а в 15 раз, что дало ускорение почти в 2 раза — микрооптимизация? Ну ok. Готов к ссылке в 1980, я тогда был сильно моложе :)
На самом деле статья была о том, что «в жизни всегда есть место подвигу», т.е. почти в любой задаче найдется, что пооптимизировать, было бы желание, а вся история про якобы интервью — для драмы.
Но я удивился, увидев большое кол-во комментов о том, что не сениорское это дело — такие оптимизации. Мне кажется, есть два взгляда на то, кто такой сениор:
1. Сениор знает методики, пишет простой код с низкой цикломатической сложностью, этот код легко читать и поддерживать. Работает в большой конторе с четкими стандартами, читает на досуге GoF и «чистые» книги от дяди Боба. От джуниора отличается тем, что глубже влезает в предметную область, пишет код, который потом проще развивать. Он знает, где грабли, и обходит их метров за 10, так что нос у него красивый и ровный.
2. Сениор — опытный разработчик, который представляет, что с его кодом сделает компилятор, как он будет исполняться, знает, почему в большинстве случаев массив намного лучше связанного списка, при необходимости умеет в алгоритмы. Работает скорее всего в «бутике». Читает разное — МакКоннела, Ричарда Стивенса, да всякое разное, ну может кроме дяди Боба. От джуниора отличается тем, что занимается самыми сложными и нестандартными задачами, вянет от рутины. Про цикломатическую сложность его лучше не спрашивать, если не хочешь быть посланным куда подальше. Он тоже знает, где грабли, и ловко лавирует между ними, ну иногда получает по носу, как без этого.
Речь не о том, какой взгляд более правильный — скорее всего они оба правильные, просто каждый для своей ситуации. В «кровавом энтырпрайзе» от второго типа будет больше проблем, зато для «бутика» это находка. А когда первый тип приходит в «бутик» и пытается там навести порядок, редко это дает хороший результат, а в большой конторе он — столп. Бытие определяет сознание.
Мне лично ближе второй вариант, и примерно про такого сениора и был мой рассказ.
Не с нуля, конечно, но изменения будут заметные, поскольку наименьшее общее кратное становится 105. Но это нормально — менять код, когда меняются требования.
Дело в том, что заранее никогда не знаешь, как они изменятся, и, как показывает опыт, если ты закладываешься на некое возможное изменение какого-то требования. меняется какое-то другое требование, к которому ты не готов. Такая разновидность закона Мэрфи для программистов.
А что, в Сбере спрашивают 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 сек — очень близко к тому, во что я уперся.
Что значит «неподдерживаемые»? Где? Если на ARMе или до-Haswell'овских Intel'ах (не помню AMD'шную линейку), то да, но герой оптимизировал под конкретный проц в своем конкретном лаптопе. И если будет задача оптимизации какого-то сервиса, например, то это нормально — учитывать, на какой архитектуре этот сервис бежит. Можно было реализовать как простое побайтовое сравнение, но зачем, если есть векторные инструкции? Тем более герой хотел уесть интервьюера, у него была мотивация.
И ускорение чего-то в 4 и 8 раз — это офигенно хороший результат. Я, бывает, на работе бьюсь неделями, чтобы выжать какие-то 10% из сервиса.
> Если в XXI веке человек начинает с микрооптимизации условных переходов и ручной буферизации, его можно смело отправлять обратно в 1980-й год
Одним махом уменьшить кол-во branch инструкций в 45 раз, и количество вызовов printf'а в 15 раз, что дало ускорение почти в 2 раза — микрооптимизация? Ну ok. Готов к ссылке в 1980, я тогда был сильно моложе :)
Но я удивился, увидев большое кол-во комментов о том, что не сениорское это дело — такие оптимизации. Мне кажется, есть два взгляда на то, кто такой сениор:
1. Сениор знает методики, пишет простой код с низкой цикломатической сложностью, этот код легко читать и поддерживать. Работает в большой конторе с четкими стандартами, читает на досуге GoF и «чистые» книги от дяди Боба. От джуниора отличается тем, что глубже влезает в предметную область, пишет код, который потом проще развивать. Он знает, где грабли, и обходит их метров за 10, так что нос у него красивый и ровный.
2. Сениор — опытный разработчик, который представляет, что с его кодом сделает компилятор, как он будет исполняться, знает, почему в большинстве случаев массив намного лучше связанного списка, при необходимости умеет в алгоритмы. Работает скорее всего в «бутике». Читает разное — МакКоннела, Ричарда Стивенса, да всякое разное, ну может кроме дяди Боба. От джуниора отличается тем, что занимается самыми сложными и нестандартными задачами, вянет от рутины. Про цикломатическую сложность его лучше не спрашивать, если не хочешь быть посланным куда подальше. Он тоже знает, где грабли, и ловко лавирует между ними, ну иногда получает по носу, как без этого.
Речь не о том, какой взгляд более правильный — скорее всего они оба правильные, просто каждый для своей ситуации. В «кровавом энтырпрайзе» от второго типа будет больше проблем, зато для «бутика» это находка. А когда первый тип приходит в «бутик» и пытается там навести порядок, редко это дает хороший результат, а в большой конторе он — столп. Бытие определяет сознание.
Мне лично ближе второй вариант, и примерно про такого сениора и был мой рассказ.
Дело в том, что заранее никогда не знаешь, как они изменятся, и, как показывает опыт, если ты закладываешься на некое возможное изменение какого-то требования. меняется какое-то другое требование, к которому ты не готов. Такая разновидность закона Мэрфи для программистов.