> За такой «простой и очевидный вариант» следует сразу лицо бить.
Бить лицо — перебор, но вариант с тремя 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-байтных заметно ускорило процесс, но все равно до обычного многопоточного варианта было далеко.
> Экономить на вызовах fwrite. Для этого процессим числа в блоках, кратных 15. Я остановился на 35000 блоках. Дает небольшой выигрыш
Сомневаюсь, что это дает какой-то выигрыш, поскольку fwrite() уже буферизован. Возможно, если поиграть с размером буфера, используя setvbuf(), можно что-то выиграть, но это какие-то сущие копейки будут.
> Поддерживать текущее число в виде строки и эмулировать инкремент. Ускоряет за счет того, мы не всегда итерируемся по всем цифрам текущего числа (гораздо чаще инкрементится только последняя цифра).
Примерно эта идея и была использована в reusebuffer.c, только сразу для всего буфера.
> Мелкие микрооптимизации, которые почти ни на что не повлияли (например, полное избавление от деления и взятия по модулю при инкременте)
В customprint.c нет деления по модулю, я от него избавился шагом раньше, в unrolled.c (ну если не считать обработки хвоста, то его нет смысла хоть как-то оптимизировать, цикл на 10 итераций).
Более-менее используется память в последнем варианте — для каждого потока выделяется буфер в 3M * 119 байт / 15 = 22.7 Mb, для 4 потоков выходит 91 Mb. Все остальные варианты очень скромные по памяти.
Я проверял — одинаково правильно :)
Просто проверять каждый раз 7.5-гиговый файл довольно муторно, я проверил первый, а дальше просто сверял размер и контрольные суммы
Проблема с трудоустройством после какого-то возраста действительно наступает.
Мне 48, из них последние 30 занимаюсь программированием, CV соответствующее, но сколько его не посылал — ноль реакции. Убрал из CV дату рождения и самые старые места работы (хотя там было чем похвастаться), так что можно предположить, что мне лет 35 каких — стал получать приглашения на интервью.
И это несмотря на то, что все работодатели гордо пишут всякое типа equal opportunity employer. Причины у работодателей могут быть разные, но выходит, что возраст надо скрывать.
Бить лицо — перебор, но вариант с тремя 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-байтных заметно ускорило процесс, но все равно до обычного многопоточного варианта было далеко.
Сомневаюсь, что это дает какой-то выигрыш, поскольку fwrite() уже буферизован. Возможно, если поиграть с размером буфера, используя setvbuf(), можно что-то выиграть, но это какие-то сущие копейки будут.
> Поддерживать текущее число в виде строки и эмулировать инкремент. Ускоряет за счет того, мы не всегда итерируемся по всем цифрам текущего числа (гораздо чаще инкрементится только последняя цифра).
Примерно эта идея и была использована в reusebuffer.c, только сразу для всего буфера.
> Мелкие микрооптимизации, которые почти ни на что не повлияли (например, полное избавление от деления и взятия по модулю при инкременте)
В customprint.c нет деления по модулю, я от него избавился шагом раньше, в unrolled.c (ну если не считать обработки хвоста, то его нет смысла хоть как-то оптимизировать, цикл на 10 итераций).
Просто проверять каждый раз 7.5-гиговый файл довольно муторно, я проверил первый, а дальше просто сверял размер и контрольные суммы
Мне 48, из них последние 30 занимаюсь программированием, CV соответствующее, но сколько его не посылал — ноль реакции. Убрал из CV дату рождения и самые старые места работы (хотя там было чем похвастаться), так что можно предположить, что мне лет 35 каких — стал получать приглашения на интервью.
И это несмотря на то, что все работодатели гордо пишут всякое типа equal opportunity employer. Причины у работодателей могут быть разные, но выходит, что возраст надо скрывать.