Что влияет на скорость кода?

Question

Способ увидеть, как быстро работает ваш код, - это профилирование производительности. Есть инструменты для этого и тому подобное, но мне интересно, каковы факторы для скорости кода.

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

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

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

Итак, я спрашиваю: вы знаете, что влияет на скорость кода?

Не обязательно скорость программ.

Answer 1

Целые числа являются двоичными. Вернее, целые числа - это просто целые числа, которые могут быть представлены в любой числовой базе. В базе 10 вы написали бы 13, в базе 16 вы написали бы d (или 0xd), в двоичном - 1101 (или 0b1101). Римляне написали бы XIII. Все они представляют одну и ту же концепцию числа «тринадцать». Среди людей мы склонны использовать представление base 10, но когда вы запрашиваете компьютер для обработки целых чисел, он использует двоичное представление. И это не имеет значения. Тринадцать плюс сорок пять дают один и тот же результат, независимо от того, как я это пишу. XIII + 0x2D = 13 + 45 = 0xd + 0b101101. Неважно, какое представление вы используете, результат арифметической операции одинаков. Именно поэтому мы позволяем ЦПУ использовать двоичное представление для всей обработки целых чисел.

Некоторые языки программирования также предоставляют «десятичный» тип данных, но это, как правило, связано с арифметикой с плавающей запятой, где не все значения могут быть представлены во всех базах (1/3 может быть легко представлена ​​в базе 3, но не в 2 или 10, например, 1/10 может быть представлено в базе 10, но не 2)

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

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

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

Иногда сохранение значений в переменных, которые могут быть заново вычислены при необходимости, будет быстрее, поскольку их можно поместить в регистр, сохранив несколько циклов. В других случаях это будет медленнее, потому что у вас закончились регистры, и значение пришлось бы помещать в кэш или даже в ОЗУ, что делает пересчет при каждом использовании предпочтительным. Порядок, в котором вы пересекаете память, имеет огромное значение. Случайный (рассеянный) доступ может занять сотни циклов, но последовательные почти мгновенные. Выполнение ваших операций чтения / записи в правильном порядке позволяет процессору практически постоянно хранить требуемые данные в кэше, а обычно «правильный шаблон» означает последовательное чтение данных и работу с блоками размером ~ 64 КБ при время. Но иногда нет.На процессоре x86 некоторые инструкции занимают 1 байт, другие - 17. Если ваш код содержит много первых, выборка и декодирование инструкций не будут узким местом, но если в нем много более длинных инструкций, это, вероятно, ограничить количество инструкций, загружаемых процессором за цикл, и тогда количество, которое он сможет выполнить, не имеет значения.

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

Answer 2

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

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

Например: последние два дня я потратил на то, чтобы ускорить процесс пересчета определенного набора значений. Я вытащил некоторые вещи из цикла и предварительно рассчитал их, так что это было сделано только M раз вместо M x N раз, и сохранил значение в переменной вместо того, чтобы искать его каждый раз где-то еще, потому что это значение использовалось в компараторе, поэтому он будет вызываться много на этапе Collections.sort. Я получил общее время выполнения от 45 до 20 секунд. А потом один из моих коллег, который был здесь намного дольше, указал, что мне не нужно пересчитывать эти значения, я могу вытащить их из другого объекта. И вдруг он выполняется за 2 секунды. Теперь , что - это оптимизация, в которую я могу поверить.

Answer 3

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

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

Прежде всего, очевидно, Word Size. 64-битные машины имеют больший размер слова (да, здесь больше обычно означает лучше), так что большинство операций может выполняться быстрее, например, операции с двойной точностью (где double обычно означает 2 * 32 бита). 64-битная архитектура также выигрывает от большей шины данных, которая обеспечивает более высокую скорость передачи данных.

Во-вторых, трубопровод также важен. Основные инструкции могут быть классифицированы в различных состояниях или фазах, так что, например, инструкции обычно делятся на:

• Выборка: инструкция читается из кэша инструкций
• Декодирование: инструкция расшифровывается как интерпретированная, чтобы увидеть, что мы должны сделать.
• Выполнить: инструкция выполняется (обычно это означает перенос операций в АЛУ)
• Доступ к памяти: если инструкция должна получить доступ к памяти (например, загрузить значение реестра из кэша данных), она выполняется здесь.
• Обратная запись: значения записываются обратно в регистр назначения.

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

Некоторые инструкции имеют зависимости. Если я добавляю в регистры вместе, для выполнения фазы инструкции add потребуются значения, прежде чем они действительно будут восстановлены из памяти. Зная структуру конвейера, компилятор может переупорядочить инструкции по сборке, чтобы обеспечить достаточное «расстояние» между нагрузками и надстройкой, чтобы процессору не пришлось ждать.

