在内存中移动字节，而不替换现有字节，也不使用大bu

Question

如何在保存现有数据和使用与CPU寄存器大小匹配的缓冲区的情况下，将内存中的一些字节从一个位置移动到另一个位置？

更精确的公式：

我正在用FreePascal编写一些代码（为了好玩）。现在我需要一个函数，它能把一些字节移到另一个地方。内置函数系统。移动这样做很粗鲁-当移动和重写数据时，它不关心在目标地址中保存数据。当然，我可以使用缓冲区来保存数据，然后使用移动函数从缓冲区恢复数据。但是当移动大量数据时，需要很大的缓冲区。我想避免它，并使用与CPU寄存器大小匹配的缓冲区。在

我需要的例子是假设我们总是从较低的位置移动到较高的位置（Pos1<；Pos2）。 将3个字节从位置2移到位置7：

我可以使用字节大小的缓冲区（→表示写入，↔ 平均交换值）：

    7 → Buffer
    2 → 7
    Buffer ↔ 4
    Buffer ↔ 9
    Buffer ↔ 6
    Buffer ↔ 3
    Buffer ↔ 8
    Buffer ↔ 5
    Buffer ↔ 2

更大的例子：将3个字节从位置3移到位置15

现在的算法如下所示：

^{pr2}$

在前面的例子中有一个大步骤-我们使用一个操作序列移动所有的步骤，但是这里有3个大步骤。在

以我不理解的方式——这样大的步骤的数量似乎等于（Pos2-Pos1）的GCD（最大公约数）和长度。在

我编写了一些python代码，似乎为给定的移动请求提供了正确的操作序列

# -*- coding: utf-8 -*-
def func1(Pos1, Pos2, Length):
    Delta = Pos2 - Pos1;
    j = Pos2;
    p1 = Pos1;
    p2 = Pos2;
    Step = 0;
    SubStep = 0;
    while (Step < Delta + Length):
        Step = Step + 1;
        SubStep = SubStep + 1;
        print(" %d → Buffer"%j);
        print(" %d → %d"%(p1,j));
        while 1:
            Step = Step + 1;
            if (j + Delta < Pos2 + Length):
                j = j + Delta;
            else:
                j = j - Length;
            print(" Buffer ↔ %d"%(j));
            if (j == p1):
                p1 = p1 + 1;
                p2 = p2 + 1;
                j = p2;
                break;
    return SubStep;

假设这是正确的，有一个巨大的问题——这个算法处理的字节操作速度很慢，而且由于我有amd64——我想让它在每次操作中使用8字节。在

我要怎么做？在

Answer 1

我自己的问题中所描述的问题似乎可以用两种简单的方法来解决（看问题图片）：

1）你有橙色和绿色的块，你需要交换它们-把橙色块放在缓冲区（因为它比较小），移动绿色块，然后他们从缓冲区取橙色块。在

取舍：简单，明显，快速和小的块

问题：如果橙色和绿色块的大小相同-您将需要最大的缓冲区，并且可能需要大量内存

2）使用方法。您将能够使用不大于两个块大小（橙色和绿色）的GCD的缓冲区。所以，最好使用两个缓冲区：一个是CPU寄存器大小（我的amd64是8个字节）和一个字节大小的缓冲区。因此，首先使用（GCD div 8）（对于64位系统）步骤移动（或移位）寄存器大小的缓冲区，然后用字节大小的缓冲区结束。在

权衡：不需要大缓冲

问题：如果两个块大小的GCD小于寄存器大小-我们会变得非常慢（因为在这种情况下只有字节大小的移位操作可用）。一点也不明显。在

我做了两个函数来测试这两个解决方案

