Форум программистов, компьютерный форум, киберфорум
Evg
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск  

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

Запись от Evg размещена 02.05.2012 в 17:53
Показов 202877 Комментарии 38
Метки asm, c, c++

1. Предисловие

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

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

Чисто на всякий случай. Кода речь идёт об intel'овских процессорах, то имеются в виду процессоры с intel'овской системой команд, коими, помимо процессоров Intel, являются и процессоры AMD

2. Постановка простой задачи

В качестве постановки задачи я просто напишу коротенькую функцию, глядя на которую легко понять, что она делает.

C
1
2
3
4
5
6
7
8
void
copy (int *dst, const int *src, unsigned long length)
{
  unsigned long i;
 
  for (i = 0; i < length; i++)
    dst[i] = src[i] + 1023;
}
Здесь всё понятно. На вход функции подаются два указателя на массив и размер массивов, далее поэлементно выполняется операция сложения. На языке Си программа написана предельно просто и что-то короче написать уже нельзя. Можно посмотреть выдачу ассемблерного текста из-под компилятора. Я использую gcc, а потому для получения ассемблерного текста я запускаю "gcc t.c -O3 -S" и смотрю итоговый файл t.s:

Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
copy:
    pushl   %ebp
    movl    %esp, %ebp
    movl    16(%ebp), %ecx
    pushl   %esi
    movl    8(%ebp), %esi
    pushl   %ebx
    movl    12(%ebp), %ebx
    testl   %ecx, %ecx
    je  .L5
    xorl    %edx, %edx
    .p2align 4,,15
.L4:
    movl    (%ebx,%edx,4), %eax
    addl    $1023, %eax
    movl    %eax, (%esi,%edx,4)
    incl    %edx
    cmpl    %edx, %ecx
    jne .L4
.L5:
    popl    %ebx
    popl    %esi
    popl    %ebp
    ret
"Горячий" (т.е. наиболее часто исполняемый) фрагмент кода, который представляет собой полезные действия внутри цикла, находится между метками .L4 и .L5. Здесь на вид тоже всё предельно просто и ясно. Читаем из памяти значение (src[i]), прибавляем нему 1023, записываем в память результат (dst[i]), увеличиваем на 1 счётчик цикла, сравниваем счётчик с верхней границей цикла и затем условный переход на начало цикла.

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

Ну а теперь вопрос: а можно ли как-то ускорить этот код?

3. Каким образом происходит исполнение в процессоре

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

Все процессоры содержат исполнительное устройство - конвейер. Я видел в книгах, что про это немного рассказывают, но лишь для общего понимания. Современные процессоры имеют несколько конвейеров, которые могут исполнять команды параллельно. Можно две операции выполнять параллельно, или нельзя, решает аппаратура в процессе декодирования операции. Т.е., к примеру, если есть операция чтения из памяти в регистр %eax и операция инкрементации регистра %ebx, то эти две операции аппаратура может исполнять параллельно, поскольку они не конфликтуют по ресурсам. Но вот если бы вторая операция была операцией инкрементирования регистра %eax, то параллельное исполнение было бы невозможным: сначала нужно дождаться загрузки значения из памяти в %eax и только потом значение регистра инкрементировать.

Есть ещё один момент, которому тоже нечасто уделяют внимание - это время исполнения операций. Простые операции типа целочисленного сложения-вычитания или битовой арифметики исполняются за один такт на любом более-менее приличном процессоре. Более сложные операции типа умножения или деления, как правило, исполняются несколько тактов (причём на разных процессорах время исполнения может сильно различаться). Связано это со сложным устройством апаратных элементов, которые исполняют данные операции. Операции чтения из памяти на любом современном высокоскоростном процессоре исполняется несколько тактов. Точной причины этого я не знаю, но есть некоторый минимальный порог времени, требуемый для прочтения данных из транзисторной матрицы: нужно вычислить, из какого места нужно данные прочитать, а потом ещё и прочитать сами данные. Дальше эти данные через шину нужно передать на процессор. На всех железках процессор и память представляют физически разведённые друг от друга устройства на общей плате. Чтение из памяти может исполняться несколько десятков или даже сотен машинных тактов. Именно из-за этого в современных процессорах присутсвует кэш (и даже не один), который физически находится на процессоре или очень близко к нему, а потому имеет более короткое время доступа к данным, но ограниченный размер памяти. И даже в тех случаях, когда данные оказываются в кэше первого уровня, их чтение занимает порядка трёх машинных тактов

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

