Evg |
СОДЕРЖАНИЕ
Влияние конвейера на скорость исполнения кода
Запись от Evg размещена 02.05.2012 в 17:53
Показов 202877
Комментарии 38
|
1. Предисловие Одно из стандартных заблуждений начинающих программистов заключается в том, что многие думают, что чем короче исходник программы, тем быстрее программа будет работать. На самом деле для больших проектов первоочередным показателем является грамотное проектирование программы, а не количество строк кода. Но это всего лишь лирическое отступление, которое упомянуто к слову. В статье речь пойдёт немного о другом. Ещё одним из стандартных заблуждений является то, что если написать программу на ассемблере, то программа будет работать быстрее. В данной статье я не буду рассматривать какую-то большую программу, а рассмотрю лишь коротенькую функцию, которая выполняет весьма простое действие. При этом всё равно возникает подсознательное ощущение, что фрагмент кода будет работать быстро, если количество операций в нём минимизировать. Чисто на всякий случай. Кода речь идёт об intel'овских процессорах, то имеются в виду процессоры с intel'овской системой команд, коими, помимо процессоров Intel, являются и процессоры AMD 2. Постановка простой задачи В качестве постановки задачи я просто напишу коротенькую функцию, глядя на которую легко понять, что она делает.
Указанный "горячий" фрагмент кода является определяющим с точки зрения скорости работы, т.к. он будет исполняться часто, а потому паровоз операций, который стоит до цикла и после цикла на скорость работы программы не оказывают практически никакого влияния. Потому что эти операции будут работать только один раз за один вызов функции, против, условно говоря, нескольких тысяч исполнений операций, находящихся внутри цикла. Таким образом, глядя на ассемблерный код, дело выглядит так, что компилятор построил его самым оптимальны образом и сокращать тут просто нечего. Ну а теперь вопрос: а можно ли как-то ускорить этот код? 3. Каким образом происходит исполнение в процессоре В учебниках по ассемблеру обычно рассказывают только то, что делает та или иная машинная операция. Но довольно редко уделяется внимание тому, а каким же образом происходит выполнение операций в процессоре. И это вполне логично: мы имеем последовательность машинных команд на входе и имеем однозначный результат в виде значений в регистрах и в памяти на выходе, а каким образом это достигается - это дело процессора. Но на самом деле есть целая куча тонкостей, на хорошее понимание которых может потребоваться несколько лет. В данном разделе я ограничусь лишь поверхностным описанием тех сведений, которые необходимы для последующего понимания статьи. Кто-то эти моменты знает, а кто-то о них ещё не задумывался Все процессоры содержат исполнительное устройство - конвейер. Я видел в книгах, что про это немного рассказывают, но лишь для общего понимания. Современные процессоры имеют несколько конвейеров, которые могут исполнять команды параллельно. Можно две операции выполнять параллельно, или нельзя, решает аппаратура в процессе декодирования операции. Т.е., к примеру, если есть операция чтения из памяти в регистр %eax и операция инкрементации регистра %ebx, то эти две операции аппаратура может исполнять параллельно, поскольку они не конфликтуют по ресурсам. Но вот если бы вторая операция была операцией инкрементирования регистра %eax, то параллельное исполнение было бы невозможным: сначала нужно дождаться загрузки значения из памяти в %eax и только потом значение регистра инкрементировать. Есть ещё один момент, которому тоже нечасто уделяют внимание - это время исполнения операций. Простые операции типа целочисленного сложения-вычитания или битовой арифметики исполняются за один такт на любом более-менее приличном процессоре. Более сложные операции типа умножения или деления, как правило, исполняются несколько тактов (причём на разных процессорах время исполнения может сильно различаться). Связано это со сложным устройством апаратных элементов, которые исполняют данные операции. Операции чтения из памяти на любом современном высокоскоростном процессоре исполняется несколько тактов. Точной причины этого я не знаю, но есть некоторый минимальный порог времени, требуемый для прочтения данных из транзисторной матрицы: нужно вычислить, из какого места нужно данные прочитать, а потом ещё и прочитать сами данные. Дальше эти данные через шину нужно передать на процессор. На всех железках процессор и память представляют физически разведённые друг от друга устройства на общей плате. Чтение из памяти может исполняться несколько десятков или даже сотен машинных тактов. Именно из-за этого в современных процессорах присутсвует кэш (и даже не один), который физически находится на процессоре или очень близко к нему, а потому имеет более короткое время доступа к данным, но ограниченный размер памяти. И даже в тех случаях, когда данные оказываются в кэше первого уровня, их чтение занимает порядка трёх машинных тактов На этом данный раздел можно закончить. Мне кажется, что для общего понимания данных сведений вполне достаточно 4. Что происходит при исполнении нашей тестовой программы FIXME Данный раздел получился очень сложным для восприятия. Надо как-то его более внятно переписать Посмотрим, как исполняется на процессоре наша тестовая программа. Для удобства ещё раз приведу ассемблерный код "горячего" участка
5. Переписываем программу под параллельное исполнение При вычислении выражения "dst[i] = src[i] + 1023", как мы уже выяснили, практически ничего нельзя распараллелить по разным конвейерам, т.к. все операции цепочкой зависят друг от друга. Но если посмотреть, как исполняется не одна итерация цикла, а весь цикл, то легко можно заметить, что две соседние итерации цикла являются полностью независимыми. Т.е. при вычислении двух операторов "dst[0] = src[0] + 1023" и "dst[1] = src[1] + 1023" нету той цепочной зависимости, о которой писалось в разделе 4. А потому нашу функцию можно переписать по другому:
6. Результаты замеров В заключение статьи осталось померить тот выигрыш, который даёт нам оптимизированный вариант кода по сравнению с "простым". Итоговый вариант программы, на которой я проводил замеры, приведён ниже. Важные моменты, связанные с методикой измерения, отмечены в комментариях. Внутри функции copy имеются две реализации под макросом. По умолчанию работает "простой" вариант, при замене "#if 1" на "#if 0" будет работать оптимизированный вариант
Результаты получились следующие: Code Процессор: Intel Core2 Q9400, 2.66 ГГц ОС: linux Компилятор: gcc-4.1.2 Опции компилятора: -m32 -O3 "Обычный" вариант: time: 10.270 time: 10.050 time: 10.140 time: 10.100 time: 10.120 Оптимизированный вариант: time: 8.940 time: 8.960 time: 9.080 time: 8.950 time: 8.980 Code Процессор: AMD Athlon 64 X2, 2.8 ГГц ОС: windows Компилятор: borland builder 2007 Опции компилятора: те, что по умолчанию стоят в режиме RELEASE, 32-битный режим "Обычный" вариант: time: 10.015 time: 10.000 time: 10.000 time: 10.015 time: 10.000 Оптимизированный вариант: time: 8.799 time: 8.798 time: 8.799 time: 8.798 time: 8.783 Code Процессор: Sun UltraSPARC-III+, 1.2 ГГц ОС: solaris Компилятор: Sun cc Опции компилятора: -xarch=v8plusb -xO4 (32-битный режим) "Обычный" вариант: time: 10.020 time: 10.030 time: 10.020 time: 10.040 time: 10.030 Оптимизированный вариант: time: 8.830 time: 8.830 time: 8.840 time: 8.840 time: 8.840 Code Процессор: TI UltraSparc IIi, 400 МГц ОС: linux Компилятор: gcc-4.2.4 Опции компилятора: -m32 -mcpu=ultrasparc3 -O3 "Обычный" вариант: time: 10.310 time: 10.310 time: 10.310 time: 10.310 time: 10.320 Оптимизированный вариант: time: 8.340 time: 8.340 time: 8.340 time: 8.330 time: 8.340 Первым делом хочется сказать, что пример, рассматриваемый в данной статье - это всего лишь демонстрационный пример, на котором можно пощупать, как работает многоконвейерный процессор. Ни в коем случае данный пример не стОит рассматривать как рекомендацию к самостоятельному переписыванию циклов в подобном стиле. Компилятор, надлежащим образом настроенный, справится с задачей лучше, чем среднестатистический программист (см. этот, этот и этот посты в комментариях). Построить код лучше компилятора сможет разве что эксперт, хорошо понимающий работу конвейера FIXME Что-то ещё хотел сказать 8. Ссылки на темы, где обсуждался данный вопрос | ||||||||||||||||||||||||||||||||||||||||
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Всего комментариев 38
Комментарии
-
Все эти нанотехнологии, на самом деле, говорят с одной стороны о дерьмовости intel'овской системы команд, с другой стороны о том, что intel всем доступными средствами пытается обеспечить производительность для "старых" кодов (т.е. кодов, которые были получены компиляторами, настроенными на те конвейеры, которые были актуальными в "те времена")
Сообщение от snake32
Запись от Evg размещена 17.09.2012 в 21:13
-
Не по теме:
в IA-32e (64-bit) отсутствуют многие инструкции IA-32. Почему? Потому, что им не хватило места их закодировать :) Старались как могил, ввели новые префиксы, все равно не смогли уложиться в prefix, opcode, ModR/M, SIB. Получилось все довольно по-дебильному, например в 64 битном режиме нельзя сделать push/pop r32/mem32. Только push/pop r16/mem16 и push/pop r64/mem64.
Сообщение от Evg
Запись от Kastaneda размещена 18.09.2012 в 10:03
-
Наверное ты имеешь в виду X86_64 (ибо IA64 - это Itanium).
Сообщение от Kastaneda
А почему оно должны быть? X86_64 и IA64 - это совершенно новые системы команд, в идеале должны быть полностью отрезаны от "плохой" системы команд i386 (IA-32). Но проблема, как обычно, возникает в совместимости: хочется, чтобы старые бинарники работали на новой железке. В IA-64 пошли по пути двоичной компиляции: на машине IA-64 работает двоичный компилятор приложений, который коды IA-32 на лету конвертирует в IA-64. В X86_64 пошли по более простому пути: в аппаратуру затащили поддержку "старой" системы команд (правда не знаю, как оно реализовано технически), чтобы старый бинарник можно было вживую исполнить на новом процессоре. Понятно, что всю "старую" систему команд поддерживать не надо, нужна только та часть, которая используется в пользовательском софте. Та часть, кторая требуется для операционных систем и драйверов она не поддержана и все эти проблемы решаются на уровне операционной системы.Запись от Evg размещена 18.09.2012 в 15:48
-
Не совсем понял, что имеется ввиду. Для 32 битного кода есть т.н. legacy или compatibility mode (intel с amd в терминологии договориться не могут
Сообщение от Evg
). Он выполняется фактически в 64 битном окружении, но с 32 битными (имеется ввиду как в protected mode) селекторами в сегментных регистрах.
А в x86_64 старые инструкции просто расширили путем добавления префиска REX.
REX - это один байт, старшие 4 бита которого всегда равны 0x4, а младшие имеют свои значения. Например 3 байт (т.е. 4 справа) имеет имя W. И префикс REX.W расширяет используемые регистры до 64 бит, при чем опкод инструкции не меняется. Например:
в зависимости от наличия REX.W ModR/M байт интерпритируется по разному, а поскольку добавлены новые регистры R9-R15, то закодировать все старые инструкции под x86_64 просто не хватило местаAssembler 1 2
db 0x89, 0xd3 ; mov ebx, edx db 0x48, 0x89, 0xd3 ; 0x48 = REX.W, т.е. mov rbx, rdx