// License: LGPL
//──────────────────────────────────────────────────────────────────────────────
procedure MemoryMove(const Pos1, Pos2: Pointer; const Len: PtrUInt);
  var
    // Memory addresses
    MemPos1:     PtrUInt;  // bottom block address
    MemPos2:     PtrUInt;  // top block address
    CurPos:      PtrUInt;  // current position
    CurPos1:     PtrUInt;  // current position 1
    CurPos2:     PtrUInt;  // current position 2
    CurPosLimit: PtrUInt;
    // Memory sizes
    MemSize1:    PtrUInt;  // size of bottom memory block
    MemSize2:    PtrUInt;  // size of top memory block
    // Counters
    BufSizeReq:  PtrUInt;  // buffer size required
    // Counters for buffers
    BufCount:    PtrUInt;
    // Mini buffers
    BufReg:      PtrUInt;  // buffer match pointer (registers) size
    BufByte:     Int8U;    // byte sized buffer
    // Temporary variables
    TempReg:     PtrUInt;
    TempByte:    Int8U;
    // Variables for iterations
    Count: IntU;
  begin
    // This code is not obvious, see manual or other documentation
    // http://stackoverflow.com/questions/18539341/move-bytes-in-memory-without-replacing-existing-bytes-and-without-big-buffer

    // Check parameters
    // for being out of memory bounds
    if (PtrUInt(Pos1) > High(PtrUInt) - Len) OR (PtrUInt(Pos2) > High(PtrUInt) - Len) then
    begin
      raise Exception.Create(rsMemOutOfBounds);
    end;
    // Does it make sense to do anything?
    if (Pos1 = Pos2) OR (Len = 0) then
    begin
      Exit;
    end;

    // Move operation interpreted as cycle shifting from low to high address

    // Convert parameters of Move operation to cycle shifting
    if Pos1 < Pos2 then
    begin
      MemPos1  := PtrUInt(Pos1);
      MemPos2  := PtrUInt(Pos2);
      MemSize1 := Len;
      MemSize2 := PtrUInt(Pos2) - PtrUInt(Pos1);
    end
    else
    begin
      MemPos1  := PtrUInt(Pos2);
      MemPos2  := PtrUInt(Pos2) + Len;
      MemSize1 := PtrUInt(Pos1) - PtrUInt(Pos2);
      MemSize2 := Len;
    end;

    // Buffer can't be bigger than GCD of two block sizes
    BufSizeReq := GCD(MemSize1, MemSize2);

    // Prepare some variables
    CurPos1  := MemPos1;
    CurPos2  := MemPos2;
    BufCount := 0;

    // Shift with different buffer sizes
    // Start with biggest, end with smallest

    // Using pointer-size buffer

    // Calculate amount of mini buffers needed to fit required buffer size
    if SizeOf(Pointer) >= SizeOf(BufReg) then
    begin
      BufCount   := BufSizeReq div SizeOf(BufReg);
      BufSizeReq := BufSizeReq - BufCount * SizeOf(BufReg);
    end;
    // Shift data with current buffer size and count
    Count := 1;
    while Count <= BufCount do
    begin
      // First step
      BufReg := PtrUInt(Pointer(CurPos2)^);
      PtrUInt(Pointer(CurPos2)^) := PtrUInt(Pointer(CurPos1)^);
      // Next steps done in loop
      CurPos      := CurPos2;
      CurPosLimit := CurPos2 - MemSize2 + MemSize1;
      repeat
        // Calculate where current element from buffer should be placed
        if (CurPos < CurPosLimit) then
        begin
          CurPos := CurPos + MemSize2;
        end
        else
        begin
          CurPos := CurPos - MemSize1;
        end;
        // Exchange value from buffer with current memory position
        TempReg := BufReg;
        BufReg  := PtrUInt(Pointer(CurPos)^);
        PtrUInt(Pointer(CurPos)^) := TempReg;
      until CurPos = CurPos1; // very bad condition - one mistake and loop will be infinite
      CurPos1 := CurPos1 + SizeOf(BufReg);
      CurPos2 := CurPos2 + SizeOf(BufReg);
      Count   := Count + 1;
    end;

    // NOTE: below code is copy-paste+edit of code above
    // It's very bad for readability, but good for speed

    // Using one-byte-size buffer
    // This **IS** necessarily

    // Calculate amount of mini buffers needed to fit required buffer size
    BufCount   := BufSizeReq;
    // Shift data with current buffer size and count
    Count := 1;
    while Count <= BufCount do
    begin
      // First step
      BufByte := Int8U(Pointer(CurPos2)^);
      Int8U(Pointer(CurPos2)^) := Int8U(Pointer(CurPos1)^);
      // Next steps done in loop
      CurPos      := CurPos2;
      CurPosLimit := CurPos2 - MemSize2 + MemSize1;
      repeat
        // Calculate where current element from buffer should be placed
        if (CurPos < CurPosLimit) then
        begin
          CurPos := CurPos + MemSize2;
        end
        else
        begin
          CurPos := CurPos - MemSize1;
        end;
        // Exchange value from buffer with current memory position
        TempByte := BufByte;
        BufByte  := Int8U(Pointer(CurPos)^);
        Int8U(Pointer(CurPos)^) := TempByte;
      until CurPos = CurPos1; // very bad condition - one mistake and loop will be infinite
      CurPos1 := CurPos1 + 1;
      CurPos2 := CurPos2 + 1;
      Count   := Count + 1;
    end;
  end;
