基4重排功能

Question

我有一个基4算法的重新排序函数，它需要大约60万个周期来完成4096个浮标元素(实部和虚部)的工作：

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

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

  for (i = 0; i < N; i++)
  {
      j = 0;
      for (k = 0; k < bits; k += 2)
      {
         if (i & pow_2[k])     j += pow_2[bits - k - 2];
         if (i & pow_2[k + 1]) 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;
  }
 }
}

我计算了这个函数的不同部分的循环，结果(可能很明显)，包含交换部分的最后一个for()循环是占循环大部分的部分。

您能看一下这段代码并给我一些提示或建议，说明我如何优化代码(如果可能的话)？

Answer 1

首先，我很抱歉。我完全误解了你的代码。

最终的目标是反转位对。这个任务非常类似于倒转位 (这个讨论确实鼓舞人心)，而且方法应该是相同的。

例如，第一种解决方案可以按照(对草率编码表示抱歉)的方式采用：

unsigned int radix4_reverse(unsigned int index)
{
    x = (((x & 0xcccccccc) >> 2) | ((x & 0x33333333) << 2));
    x = (((x & 0xf0f0f0f0) >> 4) | ((x & 0x0f0f0f0f) << 4));
    x = (((x & 0xff00ff00) >> 8) | ((x & 0x00ff00ff) << 8));
    x = (x >> 16) | (x << 16));
    return x >> (32 - bits);
}

(注意，省略了0xaaaaaaaa/0x55555555行，因为它将在一对中交换位)。

关于你的代码，

• 循环中的ifs是严重的性能杀手。
• 1 << k比pow_2[k]更可取。编译器比顺序内存获取有更好的优化顺序移位的机会。此外，它还放松了内存消耗。
• 您应该对位对进行操作(例如，i & (0x03 << k)而不是单个位)。
• |比+ (IMnsHO)干净。
• 我建议通过bits而不是N。