Profiler
Первых вещи сначала, когда вы выходите за пределы вопиющей алгоритмической неэффективности, вы хотите, чтобы найти себе хороший профайлер. Профилировщик имеет несколько преимуществ:
- Показывает ваши точные измерения (где потрачено время, недостатки кэша, неверные предсказания ветвей и т. Д.).
- Преследуя верхние горячие точки, вы стремитесь быстро ускорить процесс обучения и интуицию того, что вызывает узкие места на микроуровне (например, иерархия памяти и ветвление).
- Сделает вас лучшим приоритетом. Он также научит вас, какой код не нуждается в оптимизации, что означает, что вы можете сосредоточиться там на других показателях, таких как производительность (ремонтопригодность, безопасность и т. Д.).
Для меня № 2 на самом деле довольно большой. Я действительно не начал очень многому научиться, пока у меня не было профилировщика. Это то, как вы можете многому научиться программированию, работая над реальным, значительным проектом и просматривая вещи, которые возникают посередине. Точно так же изучение микроэффективности и компьютерной архитектуры, как правило, проще с помощью профилировщика, поскольку вы преследуете одну точку доступа за другой и исследуете, почему она существует.
Оптимизация памяти
С, что в стороне, вероятно, номер один вещь за алгоритмической сложности (что о масштабируемости, а не какой-то абсолютном смысле производительности) является эффективность памяти.
Оговорка: это будет несколько упрощен и не вдаваться в темы дизайна компилятора как выделение регистров и стека разливы или даже очень подробное описание иерархии памяти.
Путь машины и операционные системы работы устанавливается в иерархическом виде памяти, начиная от абсолютной, но быстро наименьшему памяти (регистры) к абсолютному медленный и самый большой (диск).
При доступе к памяти система загружает ее из более медленной памяти в более быструю память в довольно больших, выровненных фрагментах. Например, операционная система может загружать память страницы из дополнительного устройства хранения в физическую память (DRAM) в 4 килобайтных фрагментах.
[4 kilobyte chunk][*4 kilobyte chunk][4 kilobyte chunk][...]
// '*' indicates the chunk that's loaded in.
При запросе доступа к виртуальной памяти в любом месте, окружающей выровненной, 4 килобайта кусок, система будет страница в этом куске к DRAM. Но мы еще не закончили. Как правило, прежде чем мы можем что-либо сделать, мы должны загружать из DRAM в кэш CPU, который сам по себе разделен на иерархию. В тех случаях, память может быть загружена в 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][...]
Итак, наконец, после того, как работает наш путь вниз к самой маленькой и самой быстрой памяти, мы делаем некоторые арифметические инструкции на регистры, а затем, как правило, перемещают результаты обратно в иерархию.
Теперь это несколько грубое упрощение, и в конце концов я смущаюсь об этом позже. Тем не менее, следует иметь в виду, что CPU извлекает память из более медленных, больших регионов в более быстрые, более мелкие регионы в выровненных кусках. Он захватывает память прилегающей рукой. Надежда на это заключается в том, что вы в конечном итоге получаете доступ к этому фрагменту памяти несколько раз (пространственная/временная локальность), прежде чем он окажется выселенным позже.
Оптимизация памяти
Имея это в виду, получить максимальную производительность из вашего кода, как правило, необходимо, чтобы начать приоритизации расположение памяти и доступ (к тому же алгоритмы и структуры данных, конечно). Без эффективного доступа к памяти самые быстрые арифметические инструкции вряд ли помогут.
Одна из вещей, которые стоит иметь в виду, - это непрерывные массивы. Данные, упорядоченные и доступные по последовательному шаблону, идеально подходят для такого типа иерархии памяти. Это связано с тем, что компьютер может захватить большой старый фрагмент памяти (страница, линия кэша), затем мы последовательно пробираем его и получаем доступ ко всему фрагменту, пока он находится в более быстрой форме памяти до выселения.
Использование данных Перед Это выселяют
В худшем случае, когда вы в конечном итоге загрузки большой старый кусок памяти использовать только небольшую часть его, а затем иметь систему выселить его, прежде чем мы используйте остальную часть. Такие сценарии могут отображаться в связанных структурах, таких как связанные списки и деревья (без использования распределителя памяти, чтобы дать им более непрерывное представление), где мы могли бы загружать кусок памяти для области памяти, окружающей узел, только для доступа к одному узлу внутри а затем выселить его.
Другой случай, когда это отображается, находится в управляемых языках, где каждый пользовательский тип должен быть выделен отдельно (например: через сборщик мусора), но агрегирован в структуру списка на основе массива. В этом случае, хотя мы храним массив этих объектов, каждый объект фактически представлен посредством ссылки (например, указателя), которая указывает где-то еще в памяти.
Это может быть одной из самых веских причин использовать язык, такой как C или C++. Они позволяют агрегировать определенные пользователем типы, а также распределять их по стеку (который имеет большую временную локальность).
TL; DR
Если вы хотите узнать больше об этих предметах, я предлагаю исследование локальности ссылок.Эта статья также обязательна: http://lwn.net/Articles/250967/
И последнее, но не менее важное: если мне разрешен бесстыдный штекер для вопроса о щедрости, на который я потратил много времени, чтобы ответить: What is the most efficient way to represent small values in a struct?.
Но, в любом случае, сначала сначала нужно захватить профайлер и начать преследовать горячие точки. Это самый быстрый способ узнать и наиболее эффективный способ оптимизации.
Update
Советы мудрости в хорошем ответе Jenz»также дал мне желание включать отказ от ответственности, в том, что алгоритмическая эффективность все еще имеет тенденцию быть первым и главное, чтобы беспокоиться о. Я работал с теми типами, которые говорят об эффективности кеш-памяти и многопоточности в течение всего дня, имея дело с самыми субоптимальными алгоритмами, и это неэффективная приоритизация. Микрооптимизация или распараллеливание типа пузыря на миллион элементов далеко не эффективны, как вопиющий пример.
В тех случаях, когда многие методы оптимизации памяти имеют тенденцию наиболее эффективно помогать, в тех последовательных случаях, когда нет выбора, кроме как касаться каждого элемента (нет возможности получить ниже линейной сложности). Примером может служить, например, симулятор частиц, который должен обрабатывать каждую частицу, алгоритм обработки изображений, который должен влиять на каждое умножение матрицы, включающее массивные матрицы. В этих случаях нет возможности алгоритмически пропускать огромную часть работы и получать одинаковый результат, так как мы должны обрабатывать каждый элемент. В те времена методы оптимизации памяти могут стать еще более эффективными, чем распараллеливание, а также дать вам больше возможностей для параллелизации.
Тем не менее, существует проблема памяти, лежащая в основе структуры структур данных и алгоритмов. Быстрое сортирование массива по-прежнему имеет тенденцию бить слияние в практических сценариях исключительно из-за эффективности памяти. Есть даже случаи, когда линейный алгоритм может превзойти линейный, при условии, что первый обладает большей эффективностью памяти.
распределители памяти
Я упомянул кэш-недружелюбие связанных между собой структур, таких как деревья и связные списки ранее, но это при условии, каждый узел выделяется на фоне общего назначения распределителем (и, возможно, не все сразу). Одна из вещей, которые могут начать фактически создавать даже структуру, подобную односвязному списку, намного более применимы, это использование распределителя памяти, который возвращает его узлам пространственную локальность, которой они обычно не нуждаются. Таким образом, есть способы копаться под вашими структурами данных и использовать распределители памяти и сделать их более эффективными таким образом, фактически не используя совершенно новый.
Существуют также структуры данных, такие как развернутые списки, которые часто игнорируются, поскольку они не предлагают никаких алгоритмических преимуществ по связанному списку. Тем не менее они предлагают существенно большие преимущества с точки зрения эффективности памяти, и в тех сценариях, где у нас есть две структуры данных, которые имеют схожую алгоритмическую сложность, но значительно отличающиеся макеты памяти, победитель, как правило, имеет более эффективную структуру памяти и шаблоны доступа. Развернутый список связывает массивы элементов вместе, а не отдельные элементы, и, опять же, пространственная локальность сильно благоприятствует непрерывным представлениям на основе массива.
Однако любая микро-оптимизация ухудшит прямолинейность и удобство обслуживания вашего кода. Таким образом, ключом к оптимизации в целом является приоритизация, и именно здесь профилировщик может по крайней мере несколько помочь вам оставаться под контролем (с точки зрения производительности, профилировщик имеет огромное преимущество, показывающее вам, что не, чтобы оптимизировать то, что вы могли бы иметь в противном случае были искушены попытки).
Как правило, все, что вам нужно, это алгоритм с низкой сложностью. Затем компилятор может выполнить некоторую оптимизацию, и вы настроены. – Alexguitar
Пожалуйста, не ошибайтесь, думая, что оптимизация компилятора улучшит плохой алгоритм. Компилятор не знает, чего вы пытаетесь достичь. –