Как написать быстрый (низкий уровень) код?

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

Подробнее:

Меня интересует оптимизация в контексте научных вычислений (которые много хрустят, но не только) на языках низкого уровня, таких как C/С++. Меня особенно интересуют методы оптимизации, которые не очевидны, если у вас нет хорошего понимания того, как работает машина (чего я еще не знаю).

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

Приветствуем основные советы по теме или указателям на статьи.

Ответы

Получил ответы с большим количеством великих указателей, намного больше, чем когда-либо успел прочитать. Вот список всех из них:

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

Ответы

Ответ 3

Прошло несколько лет с тех пор, как я прочитал его, но Write Great Code, том 2: мышление низкого уровня, написание высокого уровня Рэндалл Хайд был неплох. Это дает хорошие примеры того, как код C/С++ преобразуется в сборку, например. что действительно происходит, когда у вас есть большой оператор switch.

Кроме того, altdevblogaday.com сосредоточен на разработке игр, но статьи по программированию могут дать вам некоторые идеи.

Ответ 4

Интересная книга о бит-манипуляции и умных способах выполнения низкоуровневых вещей - Hacker Delight.

Это определенно стоит прочитать для всех, кто интересуется низкоуровневым кодированием.

Ответ 6

C и С++ обычно являются языками, которые используются для этого из-за их скорости (игнорируя Fortran, поскольку вы не упомянули об этом). Что вы можете использовать (что компилятор icc делает много) - это наборы команд SSE для большого количества чисел с плавающей запятой. Еще одна вещь, которая возможна, - это использование CUDA и Stream API для Nvidia/Ati, соответственно, чтобы делать ОЧЕНЬ быстрые операции с плавающей запятой на графической карте, оставляя процессор свободным для выполнения остальной части работы.

Ответ 7

Другим подходом к этому является практическое сравнение. Вы можете получить библиотеку Blitz ++ (http://www.oonumerics.org/blitz/), которая, как мне сказали, реализует агрессивные оптимизации для числовых/научных вычислений, а затем записывает некоторые простые программы, делающие интересующие вас операции ( например, матричные умножения). Когда вы используете Blitz ++ для их выполнения, напишите свой собственный класс, который сделает то же самое, и если Blitz ++ быстрее начнет исследовать его реализацию, пока вы не поймете, почему. (Если ваш значительно быстрее, вы можете сказать разработчикам Blitz ++!)

Вам нужно узнать о многом, например:

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

Ответ 8

Я многому научился из книги Внутренние петли. Это древнее сейчас, в компьютерных терминах, но это очень хорошо написано, и Рик Бут настолько восторженно относится к своей теме, что все равно скажу, что стоит посмотреть на вид мышления, который вам нужен, чтобы заставить процессор летать.