//──────────────────────────────────────────────────────────────────────────────
procedure MemoryMoveBuf(const Pos1, Pos2: Pointer; const Len: PtrUInt);
  var
    Buf: Int8UAD; // buffer
    MemPos11, MemPos12, MemPos21, MemPos22: PtrUInt;
    MemLen1, MemLen2: PtrUInt;
  begin
    // Check parameters
    // for being out of memory bounds
    if (PtrUInt(Pos1) > High(PtrUInt) - Len) OR (PtrUInt(Pos2) > High(PtrUInt) - Len) then
    begin
      raise Exception.Create(rsMemOutOfBounds);
    end;
    // Does it make sense to do anything?
    if (Pos1 = Pos2) OR (Len = 0) then
    begin
      Exit;
    end;
    // There are two memory blocks
    // First is given in parameters
    MemPos11 := PtrUInt(Pos1);
    MemPos12 := PtrUInt(Pos2);
    MemLen1  := Len;
    // The second one must be calculated
    if Pos2 > Pos1 then
    begin
      MemPos21 := PtrUInt(Pos1) + Len;
      MemPos22 := PtrUInt(Pos1);
      MemLen2  := PtrUInt(Pos2) - PtrUInt(Pos1);
    end
    else
    begin
      MemPos21 := PtrUInt(Pos2);
      MemPos22 := PtrUInt(Pos2) + Len;
      MemLen2  := PtrUInt(Pos1) - PtrUInt(Pos2);
    end;
    // Moving
    try
      // Use smaller buffer
      if MemLen1 <= MemLen2 then
      begin
        SetLength(Buf, MemLen1);
        system.Move(Pointer(MemPos11)^, Pointer(Buf)^, MemLen1);
        system.Move(Pointer(MemPos21)^, Pointer(MemPos22)^, MemLen2);
        system.Move(Pointer(Buf)^, Pointer(MemPos12)^, MemLen1);
      end
      else
      begin
        SetLength(Buf, MemLen2);
        system.Move(Pointer(MemPos21)^, Pointer(Buf)^, MemLen2);
        system.Move(Pointer(MemPos11)^, Pointer(MemPos12)^, MemLen1);
        system.Move(Pointer(Buf)^, Pointer(MemPos22)^, MemLen2);
      end;
    finally
      SetLength(Buf, 0);
    end;
  end;
//──────────────────────────────────────────────────────────────────────────────

对于测试，我创建了一个缓冲区，将下半部分移动到上半部分（交换缓冲区数据的一半）-这是解决方案1的最坏情况。在

我用相同的缓冲区大小重复每个移动测试以得到平均结果。在

所以我从512字节的缓冲区开始，将256字节从0位移到256位，重复移动1048576次，然后使缓冲区变大2倍，减少重复2次，…，以536870912字节的缓冲区结束，只重复1次（总共21次大的迭代）

这样可以获得良好的GCD（GCD>；寄存器大小）。为了模拟解决方案2的最坏情况，当（GCD=1）时，我只将移动长度减少1，所以在第一次迭代中，它将255个字节从位置0移动到位置256。在

我很失望-我最喜欢的解决方案2的自写函数很慢，即使使用（GCD>；8），当（GCD=1）时，它也非常慢。在

Fig. 1 此图显示结果。OX-缓冲区大小，OY-时间（更少=更好）。实心黑圆圈和粗线-解决方案1。底部白色圆圈和细线是GCD良好（GCD>；8，最佳情况）的解决方案2，顶行-GCD差（GCD=1，最坏情况）。灰色填充-解决方案2的中间部分。在

说明：解决方案1使用汇编程序中由专业程序员编写的“Move”函数，以性能取胜很难。在

几周后，我发现编译器并没有给出最佳的汇编代码。通过一些额外的优化（-O3-或）结果会变得更好一些 Fig. 2

结论： 我已经测试了这两个函数，得到了相同的结果，但当我做那个图形时却没有，所以它可能都是错误的。在

当你移动的内存块很小时，解决方案1似乎很好。但是它有一些瓶颈，并且不是很线性（因此很难预测执行时间）。在

当您被限制分配更多内存时，解决方案2似乎适合移动大量内存。它是一个非常线性的，并且可以通过执行时间来预测。但可能非常慢。在