Другая оптимизация ЦП будет суперскалярной, в которой используются, например, избыточные ALU, так что две команды добавления могут выполняться одновременно. Опять же, точно зная архитектуру, вы можете оптимизировать порядок команд, чтобы воспользоваться преимуществами. Например, если компилятор обнаруживает, что в коде не существует зависимостей, он может переставить нагрузки и арифметику так, чтобы арифметика была перенесена на более позднее место, где все данные были доступны, а затем выполняла 4 операции одновременно.

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

Что может быть полезно при разработке вашего приложения и что действительно может повысить скорость кода, так это знание политик и организации кэша. Наиболее типичный пример приведен для неправильно упорядоченного доступа к двойному массиву в цикле:

// Make an array, in memory this is represented as a 1.000.000 contiguous bytes
byte[][] array1 = new byte[1000, 1000];
byte[][] array2 = new byte[1000, 1000;
// Add the array items

for (int j = 0; j < 1000; i++)
  for (int i = 0; i < 1000; j++)
     array1[i,j] = array1[i,j] + array2[i,j]

Посмотрим, что здесь происходит.

array1 [0,0] заносится в кеш. Поскольку кеш работает в блоках, вы получаете первые 1000 байтов в кеш, поэтому кеш содержит массив1 [0,0] и массив1 [0,999].

array2 [0,0] добавлено в кеш. Снова блокирует, так что у вас есть массив2 [0,0] в массив2 [0,999].

На следующем шаге мы получаем доступ к массиву 1 [1,0], которого нет в кэше, и к массиву 2 [1,0], поэтому мы переносим их из памяти в кэш. Теперь, если мы предположим, что у нас очень маленький размер кэша, из-за этого массив2 [0 ... 999] будет удален из кэша ... и так далее. Поэтому, когда мы обращаемся к array2 [0,1], он больше не будет в кеше. Кэш не будет полезен для array2 или array1.

Если мы изменим порядок обращения к памяти:

for (int i = 0; i < 1000; i++)
  for (int j = 0; j < 1000; j++)
     array1[i,j] = array1[i,j] + array2[j,i]

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

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

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

Answer 4

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

Это особенно верно для процессоров CISC, таких как x86, где сами инструкции могут иметь различное число циклов, хотя современные разработки в основном смягчают это. Однако это справедливо для всех процессоров в случае операций загрузки и хранения памяти, которые могут быть во много, много, много раз дороже, чем любая другая операция. С тактовой частотой современных процессоров в сравнении с задержкой памяти, вы можете увидеть, возможно, десятки инструкций, потраченных впустую в случае пропадания кеша до миллионов, если вы получаете ошибку страницы и выходите на диск. Во многих случаях, когда учитывается поведение кэша, а также загрузка и сохранение, может быть гораздо, гораздо быстрее выполнить значительное количество арифметических операций для пересчета значения вместо его кэширования и повторного чтения из памяти, даже если загрузка - это одна инструкция по сборке против множества инструкций по выполнению вычислений. В некоторых случаях может иметь смысл считать, что ваша производительность ограничена только нагрузкой и хранением, а другие операции считаются «свободными», хотя это, естественно, зависит от обстоятельств.

Answer 5

«Скорость программ» обычно сводится к выбору алгоритма. Неправильный алгоритм может превратить 2-секундное задание в 2-минутное или даже хуже. Вы увидите лучший прирост производительности, если сконцентрируетесь на правильном подходе.

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

Некоторые факторы "скорости кода":

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

Answer 6

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

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

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

Answer 7

Предположим, что код имеет «скорость» - неправильный способ думать о проблеме, ИМО.

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

Answer 8

На скорость кода влияет, в основном, количество операций, которые он должен выполнить.

Чем больше операций он должен выполнить, тем медленнее будет код. Операции, выполняемые определенным кодом, напрямую связаны с алгоритмом, который он использует.

Итак, в конце - алгоритм.

Дополнительно (только для того, чтобы отметить разницу между скоростью кода и скоростью программы)

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

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

Answer 9

Да, профилирование - это способ определить скорость.

И да, различные вещи могут вызвать медленное выполнение.

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

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

Если X, Y или Z вызывают потерю времени, они будут находиться в стеке вызовов, пока они это делают, и вы сможете легко их увидеть. Если это обычно не в стеке вызовов, то это, вероятно, не вызывает это. Смотри здесь.

Answer 10

На оборудовании 2009 года, как и в сфере недвижимости, нужно помнить о трех вещах, когда речь идет о скорости кода: память, память, память. (Я включаю кеш и локальность.)

Сокращение ассигнований. Уменьшить пишет. Уменьшить чтение.

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

Если вы можете одновременно сохранять несколько целочисленных единиц и единицу с плавающей запятой, это плюс.