UPDATE in 2019
Мнение выше может быть глупостью в силу недостатка ума на момент написания коммента, не следует воспринимать его всерьез
Запись от Kastaneda размещена 18.09.2012 в 16:55
-
Запись от Evg размещена 18.09.2012 в 17:07
-
С точки зрения ассемблера скорость можно поднять если массив заполнять с "конца", тогда отпадает необходимость в команде CMP, во вторых можно немного изменить последовательность команд
Code 1 2 3 4 5 6 7 8 9
.L4: movl 4(%ebx,%ecx,4), %edx movl (%ebx,%ecx,4), %eax subl $1, %ecx addl $1023, %edx addl $1023, %eax movl %eax, 4(%esi,%ecx,4) movl %edx, 8(%esi,%ecx,4) jnz .L4
Запись от Mikl___ размещена 24.09.2012 в 06:27
-
Цель статьи - не в том, чтобы показать, как максимально эффективно написать код для данного цикла. Данный тупой цикл - это всего лишь простой наглядный пример, на котором вживую можно было бы пощупать, как происходит ускорение за счёт раздувания кода (а не за счёт его сокращения, как многим интуитивно кажется)
Сообщение от Mikl___
Запись от Evg размещена 24.09.2012 в 09:02
-
Evg, прежде чем писать комментарий я внимательно прочитал статью и мое замечание направлено не на оптимизацию "тупого цикла" (хотя, почему он тупой? нормальная "муха-дрозофила" для опытов и пояснений), многие циклы типа for можно избавить от лишнего сравнения в конце цикла если в счетчик сразу положить предельное значение и не инкрементировать счетчик, а декрементировать. Что касается данного примера, то для сложения/вычитания/умножения с константой не обязательно использовать регистр, можно складывать/вычитать/умножать непосредственно в памяти
Assembler 1 2 3 4 5 6 7 8 9 10 11 12
mov ecx,length lea esi,src L4: add dword ptr [esi+ecx*4],1023h add dword ptr [esi+ecx*4-4],1023h add dword ptr [esi+ecx*4-8],1023h add dword ptr [esi+ecx*4-12],1023h add dword ptr [esi+ecx*4-16],1023h add dword ptr [esi+ecx*4-20],1023h add dword ptr [esi+ecx*4-24],1023h add dword ptr [esi+ecx*4-28],1023h sub ecx,8 jnz L4
Запись от Mikl___ размещена 25.09.2012 в 04:18
-
Mikl___, дошло, что ты имел в виду. Но пример всё-таки написан на Си. В данном примере компилятор не вправе делать такое преобразование, т.к. он не знает, пересекаются ли блоки памяти под src и dst. Чтобы у компилятора появилась возможность развернуть цикл в обратную сторону, надо налепить Restrict'ы на параметры-указатели. После чего компилятор, как мне кажется, вполне бы мог такое преобразование и сделать. Но gcc даже в этом случае не делает. Как вариант, он знает, что на скорость кода это не повлияет. Но мне кажется, что это не так и здесь просто случай, с которым не умеет справляться gcc (либо делает только по каким-то опциям для оптимизации циклов). Ради интереса надо посмотреть код на микрософтовском компиляторе (правда я не знаю, как под виндой ассемблерный код смотреть)
А насчёт того, что можно производить операцию непосредственно над памятью без пересылки значения в регистр, есть некое подозрение, что такая конструкция работает медленнее, чем три операции (чтение, инкрементация, запись).Запись от Evg размещена 25.09.2012 в 09:19
-
Evg,
а проверить слабо? Здесь нет зависимости от регистров, параллельно происходит целых восемь (а можно и шестнадцать) сложений. А по поводу того, что "пример всё-таки написан на Си" есть целый цикл статей Криса Касперски "С-шные трюки от мыщъх'а" на http://www.insidepro.com/rus/doc.shtml и там же:
"Техника оптимизации под Linux (Часть 1)"
"Техника оптимизации под Linux (Часть 2 - ветвления)"
"Техника оптимизации под Linux (Часть 3 - оптимизация циклов)"Запись от Mikl___ размещена 25.09.2012 в 09:44
-
> а проверить слабо?
С учётом того, что я не знаю intel'овский ассемблер, для меня это вопрос вовсе не 5 секунд, а требует усилий и времени. А потому с полпинка на ходу не проверю.
> Здесь нет зависимости от регистров, параллельно происходит целых восемь
> (а можно и шестнадцать) сложений
Только вот в исходнике на Си данные копировались из одного места, а записываются в другое. В то время как в твоём ассемблерном коде, если я правильно его понимаю, чтение и запись происходит по одному и тому же адресу. Ну и подозрения касаются в том числе и параллельного исполнения. Я не схемотехник, но есть подозрения, что такие операции очень сложны в техническом исполнении, особенно для современных длинноконвейерных и многоконвейерных процессоров. Думаю, что поддержаны они для совместимости со старыми процессорами. Но это только мои собственные соображения, которые надо ещё проверитьЗапись от Evg размещена 25.09.2012 в 11:35
-
Evg,
взаимно, я не работаю на синтаксисе AT&T, если пересылка идет из одной в другую область памяти то:Assembler 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
movl length,%ecx lea src,%esi lea dst,%edi L4: movl (%esi,%ecx,4),%eax movl -4(%esi,%ecx,4),%ebx movl -8(%esi,%ecx,4),%edx movl -12(%esi,%ecx,4),%ebp addl $1023,%eax addl $1023,%ebx addl $1023,%edx addl $1023h,%ebp movl %eax,(%edi,%ecx,4) movl %ebx,-4(%edi,%ecx,4) movl %edx,-8(%edi,%ecx,4) movl %ebp,-12(%edi,%ecx,4) subl $4,ecx jnz L4
Запись от Mikl___ размещена 25.09.2012 в 12:04
-
> я не работаю на синтаксисе AT&T
Я говорю не про синтаксис, а про intel'овскую систему команд вообще. В самом общем виде я её знаю. Но с учётом того, что я вообще не занимаюсь программированием на ассемблере, для меня эта задача всё-таки требует усилий даже в простом варианте
> если пересылка идет из одной в другую область памяти то
Т.е. ровно то же самое, что и в статье, только в параллель пущено 4 ветки вместо двух и цикл в обратную сторону (что позволило сократить 1 сравнение). Т.е. ничего нового
На всякий случай подытожу текущие задачи (которые к статье в общем-то и не относятся):
1. Проверить на каком-нибудь коммерческом компиляторе, приведёт ли наличие restrict'а к тому, что компилятор развернёт цикл в обратную сторону с целью экномии операции сравнения
2. Проверить время работы операции "чтение-инкрементация-запись" по сравнению стрёмя операциями "чтение"-"инкрементация"-"запись"Запись от Evg размещена 25.09.2012 в 12:53
-
добавил свой вариант без развёртки цикла, но с векторизациейC 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96
#include <stdio.h> #include <stdlib.h> #include <time.h> #define N 100000 int __attribute__((aligned(16))) src[sizeof (int) * N]; int __attribute__((aligned(16))) dst[sizeof (int) * N]; int lenth = N; void copy (void) { unsigned long i; #if 1 /* "Простой" вариант for (i = 0; i < lenth; i++) dst[i] = src[i] + 1023;*/ __asm__ __volatile__ ( "movl lenth, %ecx \n" "xorl %eax, %eax \n" "movdqa (2f), %xmm1 \n" "shrl $2, %ecx \n" "jmp 1f \n" ".p2align 4 \n" "2: \n" ".long 1023 \n" ".long 1023 \n" ".long 1023 \n" ".long 1023 \n" "1: \n" "movdqa src(%eax), %xmm0 \n" "paddd %xmm1, %xmm0 \n" "movdqa %xmm0, dst(%eax) \n" "dec %ecx \n" "addl $16, %eax \n" "testl %ecx, %ecx \n" "jnz 1b \n" ); /*int k = 0; for (i = 0; i < lenth; i++) //if (dst[i] == 1023) //k++; printf("%d\n", dst[i]);*/ #else /* Оптимизированный вариант */ for (i = 0; i < lenth; i += 2) { int a, b, c, d; a = src[i]; b = src[i+1]; c = a + 1023; d = b + 1023; dst[i] = c; dst[i+1] = d; } #endif } #define LOOP 100000 #define COUNT 1 int main (void) { clock_t t1, t2; unsigned i, j; for (i = 0; i < COUNT; i++) { t1 = clock(); for (j = 0; j < LOOP; j++) copy(); t2 = clock(); printf("time: %.03f\n", ((double)(t2 - t1))/CLOCKS_PER_SEC); } return 0; }
gcc (GCC) 4.7.1 20120721 (prerelease)
Intel Core i-2410
опции компилятора -m32 -O3
"Простой вариант": 1.860
"Оптимизированный вариант": 5.410
Мой вариант: 1.820(без -O3)
с опцией -mno-sse
"Простой вариант": 7.080
"Оптимизированный вариант": 5.410
O3 включает в себя опцию floop-optimize, которая не гарантирует развёртку циклов, а вот опция -funroll-loops сделает это, если цикл подходит под условия, описанные в Software Optimization Guide for AMD\Intel, при сборке приложений конечно же не ограничиваются опцией -O3, там ещё куча опций идёт и обычно включает в себя -fprofile-use, которая включает в себя -funroll-loops
В заключение нужно написать, что все эти примеры были исключительно для демонстрации работы конвеера, а то читая предисловие, складывается впечатление, что
могут дать какой то существенный прирост в производительности и надо всегда так разворачивать циклы. На самом деле такая помощь компилятору обычно приводят к деградации производительноститакие конструкцииint a, b, c, d;
a = src[i];
b = src[i+1];
c = a + 1023;
d = b + 1023;
dst[i] = c;
dst[i+1] = d;
это "заблуждение" распространяют студенты-неудачники, которые полгода дрочили тасм, сдали на троечку и думают, что и все остальные такие же дураки, что не могут написать ничего быстрее, чем компиляторЗапись от Super-Windоws размещена 25.09.2012 в 18:33
-
> В заключение нужно написать <...>
ВО!!!! Именно это я планировал написать, но потом никак не мог вспомнить. Правда, как мне сейчас кажется, была ещё одна мысль для заключения, но, может быть, кто-то ещё своим замечанием напомнит. (в скобках замечу, что предисловие тоже дерьмово написано)
Пойду-ка по этому поводу тебе где-нибудь плюсик выдамЗапись от Evg размещена 25.09.2012 в 22:40
-
Запись от Evg размещена 02.10.2012 в 20:58


). Он выполняется фактически в 64 битном окружении, но с 32 битными (имеется ввиду как в protected mode) селекторами в сегментных регистрах. 
