c - 使用 Intel 内在函数进行位逆向重新排序优化

Question

不久前，我使用 SSE 内在函数优化了 radix2 函数，并且我几乎接近 FFTW 性能，因此，我的下一步是优化我在原始代码中找到的位反向重新排序函数，说实话，我想优化它。原来的代码是这样的:

void bit_reverse_reorder(float *x,float *y, int N)
{
   int bits=0;
   int i, j, k;
   float tempr, tempi;
   //MAXPOW = 12

   for (i=0; i<MAXPOW; i++)
      if (pow_2[i]==N) bits=i;

   for (i=0; i<N; i++)
   {
      j=0;
      for (k=0; k<bits; k++)
         if (i&pow_2[k]) j+=pow_2[bits-k-1];
      if (j>i)
      {
        tempr=x[i];
        tempi=y[i];
        x[i]=x[j];
        y[i]=y[j];
        x[j]=tempr;
        y[j]=tempi;
      }
   }
}

int main()
{
   radix2(re,im,N);

   bit_reverse_reorder(re,im,N);
}

PS:pow_2[]是一个预先计算的数组，包含2的幂(1,2,4,8,16,32,...)，N是元素数量= 4096 ，*x和*y分别表示输入数据每个元素的实部和虚部。

radix2 生成未排序的结果，因此指定的函数会对结果重新排序。

首先，我并没有完全理解这个位反转是如何工作的!因此，我认为如果有人给我有关此功能如何工作的提示，那就太好了。

其次，我打算使用 SSE 内在函数来增强该函数的性能，那么是否有任何 2 条指令的 vector 可以在交换循环中使用？

Answer 1

感谢@nwellnhof 评论，我对交换函数进行了另一项修改，如下所示:

void bit_reverse_reorder(float *x,float *y, int N)
{
   unsigned i,j;
   for (i = 0, j = 0; i < N; i++) {
      if (i < j) 
      {
         float tmpx = x[i];
         x[i] = x[j];
         x[j] = tmpx;

         float tmpy = y[i];
         y[i] = y[j];
         y[j] = tmpy;
      }
      unsigned bit = ~i & (i + 1);

      unsigned rev = (N / 2) / bit;

      j ^= (N - 1) & ~(rev - 1);
   }
}

现在我得到了函数内 for 循环 54 900 个周期的性能，这也不错:)