> Все неподдерживаемые приседания с шага 2 до многопоточности ускорили код в 4 с небольшим раза. Даже с первого наивного варианта — разница в восемь раз. Современные машины, на которых будет выполняться такой код — уж как-нибудь наделены 4 камнями с гипертредингом.
Что значит «неподдерживаемые»? Где? Если на ARMе или до-Haswell'овских Intel'ах (не помню AMD'шную линейку), то да, но герой оптимизировал под конкретный проц в своем конкретном лаптопе. И если будет задача оптимизации какого-то сервиса, например, то это нормально — учитывать, на какой архитектуре этот сервис бежит. Можно было реализовать как простое побайтовое сравнение, но зачем, если есть векторные инструкции? Тем более герой хотел уесть интервьюера, у него была мотивация.
И ускорение чего-то в 4 и 8 раз — это офигенно хороший результат. Я, бывает, на работе бьюсь неделями, чтобы выжать какие-то 10% из сервиса.
> Если в XXI веке человек начинает с микрооптимизации условных переходов и ручной буферизации, его можно смело отправлять обратно в 1980-й год
Одним махом уменьшить кол-во branch инструкций в 45 раз, и количество вызовов printf'а в 15 раз, что дало ускорение почти в 2 раза — микрооптимизация? Ну ok. Готов к ссылке в 1980, я тогда был сильно моложе :)
На самом деле статья была о том, что «в жизни всегда есть место подвигу», т.е. почти в любой задаче найдется, что пооптимизировать, было бы желание, а вся история про якобы интервью — для драмы.
Но я удивился, увидев большое кол-во комментов о том, что не сениорское это дело — такие оптимизации. Мне кажется, есть два взгляда на то, кто такой сениор:
1. Сениор знает методики, пишет простой код с низкой цикломатической сложностью, этот код легко читать и поддерживать. Работает в большой конторе с четкими стандартами, читает на досуге GoF и «чистые» книги от дяди Боба. От джуниора отличается тем, что глубже влезает в предметную область, пишет код, который потом проще развивать. Он знает, где грабли, и обходит их метров за 10, так что нос у него красивый и ровный.
2. Сениор — опытный разработчик, который представляет, что с его кодом сделает компилятор, как он будет исполняться, знает, почему в большинстве случаев массив намного лучше связанного списка, при необходимости умеет в алгоритмы. Работает скорее всего в «бутике». Читает разное — МакКоннела, Ричарда Стивенса, да всякое разное, ну может кроме дяди Боба. От джуниора отличается тем, что занимается самыми сложными и нестандартными задачами, вянет от рутины. Про цикломатическую сложность его лучше не спрашивать, если не хочешь быть посланным куда подальше. Он тоже знает, где грабли, и ловко лавирует между ними, ну иногда получает по носу, как без этого.
Речь не о том, какой взгляд более правильный — скорее всего они оба правильные, просто каждый для своей ситуации. В «кровавом энтырпрайзе» от второго типа будет больше проблем, зато для «бутика» это находка. А когда первый тип приходит в «бутик» и пытается там навести порядок, редко это дает хороший результат, а в большой конторе он — столп. Бытие определяет сознание.
Мне лично ближе второй вариант, и примерно про такого сениора и был мой рассказ.
Не с нуля, конечно, но изменения будут заметные, поскольку наименьшее общее кратное становится 105. Но это нормально — менять код, когда меняются требования.
Дело в том, что заранее никогда не знаешь, как они изменятся, и, как показывает опыт, если ты закладываешься на некое возможное изменение какого-то требования. меняется какое-то другое требование, к которому ты не готов. Такая разновидность закона Мэрфи для программистов.
> За такой «простой и очевидный вариант» следует сразу лицо бить.
Бить лицо — перебор, но вариант с тремя if'ами и двумя printf'ами на КАЖДУЮ итерацию действительно очень плох, я бы сильно задумался, брать ли такого даже джуниора, потому как его придется слишком много чему учить.
Это уже неизвестный мне уровень магии :)
Как это посмотреть? Есть какой-то гайд на эту тему?
Я подозреваю, что упирается все в память, syscall'ов в результате получается не так много. Кстати, появилась странная мысль попробовать отключить всякие Meltdown и Spectre mitigations в ядре, чтобы переключение user space-kernel space быстрее было, и сравнить.
Это называется «буферизация».
В стандартной библиотеке C (на Linux, по крайней мере) когда вывод идет на консоль, стандартные функции вывода (f)printf/(f)puts/fwrite/etc используют line buffering, т.е. каждый символ `\n` приводит к fflush'у. Когда вывод перенаправлен в файл, то по умолчанию full buffering с буфером размера BUFSIZ, но при желании можно установить и свой буфер, побольше.
Смысл в том, что, как я написал в начале, весь вывод идет в файл или даже в /dev/null, так что буферизация там уже есть.
А OpenMP даст выигрыш по сравнению с обычным использованием потоков? Я не знаю, никогда с ним не работал, но мне всегда казалось, это просто еще один уровень абстракции над родными для платформы потоками, и соответственно дополнительные расходы
> Думаю передавать много маленьких буферов в 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 и посмотреть, изменится ли что-то.
Это точно. И все x86_64 интринсики отправятся туда же. Хотя вроде как у ARM есть какие-то vector extensions. Но переписывать под них по-любому придется.
Помимо Fizz, Buzz и FizzBuzz надо еще выводить числа.
> Например, если в первой тысяче Fizz, Buzz и FizzBuz каждый встречается по 10 раз, то получается в миллионе оно будет встречаться по 10.000 раз, а в миллиарде по 10.000.000 раз? Получается вместо пересчета можно всего миллиарда можно посчитать первую тысячу, и выводить просто кратные результаты?
Это некорректно, поскольку ни тысяча, ни миллион не кратны 15. Вот если взять полторы тысячи и полтора миллиона, тогда да, эта логика сработает. Но, как сказано выше, числа тоже надо выводить.
Вот полностью согласен. Часто с этим сталкивался, приходилось напоминать людям про ru.wikipedia.org/wiki/YAGNI
Особенно прикольно, если фичей не будут пользоваться потому, что она слишком тормозная.
Для этого должна быть включена поддержка в kernel'е. В /proc/meminfo надо найти Hugepagesize, и при маппинге использовать именно этот размер.
В mmap'овском man'е написано, как правильно надо задавать флаг с размером huge page, там нужно правильный сдвиг сделать.
Иногда приходит product owner и говорит, что надо сделать вот такую-то штуку минимум в 5 раз быстрее, иначе в ней нет смысла. И тогда начинаются такие танцы с бубном, когда на калькуляторе считаешь, что влезает, а что не влезает в кэш процессора, и где можно избавится от лишнего if'а, чтобы branch prediction не обижать, и всякое такое. И о том, как это поддерживать, будем думать потом. Это тоже одна из сторон жизни, не самая приятная, но это не значит, что ее нет.
> Вы не пробовали писать «технологические рассказы»?
Вы удивитесь, но в числе моих хобби есть и такое. Надеюсь, что когда-то это доберется до публики :)
История полностью выдуманная, захотелось добавить немного драмы в сухую статью об оптимизации. Просто как-то пришла идея про возможную оптимизацию FizzBuzz через небольшой unrolling цикла, а дальше просто не смог вовремя остановиться (почти как герой статьи).
Был еще один вариант, многопоточный с memory-mapped I/O, но он оказался сильно медленнее обычного многопоточного, я думаю, это вызвано тем, что когда маппируешь в память 7.5 гигов, и потом пишешь туда, то количество page fault'ов такое, что их обработка kernel'ом обходится очень дорого. Эта версия косвенно подтверждается тем, что использование huge pages (2M-байтных), вместо стандартных 4K-байтных заметно ускорило процесс, но все равно до обычного многопоточного варианта было далеко.
Что значит «неподдерживаемые»? Где? Если на ARMе или до-Haswell'овских Intel'ах (не помню AMD'шную линейку), то да, но герой оптимизировал под конкретный проц в своем конкретном лаптопе. И если будет задача оптимизации какого-то сервиса, например, то это нормально — учитывать, на какой архитектуре этот сервис бежит. Можно было реализовать как простое побайтовое сравнение, но зачем, если есть векторные инструкции? Тем более герой хотел уесть интервьюера, у него была мотивация.
И ускорение чего-то в 4 и 8 раз — это офигенно хороший результат. Я, бывает, на работе бьюсь неделями, чтобы выжать какие-то 10% из сервиса.
> Если в XXI веке человек начинает с микрооптимизации условных переходов и ручной буферизации, его можно смело отправлять обратно в 1980-й год
Одним махом уменьшить кол-во branch инструкций в 45 раз, и количество вызовов printf'а в 15 раз, что дало ускорение почти в 2 раза — микрооптимизация? Ну ok. Готов к ссылке в 1980, я тогда был сильно моложе :)
Но я удивился, увидев большое кол-во комментов о том, что не сениорское это дело — такие оптимизации. Мне кажется, есть два взгляда на то, кто такой сениор:
1. Сениор знает методики, пишет простой код с низкой цикломатической сложностью, этот код легко читать и поддерживать. Работает в большой конторе с четкими стандартами, читает на досуге GoF и «чистые» книги от дяди Боба. От джуниора отличается тем, что глубже влезает в предметную область, пишет код, который потом проще развивать. Он знает, где грабли, и обходит их метров за 10, так что нос у него красивый и ровный.
2. Сениор — опытный разработчик, который представляет, что с его кодом сделает компилятор, как он будет исполняться, знает, почему в большинстве случаев массив намного лучше связанного списка, при необходимости умеет в алгоритмы. Работает скорее всего в «бутике». Читает разное — МакКоннела, Ричарда Стивенса, да всякое разное, ну может кроме дяди Боба. От джуниора отличается тем, что занимается самыми сложными и нестандартными задачами, вянет от рутины. Про цикломатическую сложность его лучше не спрашивать, если не хочешь быть посланным куда подальше. Он тоже знает, где грабли, и ловко лавирует между ними, ну иногда получает по носу, как без этого.
Речь не о том, какой взгляд более правильный — скорее всего они оба правильные, просто каждый для своей ситуации. В «кровавом энтырпрайзе» от второго типа будет больше проблем, зато для «бутика» это находка. А когда первый тип приходит в «бутик» и пытается там навести порядок, редко это дает хороший результат, а в большой конторе он — столп. Бытие определяет сознание.
Мне лично ближе второй вариант, и примерно про такого сениора и был мой рассказ.
Дело в том, что заранее никогда не знаешь, как они изменятся, и, как показывает опыт, если ты закладываешься на некое возможное изменение какого-то требования. меняется какое-то другое требование, к которому ты не готов. Такая разновидность закона Мэрфи для программистов.
Бить лицо — перебор, но вариант с тремя if'ами и двумя printf'ами на КАЖДУЮ итерацию действительно очень плох, я бы сильно задумался, брать ли такого даже джуниора, потому как его придется слишком много чему учить.
Как это посмотреть? Есть какой-то гайд на эту тему?
Я подозреваю, что упирается все в память, syscall'ов в результате получается не так много. Кстати, появилась странная мысль попробовать отключить всякие Meltdown и Spectre mitigations в ядре, чтобы переключение user space-kernel space быстрее было, и сравнить.
В стандартной библиотеке C (на Linux, по крайней мере) когда вывод идет на консоль, стандартные функции вывода (f)printf/(f)puts/fwrite/etc используют line buffering, т.е. каждый символ `\n` приводит к fflush'у. Когда вывод перенаправлен в файл, то по умолчанию full buffering с буфером размера BUFSIZ, но при желании можно установить и свой буфер, побольше.
Смысл в том, что, как я написал в начале, весь вывод идет в файл или даже в /dev/null, так что буферизация там уже есть.
Только посадить его отдельно, чтобы джуниоров не пугать.
По идее не должно, поскольку 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 и посмотреть, изменится ли что-то.
> Например, если в первой тысяче Fizz, Buzz и FizzBuz каждый встречается по 10 раз, то получается в миллионе оно будет встречаться по 10.000 раз, а в миллиарде по 10.000.000 раз? Получается вместо пересчета можно всего миллиарда можно посчитать первую тысячу, и выводить просто кратные результаты?
Это некорректно, поскольку ни тысяча, ни миллион не кратны 15. Вот если взять полторы тысячи и полтора миллиона, тогда да, эта логика сработает. Но, как сказано выше, числа тоже надо выводить.
Особенно прикольно, если фичей не будут пользоваться потому, что она слишком тормозная.
В mmap'овском man'е написано, как правильно надо задавать флаг с размером huge page, там нужно правильный сдвиг сделать.
> Вы не пробовали писать «технологические рассказы»?
Вы удивитесь, но в числе моих хобби есть и такое. Надеюсь, что когда-то это доберется до публики :)
История полностью выдуманная, захотелось добавить немного драмы в сухую статью об оптимизации. Просто как-то пришла идея про возможную оптимизацию FizzBuzz через небольшой unrolling цикла, а дальше просто не смог вовремя остановиться (почти как герой статьи).
Был еще один вариант, многопоточный с memory-mapped I/O, но он оказался сильно медленнее обычного многопоточного, я думаю, это вызвано тем, что когда маппируешь в память 7.5 гигов, и потом пишешь туда, то количество page fault'ов такое, что их обработка kernel'ом обходится очень дорого. Эта версия косвенно подтверждается тем, что использование huge pages (2M-байтных), вместо стандартных 4K-байтных заметно ускорило процесс, но все равно до обычного многопоточного варианта было далеко.