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

Это был интересный опыт, потому что это произошло, когда я все еще пребывал в иллюзии, что O-нотация доминирует во времени выполнения. Я имею в виду, что я знал, что он использует только большие числа, и понимал, что сортировка вставками займет больше времени для 1M списка, чем сортировка слиянием… но чего я не знал, так это того, что хорошо написанный алгоритм может легко превзойти его. с превосходной алгоритмической сложностью, если он избегает странных приведений типов и поддерживает кеширование.

Как бы то ни было, во время стажировки мне и коллеге было поручено разработать инструмент, который компания будет использовать для ускорения отладки. Идея была проста: иметь возможность конвертировать между двоичным форматом и XML (который был в 2–8 раз больше исходного двоичного формата). Это простой незамысловатый процесс: просто последовательно считывайте байты и в соответствии с их значением записывайте разные элементы XML. Целью было 30 секунд для двоичного файла с 1 ГБ, что означает, что пропускная способность записи должна была бы составлять около 130 МБ/с, что является реалистичным.

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

При взгляде на график пламени, созданный профилировщиком, узкое место сразу стало очевидным. Проблема заключалась в функции, которая преобразовывала произвольный (собственный) тип в строку, например:

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

До 70-х, лучше, но все еще недостаточно хорошо. После этого мы прочитали о том, как шаблоны могут повлиять на производительность, поэтому пришло время прибегнуть к специализации шаблонов для наиболее распространенных случаев:

Это мало что изменило и вызвало улучшение всего на ~8%. После применения этого к другим типам (не только float), эффективного избавления от шаблонов и преобразования строкового потока и встраивания этих функций, мы все еще были в 60-х годах.

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

Есть несколько способов реализовать это, но мы использовали циклическую буферизацию, которая подходит, когда вы хотите, чтобы записи выполнялись в порядке FIFO. В циклическом буфере у вас есть непрерывная область памяти с фиксированным размером, где вы будете сохранять ожидающие записи (где каждая запись может иметь разный размер). Затем вы будете продолжать записывать новые элементы в этот буфер, пока не заполните его емкость, после чего вы записываете все, что еще не было сброшено на диск, и с этого момента вы можете записывать поверх того, что вы только что сбросили!

Если у нас есть пустой буфер и вставляем 1, 2 и 3, мы получаем:

И если мы продолжим вставлять 4, 5, 6, 7, 8, 9, A, B, C:

Где содержимое сбрасывается на диск перед вставкой 8, который переопределяет 1.

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

Теоретически C++ cout уже должен позаботиться об этом, но я никогда не копался в теме достаточно глубоко, чтобы понять, почему это изменение имело такое большое значение. Была ли это деталь реализации Sun Studio? Думаю, я никогда не узнаю.

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

После всего этого: 38,5 МБ/с, что означает 26 с на 1 ГБ. Эй!