优化NEON XOR实现方式

Question

尝试对一个巨大的uint32数组进行异或操作时，我决定使用NEON协处理器。我实现了两个C版本：

版本1：

uint32_t xor_array_ver_1(uint32_t *array, int size)
{
    uint32x2_t acc = vmov_n_u32(0);
    uint32_t acc1 = 0;
    for (; size != 0; size -= 2) {
        uint32x2_t vec;
        vec = vld1_u32(array);
        array += 2;
        acc = veor_u32(acc, vec);
    }
    acc1 = vget_lane_u32(acc,0) ^ vget_lane_u32(acc,1);
    return acc1;
}

版本2：

uint32_t xor_array_ver_2(uint32_t *array, int size)
{
    uint32x4_t acc = vmovq_n_u32(0);
    uint32_t acc1 = 0;

    for (; size != 0; size -= 4) {
        uint32x4_t vec;
        vec = vld1q_u32(array);
        array += 4;
        acc = veorq_u32(acc, vec);
    }

    acc1 ^= vgetq_lane_u32(acc,0);
    acc1 ^= vgetq_lane_u32(acc,1);
    acc1 ^= vgetq_lane_u32(acc,2);
    acc1 ^= vgetq_lane_u32(acc,3);

    return acc1;
}

将上述两个版本与传统的异或实现进行比较：

for (i=0; i<arr_size; i++)
        val ^= my_array[i];

我发现了2个问题：

1. 版本1的性能与原来相同。
2. 版本2比原来好30%左右。

---

1. 如果我将my_array 声明为uint32_t my_array[BIG_LENGTH];，那我可不可以重写它以使其更好？
2. 有没有一种非NEON的方式可以改进常规异或代码的性能？展开循环并没有任何改进。

- 0x90

---

你尝试过增加数据的对齐方式吗？例如，将其与uint32x4_t数组联合起来？ - technosaurus

@technosaurus 是的，它是对齐的。假设数据是对齐的。 - 0x90

将数据对齐到int并不相同。如果将数据对齐到128位而不是32位，您可以减少缓存未命中并使用对齐加载。如果只对齐到int，则可能跨越缓存行执行非对齐加载……这会导致双倍的性能损失。 - technosaurus

@technosaurus 它对PAGE_SIZE进行了对齐。不过你的评论总体上是正确的。 - 0x90

Answer 1

很可能这将受到内存带宽的限制-一旦您饱和了可用的DRAM带宽(只需每次加载一次ALU操作即可轻松完成)，您将无法从优化中获得进一步的好处。

如果可能的话，请尝试将XOR与相同数据上的另一个操作结合使用-这样可以分摊缓存未命中的成本。

- Paul R

---

确实，这将受到带宽限制，但是neon后端具有更好的内存端口。例如，如果您在寻找智能手机的memcpy实现，您可能会看到它们尝试通过neon单元处理64个块。 - auselen

你能解释一下这一行代码吗？“如果可能的话，尝试将XOR与相同数据上的另一个操作组合使用-这样你就可以分摊缓存丢失的成本。” 你的意思是除了执行 eor 操作之外，还要对数据进行虚拟操作吗?! - 0x90

我不了解你的具体应用程序，但如果对数据进行了多个操作，例如假设您有两个操作：一个操作是从两个缓冲区中减去，然后另一个操作是异或前一个操作的结果缓冲区，则如果您将其作为两次数据遍历执行，则需要支付两倍的负载（和存储）成本，而如果您在一次遍历中完成所有操作，则每个元素只需支付一次负载/存储成本。当然，这可能不适用于您的情况，但这是代码优化的重要通用原则。 - Paul R

Answer 2

一个没有任何代码片段的冗长回答。

硬件限制

首先你应该问自己想要什么？你想写出最快的代码吗？你如何验证？从例如编写一些测试来开始，了解你的硬件可以实现什么。正如其他人所指出的，这将主要受到内存带宽限制，但是你需要知道你的内存接口有多快。了解你的平台的L1、L2和RAM容量/性能特征，然后你就会知道对于不同的缓冲区大小你最多可以期望什么。

编译器

你是否使用最新的编译器？接下来的问题是，你是否充分利用了可用的工具？除非你告诉它们，否则大多数编译器不会积极地尝试优化你的代码。你是否为你的最大收益进行了配置？你是否启用了全面优化（gcc：-O3）、矢量化（gcc：-ftree-vectorize -ftree-vectorizer-verbose=1）？你是否为你的平台设置了正确的配置标志（-mcpu -mfpu）？

你是否验证了编译器生成的目标代码？对于这样一个简单的循环，这将非常容易，并且可以帮助你尝试许多配置选项并检查生成的代码。

调整

你是否检查使用受限指针是否提高了性能？

关于对齐信息怎么样？（例如，在你的内嵌示例中你没有提到，但是它们期望大小为2或4的倍数，并且当然在使用quad寄存器时可以创建30%的改进。）

还有什么关于尝试缓存行大小的对齐？

硬件能力

你知道你的硬件能力吗？例如，Cortex-A9被介绍为“乱序推测问题超标量”。你能利用双重问题能力吗？

因此，答案介于“这取决于”和“你需要实验”之间。

- auselen

---

很棒的答案，您能否解释一下在硬件能力方面，“您能否利用双重问题能力”是什么意思？ - 0x90

我在arm手册中没有看到使用vld1q_u32加载数据的最佳对齐方式。 - 0x90

