Оптимизация C код без параллельного программирования

Question

я написать код C, который является

for(i=1;i<10000;i++) 
    x[i]=array1[h][x[i]^x[i-1]] 

И

for(i=9999;i>0;i--) 
    x[i]=x[i-1]^array2[h][x[i]] 

Примечание:

1- массив1 и массив2 являются содержащими байтами значения

2- вторая петля выполняет противоположную функцию первого контура

3- ч является значением байта и то же самое в loop1 и loop2

Мой вопрос

Второй цикл происходит быстрее, чем первый, и я понимаю это, так как в первом цикле каждое значение в x зависит от нового значения предыдущего байта, IE. Чтобы вычислить x2, вы должны вычислить x1, тогда как во втором цикле каждый байт зависит от старого значения предыдущего байта, который уже существует, IE. Для вычисления x9999 вам нужно старое значение x9998, а не новое, и поэтому не нужно ждать вычисления x9999, как это делается в C-коде и вызываемом, это параллельное программирование, которое означает, что язык C делает параллельное программирование для некоторых циклов что не является последовательным без пользователя, контролирующего и записывающего такую ​​параллельную связь

Вопрос: Почему цикл 2. быстрее, чем 1. цикл?

Большое спасибо

Я новичок в коде C

Извините за этот вопрос, если это слишком легко

Answer 1

Большинство современных процессоров могут нарушить порядок инструкций и выполнять их не по порядку, основываясь только на готовности исходных данных. Подумайте о пуле, в который вы выливаете первые ~ 50 итераций в устойчивое состояние (возможно, быстрее, чем они выполняются). Сколько можно начать параллельно, если у вас есть несколько ALU? В некоторых случаях вы даже можете распараллелить весь свой код, что сделает вас ограниченным количеством ресурсов выполнения (что может быть очень высоким). EDIT: важно заметить, что это осложняется в сложных потоках управления (например, если у вас есть куча условий, в которых вы работаете, особенно если они зависят от данных), так как вам нужно предсказать их и скрыть младшие инструкции, если вы были ошибочны.

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

Дэн полностью прав насчет зависимости (хотя это не простой «конвейер»). В первом цикле ваш x [i-1] каждой итерации будет распознан как aliased с x [i] предыдущего (с помощью обнаружения псевдонима CPU), что делает его сценарием чтения и записи и принуждает его для ожидания и пересылки результатов (охватывающих несколько итераций, это образует длинную цепочку зависимостей), в то время как вы можете увидеть итерацию N, вы не сможете выполнить ее, пока не сделали N-1, который ждет N-2, и поэтому на..). Кстати, это может стать еще более неприятным, если это сложный процесс, например, разделение на кеш-строку или разделение на страницы.

Второй цикл также использует значение в других ячейках, но есть важное различие - порядок программы сначала считывает значение x [i-1] (для вычисления x [i]) и только после этого записывает x [ I-1]. Это изменяет чтение-после-запись на запись после чтения, что намного проще, так как нагрузки выполняются намного раньше по конвейеру, чем магазины. Теперь процессору разрешено считывать все значения заранее (держать их где-то во внутренних регистрах) и параллельно выполнять вычисления. Записи буферизуются и делаются на досуге, так как от них никто не зависит.

EDIT: Еще одним соображением в некоторых случаях является шаблон доступа к памяти, но в этом случае он выглядит как простой шаблон потока по массиву x (шаг 1-го уровня), либо в положительном, либо в отрицательном направлениях, но оба могут быть легко распознается, и prefetcher должен начать стрелять вперёд, поэтому большинство из этих доступов должны попасть в кеш. Доступ к массиву 1/2 с другой стороны сложный, поскольку они определяются результатами загрузки - это также немного остановит вашу программу, но в обоих случаях это одно и то же.

Answer 2

Ваш первый цикл зависит от результата предыдущих итераций. Это означает, что просто, процессор не может начать думать о i=2, пока он не закончит i=1, потому что x[2] зависит от x[1]. Однако второй цикл не зависит от результата предыдущих итераций.

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

Это говорит о том, что похоже на то, что вы внедряете какое-то шифрование. Фактически, этот код выглядит как усеченная версия шифрования типа RC4. Если это то, что вы делаете, у меня есть несколько предупреждений для вас:

1) Если вы пишете шифрование для производственного кода, что вы в зависимости от безопасности, я предлагаю вам что-то использовать из колодца - известная и протестированная библиотека, а не написание собственной, она будет быстрее и безопаснее.

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

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

Answer 3

for(i=1;i<10000;i++) 
     x[i]=array1[h][x[i]^x[i-1]] 

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

Теперь, в цикле выше, x [i]^x [i-1] может оценивать индексы массива, значение которых не лежит в пределах размера строки кэша для последовательных итераций. Например, возьмем кеш L1. Для первой итерации цикла for доступен массив значений [h] [x [i]^x [i-1]], который находится в основной памяти. 64 байта данных, окружающих это значение байта, приводятся и сохраняются в кеше в кеше L1. Для следующей итерации x [i]^x [i-1] может привести к индексу, значение которого хранится в месте, не находящемся рядом с 64 байтами, которое было введено на первой итерации. Следовательно, кэш-память и основная память снова доступны. Это может произойти много раз во время выполнения цикла for, что приводит к низкой производительности.

Посмотрите, что x [i]^x [i-1] оценивается для каждой итерации. Если они сильно отличаются друг от друга, то медленность частично объясняется тем, что указано выше.

Ссылка ниже прекрасно объясняет эту концепцию.

http://channel9.msdn.com/Events/Build/2013/4-329

Answer 4

В обоих случаях следует сказать unsigned char * aa = &array1[h]; (или array2[h] для второго цикла). Нет смысла надеяться, что компилятор поднимет эту операцию индекса, когда вы сможете это сделать и быть уверенным.

Две петли делают разные вещи:

Цикл 1 делает x[i]^x[i-1] перед индексированием в aa, в то время как Loop 2 индексов aa от x[i] до этого, а затем выполняет ^ x[i-1] после.

Несмотря на это, я хотел бы использовать указатели для x[i] и x[i-1], и я бы раскатать петлю, так что Loop 1 будет выглядеть примерно так:

unsigned char * aa = &array1[h]; 
unsigned char * px = &x[1]; 
unsigned char * px1 = &x[0]; 
for (i = 1; i < 10; i++){ 
    *px = aa[ *px^*px1 ]; px++; px1++; 
} 
for (; i < 10000; i += 10){ 
    *px = aa[ *px^*px1 ]; px++; px1++; 
    *px = aa[ *px^*px1 ]; px++; px1++; 
    *px = aa[ *px^*px1 ]; px++; px1++; 
    *px = aa[ *px^*px1 ]; px++; px1++; 
    *px = aa[ *px^*px1 ]; px++; px1++; 
    *px = aa[ *px^*px1 ]; px++; px1++; 
    *px = aa[ *px^*px1 ]; px++; px1++; 
    *px = aa[ *px^*px1 ]; px++; px1++; 
    *px = aa[ *px^*px1 ]; px++; px1++; 
    *px = aa[ *px^*px1 ]; px++; px1++; 
} 

В качестве альтернативы можно использовать один p указатель, и используйте жесткие смещения, например:

unsigned char * aa = &array1[h]; 
unsigned char * px = &x[0]; 
for (i = 1; i < 10; i++){ 
    px[1] = aa[ px[1]^px[0] ]; px++; 
} 
for (; i < 10000; i += 10, px += 10){ 
    px[ 1] = aa[ px[ 1]^px[0] ]; 
    px[ 2] = aa[ px[ 2]^px[1] ]; 
    px[ 3] = aa[ px[ 3]^px[2] ]; 
    px[ 4] = aa[ px[ 4]^px[3] ]; 
    px[ 5] = aa[ px[ 5]^px[4] ]; 
    px[ 6] = aa[ px[ 6]^px[5] ]; 
    px[ 7] = aa[ px[ 7]^px[6] ]; 
    px[ 8] = aa[ px[ 8]^px[7] ]; 
    px[ 9] = aa[ px[ 9]^px[8] ]; 
    px[10] = aa[ px[10]^px[9] ]; 
} 

Я не уверен, что было бы быстрее.

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