如何快速将 6 字节无符号整数复制到内存区域?

How to quickly replicate a 6-byte unsigned integer into a memory region?

我需要将一个 6 字节的整数值复制到一个内存区域中,从它的开头开始并尽可能快地复制。如果硬件支持这样的操作,我想使用它(我现在在 x64 处理器上,编译器是 GCC 4.6.3)。

memset不适合这项工作,因为它只能复制字节。 std::fill 也不好,因为我什至无法定义迭代器,在内存区域中的 6 个字节宽度位置之间跳转。

所以,我想要一个函数:

void myMemset(void* ptr, uint64_t value, uint8_t width, size_t num)

这看起来像 memset,但还有一个额外的参数 width 来定义要从 value 复制多少 字节 。如果这样的东西能用C++表达就更好了

我已经知道明显的 myMemset 实现,它会在循环中调用 memcpy,最后一个参数(要复制的字节数)等于 width。我还知道,我可以定义一个大小为 6 * 8 = 48 字节的临时内存区域,用 6 字节整数填充它,然后 memcpy 到目标区域。

我们可以做得更好吗?

一些事情 @Mark Ransom 评论:

复制6个字节,然后复制6、12、24、48、96等

void memcpy6(void *dest, const void *src, size_t n /* number of 6 byte blocks */) {
  if (n-- == 0) {
    return;
  }
  memcpy(dest, src, 6);
  size_t width = 1;
  while (n >= width) {
    memcpy(&((char *) dest)[width * 6], dest, width * 6);
    n -= width;
    width <<= 1; // double w
  }
  if (n > 0) {
    memcpy(&((char *) dest)[width * 6], dest, n * 6);
  }
}

优化:将 nwidth 缩放 6。

[编辑]
更正目的地 @SchighSchagh
添加演员 (char *)

如果您的 Num 足够大,您可以尝试使用一次处理 32 个字节的 AVX 矢量指令 (_mm256_load_si256/_mm256_store_si256 或其未对齐的变体)。 =14=]

由于 32 不是 6 的倍数,您必须首先使用短 memcpy 或 32/64 位移动将 6 字节模式复制 16 次。

ABCDEF
ABCDEF|ABCDEF
ABCD EFAB CDEF|ABCD EFAB CDEF
ABCDEFAB CDEFABCD EFABCDEF|ABCDEFAB CDEFABCD EFABCDE
ABCDEFABCDEFABCD EFABCDEFABCDEFAB CDEFABCDEFABCDEF|ABCDEFABCDEFABCD EFABCDEFABCDEFAB CDEFABCDEFABCDEF

您还将以一个简短的 memcpy 结束。

尝试使用 __movsq 内部函数(仅限 x64;在汇编中,rep movsq)一次移动 8 个字节,使用合适的重复因子,并将目标地址设置在资源。检查是否巧妙地处理了重叠地址。

确定 CPU 支持的最有效写入大小;然后找到可以同时被 6 和写入大小均除的最小数字,并将其称为 "block size".

现在将内存区域分成该大小的块。每个块都是相同的,所有写入都将正确对齐(假设内存区域本身正确对齐)。

例如,如果 CPU 支持的最有效写入大小是 4 字节(例如 ancient 80486),那么 "size of block" 将是 12 字节。您将设置 3 个通用寄存器并在每个块中存储 3 个。

再举一个例子,如果 CPU 支持的最有效写入大小是 16 字节(例如 SSE),那么 "size of block" 将是 48 字节。您将设置 3 个 SSE 寄存器并在每个块中存储 3 个。

此外,我建议将内存区域的大小四舍五入以确保它是块大小的倍数(带有一些 "not strictly necessary" 填充)。一些不必要的写入比填充 "partial block".

的代码更便宜

第二个最有效的方法可能是使用内存副本(但不是memcpy()memmove())。在这种情况下,您将写入最初的 6 个字节(或 12 个字节或 48 个字节或其他字节),然后从(例如)&area[0] 复制到 &area[6](从最低到最高工作)直到您到达结尾。对于此 memmove() 将不起作用,因为它会注意到该区域是重叠的,而是从最高到最低工作;并且 memcpy() 将不起作用,因为它假定源和目标不重叠;所以你必须创建自己的内存副本来适应。这样做的主要问题是内存访问次数加倍 - "reading and writing" 比 "writing alone".

一次写入 8 个字节。

在 64 位机器上,生成的代码当然可以很好地运行 8 字节写入。在处理了一些设置问题之后,在一个紧密的循环中,每次写入大约 num 次写入 8 个字节。假设适用 - 请参阅代码。

// assume little endian
void myMemset(void* ptr, uint64_t value, uint8_t width, size_t num) {
  assert(width > 0 && width <= 8);

  uint64_t *ptr64 = (uint64_t *) ptr;
  // # to stop early to prevent writing past array end
  static const unsigned stop_early[8 + 1] = { 0, 8, 3, 2, 1, 1, 1, 1, 0 };
  size_t se = stop_early[width];
  if (num > se) {
    num -= se;

    // assume no bus-fault with 64-bit write @ `ptr64, ptr64+1, ... ptr64+7`
    while (num > 0) { // tight loop
      num--;
      *ptr64 = value;
      ptr64 = (uint64_t *) ((char *) ptr64 + width);
    }

    ptr = ptr64;
    num = se;
  }
  // Cope with last few writes
  while (num-- > 0) {
    memcpy(ptr, &value, width);
    ptr = (char *) ptr + width;
  }
}

进一步优化包括一次写入 2 个块 width == 3 or 4width == 2 时一次写入 4 个块,width == 1 时一次写入 8 个块。