@0x90 用于vld对齐 http://infocenter.arm.com/help/topic/com.arm.doc.dui0204j/CIHCCEBB.html。我认为随着值的增加会变得更好，也就是说16字节对齐比8字节更好。 - auselen

@0x90 双发射想法：使用两个不同的寄存器（ARM）对偶数和奇数索引数据进行异或，然后在最后将它们异或起来。看看这是否与使用单个寄存器对所有数据进行异或有所不同。 - auselen

+1。不过，我可以补充一点，GCC烂到了无以复加的地步。即使是最新版本（4.7.3），也很糟糕，人们不应该浪费时间去优化他们的代码。-O3选项几乎总是导致代码过大、运行速度变慢。它就像一头驴子。 - Jake 'Alquimista' LEE

Answer 3

众所周知，gcc上的neon内在函数非常糟糕。不确定是否有改进，但使用汇编完成相同任务应该比纯c提高30%以上。首先，您可能需要展开内部循环。将内在函数转换为适当的汇编的简单方法是使用armcc（来自arm的编译器），它可以处理内在函数。

因此，首先尝试展开您的纯c版本（伪代码）：

for (i=arr_size; i<arr_size; i -= 4)
{
    val1 ^= my_array[0];
    val2 ^= my_array[1];
    val1 ^= my_array[2];
    val2 ^= my_array[3];
    my_array += 4;
}

使用 NEON 进行类似操作应该会得到更好的结果。最终，你应该转向 NEON 汇编语言，它非常简单（个人认为比内嵌函数更容易编写）。

这是关于 NEON 汇编语言的建议（未经测试，需要自己组装）。

//data has to be suitably aligned (it has to be 8 or 16 byte aligned, not sure).
//dataSize in bytes has to be multiple of 64 and has to be at least 128.
//function does xor of uint32_t values and returns the result.
unsigned xor_array_64(const void *data, int dataSize);

xor_array_64:
      vldm r0!,{d0-d7}
      subs r1,r1,#0x40
0:
      pld [r0, #0xC0]
      vldm r0!,{d16-d23}
      veor q0, q0, q8
      veor q1, q1, q9
      veor q2, q2, q10
      veor q3, q3, q11
      subs r1,r1,#0x40
      bge 0b

      veor q0, q0, q1
      veor q2, q2, q3
      veor q0, q0, q2
      veor d0, d0, d1

      vtrn.32 d1, d0
      veor d0, d0, d1

      vmov r0, s0
      bx lr

- Pavel P

---

我认为你的情况太简单了，不需要编写NEON代码。请在arm.com上查看memcpy实现文章。最优化的版本比C语言中最简单的循环快50％。正如所说，它受到内存访问的限制，因为数据没有太多变化。如果您需要对每个字节/字执行多个操作，使用NEON将是有意义的。做异或运算几乎等于对数据什么都没做 :) - Pavel P

@0x90 它真的需要超过一秒钟吗？ - auselen

@auselen 是的，那很尴尬，200MB需要8秒钟。 - 0x90

@0x90 哪种CPU / SoC？现代系统可达6GB/s。 - auselen

@auselen Cortex A-7，是一种用于开发的SoC芯片。 - 0x90

Answer 4

我不写ARM，对NEON也一窍不通，但我有以下想法。这取决于ARM NEON是否是流水线架构，我不确定它是否是...如果Paul R正确地指出了您的内存带宽已经饱和，那么这可能没有什么好处，但如果您稍微按照以下方式重组代码……

uint32_t xor_array_ver_2(uint32_t *array, int size)
{
  // Caveat:  'size' must be a positive multiple of 4, otherwise this
  //          code will loop for a very long time... and almost certainly
  //          segfault (or whatever term your system uses).

  uint32x4_t acc = vmovq_n_u32(0);
  uint32x4_t next_vec = vld1q_u32(array);
  uint32_t acc1 = 0;

  for (size-=4, array+=4; size != 0; size-=4) {
     uint32x4_t vec = next_vec;
     array += 4;
     next_vec = vld1q_u32(array);
     acc = veorq_u32(acc, vec);
  }
  acc = veorq_u32(acc, next_vec);

  acc1 ^= vgetq_lane_u32(acc,0);
  acc1 ^= vgetq_lane_u32(acc,1);
  acc1 ^= vgetq_lane_u32(acc,2);
  acc1 ^= vgetq_lane_u32(acc,3);

  return acc1;
}

....旨在开始加载下一个向量元素，以便在以下循环中需要时立即使用。

你可以尝试另一种微小的变化：

uint32_t xor_array_ver_2(uint32_t *array, int size)
{
  // Caveat:  'size' must be a positive multiple of 4, otherwise this
  //          code will loop for a very long time... and almost certainly
  //          segfault (or whatever term your system uses).

  uint32x4_t acc = vmovq_n_u32(0);
  uint32x4_t next_vec = vld1q_u32(&array[size-4]);
  uint32_t acc1 = 0;

  for (size-=8; size>=0; size-=4) {
     uint32x4_t vec = next_vec;
     next_vec = vld1q_u32(&array[size]);
     acc = veorq_u32(acc, vec);
  }
  acc = veorq_u32(acc, next_vec);

  acc1 ^= vgetq_lane_u32(acc,0);
  acc1 ^= vgetq_lane_u32(acc,1);
  acc1 ^= vgetq_lane_u32(acc,2);
  acc1 ^= vgetq_lane_u32(acc,3);

  return acc1;
}

- phonetagger

---

@0x90 - 如果您尝试了我上面的建议，我会很感兴趣知道结果。 - phonetagger