Методы оптимизации сборки Intel x86 в примере задачи - PullRequest
Новая
       83

Методы оптимизации сборки Intel x86 в примере задачи

21 голосов
/ 12 сентября 2009

Я довольно давно изучаю ассемблер и пытаюсь переписать некоторые простые процедуры \ функции, чтобы увидеть выигрыш в производительности (если есть). Мой основной инструмент разработки - Delphi 2007, и первые примеры будут на этом языке, но их также можно легко перевести на другие языки.

Проблема гласит:

Мы указали значение байта без знака, в котором каждый из восьми бит представляет пиксель в одной строке экрана. Каждый отдельный пиксель может быть сплошным (1) или прозрачным (0). Другими словами, у нас есть 8 пикселей, упакованных в одно байтовое значение. Я хочу распаковать эти пиксели в восьмибайтовый массив так, чтобы младший пиксель (бит) попадал под самый низкий индекс массива и так далее. Вот пример: 

One byte value -----------> eight byte array

10011011 -----------------> [1][1][0][1][1][0][0][1]

Array index number ------->  0  1  2  3  4  5  6  7

Ниже я представляю пять методов, которые решают проблему. Далее я покажу их сравнение времени и то, как я их измерял.

Мои вопросы состоят из двух частей:

1

Я прошу у вас подробный ответ относительно методов DecodePixels4a и DecodePixels4b. Почему метод 4b несколько медленнее, чем 4a?

Если, например, это медленнее, потому что мой код не выровнен правильно, то покажите мне, какие инструкции в данном методе могут быть лучше выровнены и как это сделать, чтобы не нарушать метод.

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

2

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

Разрешены все процессоры семейства Intel и те, которые совместимы с ними.

Ниже вы найдете процедуры, написанные мной: 

procedure DecodePixels1(EncPixels: Byte; var DecPixels: TDecodedPixels);
var
  i3: Integer;
begin
  DecPixels[0] := EncPixels and $01;
  for i3 := 1 to 7 do
  begin
    EncPixels := EncPixels shr 1;
    DecPixels[i3] := EncPixels and $01;
    //DecPixels[i3] := (EncPixels shr i3) and $01;  //this is even slower if you replace above 2 lines with it
  end;
end;


//Lets unroll the loop and see if it will be faster.
procedure DecodePixels2(EncPixels: Byte; var DecPixels: TDecodedPixels);
begin
  DecPixels[0] := EncPixels and $01;
  EncPixels := EncPixels shr 1;
  DecPixels[1] := EncPixels and $01;
  EncPixels := EncPixels shr 1;
  DecPixels[2] := EncPixels and $01;
  EncPixels := EncPixels shr 1;
  DecPixels[3] := EncPixels and $01;
  EncPixels := EncPixels shr 1;
  DecPixels[4] := EncPixels and $01;
  EncPixels := EncPixels shr 1;
  DecPixels[5] := EncPixels and $01;
  EncPixels := EncPixels shr 1;
  DecPixels[6] := EncPixels and $01;
  EncPixels := EncPixels shr 1;
  DecPixels[7] := EncPixels and $01;
end;


procedure DecodePixels3(EncPixels: Byte; var DecPixels: TDecodedPixels);
begin
  asm
    push eax;
    push ebx;
    push ecx;
    mov bl, al;
    and bl, $01;
    mov [edx], bl;
    mov ecx, $00;
@@Decode:
    inc ecx;
    shr al, $01;
    mov bl, al;
    and bl, $01;
    mov [edx + ecx], bl;
    cmp ecx, $07;
    jnz @@Decode;
    pop ecx;
    pop ebx;
    pop eax;
  end;
end;


//Unrolled assembly loop
procedure DecodePixels4a(EncPixels: Byte; var DecPixels: TDecodedPixels);
begin
  asm
    push eax;
    push ebx;
    mov bl, al;
    and bl, $01;
    mov  [edx], bl;
    shr al, $01;
    mov bl, al;
    and bl, $01;
    mov [edx + $01], bl;
    shr al, $01;
    mov bl, al;
    and bl, $01;
    mov [edx + $02], bl;
    shr al, $01;
    mov bl, al;
    and bl, $01;
    mov [edx + $03], bl;
    shr al, $01;
    mov bl, al;
    and bl, $01;
    mov [edx + $04], bl;
    shr al, $01;
    mov bl, al;
    and bl, $01;
    mov [edx + $05], bl;
    shr al, $01;
    mov bl, al;
    and bl, $01;
    mov [edx + $06], bl;
    shr al, $01;
    mov bl, al;
    and bl, $01;
    mov [edx + $07], bl;
    pop ebx;
    pop eax;
  end;
end;


// it differs compared to 4a only in switching two instructions (but seven times)
procedure DecodePixels4b(EncPixels: Byte; var DecPixels: TDecodedPixels);
begin
  asm
    push eax;
    push ebx;
    mov bl, al;
    and bl, $01;
    shr al, $01;          //
    mov [edx], bl;        //
    mov bl, al;
    and bl, $01;
    shr al, $01;          //
    mov [edx + $01], bl;  //
    mov bl, al;
    and bl, $01;
    shr al, $01;          //
    mov [edx + $02], bl;  //
    mov bl, al;
    and bl, $01;
    shr al, $01;          //
    mov [edx + $03], bl;  //
    mov bl, al;
    and bl, $01;
    shr al, $01;          //
    mov [edx + $04], bl;  //
    mov bl, al;
    and bl, $01;
    shr al, $01;          //
    mov [edx + $05], bl;  //
    mov bl, al;
    and bl, $01;
    shr al, $01;          //
    mov [edx + $06], bl;  //
    mov bl, al;
    and bl, $01;
    mov [edx + $07], bl;
    pop ebx;
    pop eax;
  end;
end;

А вот как я могу их проверить: 

program Test;

{$APPTYPE CONSOLE}

uses
  SysUtils, Windows;

type
  TDecodedPixels = array[0..7] of Byte;
var
  Pixels: TDecodedPixels;
  Freq, TimeStart, TimeEnd :Int64;
  Time1, Time2, Time3, Time4a, Time4b: Extended;
  i, i2: Integer;

begin
  if QueryPerformanceFrequency(Freq) then
  begin
    for i2 := 1 to 100 do
    begin
      QueryPerformanceCounter(TimeStart);
      for i := 1 to 100000 do
        DecodePixels1(155, Pixels);
      QueryPerformanceCounter(TimeEnd);
      Time1 := Time1 + ((TimeEnd - TimeStart) / Freq * 1000);

      QueryPerformanceCounter(TimeStart);
      for i := 1 to 100000 do
        DecodePixels2(155, Pixels);
      QueryPerformanceCounter(TimeEnd);
      Time2 := Time2 + ((TimeEnd - TimeStart) / Freq * 1000);

      QueryPerformanceCounter(TimeStart);
      for i := 1 to 100000 do
        DecodePixels3(155, Pixels);
      QueryPerformanceCounter(TimeEnd);
      Time3 := Time3 + ((TimeEnd - TimeStart) / Freq * 1000);

      QueryPerformanceCounter(TimeStart);
      for i := 1 to 100000 do
        DecodePixels4a(155, Pixels);
      QueryPerformanceCounter(TimeEnd);
      Time4a := Time4a + ((TimeEnd - TimeStart) / Freq * 1000);

      QueryPerformanceCounter(TimeStart);
      for i := 1 to 100000 do
        DecodePixels4b(155, Pixels);
      QueryPerformanceCounter(TimeEnd);
      Time4b := Time4b + ((TimeEnd - TimeStart) / Freq * 1000);

    end;
    Writeln('Time1 : ' + FloatToStr(Time1 / 100) + ' ms.    <- Delphi loop.');
    Writeln('Time2 : ' + FloatToStr(Time2 / 100) + ' ms.    <- Delphi unrolled loop.');
    Writeln('Time3 : ' + FloatToStr(Time3/ 100) + ' ms.    <- BASM loop.');
    Writeln('Time4a : ' + FloatToStr(Time4a / 100) + ' ms.    <- BASM unrolled loop.');
    Writeln('Time4b : ' + FloatToStr(Time4b / 100) + ' ms.    <- BASM unrolled loop instruction switch.');
  end;
  Readln;
end.

Вот результаты с моего компьютера (Intel® Pentium® E2180 на Win32 XP): 

Time1  : 1,68443549919493 ms.     <- Delphi loop.
Time2  : 1,33773024572211 ms.     <- Delphi unrolled loop.
Time3  : 1,37015271374424 ms.     <- BASM loop.
Time4a : 0,822916962526627 ms.    <- BASM unrolled loop.
Time4b : 0,862914462301607 ms.    <- BASM unrolled loop instruction switch.

Результаты довольно стабильны - время варьируется только на несколько процентов между каждым тестом, который я сделал. И это всегда было правдой: Time1 > Time3 > Time 2 > Time4b > Time4a

Так что я думаю, что разница между Time4a и Time4b зависит от того, как инструкции переключаются в методе DecodePixels4b. Иногда это 4%, иногда до 10%, но 4b всегда медленнее, чем 4a.

Я думал о другом методе с использованием инструкций MMX для записи в память восьми байтов за один раз, но я не могу найти быстрый способ распаковать байт в 64-битный регистр.

Спасибо за ваше время.

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

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

Это для меня загадка. Я снова запустил свой код с процедурами Wouter и PhilS, и вот результаты: 

Time1  : 1,66535493194387 ms.     <- Delphi loop.
Time2  : 1,29115785420688 ms.     <- Delphi unrolled loop.
Time3  : 1,33716934524107 ms.     <- BASM loop.
Time4a : 0,795041753757838 ms.    <- BASM unrolled loop.
Time4b : 0,843520166815013 ms.    <- BASM unrolled loop instruction switch.
Time5  : 1,49457681191307 ms.     <- Wouter van Nifterick, Delphi unrolled
Time6  : 0,400587402866258 ms.    <- PhiS, table lookup Delphi
Time7  : 0,325472442519827 ms.    <- PhiS, table lookup Delphi inline
Time8  : 0,37350491544239 ms.     <- PhiS, table lookup BASM

Посмотрите на результат Time5, довольно странно, не правда ли? Я предполагаю, что у меня другая версия Delphi, так как мой сгенерированный ассемблерный код отличается от предоставленного Wouter.

Второе основное редактирование:

Я знаю, почему рутина 5 была медленнее на моей машине. Я проверил «Проверка диапазона» и «Проверка переполнения» в опциях компилятора. Я добавил директиву assembler в подпрограмму 9, чтобы посмотреть, поможет ли это. Кажется, что с этой директивой процедура сборки так же хороша, как встроенный вариант Delphi или даже немного лучше.

Вот окончательные результаты: 

Time1  : 1,22508325749317 ms.     <- Delphi loop.
Time2  : 1,33004145373084 ms.     <- Delphi unrolled loop.
Time3  : 1,1473583622526 ms.      <- BASM loop.
Time4a : 0,77322594033463 ms.     <- BASM unrolled loop.
Time4b : 0,846033593023372 ms.    <- BASM unrolled loop instruction switch.
Time5  : 0,688689382044384 ms.    <- Wouter van Nifterick, Delphi unrolled
Time6  : 0,503233741036693 ms.    <- PhiS, table lookup Delphi
Time7  : 0,385254722925063 ms.    <- PhiS, table lookup Delphi inline
Time8  : 0,432993919452751 ms.    <- PhiS, table lookup BASM
Time9  : 0,362680491244212 ms.    <- PhiS, table lookup BASM with assembler directive

Третье основное редактирование:

По мнению @Pascal Cuoq и @j_random_hacker, разница во времени выполнения между подпрограммами 4a, 4b и 5 вызвана зависимостью данных. Однако я должен не согласиться с этим мнением, основываясь на дальнейших тестах, которые я провел.

Я также изобрел новую процедуру 4c, основанную на 4a. Вот оно: 

procedure DecodePixels4c(EncPixels: Byte; var DecPixels: TDecodedPixels);
begin
  asm
    push ebx;
    mov bl, al;
    and bl, 1;
    mov [edx], bl;
    mov bl, al;
    shr bl, 1;
    and bl, 1;
    mov [edx + $01], bl;
    mov bl, al;
    shr bl, 2;
    and bl, 1;
    mov [edx + $02], bl;
    mov bl, al;
    shr bl, 3;
    and bl, 1;
    mov [edx + $03], bl;
    mov bl, al;
    shr bl, 4;
    and bl, 1;
    mov [edx + $04], bl;
    mov bl, al;
    shr bl, 5;
    and bl, 1;
    mov [edx + $05], bl;
    mov bl, al;
    shr bl, 6;
    and bl, 1;
    mov [edx + $06], bl;
    shr al, 7;
    and al, 1;
    mov [edx + $07], al;
    pop ebx;
  end;
end;

Я бы сказал, что это зависит от данных.

А вот и тесты и результаты. Я сделал четыре теста, чтобы убедиться, что нет несчастного случая. Я также добавил новое время для процедур, предложенных GJ (Time10a, Time10b). 

          Test1  Test2  Test3  Test4

Time1   : 1,211  1,210  1,220  1,213
Time2   : 1,280  1,258  1,253  1,332
Time3   : 1,129  1,138  1,130  1,160

Time4a  : 0,690  0,682  0,617  0,635
Time4b  : 0,707  0,698  0,706  0,659
Time4c  : 0,679  0,685  0,626  0,625
Time5   : 0,715  0,682  0,686  0,679

Time6   : 0,490  0,485  0,522  0,514
Time7   : 0,323  0,333  0,336  0,318
Time8   : 0,407  0,403  0,373  0,354
Time9   : 0,352  0,378  0,355  0,355
Time10a : 1,823  1,812  1,807  1,813
Time10b : 1,113  1,120  1,115  1,118
Time10c : 0,652  0,630  0,653  0,633
Time10d : 0,156  0,155  0,172  0,160  <-- current winner!

Как видите, результаты 4a, 4b, 4c и 5 очень близки друг к другу. Это почему? Поскольку я удалил из 4a, 4b (у 4c его уже нет) две инструкции: push eax и pop eax. Так как я знаю, что не буду использовать где-либо еще в своем коде значение в eax, мне не нужно его сохранять. Теперь в моем коде только одна пара push / pop, так же как и в процедуре 5. Подпрограмма 5 сохраняет значение eax, потому что сначала делает его копию под ecx, но не сохраняет ecx.

Итак, мой вывод таков: разница во времени выполнения 5 и 4a и 4b (до третьего редактирования) не касалась зависимости от данных, а была вызвана дополнительной парой инструкций push / pop .

Мне очень интересны ваши комментарии.

Через несколько дней GJ изобрел еще более быстрый режим (время 10d), чем у PhiS. Отличная работа GJ!

Ответы [ 13 ]

0 голосов
/ 02 октября 2009

Невероятное интеллектуальное решение Крис , что бы вы сделали с обратной задачей: сделать байт из массива из 8 байтов?

Неоптимизированное решение обратной задачи: 

BtBld PROC Array:DWORD, Pixels:DWORD
  mov  eax, [Array]
  add  eax, 7
  mov  edx, [Pixels]

  mov  bx, 0

  mov  ecx, 8
rpt:  or  bx, [eax]
  dec  eax
  shl  bx, 1
  loop rpt
  shr  bx, 1
  mov  [edx], bl
  ret
BtBld ENDP
0 голосов
/ 15 сентября 2009

SIMD

Если вы расширите алгоритм для обработки массивов, SIMD станет опцией оптимизации. Вот SIMD-версия, которая составляет 1/3 времени оптимизированного эквивалента C: 

int main ()
{
  const int
    size = 0x100000;

  unsigned char
    *source = new unsigned char [size],
    *dest,
    *dest1 = new unsigned char [size * 32],
    *dest2 = new unsigned char [size * 32];

  for (int i = 0 ; i < size ; ++i)
  {
    source [i] = rand () & 0xff;
  }

  LARGE_INTEGER
    start,
    middle,
    end;

  QueryPerformanceCounter (&start);
  dest = dest1;
  for (int i = 0 ; i < size ; ++i)
  {
    unsigned char
      v = source [i];

    for (int b = 0 ; b < 8 ; ++b)
    {
      *(dest++) = (v >> b) & 1;
    }
  }
  unsigned char
    bits [] = {1,2,4,8,16,32,64,128,1,2,4,8,16,32,64,128},
    zero [] = {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
    ones [] = {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1};

  QueryPerformanceCounter (&middle);
  __asm
  {
    movdqu xmm1,bits
    movdqu xmm2,zero
    movdqu xmm3,ones
    mov ecx,0x100000/4
    mov esi,source
    mov edi,dest2
l1:
    lodsd
    movd xmm0,eax
    movd xmm4,eax
    punpcklbw xmm0,xmm0
    punpcklbw xmm4,xmm4
    punpcklwd xmm0,xmm0
    punpcklwd xmm4,xmm4
    punpckldq xmm0,xmm0
    punpckhdq xmm4,xmm4
    pand xmm0,xmm1
    pand xmm4,xmm1
    pcmpeqb xmm0,xmm2
    pcmpeqb xmm4,xmm2
    paddb xmm0,xmm3
    paddb xmm4,xmm3
    movdqu [edi],xmm0
    movdqu [edi+16],xmm4
    add edi,32
    dec ecx
    jnz l1
  }
  QueryPerformanceCounter (&end);

  cout << "Time taken = " << (middle.QuadPart - start.QuadPart) << endl;
  cout << "Time taken = " << (end.QuadPart - middle.QuadPart) << endl;
  cout << "memcmp = " << memcmp (dest1, dest2, size * 32) << endl;

  return 0;
}
0 голосов
/ 12 сентября 2009

I думаю дело в том, что запись в память (фактически, в кэш-память) медленнее, чем работа с регистрами.

Итак, 

mov [edx+...], bl
shr al, $01;
mov bl, al;

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

shr al, $01;
mov [edx], bl;
mov bl, al;

требуется bl немедленно, поэтому процессор должен остановиться и ждать завершения записи в память.

Это удивительно для меня. Современные процессоры Intel делают сумасшедшую конвейеризацию и регистрируют переименование, поэтому, на мой взгляд, во всяком случае, DecodePixels4b должен быть быстрее, поскольку зависимости каждой инструкции возвращаются назад. Выше приведено все объяснение, кроме этого:

x86 - ужасный набор инструкций, и Intel делает потрясающий и очень продвинутый фокус-покус, чтобы сделать его эффективным. На твоем месте я бы занялся чем-то другим. Сегодня очень мало спроса на программное обеспечение megaMcOptimised для ПК. Мое дружеское предложение - взглянуть на процессоры для мобильных устройств (в основном ARM), потому что в мобильных устройствах проблемы со скоростью процессора, энергопотреблением и временем автономной работы означают, что микрооптимизированное программное обеспечение более важно. И ARM имеет более высокий набор команд для x86.

Страница:
...