4. Что происходит при исполнении нашей тестовой программы

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

Посмотрим, как исполняется на процессоре наша тестовая программа. Для удобства ещё раз приведу ассемблерный код "горячего" участка

Code
1
2
3
4
5
6
7
.L4:
    movl    (%ebx,%edx,4), %eax
    addl    $1023, %eax
    movl    %eax, (%esi,%edx,4)
    incl    %edx
    cmpl    %edx, %ecx
    jne .L4
Что здесь происходит. Сначала исполняется операция чтения из памяти (строка 2), которая требует 3 такта на исполнение (а может и больше, это всё нужно смотреть в описании процессора). Далее идёт операция сложения в регистре %eax (строка 3). Эта операция не может начать исполняться, пока не загрузится значение из памяти, а потому аппаратура вхолостую прощёлкает два пустых такта в ожидании данных из памяти. Далее идёт операция записи в память (строка 4), которая записывает в память результат вычисления, а потому она должна дождаться исполнения операции сложения (из строки 3). Далее идёт операция инкрементации счётчика (строка 5). Инкрементировать счётчик можно только после того, как мы исполним операцию записи в память (из строки 4), которая использует регистр %edx. Реально аппаратура умеет справляться с такими зависимостями и на пальцах исполняется что-то типа: прочитать текущее значение %edx, параллельно исполнить операцию записи в память и операцию прибавления единицы (без записи результата) и после того, как будет вычислен адрес для записи в память, записать результать прибавления единицы в регистр. Затем идёт операция сравнения (строка 6), которая должна дождаться исполнения операции инкрементации (из строки 5) и в конце выполняется условный переход, который благодаря механизму предсказания переходов начнёт выполняться не дожидаясь результата сравнения и уже потом сделать контрльную проверку того, что переход исполнен по делу. Предсказание переходов - это отдельная огромная тема, которую здесь не хочется затрагивать более подробно. Итого с учётом того, что две операции удалось поставить на параллельное исполнение, а операцию перехода аппаратура сделала заранее, то в грубой прикидке одна итерация цикла будет исполняться 6 тактов. При этом будет задействован один конвейер + немного второй. И это при том, что современные Intel'ы имеют 4 конвейра, которые при исполнении данного участка кода будут простаивать. Потактно исполнение будет выглядеть примерно так:

Code
1
2
3
4
5
6
1. Исполняем "movl (%ebx,%edx,4), %eax"
2. Ждём
3. Ждём
4. Исполняем "addl $1023, %eax"
5. Исполняем "movl %eax, (%esi,%edx,4)" и "incl %edx"
6. Исполняем "cmpl %edx, %ecx" и "jne .L4"
Потактно расписанная схема является очень условной. Есть много тонкостей при работе с конвейером типа того, что на самом деле конвейер разбит на несколько стадий: декодирование, чтение входных аргументов, исполнение, запись результатов и целая куча промежуточных стадий. Те операции, которые исполняются один такт, на самом деле проводят в конвейере несколько тактов. Но в то время, когда первая операция проходит через вторую стадию конвейера, вторая операция уже попадает на первую стадию. Мне не хотелось бы загромождать статью такими особенностями, чтобы не загородить ими основную мысль, а потому следует к моим словам относиться как к чему-то очень общему, а не детальным подробностям

5. Переписываем программу под параллельное исполнение

При вычислении выражения "dst[i] = src[i] + 1023", как мы уже выяснили, практически ничего нельзя распараллелить по разным конвейерам, т.к. все операции цепочкой зависят друг от друга. Но если посмотреть, как исполняется не одна итерация цикла, а весь цикл, то легко можно заметить, что две соседние итерации цикла являются полностью независимыми. Т.е. при вычислении двух операторов "dst[0] = src[0] + 1023" и "dst[1] = src[1] + 1023" нету той цепочной зависимости, о которой писалось в разделе 4. А потому нашу функцию можно переписать по другому:

C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void
copy (int *dst, const int *src, unsigned long length)
{
  unsigned long i;
 
  for (i = 0; i < length; 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;
    }
}
Данный код по количеству строк выглядит гораздо более громоздким. Математически он делает ровно то же самое, что и предыдущий вариант (на самом деле это справедливо только для чётного количества итераций, но на текущий момент это не важно): количество итераций цикла уменьшилось вдвое, но при этом вдвое увеличилось количество значащих операций в одной итерации. И кажется, что такой код является избыточным. Но если вспомнить те проблемы с распараллеливанием, о которых писалось в разделе 4, то здесь можно увидеть качественные изменения. Ассемблерный текст, соответствующий "горячему" участку данного кода, выглядит следующим образом:

Code
1
2
3
4
5
6
7
8
9
10
.L4:
    movl    4(%ebx,%ecx,4), %edx
    movl    (%ebx,%ecx,4), %eax
    addl    $1023, %edx
    addl    $1023, %eax
    movl    %eax, (%esi,%ecx,4)
    movl    %edx, 4(%esi,%ecx,4)
    addl    $2, %ecx
    cmpl    %ecx, %edi
    ja  .L4
Мы читаем два значения из памяти (строки 2 и 3) в разные регистры, а потому их можно исполнить параллельно. Далее мы проводим операции сложения (строки 4 и 5) над разными регистрами, а потому их можно исполнить паралельно. Затем мы два значения записываем в память (строки 6 и 7) в разные адреса, а потому их тоже можно исполнить параллельно. Далее идёт хвостик с инкрементацией счётчика и условным переходом на начало цикла, который исполнится ровно так же, как и в "простом" варианте программы. В итоге за одну итерацию нашего оптимизированного цикла мы исполняем две итерации исходного цикла, но время исполнения будет меньше за счёт того, что нам часть вычислений удалось раскидать по двум конвейерам для параллельного вычисления. Если расписать по тактам, то будет что-то типа того:

Code
1
2
3
4
5
6
1. Исполняем "movl 4(%ebx,%ecx,4), %edx" и "movl (%ebx,%ecx,4), %eax"
2. Ждём
3. Ждём
4. Исполняем "addl $1023, %edx" и "addl $1023, %eax"
5. Исполняем "movl %eax, (%esi,%ecx,4)", "movl %edx, 4(%esi,%ecx,4)" и "addl $2, %ecx"
6. Исполняем "cmpl %ecx, %edi" и "ja .L4"
Т.е. мы получаем как бы те же самые 6 тактов (но уже на две исходные итерации), что и в "простой" реализации. В конце раздела 4 я оговорил, что расписывание по тактам является очень условным. В данном случае это имеет ещё бОльшую роль. Раскидываени по тактам следует рассметривать как логическое. Реально конвейеры будут работать немного не так (хотя бы потому, что начало процесса декодирования каждой отдельной машинной команды делается строго последовательно). Оптимизированный код будет работать быстрее, но не в два раза.

6. Результаты замеров

В заключение статьи осталось померить тот выигрыш, который даёт нам оптимизированный вариант кода по сравнению с "простым". Итоговый вариант программы, на которой я проводил замеры, приведён ниже. Важные моменты, связанные с методикой измерения, отмечены в комментариях. Внутри функции copy имеются две реализации под макросом. По умолчанию работает "простой" вариант, при замене "#if 1" на "#if 0" будет работать оптимизированный вариант

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
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
 
