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

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

Итак,

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 делает удивительные и очень продвинутые фокус-покусы, чтобы сделать его эффективным. На вашем месте я бы занялся чем-нибудь другим. Сегодня очень мало спроса на мегаоптимизированное программное обеспечение для ПК. Мое дружеское предложение - изучить процессоры для мобильных устройств (в основном ARM), потому что в мобильных устройствах проблемы со скоростью процессора, энергопотреблением и временем автономной работы означают, что микрооптимизированное программное обеспечение более важно. А ARM имеет улучшенный набор инструкций для x86.

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

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

Вероятный Причина того, что 4b быстрее, чем 4a, заключается в том, что он лучше распараллеливается. Из 4a:

mov bl, al;
and bl, $01;          // data dep (bl)
mov  [edx], bl;       // data dep (bl)
shr al, $01;
mov bl, al;           // data dep (al)
and bl, $01;          // data dep (bl)
mov [edx + $01], bl;  // data dep (bl)

Инструкции с пометкой «data dep» не могут начать выполняться, пока не завершится предыдущая инструкция, и я написал регистры, которые вызывают эту зависимость данных. Современные процессоры способны запускать инструкцию до того, как последняя будет завершена, если нет зависимости. Но способ, которым вы упорядочили эти операции, предотвращает это.

В 4b у вас меньше зависимостей данных:

mov bl, al;
and bl, $01;          // data dep (bl)
shr al, $01;
mov [edx], bl;
mov bl, al;
and bl, $01;          // data dep (bl)
shr al, $01;
mov [edx + $01], bl;

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

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

Я собирался дать тот же алгоритм, что и Воутер ван Нифтерик

Кроме того, я бы объяснил лучшую производительность с точки зрения цепочек зависимостей. В каждой из предложенных вами версий при развертывании базового цикла вы сохраняли зависимость между двумя последовательными итерациями: каждая из ваших shr al, $ 01; требует, чтобы предыдущее значение al было вычислено. Если вы организуете развернутые итерации так, чтобы их можно было выполнять параллельно, они фактически будут выполняться на современном процессоре. Пусть вас не вводят в заблуждение ложные зависимости, которые могут быть подавлены переименованием регистров.

Кто-то указал, что Pentium может выполнять две инструкции одновременно. Это правда, но современные процессоры (начиная с Pentium Pro, PII, ..., Core, Core 2) одновременно выполняют гораздо больше двух инструкций, когда у них есть такая возможность, то есть когда нет зависимости между выполняемыми инструкциями. Обратите внимание, как в версии Воутера ван Нифтерика каждая строка может выполняться независимо от других.

http://www.agner.org/optimize/ содержит всю информацию, которая может вам понадобиться для понимания архитектуры современных процессоров. и как ими воспользоваться.

Компиляторы очень хорошо справляются с оптимизацией небольших подпрограмм.

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

Изменить: Обратите внимание, что процессоры Pentium могут выполнять определенные инструкции параллельно ( Суперскалярная архитектура ), это называется спариванием.

если вы поддерживаете только 80386 и выше, вы можете использовать набор инструкций BTcc и SETcc следующим образом:

BT ax,1
SETC [dx]
inc dx

BT ax,2
SETC [dx]
inc dx

и т. Д.

Расширяя ответ Ника D, я пробовал следующие версии на основе поиска по таблице, все из , которые быстрее, чем реализации, которые вы даете (и быстрее, чем код Воутера ван Нифтерика ).

Дан следующий упакованный массив:

      const Uint64DecPix : PACKED ARRAY [0..255] OF UINT64 =
  ( $0000000000000000, $0000000000000001, $0000000000000100, $0000000000000101, $0000000000010000, $0000000000010001, $0000000000010100, $0000000000010101, $0000000001000000, $0000000001000001, $0000000001000100, $0000000001000101, $0000000001010000, $0000000001010001, $0000000001010100, $0000000001010101,
    $0000000100000000, $0000000100000001, $0000000100000100, $0000000100000101, $0000000100010000, $0000000100010001, $0000000100010100, $0000000100010101, $0000000101000000, $0000000101000001, $0000000101000100, $0000000101000101, $0000000101010000, $0000000101010001, $0000000101010100, $0000000101010101,
    $0000010000000000, $0000010000000001, $0000010000000100, $0000010000000101, $0000010000010000, $0000010000010001, $0000010000010100, $0000010000010101, $0000010001000000, $0000010001000001, $0000010001000100, $0000010001000101, $0000010001010000, $0000010001010001, $0000010001010100, $0000010001010101,
    $0000010100000000, $0000010100000001, $0000010100000100, $0000010100000101, $0000010100010000, $0000010100010001, $0000010100010100, $0000010100010101, $0000010101000000, $0000010101000001, $0000010101000100, $0000010101000101, $0000010101010000, $0000010101010001, $0000010101010100, $0000010101010101,
    $0001000000000000, $0001000000000001, $0001000000000100, $0001000000000101, $0001000000010000, $0001000000010001, $0001000000010100, $0001000000010101, $0001000001000000, $0001000001000001, $0001000001000100, $0001000001000101, $0001000001010000, $0001000001010001, $0001000001010100, $0001000001010101,
    $0001000100000000, $0001000100000001, $0001000100000100, $0001000100000101, $0001000100010000, $0001000100010001, $0001000100010100, $0001000100010101, $0001000101000000, $0001000101000001, $0001000101000100, $0001000101000101, $0001000101010000, $0001000101010001, $0001000101010100, $0001000101010101,
    $0001010000000000, $0001010000000001, $0001010000000100, $0001010000000101, $0001010000010000, $0001010000010001, $0001010000010100, $0001010000010101, $0001010001000000, $0001010001000001, $0001010001000100, $0001010001000101, $0001010001010000, $0001010001010001, $0001010001010100, $0001010001010101,
    $0001010100000000, $0001010100000001, $0001010100000100, $0001010100000101, $0001010100010000, $0001010100010001, $0001010100010100, $0001010100010101, $0001010101000000, $0001010101000001, $0001010101000100, $0001010101000101, $0001010101010000, $0001010101010001, $0001010101010100, $0001010101010101,
    $0100000000000000, $0100000000000001, $0100000000000100, $0100000000000101, $0100000000010000, $0100000000010001, $0100000000010100, $0100000000010101, $0100000001000000, $0100000001000001, $0100000001000100, $0100000001000101, $0100000001010000, $0100000001010001, $0100000001010100, $0100000001010101,
    $0100000100000000, $0100000100000001, $0100000100000100, $0100000100000101, $0100000100010000, $0100000100010001, $0100000100010100, $0100000100010101, $0100000101000000, $0100000101000001, $0100000101000100, $0100000101000101, $0100000101010000, $0100000101010001, $0100000101010100, $0100000101010101,
    $0100010000000000, $0100010000000001, $0100010000000100, $0100010000000101, $0100010000010000, $0100010000010001, $0100010000010100, $0100010000010101, $0100010001000000, $0100010001000001, $0100010001000100, $0100010001000101, $0100010001010000, $0100010001010001, $0100010001010100, $0100010001010101,
    $0100010100000000, $0100010100000001, $0100010100000100, $0100010100000101, $0100010100010000, $0100010100010001, $0100010100010100, $0100010100010101, $0100010101000000, $0100010101000001, $0100010101000100, $0100010101000101, $0100010101010000, $0100010101010001, $0100010101010100, $0100010101010101,
    $0101000000000000, $0101000000000001, $0101000000000100, $0101000000000101, $0101000000010000, $0101000000010001, $0101000000010100, $0101000000010101, $0101000001000000, $0101000001000001, $0101000001000100, $0101000001000101, $0101000001010000, $0101000001010001, $0101000001010100, $0101000001010101,
    $0101000100000000, $0101000100000001, $0101000100000100, $0101000100000101, $0101000100010000, $0101000100010001, $0101000100010100, $0101000100010101, $0101000101000000, $0101000101000001, $0101000101000100, $0101000101000101, $0101000101010000, $0101000101010001, $0101000101010100, $0101000101010101,
    $0101010000000000, $0101010000000001, $0101010000000100, $0101010000000101, $0101010000010000, $0101010000010001, $0101010000010100, $0101010000010101, $0101010001000000, $0101010001000001, $0101010001000100, $0101010001000101, $0101010001010000, $0101010001010001, $0101010001010100, $0101010001010101,
    $0101010100000000, $0101010100000001, $0101010100000100, $0101010100000101, $0101010100010000, $0101010100010001, $0101010100010100, $0101010100010101, $0101010101000000, $0101010101000001, $0101010101000100, $0101010101000101, $0101010101010000, $0101010101010001, $0101010101010100, $0101010101010101);
