Un moyen rapide de remplacer des éléments dans un tableau - C

Question

Supposons que nous ayons un tableau d'ints comme celui-ci:

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

Je voudrais remplacer tous les éléments qui ont une valeur de 1 par une autre valeur, par exemple 123456. Cela peut être implémenté de manière triviale avec:

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

Par curiosité, existe-t-il un moyen plus rapide de le faire, par une sorte de ruse x86, ou est-ce le meilleur code pour le processeur?

Answer 1

Pour votre cas spécifique où vous devez initialement 0 et 1, la suite pourrait être plus rapide. Vous aurez à banc de marquer. Vous ne pourrez probablement pas faire beaucoup mieux avec la plaine C bien; vous pouvez avoir besoin de se plonger dans de l'assemblée si vous souhaitez profiter de "x86 supercherie" qui peuvent exister.

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

EDIT:

Référence 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));
}

---

mes résultats:

Ordinateur: quad core AMD Phenom @2.5 GHz, Linux, GCC 4.7, compilé avec

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

• if de la version: ~5-10ms
• *= de la version: ~1.3 ms

Answer 2

Pour un petit tableau tel que le vôtre, il est inutile d'essayer de trouver un autre algorithme, et si les valeurs ne sont pas dans un modèle spécifique, une simple boucle est le seul moyen de le faire de toute façon.

Cependant, si vous avez un très grand tableau (nous parlons de plusieurs millions d'entrées), vous pouvez diviser le travail en threads. Chaque thread séparé gère une partie plus petite de l'ensemble de données.

Answer 3

Vous pourriez indice de référence présente ainsi:

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

Je le lance par la même référence que SchighSchagh, avec peu ou pas de différence sur mon jeu en place. Elle peut différer sur le vôtre, mais.

EDIT: Arrêtez les presses!

Je viens de me rappeler que x86 peut "unbranch ternaire" opérateurs en cas de disputes entre les ":" sont des constantes. Envisager de code suivant:

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

Ressemble presque à votre code d'origine, n'est-ce pas? Eh bien, démontage montre qu'il a été compilé sans branches:

  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)  
    }

Performance sage, il semble à la hauteur ou peu mieux que mon origine et SchighSchagh solution. Il est plus lisible et plus souple, si. Par exemple, il peut travailler avec tableau[i] avoir des valeurs différentes de 0 et de 1.

Bas de la ligne, de comparer ET de prendre un coup d'oeil dans le démontage.

Answer 4

Le tableau est suffisamment petit pour tenir dans le cache, il devrait donc être intéressant d'utiliser SIMD: (non testé)

   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
 

Dérouler par 2 pourrait aider.

Si vous avez SSE4.1, vous pouvez utiliser l'astuce de multiplication de SchighSchagh avec pmulld .

Answer 5

Voici quelques code Win32 profil des différentes versions de l'algorithme (compilé à l'aide de VS2010 Exprimer à l'aide de défaut de libération de construire):-

#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");
}

Il a pour les tests: C à l'aide d'un if()..., C à l'aide d'une multiplication, d'harold simd version et mon simd version.

L'exécutant de nombreuses fois (rappelez-vous, lorsque le profilage vous devriez la moyenne des résultats sur plusieurs pistes) il y a peu de différence entre toutes les versions sauf la ramification qui est sensiblement plus lent.

Ce n'est pas très surprenant que le algortihm fait très peu de travail pour chaque élément de mémoire. Ce que cela signifie, c'est que le vrai facteur limitant est la bande passante entre le CPU et la mémoire, le CPU est constamment en attente pour la mémoire de la rattraper, même avec le cpu aider avec le pré-chargement de données (ia32 de détecter et de prélecture de données de façon linéaire).