Schnelle Möglichkeit, Elemente in einem Array zu ersetzen – C

Nehmen wir an, wir haben ein Array von Ints wie dieses:

const int size = 100000;
int array[size];
//set some items to 0 and other items to 1

Ich möchte alle Elemente mit dem Wert 1 durch einen anderen Wert ersetzen, z. B. 123456. Dies kann trivial implementiert werden mit:

for(int i = 0; i < size ; i++){
    if(array[i] != 0) 
        array[i] = 123456;
}

Gibt es aus Neugier einen schnelleren Weg, dies durch eine Art x86-Trick zu tun, oder ist dies der beste Code für den Prozessor?

Für Ihren speziellen Fall, in dem Sie anfänglich 0 und 1 haben, Folgendes könnte sei schneller. Sie müssen es abgleichen. Mit einfachem C können Sie es jedoch wahrscheinlich nicht viel besser machen. Möglicherweise müssen Sie in die Assemblierung eintauchen, wenn Sie die möglicherweise vorhandenen “x86-Tricks” ausnutzen möchten.

for(int i = 0; i < size ; i++){
  array[i] *= 123456;
}

BEARBEITEN:

Benchmark-Code:

#include <time.h>
#include <stdlib.h>
#include <stdio.h>

size_t diff(struct timespec *start, struct timespec *end)
{
  return (end->tv_sec - start->tv_sec)*1000000000 + end->tv_nsec - start->tv_nsec;
}

int main(void)
{
  const size_t size = 1000000;
  int array[size];

  for(size_t i=0; i<size; ++i) {
    array[i] = rand() & 1;
  }

  struct timespec start, stop;

  clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &start);
  for(size_t i=0; i<size; ++i) {
    array[i] *= 123456;
    //if(array[i]) array[i] = 123456;
  }
  clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &stop);

  printf("size: %zu\t nsec: %09zu\n", size, diff(&start, &stop));
}

meine Ergebnisse:

Computer: Quad-Core AMD Phenom @2.5GHz, Linux, GCC 4.7, kompiliert mit

$ gcc arr.c -std=gnu99 -lrt -O3 -march=native

• if Version: ~5-10ms
• *= Version: ~1,3 ms

Für ein kleines Array wie Ihres ist es sinnlos, einen anderen Algorithmus zu finden, und wenn die Werte nicht in einem bestimmten Muster liegen, ist eine einfache Schleife sowieso die einzige Möglichkeit, dies zu tun.

Wenn Sie jedoch ein sehr großes Array haben (wir sprechen von mehreren Millionen Einträgen), können Sie die Arbeit in Threads aufteilen. Jeder separate Thread verarbeitet einen kleineren Teil des gesamten Datensatzes.

Vielleicht möchten Sie dies auch Benchmarken:

for(int i = 0; i < size ; i++){
  array[i] = (~(array[i]-1) & 123456);
}

Ich führe es durch denselben Benchmark wie SchighSchagh, mit wenig oder keinem Unterschied in meinem Setup. Bei dir kann es aber anders sein.

EDIT: Stoppt die Pressen!

Ich habe mich gerade daran erinnert, dass x86 ternäre Operatoren “entzweigen” kann, wenn Argumente zwischen “:” Konstanten sind. Betrachten Sie folgenden Code:

for(size_t i=0; i<size; ++i) {
    array[i] = array[i] ? 123456 : 0;
}

Sieht fast wie Ihr Originalcode aus, nicht wahr? Nun, die Disassemblierung zeigt, dass es ohne Zweige kompiliert wurde:

  for(size_t i=0; i<size; ++i) {
00E3104C  xor         eax,eax  
00E3104E  mov         edi,edi  
        array[i] = array[i] ? 123456 : 0;
00E31050  mov         edx,dword ptr [esi+eax*4]  
00E31053  neg         edx  
00E31055  sbb         edx,edx  
00E31057  and         edx,1E240h  
00E3105D  mov         dword ptr [esi+eax*4],edx  
00E31060  inc         eax  
00E31061  cmp         eax,5F5E100h  
00E31066  jb          wmain+50h (0E31050h)  
    }

In Bezug auf die Leistung scheint es auf Augenhöhe oder etwas besser als meine ursprüngliche und SchighSchagh-Lösung zu sein. Es ist jedoch besser lesbar und flexibler. Beispielsweise kann es mit Arrays arbeiten[i] andere Werte als 0 und 1 haben.

Unterm Strich Benchmark UND einen Blick in die Demontage werfen.

Das Array ist klein genug, dass es in den Cache passt, daher sollte es sich lohnen, SIMD zu verwenden: (nicht getestet)

  mov ecx, size
  lea esi, [array + ecx * 4]
  neg ecx
  pxor xmm0, xmm0
  movdqa xmm1, [_vec4_123456]  ; value of { 123456, 123456, 123456, 123456 }
_replaceloop:
  movdqa xmm2, [esi + ecx * 4] ; assumes the array is 16 aligned, make that true
  add ecx, 4
  pcmpeqd xmm2, xmm0
  pandn xmm2, xmm1
  movdqa [esi + ecx * 4 - 16], xmm2
  jnz _replaceloop