PUint64DecPix : pointer = @Uint64DecPix;

вы можете написать следующее:

procedure DecodePixelsPS1Pas (EncPixels: Byte; var DecPixels: TDecodedPixels);
begin
  DecPixels := TDecodedPixels(Uint64DecPix[EncPixels]);
end;

procedure DecodePixelsPS1PasInline (EncPixels: Byte; var DecPixels: TDecodedPixels);
inline;
begin
  DecPixels := TDecodedPixels(Uint64DecPix[EncPixels]);
end;

procedure DecodePixelsPS1Asm (EncPixels: Byte; var DecPixels: TDecodedPixels);
asm
  lea ecx, Uint64DecPix //[<-Added in EDIT 3] 
  //mov ecx, dword ptr PUint64DecPix - alternative to the above line (slower for me)
  movzx eax, al
  movq xmm0, [8*eax+ecx]  //Using XMM rather than MMX so we don't have to issue emms at the end
  movq [edx], xmm0        //use MOVQ because it doesn't need mem alignment
end;

Стандартные реализации PAS и ASM довольно похожи по скорости, но реализация PAS, помеченная как «INLINE», является самой быстрой, потому что она избавляется от всех вызовов / ret, участвующих в вызове процедура.

- EDIT--: Я забыл сказать: поскольку вы неявно предполагаете что-то о структуре памяти вашей структуры TDecodedPixels, было бы лучше, если бы вы объявили ее как

PACKED ARRAY [0..7] of byte

- РЕДАКТИРОВАТЬ2--: Вот мои результаты для сравнения:

Time1 : 2.51638266874701 ms.    <- Delphi loop.
Time2 : 2.11277620479698 ms.    <- Delphi unrolled loop.
Time3 : 2.21972066282167 ms.    <- BASM loop.
Time4a : 1.34093090043567 ms.    <- BASM unrolled loop.
Time4b : 1.52222070123437 ms.    <- BASM unrolled loop instruction switch.
Time5 : 1.17106364076999 ms.    <- Wouter van Nifterick
TimePS1 : 0.633099318488802 ms.    <- PS.Pas
TimePS2 : 0.551617593856202 ms.    <- PS.Pas Inline
TimePS3 : 0.70921094720139 ms.    <- PS.Asm (speed for version before 3rd EDIT)

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

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

Этот код Delphi быстрее , чем ваш самый быстрый код на ассемблере:

procedure DecodePixels5(EncPixels: Byte; var DecPixels: TDecodedPixels);
begin
  DecPixels[0] := (EncPixels shr 0) and $01;
  DecPixels[1] := (EncPixels shr 1) and $01;
  DecPixels[2] := (EncPixels shr 2) and $01;
  DecPixels[3] := (EncPixels shr 3) and $01;
  DecPixels[4] := (EncPixels shr 4) and $01;
  DecPixels[5] := (EncPixels shr 5) and $01;
  DecPixels[6] := (EncPixels shr 6) and $01;
  DecPixels[7] := (EncPixels shr 7) and $01;
