Профилировщик
Прежде всего, когда вы выходите за рамки вопиющей алгоритмической неэффективности, вы хотите найти себе хорошего профилировщика. Профайлер имеет несколько преимуществ:
- Показывает точные измерения (на что потрачено время, промахи кеша, неправильные предсказания переходов и т. д.).
- Погоня за вашими главными точками доступа, как правило, быстро ускоряет ваш процесс обучения и интуицию о том, что вызывает узкие места на микроуровне (например, иерархия памяти и ветвление).
- Сделает вас лучшим расстановщиком приоритетов. Это также научит вас, какой код не нуждается в оптимизации, что означает, что вы можете сосредоточиться на других показателях, таких как производительность (ремонтопригодность, безопасность и т. д.).
Для меня № 2 был на самом деле довольно большим. Я действительно не очень быстро начал изучать многие из этих вещей, пока у меня не было профилировщика в руках. Это своего рода то, как вы можете многому научиться программированию, работая над реальным, значительным проектом и просматривая вещи, которые возникают в середине. Точно так же изучение микроэффективности и компьютерной архитектуры, как правило, легче с профилировщиком в руках, когда вы гоняетесь за одной горячей точкой за другой и исследуете, почему она существует.
Оптимизация памяти
Помимо этого, вероятно, самое важное, помимо алгоритмической сложности (которая касается масштабируемости, а не абсолютного ощущения производительности), — это эффективность использования памяти.
Предупреждение: это будет несколько упрощено и не будет касаться таких тем проектирования компилятора, как распределение регистров и сброс стека, или даже очень подробного описания иерархии памяти.
То, как работают машины и операционные системы, устанавливается в виде иерархической формы памяти, варьирующейся от самой быстрой, но самой маленькой памяти (регистры) до самой медленной и самой большой (диск).
При доступе к памяти система загружает ее из более медленной памяти в более быструю большими выровненными фрагментами. Например, операционная система может выгружать память из вторичного запоминающего устройства в физическую память (DRAM) фрагментами по 4 килобайта.
[4 kilobyte chunk][*4 kilobyte chunk][4 kilobyte chunk][...]
// '*' indicates the chunk that's loaded in.
Когда вы запрашиваете доступ к виртуальной памяти в любом месте, окружающем выровненный фрагмент размером 4 килобайта, система выгружает этот фрагмент в DRAM. Но мы еще не закончили. Обычно, прежде чем мы сможем что-то сделать, мы должны загрузиться из DRAM в кэш ЦП, который сам разделен на иерархию. В этих случаях память может быть загружена в 64-байтовый выровненный фрагмент строки кэша, например:
[64-byte chunk][64-byte chunk][*64-byte chunk][...]
... поэтому доступ к памяти в конечном итоге загружается из DRAM в кеш ЦП таким образом. Когда вы запрашиваете доступ к памяти в DRAM вокруг одного из этих 64-байтовых фрагментов, весь 64-байтовый фрагмент загружается в кэш ЦП.
А затем сам кеш ЦП делится на иерархию (хотя обычно все используют один и тот же размер строки кеша), а память перемещается вниз к более быстрым, но меньшим кешам ЦП (самым быстрым является L1). И последнее, но не менее важное: перед выполнением таких операций, как арифметика, память из кэша L1 загружается в регистр, который может иметь размер, скажем, 64 бита для регистра ЦП общего назначения. В этом случае мы получаем кэш-память процессора, расположенную следующим образом в 64-байтовой строке кэша:
[64 bits][64 bits][64 bits][*64 bits][64 bits][...]
Итак, наконец, пройдя путь к самой маленькой и самой быстрой памяти, мы выполняем некоторые арифметические операции с регистрами, а затем обычно перемещаем результаты обратно вверх по иерархии.
Теперь это несколько грубое упрощение, и я мог бы в конечном итоге смутиться из-за этого позже. Тем не менее, следует помнить, что ЦП извлекает память из более медленных и больших областей в более быстрые и меньшие области выровненными фрагментами. Это захватывает память по смежной горстке. Надежда на это заключается в том, что вы в конечном итоге получите доступ к этому фрагменту памяти несколько раз (пространственная / временная локальность), прежде чем он будет вытеснен позже.
Оптимизация памяти
Имея это в виду, чтобы получить максимальную производительность от вашего кода, обычно нужно начинать с определения приоритетов размещения памяти и доступа (кроме алгоритмов и структур данных, конечно). Без эффективного доступа к памяти самые быстрые арифметические инструкции вряд ли помогут.
Одна из вещей, о которой стоит помнить, это непрерывные массивы. Данные, расположенные непрерывно и доступ к которым осуществляется по последовательному шаблону, идеально подходят для такой иерархии памяти. Это потому, что компьютер может захватить большой старый кусок памяти (страница, строка кэша), затем мы последовательно проходим через него и получаем доступ ко всему куску, пока он находится в более быстрой форме памяти до вытеснения.
Используйте данные до их удаления
Наихудший сценарий — это когда вы в конечном итоге загружаете большой старый кусок памяти только для того, чтобы использовать его небольшой кусок, а затем система вытесняет его, прежде чем мы используем остальную часть. Такие сценарии могут проявляться в связанных структурах, таких как связанные списки и деревья (без распределителя памяти, чтобы дать им более непрерывное представление), где мы можем в конечном итоге загрузить кусок памяти для области памяти, окружающей узел, только для доступа к одному узлу внутри. его, а затем выселить его.
Другой случай, когда это проявляется, — это управляемые языки, где каждый определяемый пользователем тип должен выделяться отдельно (например, через сборщик мусора), но агрегироваться в структуру списка на основе массива. В этом случае, несмотря на то, что мы храним массив этих объектов, каждый объект на самом деле представлен через ссылку (например, указатель), которая указывает куда-то еще в памяти.
Это может быть одной из самых веских причин для использования таких языков, как C или C++. Они позволяют агрегировать определяемые пользователем типы непрерывно, а также размещать их в стеке (который имеет большую временную локальность).
TL;DR
Если вы хотите узнать больше об этих предметах, я бы посоветовал изучить местонахождение ссылки. Эта статья также обязательна: http://lwn.net/Articles/250967/
И последнее, но не менее важное: если мне разрешено бесстыдно подключаться к вопросу о вознаграждении, на который я потратил много времени, чтобы ответить: Какой наиболее эффективный способ представления небольших значений в структуре?.
Но в любом случае, первым делом нужно взять профилировщик и начать гоняться за горячими точками. Это самый быстрый способ обучения и самый продуктивный способ оптимизации.
Обновить
Мудрый совет в прекрасном ответе Дженца также побудил меня включить отказ от ответственности, поскольку алгоритмическая эффективность по-прежнему имеет тенденцию быть первым и главным предметом беспокойства. Я целый день работал с теми типами, которые говорят об эффективности кеша и многопоточности, имея дело с наиболее неоптимальными алгоритмами, и это неэффективная расстановка приоритетов. Микрооптимизация или распараллеливание пузыря из миллиона элементов далеко не эффективны в качестве вопиющего примера.
Многие методы оптимизации памяти, как правило, помогают наиболее быстро, так это в тех последовательных случаях, когда нет другого выбора, кроме как коснуться каждого элемента (нет способа снизить линейную сложность). Примером может служить, скажем, симулятор частиц, который должен обрабатывать каждую частицу, алгоритм обработки изображений, который должен воздействовать на каждый пиксель, умножение матриц с участием массивных матриц. В таких случаях невозможно алгоритмически пропустить большую часть работы и получить тот же результат, поскольку мы должны обрабатывать каждый элемент. В таких случаях методы оптимизации памяти могут стать даже более эффективными, чем распараллеливание, а также дать вам больше от распараллеливания.
Тем не менее, в основе структур данных и алгоритмов лежит проблема эффективности памяти. Быстрая сортировка массива по-прежнему имеет тенденцию превосходить сортировку слиянием в практических сценариях исключительно из-за эффективности использования памяти. Есть даже случаи, когда линейный алгоритм может превзойти линейный при условии, что первый намного эффективнее использует память.
Распределители памяти
Ранее я упоминал о недружественности к кэшированию связанных структур, таких как деревья и связанные списки, но это предполагает, что каждый узел выделяется для универсального распределителя (и, возможно, не все сразу). Одна из вещей, которая может сделать даже такую структуру, как односвязный список, намного более применимой, — это использование распределителя памяти, который возвращает своим узлам пространственную локальность, которой в противном случае им обычно не хватало бы. Таким образом, есть способы копаться в ваших структурах данных и использовать распределители памяти и таким образом сделать их более эффективными, фактически не используя совершенно новый.
Существуют также структуры данных, такие как развернутые списки, которые часто упускают из виду, поскольку они не предлагают алгоритмических преимуществ по сравнению со связанными списками. Тем не менее, они предлагают значительно большие преимущества с точки зрения эффективности использования памяти, и в тех сценариях, где у нас есть две структуры данных, которые имеют одинаковую алгоритмическую сложность, но совершенно разные схемы памяти, побеждает, как правило, та, у которой более эффективная структура памяти и схемы доступа. Развернутый список связывает массивы элементов вместе, а не отдельные элементы, и, опять же, пространственная локальность сильно благоприятствует представлениям на основе смежных массивов.
Однако почти любая микрооптимизация ухудшит простоту и удобство сопровождения вашего кода. Таким образом, ключом к оптимизации в целом является расстановка приоритетов, и именно здесь профилировщик может хоть немного помочь вам оставаться под контролем (с точки зрения производительности, профилировщик имеет огромное преимущество, показывая вам, что не оптимизировать что в противном случае у вас могло бы возникнуть искушение попробовать).
person
Community
schedule
19.12.2015