Abrollen um 2 könnte helfen.

Wenn Sie SSE4.1 haben, können Sie den Multiplikationstrick von SchighSchagh mit verwenden pmulld.

Hier ist etwas Win32-Code, um verschiedene Versionen des Algorithmus zu profilieren (kompiliert mit VS2010 Express unter Verwendung des Standard-Release-Builds):-

#include <windows.h>
#include <stdlib.h>
#include <stdio.h>

const size_t
  size = 0x1D4C00;

_declspec(align(16)) int
  g_array [size];

_declspec(align(16)) int
  _vec4_123456 [] = { 123456, 123456, 123456, 123456 };

void Test (void (*fn) (size_t, int *), char *test)
{
  printf ("Executing test: %s\t", test);

  for(size_t i=0; i<size; ++i) {
    g_array[i] = rand() & 1;
  }

  LARGE_INTEGER
    start,
    end;

  QueryPerformanceCounter (&start);

  fn (size, g_array);

  QueryPerformanceCounter (&end);

  printf("size: %u\t count: %09u\n", size, (int) (end.QuadPart - start.QuadPart));
}

void Test1 (size_t size, int *array)
{
  for(size_t i=0; i<size; ++i) {
    array[i] *= 123456;
  }
}

void Test2 (size_t size, int *array)
{
  for(size_t i=0; i<size; ++i) {
    if(array[i]) array[i] = 123456;
  }
}

void Test3 (size_t array_size, int *array)
{
  __asm
  {
    mov edi,array
    mov ecx, array_size 
    lea esi, [edi + ecx * 4]
    neg ecx
    pxor xmm0, xmm0
    movdqa xmm1, [_vec4_123456]  ; value of { 123456, 123456, 123456, 123456 }
_replaceloop:
    movdqa xmm2, [esi + ecx * 4] ; assumes the array is 16 aligned, make that true
    add ecx, 4
    pcmpeqd xmm2, xmm0
    pandn xmm2, xmm1
    movdqa [esi + ecx * 4 - 16], xmm2
    jnz _replaceloop
  }
}

void Test4 (size_t array_size, int *array)
{
  array_size = array_size * 8 / 12;

  __asm
  {
        mov edi,array
        mov ecx,array_size
        lea esi,[edi+ecx*4]
                                      lea edi,[edi+ecx*4]
        neg ecx
                                      mov edx,[_vec4_123456]
        pxor xmm0,xmm0
        movdqa xmm1,[_vec4_123456]
replaceloop:
        movdqa xmm2,[esi+ecx*4]
                                      mov eax,[edi]
                                      mov ebx,[edi+4]
        movdqa xmm3,[esi+ecx*4+16]
                                      add edi,16
        add ecx,9
                                      imul eax,edx    
        pcmpeqd xmm2,xmm0
                                      imul ebx,edx
        pcmpeqd xmm3,xmm0
                                      mov [edi-16],eax
                                      mov [edi-12],ebx
        pandn xmm2,xmm1
                                      mov eax,[edi-8]
                                      mov ebx,[edi-4]
        pandn xmm3,xmm1
                                      imul eax,edx    
        movdqa [esi+ecx*4-36],xmm2
                                      imul ebx,edx
        movdqa [esi+ecx*4-20],xmm3
                                      mov [edi-8],eax
                                      mov [edi-4],ebx
        loop replaceloop
  }
}

int main()
{
    Test (Test1, "Test1 - mul");
    Test (Test2, "Test2 - branch");
    Test (Test3, "Test3 - simd");
    Test (Test4, "Test4 - simdv2");
}

Es hat für Tests: C mit an if()...C mit einem multiplizieren, Harolds simd-Version und meine simd-Version.

Wenn Sie es viele Male ausführen (denken Sie daran, dass Sie beim Profiling die Ergebnisse über mehrere Durchläufe mitteln sollten), gibt es kaum einen Unterschied zwischen allen Versionen, außer der Verzweigungsversion, die erheblich langsamer ist.

Dies ist nicht sehr überraschend, da der Algorithmus sehr wenig Arbeit für jedes Speicherelement leistet. Das bedeutet, dass der eigentliche Begrenzungsfaktor die Bandbreite zwischen der CPU und dem Speicher ist. Die CPU wartet ständig darauf, dass der Speicher aufholt, selbst wenn die CPU beim Vorabruf der Daten hilft (ia32 erkennt und prefetch Daten linear).

Sie könnten ein anderes Array oder eine andere Datenstruktur verwenden, um die Indizes der Elemente zu verfolgen, die Sie auf eins setzen, und dann nur diese Elemente besuchen. Dies funktioniert am besten, wenn nur wenige Elemente auf eins gesetzt sind

Dies könnte sich als schneller erweisen.

for(int i = 0; i < size ; i++){
  array[i] = ((123456 << array[i]) - 123456);
}

BEARBEITEN: Bitweise Operation auf Linksverschiebung geändert.