void
copy (int *dst, const int *src, unsigned long length)
{
 unsigned long i;
 
#if 1
  /* "Простой" вариант */
  for (i = 0; i < length; i++)
    dst[i] = src[i] + 1023;
#else
  /* Оптимизированный вариант */
  for (i = 0; i < length; 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
}
 
/* Вызов функции делаем через указатель, чтобы не было inline-подстановки.
 * На результат это практически не влияет, но без inline'а проще глазками
 * смотреть ассемблерный текст */
void (*copy_ptr)(int*, const int*, unsigned long) = copy;
 
/* Размер массива */
#define N 100000
 
/* Количество циклов копирования, входящих в задачу.
 * Казалось бы, что два параметра N и LOOP являются избыточными,
 * но это только кажется. Если сравнить 100 циклов по 1 мегабйту
 * и 1 цикл на 100 мегабайт, то мы получим разные результаты.
 * В первом случае объём обработанных данных, условно говоря, целиком
 * умещается в кэш, а во втором случае - нет. В первом случае будет
 * маленькая нагрузка на подсистему памяти, обслуживающую виртуальную
 * адресацию, а во втором случае - большая. Мы хотим померить "чистое"
 * время работы цикла, но не скорость работы подсистемы памяти */
#define LOOP 100000
 
/* Количество повторений задачи. Параметр тоже может показаться избыточным.
 * Но если увеличить значение N таким образом, чтобы оно заведомо превышало
 * размер кэша, (и в соответсвующее число раз уменьшить значение LOOP,
 * чтобы общее время работы было примерно такое же) то по результирующей
 * печати времени исполнения можно увидеть, что COUNT себя оправдывает.
 * В этом случае первые один-два запуска задачи будут работать на то,
 * чтобы "раскрутилась" подсистема памяти (и время работы будет иметь выброс),
 * а остальные запуски задачи уже будут давать более-менее справедливые
 * результаты */
#define COUNT 5
 
int
main (void)
{
 clock_t t1, t2;
 unsigned i, j;
 
 int *src = malloc (sizeof (int) * N);
 int *dst = malloc (sizeof (int) * N);
 
 for (i = 0; i < COUNT; i++)
   {
     t1 = clock();
     for (j = 0; j < LOOP; j++)
       copy_ptr (dst, src, N);
     t2 = clock();
 
     printf("time: %.03f\n", ((double)(t2 - t1))/CLOCKS_PER_SEC);
   }
 
 return 0;
}
Замеры проводились на разных машинах с разными процессорами, под управлением разных операционных систем, с применением разных компиляторов. Из-за того, что процессоры работают с разной скоростью, на каждой машине я подгонял значение макроса LOOP с тем, чтобы "обычный" вариант работал порядка 10 секунд. Сделано это исключительно ради удобства, чтобы глядя на цифры можно было сразу оценить в целом влияние кработы конвейера на разных процессорах.

Результаты получились следующие:

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
7. Заключение

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

FIXME Что-то ещё хотел сказать

8. Ссылки на темы, где обсуждался данный вопрос
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Всего комментариев 38
Комментарии
  1. Старый комментарий
    Аватар для Evg
    Цитата Сообщение от snake32
    Вот те раз, а я как наивная дура думал что кодируя асм инструкции фактически касаюсь пальцами физических регистров ЦП. Уже даже регистры виртуальные!
    Все эти нанотехнологии, на самом деле, говорят с одной стороны о дерьмовости intel'овской системы команд, с другой стороны о том, что intel всем доступными средствами пытается обеспечить производительность для "старых" кодов (т.е. кодов, которые были получены компиляторами, настроенными на те конвейеры, которые были актуальными в "те времена")
    Запись от Evg размещена 17.09.2012 в 21:13 Evg вне форума
  2. Старый комментарий
    Аватар для Kastaneda

    Не по теме:

    Цитата Сообщение от Evg
    о дерьмовости intel'овской системы команд
    в IA-32e (64-bit) отсутствуют многие инструкции IA-32. Почему? Потому, что им не хватило места их закодировать :) Старались как могил, ввели новые префиксы, все равно не смогли уложиться в prefix, opcode, ModR/M, SIB. Получилось все довольно по-дебильному, например в 64 битном режиме нельзя сделать push/pop r32/mem32. Только push/pop r16/mem16 и push/pop r64/mem64.

    Запись от Kastaneda размещена 18.09.2012 в 10:03 Kastaneda вне форума
  3. Старый комментарий
    Аватар для Evg
    Цитата Сообщение от Kastaneda
    Почему?
    Наверное ты имеешь в виду X86_64 (ибо IA64 - это Itanium).

    А почему оно должны быть? X86_64 и IA64 - это совершенно новые системы команд, в идеале должны быть полностью отрезаны от "плохой" системы команд i386 (IA-32). Но проблема, как обычно, возникает в совместимости: хочется, чтобы старые бинарники работали на новой железке. В IA-64 пошли по пути двоичной компиляции: на машине IA-64 работает двоичный компилятор приложений, который коды IA-32 на лету конвертирует в IA-64. В X86_64 пошли по более простому пути: в аппаратуру затащили поддержку "старой" системы команд (правда не знаю, как оно реализовано технически), чтобы старый бинарник можно было вживую исполнить на новом процессоре. Понятно, что всю "старую" систему команд поддерживать не надо, нужна только та часть, которая используется в пользовательском софте. Та часть, кторая требуется для операционных систем и драйверов она не поддержана и все эти проблемы решаются на уровне операционной системы.
    Запись от Evg размещена 18.09.2012 в 15:48 Evg вне форума
  4. Старый комментарий
    Аватар для Kastaneda
    Цитата Сообщение от Evg
    В X86_64 пошли по более простому пути: в аппаратуру затащили поддержку "старой" системы команд (правда не знаю, как оно реализовано технически), чтобы старый бинарник можно было вживую исполнить на новом процессоре..
    Не совсем понял, что имеется ввиду. Для 32 битного кода есть т.н. legacy или compatibility mode (intel с amd в терминологии договориться не могут). Он выполняется фактически в 64 битном окружении, но с 32 битными (имеется ввиду как в protected mode) селекторами в сегментных регистрах.
    А в x86_64 старые инструкции просто расширили путем добавления префиска REX.
    REX - это один байт, старшие 4 бита которого всегда равны 0x4, а младшие имеют свои значения. Например 3 байт (т.е. 4 справа) имеет имя W. И префикс REX.W расширяет используемые регистры до 64 бит, при чем опкод инструкции не меняется. Например:
    Assembler
    1
    2
    
    db 0x89, 0xd3 ; mov ebx, edx
    db 0x48, 0x89, 0xd3 ; 0x48 = REX.W, т.е. mov rbx, rdx
    в зависимости от наличия REX.W ModR/M байт интерпритируется по разному, а поскольку добавлены новые регистры R9-R15, то закодировать все старые инструкции под x86_64 просто не хватило места

    UPDATE in 2019
    Мнение выше может быть глупостью в силу недостатка ума на момент написания коммента, не следует воспринимать его всерьез
    Запись от Kastaneda размещена 18.09.2012 в 16:55 Kastaneda вне форума
  5. Старый комментарий
    Аватар для Evg
    Ладно, забей. Я всё равно в intel'овской системе команд не разбираюсь, чтобы в такие детали вдаваться
    Запись от Evg размещена 18.09.2012 в 17:07 Evg вне форума
  6. Старый комментарий
    Аватар для Mikl___
    С точки зрения ассемблера скорость можно поднять если массив заполнять с "конца", тогда отпадает необходимость в команде 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___ вне форума
  7. Старый комментарий
    Аватар для Evg
    Цитата Сообщение от Mikl___
    С точки зрения ассемблера скорость можно поднять если массив заполнять с "конца", тогда отпадает необходимость в команде CMP, во вторых можно немного изменить последовательность команд
    Цель статьи - не в том, чтобы показать, как максимально эффективно написать код для данного цикла. Данный тупой цикл - это всего лишь простой наглядный пример, на котором вживую можно было бы пощупать, как происходит ускорение за счёт раздувания кода (а не за счёт его сокращения, как многим интуитивно кажется)
    Запись от Evg размещена 24.09.2012 в 09:02 Evg вне форума
  8. Старый комментарий
    [QUOTE]Операции чтения из памяти на любом современном высокоскоростном процессоре исполняется несколько тактов. Точной причины этого я не знаю, но есть некоторый минимальный порог времени, [/QUOTE]всё очень просто: основная память видит на более длинной шине, чем кеш и регистры и не может работать на той же частоте. Если расстояние между памятью и процессором 20 см, то на получение данных уже уйдёт минимум 1 333 пикосекунды даже по теории относительности, не считая ёмкости и индуктивности шины и многих других факторов, а доступ к регистру на частоте 2,4 ГГц занимает всего 417 пикосекунд. Это уже 3 такта на доступ к памяти и только один на доступ к регистру.
    Запись от размещена 24.09.2012 в 09:31
  9. Старый комментарий
    Кроме того, регистр в регистре один, а памяти много в одном чипе, значит сначала выставить адрес на шину, потом его надо расшифровать и физически выполнить доступ к нужным битам, потом выставить на шину его значение. Это три операции в одной и они занимают 3 такта по алгоритму. Дальше, сколько тактов надо держать адрес на шине? Такт 417 пикосекунд, до памяти 667 световых пикосекунд. В один такт уже не уложились, надо два. Два - это 834 пикосекунды. А значение сколько надо держать на шине? По той же логике 2 такта, то есть ещё 834 пикосекунды. И сам доступ минимум один такт. Итого уже 5 тактов = 2 085 пикосекунд. А кеш находится менее, чем в 417-ти световых пикосекундах от регистра и не добавляет 2 лишних такта. Если же учесть ещё и спектральные свойства самой шины такой длины, то вот и вылезают десятки и сотни тактов.
    Запись от размещена 24.09.2012 в 09:43
  10. Старый комментарий
    Аватар для Mikl___
    Цель статьи - не в том, чтобы показать, как максимально эффективно написать код для данного цикла. Данный тупой цикл - это всего лишь простой наглядный пример, на котором в живую можно было бы пощупать, как происходит ускорение за счёт раздувания кода (а не за счёт его сокращения, как многим интуитивно кажется)
    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___ вне форума
  11. Старый комментарий
    Аватар для Evg
    Mikl___, дошло, что ты имел в виду. Но пример всё-таки написан на Си. В данном примере компилятор не вправе делать такое преобразование, т.к. он не знает, пересекаются ли блоки памяти под src и dst. Чтобы у компилятора появилась возможность развернуть цикл в обратную сторону, надо налепить Restrict'ы на параметры-указатели. После чего компилятор, как мне кажется, вполне бы мог такое преобразование и сделать. Но gcc даже в этом случае не делает. Как вариант, он знает, что на скорость кода это не повлияет. Но мне кажется, что это не так и здесь просто случай, с которым не умеет справляться gcc (либо делает только по каким-то опциям для оптимизации циклов). Ради интереса надо посмотреть код на микрософтовском компиляторе (правда я не знаю, как под виндой ассемблерный код смотреть)

    А насчёт того, что можно производить операцию непосредственно над памятью без пересылки значения в регистр, есть некое подозрение, что такая конструкция работает медленнее, чем три операции (чтение, инкрементация, запись).
    Запись от Evg размещена 25.09.2012 в 09:19 Evg вне форума
  12. Старый комментарий
    Аватар для Mikl___
    А насчёт того, что можно производить операцию непосредственно над памятью без пересылки значения в регистр, есть некое подозрение, что такая конструкция работает медленнее, чем три операции (чтение, инкрементация, запись
    Evg,
    а проверить слабо? Здесь нет зависимости от регистров, параллельно происходит целых восемь (а можно и шестнадцать) сложений. А по поводу того, что "пример всё-таки написан на Си" есть целый цикл статей Криса Касперски "С-шные трюки от мыщъх'а" на http://www.insidepro.com/rus/doc.shtml и там же:
    "Техника оптимизации под Linux (Часть 1)"
    "Техника оптимизации под Linux (Часть 2 - ветвления)"
    "Техника оптимизации под Linux (Часть 3 - оптимизация циклов)"
    Запись от Mikl___ размещена 25.09.2012 в 09:44 Mikl___ вне форума
  13. Старый комментарий
    Аватар для Evg
    > а проверить слабо?

    С учётом того, что я не знаю intel'овский ассемблер, для меня это вопрос вовсе не 5 секунд, а требует усилий и времени. А потому с полпинка на ходу не проверю.

    > Здесь нет зависимости от регистров, параллельно происходит целых восемь
    > (а можно и шестнадцать) сложений

    Только вот в исходнике на Си данные копировались из одного места, а записываются в другое. В то время как в твоём ассемблерном коде, если я правильно его понимаю, чтение и запись происходит по одному и тому же адресу. Ну и подозрения касаются в том числе и параллельного исполнения. Я не схемотехник, но есть подозрения, что такие операции очень сложны в техническом исполнении, особенно для современных длинноконвейерных и многоконвейерных процессоров. Думаю, что поддержаны они для совместимости со старыми процессорами. Но это только мои собственные соображения, которые надо ещё проверить
    Запись от Evg размещена 25.09.2012 в 11:35 Evg вне форума
  14. Старый комментарий
    Аватар для Mikl___
    С учётом того, что я не знаю intel'овский ассемблер
    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 Mikl___ вне форума
  15. Старый комментарий
    Аватар для Evg
    > я не работаю на синтаксисе AT&T

    Я говорю не про синтаксис, а про intel'овскую систему команд вообще. В самом общем виде я её знаю. Но с учётом того, что я вообще не занимаюсь программированием на ассемблере, для меня эта задача всё-таки требует усилий даже в простом варианте

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

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

    На всякий случай подытожу текущие задачи (которые к статье в общем-то и не относятся):
    1. Проверить на каком-нибудь коммерческом компиляторе, приведёт ли наличие restrict'а к тому, что компилятор развернёт цикл в обратную сторону с целью экномии операции сравнения
    2. Проверить время работы операции "чтение-инкрементация-запись" по сравнению стрёмя операциями "чтение"-"инкрементация"-"запись"
    Запись от Evg размещена 25.09.2012 в 12:53 Evg вне форума
  16. Старый комментарий
    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 Super-Windоws вне форума
  17. Старый комментарий
    Аватар для Evg
    > В заключение нужно написать <...>

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

    Пойду-ка по этому поводу тебе где-нибудь плюсик выдам
    Запись от Evg размещена 25.09.2012 в 22:40 Evg вне форума
  18. Старый комментарий
    Аватар для Evg
    Цитата Сообщение от Super-Windоws
    В заключение нужно написать, что все эти примеры были исключительно для демонстрации работы конвеера
    Написал
    Запись от Evg размещена 02.10.2012 в 20:58 Evg вне форума
 
Новые блоги и статьи
Мобильное приложение ColorStep
pavlinmavlin 17.09.2026
Реализовал приложение Красный, Зеленый, Синий в Unity3d + c#. Название изменил на ColorStep. Приложение прошло модерацию и теперь доступно для скачивания. Делал его сам, шаг за шагом — и вот,. . .
Запрет дублирования строк в табличной части
Maks 13.09.2026
Реализация из решения ниже выполнена на нетиповом справочнике "Нормы ТО" с табличной часть "Виды ТО", разработанного в КА2, со следующими реквизитами: - ВидТО (СправочникСсылка. ВидыТО); - ВидГСМ. . .
Скрипты Tampermonkey для CyberForum, ChatGPT, Claude и пр.
Jin X 06.09.2026
Скрипты Tampermonkey для CyberForum, ChatGPT, Claude и пр. Работая с форумом и нейросетями в браузере часто хочется что-то подкорректировать или добавить какого-то функционала. Ниже прикреплён. . .
Программа опроса у.з. расходомера SLS-720F
Argus19 02.09.2026
Программа опроса у. з. расходомера SLS-720F Программа опрашивает один раз в минуту три ультразвуковых расходомера SLS-720F через интерфейс RS-485 по протоколу Modbus RTU. Опрашиваются регистры. . .
Hyper-V: Компьютер должен поддерживать доверенный платформенный модуль 2.0.
Maks 31.08.2026
При установке Windows 11 на виртуальную машину Hyper-V 2-го поколения вылезла такая ошибка: Решение: в параметрах виртуальной машины, в разделе "Безопасность" (Security) активировать флаг. . .
Архитектура биовида Стива в Майнкрафте: Зачем бонобо кубический каннибализм
anaschu 30.08.2026
Кубический Вагинокапитализм в Minecraft: Математический инвариант ОДУ и рок Стивов-бонобо Главная задача разработанной «Модели Всего» — наглядно продемонстрировать наличие системной «судьбы». . .
Оттачиваю умение писать js программы.
russiannick 30.08.2026
Проектом выходного дня стало написание Книги шифров Виженера. Итогом стала версия 200, синий туман. Синий туман назван так, потому что замораживает текст под собой. Нажатие синих кнопок управляют. . .
мат медиц модель 30. презентация проекта
anaschu 27.08.2026
хоп хоп хоп хидахоп, а я кладую))
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru