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

Question

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

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

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

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

Answer 1

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

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

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

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

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

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

и два для Core :

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

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

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

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

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

Answer 2

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

#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) CPU 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

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

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

Answer 3

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

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

Вот почему.

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

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

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

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

Answer 4

Я наткнулся на этот вопрос после наблюдения значительного падения производительности при переборе массива назад и вперед. Я боялся, что это будет предварительный сборщик, но ответы выше убедили меня, что это не тот случай. Затем я продолжил исследование и выяснил, что похоже, что 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 для параллельного выполнения четырех двойных операций (например, 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 записывается в прямом направлении, код снова векторизируется.

Answer 5

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

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

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

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

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

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

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

вместо:

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

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

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

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

Answer 6

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

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

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

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

Answer 7

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