C для циклической индексации: ускорена ли прямая индексация в новых процессорах?

В списке рассылки, на который я подписан, два довольно знающих (IMO) программиста обсуждали некоторый оптимизированный код и говорили что-то вроде:

На процессорах, выпущенных 5-8 лет назад, было несколько быстрее выполнять циклы в обратном направлении (например, for (int i=x-1; i>=0; i--) {...}) потому что сравнивая i к нулю более эффективно, чем сравнивать его с каким-то другим числом. Но с очень недавними процессорами (например, с 2008-2009) логика спекулятивного загрузчика такова, что она работает лучше, если цикл for повторяется вперед (например, for (int i=0; i< x; i++) {...}).

У меня вопрос, правда ли это? Изменились ли реализации ЦП в последнее время так, что итерация в прямом цикле теперь имеет преимущество перед итерацией в обратном направлении? Если да, то как это объяснить? то есть что изменилось?

(Да, я знаю, преждевременная оптимизация - корень всего зла, пересмотрите мой алгоритм, прежде чем беспокоиться о микрооптимизации и т. Д. И т. Д., В основном мне просто любопытно)

Источник

7 ответов

Решение

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

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

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

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

Взгляните на руководство Intel по оптимизации для аппаратных устройств предварительной выборки. В списке четыре предвыборщика; два для чипов NetBurst:

  1. Аппаратная программа предварительной выборки NetBurst может обнаруживать потоки обращений к памяти в прямом или обратном направлении и пытается загрузить данные из этих мест в кэш L2.
  2. В NetBurst также имеется средство предварительной выборки смежных строк кэша (ACL), которое автоматически загружает две соседние строки кэша, когда вы выбираете первую.

и два для ядра:

  1. Ядро имеет немного более сложный аппаратный предварительный выборщик; он может обнаруживать пошаговый доступ в дополнение к потокам смежных ссылок, поэтому будет лучше, если вы будете проходить через массив через каждый элемент, каждый четвертый и т. д.
  2. В Core также есть средство предварительной выборки ACL, такое как NetBurst.

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

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

Простая эвристика не поможет вам с более сложными алгоритмами, и вам, возможно, придется задуматься о размерах кэшей L1, L2 и т. Д. Например, для обработки изображений часто требуется, чтобы вы выполнили некоторую операцию над подразделами 2D-изображения, но порядок, в котором вы пересекаете изображение, может влиять на то, насколько полезные его части остаются в вашем кэше, не будучи исключенными. Посмотрите на обходы Z-порядка и циклическое разбиение, если вы заинтересованы в подобных вещах. Это довольно простой пример отображения двумерного местоположения данных изображения в одномерное расположение памяти для улучшения производительности. Это также область, где компиляторы не всегда могут реструктурировать ваш код наилучшим образом, но реструктуризация кода C вручную может значительно повысить производительность кеша.

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

Источник

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

#include <time.h>
#include <stdio.h>

int main(void)
{
    int i;
    int s;
    clock_t start_time, end_time;
    int centiseconds;

    start_time = clock();
    s = 1;
    for (i = 0; i < 1000000000; i++)
    {
        s = s + i;
    }
    end_time = clock();
    centiseconds = (end_time - start_time)*100 / CLOCKS_PER_SEC;
    printf("Answer is %d; Forward took %ld centiseconds\n", s, centiseconds);

    start_time = clock();
    s = 1;
    for (i = 999999999; i >= 0; i--)
    {
        s = s + i;
    }
    end_time = clock();
    centiseconds = (end_time - start_time)*100 / CLOCKS_PER_SEC;
    printf("Answer is %d; Backward took %ld centiseconds\n", s, centiseconds);

    return 0;
}

Скомпилирован с -O9 с использованием gcc 3.4.4 на Cygwin, на процессоре AMD Athlon(64) 3500+ (2211 МГц) в 32-битной Windows XP:

Answer is -1243309311; Forward took 93 centiseconds
Answer is -1243309311; Backward took 92 centiseconds

(Ответы варьировались на 1 в любом случае в нескольких повторениях.)

Скомпилирован с -I9 с использованием gcc 4.4.1, работающего на процессоре Intel® Rom Atom(TM) N270 @ 1.60GHz (800 МГц и предположительно только одно ядро, учитывая программу) в 32-битной Ubuntu Linux.

Answer is -1243309311; Forward took 196 centiseconds
Answer is -1243309311; Backward took 228 centiseconds

(Ответы варьировались на 1 в любом случае в нескольких повторениях.)

Глядя на код, цикл вперед переводится в:

; Gcc 3.4.4 on Cygwin for Athlon      ; Gcc 4.4.1 on Ubuntu for Atom
L5:                                .L2:
    addl    %eax, %ebx                 addl    %eax, %ebx
    incl    %eax                       addl    $1, %eax
    cmpl    $999999999, %eax           cmpl    $1000000000, %eax
    jle     L5                         jne     .L2

Обратно к:

L9:                                .L3:
    addl    %eax, %ebx                 addl    %eax, %ebx
    decl    %eax                       subl    $1, $eax
    jns     L9                         cmpl    $-1, %eax
                                       jne .L3

Что показывает, если не сказать больше, что поведение GCC изменилось между этими двумя версиями!

Вставка старых циклов GCC в новый файл asm GCC дает результаты:

Answer is -1243309311; Forward took 194 centiseconds
Answer is -1243309311; Backward took 133 centiseconds

Резюме: на 5-летнем Athlon циклы, генерируемые GCC 3.4.4, имеют одинаковую скорость. На новом (<1 год?) Atom обратный цикл значительно быстрее. GCC 4.4.1 имеет небольшую регрессию для этого конкретного случая, который лично меня не беспокоит, учитывая суть этого. (Я должен был убедиться, что s используется после цикла, потому что в противном случае компилятор полностью исключил бы вычисления.)

[1] Я никогда не могу вспомнить команду для системной информации...

Источник

Да. но с оговоркой. Идея, что цикл в обратном направлении быстрее, никогда не применяется ко всем старым процессорам. Это x86 (как в 8086 через 486, возможно, Pentium, хотя я не думаю, что дальше).

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

Вот почему

У 8086 был регистр, который был специально оптимизирован для использования в качестве счетчика циклов. Вы помещаете свой счетчик циклов в CX, и затем есть несколько инструкций, которые уменьшают CX, а затем устанавливают коды условий, если он обнуляется. Фактически был префикс инструкции, который вы могли бы поставить перед другими инструкциями (префикс REP), который в основном повторял бы другую инструкцию до тех пор, пока CX не достигнет 0.

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

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

В наши дни производительность убивает не сравнение, а ветвление, и только тогда, когда предсказание ветвления предсказывает неверно.

Источник

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

Фактически, компиляция следующего кода ( отсюда) с -S -O3 -mavx:

  for (i = 0; i < N; ++i)
    r[i] = (a[i] + b[i]) * c[i];

приводит по существу:

.L10:
    addl    $1, %edx
    vmovupd (%rdi,%rax), %xmm1
    vinsertf128     $0x1, 16(%rdi,%rax), %ymm1, %ymm1
    vmovupd (%rsi,%rax), %xmm0
    vinsertf128     $0x1, 16(%rsi,%rax), %ymm0, %ymm0
    vaddpd  (%r9,%rax), %ymm1, %ymm1
    vmulpd  %ymm0, %ymm1, %ymm0
    vmovupd %xmm0, (%rcx,%rax)
    vextractf128    $0x1, %ymm0, 16(%rcx,%rax)
    addq    $32, %rax
    cmpl    %r8d, %edx
    jb      .L10

т.е. ассемблерный код, который использует расширения AVX для параллельного выполнения 4-х двойных операций (например, vaddpd, vmulpd).

И наоборот, следующий код скомпилирован с такими же параметрами:

  for (i = 0; i < N; ++i)
    r[N-1-i] = (a[N-1-i] + b[N-1-i]) * c[N-1-i];

производит:

.L5:
    vmovsd  a+79992(%rax), %xmm0
    subq    $8, %rax
    vaddsd  b+80000(%rax), %xmm0, %xmm0
    vmulsd  c+80000(%rax), %xmm0, %xmm0
    vmovsd  %xmm0, r+80000(%rax)
    cmpq    $-80000, %rax
    jne     .L5

который выполняет только одну двойную операцию за один раз (vaddsd, vmulsd).

Один только этот факт может быть ответственен за фактор 4 между производительностью при итерации назад и вперед.

С помощью -ftree-vectorizer-verbose=2Похоже, проблема заключается в хранении в обратном направлении: "отрицательный шаг для магазина". На самом деле, если a, b, а также c читаются задом наперед, но r записывается в прямом направлении, код снова векторизован.

Источник

Вероятно, это не имеет большого значения по скорости, но я часто пишу:

for (i = n; --i >= 0; ) blah blah

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

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

Источник

Нет, мы не можем сказать, что реализации ЦП изменились, чтобы ускорить цикл вперед. И это очень мало связано с самими процессорами.

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

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

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

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

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

for (i = 0; i < 1000; i++) { process (a[i]); }

скорее, чем:

for (i = 999; i >= 0; i--) { process (a[999-i]); }

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

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

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

Источник

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

Источник
Другие вопросы по тегам