替换数组中元素的快速方法 - C

Question

假设我们有一系列这样的整数:

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

我想将所有值为1的项替换为另一个值,例如123456.这可以通过以下方式轻松实现:

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

出于好奇,有没有更快的方法来做到这一点,通过某种x86技巧,或者这是处理器的最佳代码？

Answer 1

对于最初具有0和1的特定情况,以下可能更快.你必须对它进行基准测试.尽管如此,你可能无法用普通的C做得更好; 如果你想利用可能存在的"x86技巧",你可能需要深入装配.

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

编辑:

基准代码:

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

我的结果:

计算机:四核AMD Phenom @ 2.5GHz,Linux,GCC 4.7,编译

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

• if 版本:~5-10ms
• *= 版本:~1.3ms

Answer 2

对于像你这样的小数组试图找到另一种算法是没有用的,如果这些值不是特定的模式,那么简单的循环是唯一的方法.

但是,如果你有一个非常大的数组(我们正在谈论几百万个条目),那么你可以将工作分成线程.每个单独的线程处理整个数据集的较小部分.

Answer 3

您可能也希望对此进行基准测试:

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

我通过与SchighSchagh相同的基准测试来运行它,在我的设置上几乎没有差别.但是,它可能会有所不同.

编辑:停止按下!

我记得如果":"之间的参数是常量,x86可以"取消分支"三元运算符.考虑以下代码:

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

看起来几乎像你的原始代码,不是吗？好吧,反汇编显示它已经编译而没有任何分支:

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

在性能方面,它似乎与我原来的和SchighSchagh解决方案相提并论.但它更具可读性和灵活性.例如,它可以用于具有不同于0和1的值的array [i].

底线,基准和偷看拆解.

Answer 4

该阵列足够小,适合缓存,因此使用SIMD值得:(未经测试)

  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

展开2可能会有所帮助.

如果你有SSE4.1,你可以使用SchighSchagh的乘法技巧pmulld.