end;


Results:

Time1  : 1,03096806151283 ms.    <- Delphi loop.
Time2  : 0,740308641141395 ms.   <- Delphi unrolled loop.
Time3  : 0,996602425688886 ms.   <- BASM loop.
Time4a : 0,608267951561275 ms.   <- BASM unrolled loop.
Time4b : 0,574162510648039 ms.   <- BASM unrolled loop instruction switch.
Time5  : 0,499628206138524 ms. !!!  <- Delphi unrolled loop 5.

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

Машинный код выглядит так:

  push ebx;
  // DecPixels[0] := (EncPixels shr 0) and 1;
  movzx ecx,al
  mov ebx,ecx
  //  shr ebx,$00
  and bl,$01
  mov [edx],bl
  // DecPixels[1] := (EncPixels shr 1) and 1;
  mov ebx,ecx
  shr ebx,1
  and bl,$01
  mov [edx+$01],bl
  // DecPixels[2] := (EncPixels shr 2) and 1;
  mov ebx,ecx
  shr ebx,$02
  and bl,$01
  mov [edx+$02],bl
  // DecPixels[3] := (EncPixels shr 3) and 1;
  mov ebx,ecx
  shr ebx,$03
  and bl,$01
  mov [edx+$03],bl
  // DecPixels[4] := (EncPixels shr 4) and 1;
  mov ebx,ecx
  shr ebx,$04
  and bl,$01
  mov [edx+$04],bl
  // DecPixels[5] := (EncPixels shr 5) and 1;
  mov ebx,ecx
  shr ebx,$05
  and bl,$01
  mov [edx+$05],bl
  // DecPixels[6] := (EncPixels shr 6) and 1;
  mov ebx,ecx
  shr ebx,$06
  and bl,$01
  mov [edx+$06],bl
  // DecPixels[7] := (EncPixels shr 7) and 1;
  shr ecx,$07
  and cl,$01
  mov [edx+$07],cl
  pop ebx;

Изменить: Как и предполагалось, поиск в таблице действительно выполняется быстрее.

var
  PixelLookup:Array[byte] of TDecodedPixels;

// You could precalculate, but the performance gain would hardly be worth it because you call this once only.
for I := 0 to 255 do
  DecodePixels5b(I, PixelLookup[I]);


procedure DecodePixels7(EncPixels: Byte; var DecPixels: TDecodedPixels);
begin
  DecPixels := PixelLookup[EncPixels];
end;

Results:

Time1  : 1,03096806151283 ms.    <- Delphi loop.
Time2  : 0,740308641141395 ms.   <- Delphi unrolled loop.
Time3  : 0,996602425688886 ms.   <- BASM loop.
Time4a : 0,608267951561275 ms.   <- BASM unrolled loop.
Time4b : 0,574162510648039 ms.   <- BASM unrolled loop instruction switch.
Time5  : 0,499628206138524 ms. !!!  <- Delphi unrolled loop 5.
Time7 : 0,251533475182096 ms.    <- simple table lookup

SIMD

Если вы расширите алгоритм до обработки массивов, тогда SIMD станет вариантом оптимизации. Вот версия SIMD, которая в три раза меньше оптимизированного эквивалента 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;
}

Как насчет чего-нибудь вроде:

/* input byte in eax, address to store result in edx */
and eax, 0xff    /* may not be needed */
mov ebx, eax
shl ebx, 7
or  eax, ebx
mov ebx, eax
shl ebx, 14
or  eax, ebx
mov ebx, eax
and eax, 0x01010101
mov [edx], eax
shr ebx, 4
and ebx, 0x01010101
mov [edx+4], ebx

Incredible smart solution Chris, what would you do with the inverse problem: make a byte from an array of 8 bytes?

Non optimized solution for the inverse problem:

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