在无法使用函数 "Move" 的紧密循环中复制数据

Question

在我的一个软件项目中，我处于 "the need of" 紧密循环的最佳可能速度，该循环将索引数据从数组复制到同一数组的不同部分。

请考虑这个 freepascal 代码：

TYPE
  tIndex : ARRAY OF BYTE;
  tValues: ARRAY OF CARDINAL;

VAR
  Index : tIndex;
  Values: tValues;

CONST
  AnyCardinalSize = 65535;   

PROCEDURE InitializeArrays;
  BEGIN
    SetLength(Index, AnyCardinalSize);
    SetLength(Values,AnyCardinalSize);
  END;

PROCEDURE MoveData(CONST StartPosition,EndPosition,TargetPosition : CARDINAL);
  VAR {Note: TargetPosition is ALWAYS larger than EndPosition.}
    x, InsertOffset : CARDINAL;
  BEGIN
    InsertOffset := TargetPosition-StartPosition;
    FOR x := StartPosition TO EndPosition DO BEGIN
      Values[x+InsertOffset] := Values[Index[x]];
    END;
  END;

我的例程 MoveData 按预期工作，但我想研究一下用汇编代码替换它的可能性，以便在可能的情况下获得一点速度。

如果有人有关于如何用汇编语言完成此操作的示例，我将不胜感激。我在 Commodore 64 上做过一些 ASM，但那是很久以前的事了。

Answer 1

首先，在继续之前，我认为您必须确定以这种方式复制数据确实是瓶颈，并且没有可用的替代策略可以完全消除复制的需要。

如果你确定你需要有一个更快的复制例程，值得注意的是这些优化可能非常棘手并且取决于硬件以及内存 layout/alignment/data 组织和大小。如果没有丰富的经验或时间，您极不可能想出值得付出努力的卓越解决方案。

但是，优化内存 copy/move 例程可用。特别是，您可能想要查看 Agner Fog 的 asmlib，其中包含可以从编译代码调用的优化内存 copy/move 例程。

Answer 2

大多数优化来自hoisting 去掉表达式中代码的不变部分，然后执行强度降低以减少变体的数量。在使用汇编器之前学习优化 Pascal，即使只是因为反汇编的 Pascal 为您提供了进一步汇编器优化的框架，并且可以在测试汇编器代码时作为比较。

为了更好地识别常量部分，我们将n=0..endposition-startposition转换为基于0的for循环，表达式变为：

FOR n := 0 TO EndPosition-StartPosition  DO 
  BEGIN
    Values[n+InsertOffset+StartPosition ] := Values[Index[n+StartPosition]];
  END;

然后我们从循环不变的部分中分解出常量部分，引入指针语法。 T 是值数组的类型，PT 是指向它的指针。同样，TI是索引数组的类型，PTI是指向它的指针。

var StartValue : PT;
    StartIndex : PTI;  

StartValue:=@Values[InsertOffset+StartPosition]
StartIndex:=@Index[StartPosition];

FOR n := 0 TO EndPosition-StartPosition  DO 
    Startvalue[n]:=Values[StartIndex[n]]; // slightly depended on FPC dialect mode

现在，startvalue[n] 计算为 addressof(startvalue[0])+n*sizeof(T);但是，如果我们记住前一个循环中的地址值（在 Startvalue 中），那么差值变为 PT:=PT+sizeof(T);

我们将乘法转换为加法，但更重要的是，我们从表达式中删除了一个变量（而不是 startvalue 和 x（或 n），我们现在只需要记住 startvalue）。这称为strength reduction，我们也可以将其应用于索引数组：

FOR n := 0 TO EndPosition-StartPosition  DO 
  begin
    Startvalue^:=Values[StartIndex^];
    inc(StartValue);   // inc increments with element size and we declared as PT, so this means inc(startvalue,sizeof(T));
    inc(StartIndex);
  end;

不幸的是，这并没有完全消除对值数组的需要，但是这个循环在循环中使用了三个值（startvalue、startindex 和 values[]），而原来的有很多（index、values、x ，起始位置，插入偏移量）。此外，两者都有一些东西来识别迭代的结束。

在我们的例子中，可能是当 startvalue 到达数组末尾时，但为此我们必须使用一段时间：

 var StartValue,EndValue : PT;
     StartIndex : PTI;  

 StartValue:=@Values[InsertOffset+StartPosition]
 EndValue:=@Values[InsertOffset+EndPosition]
 StartIndex:=@Index[StartPosition];

 while (StartValue<=Endvalue) do
    begin
      Startvalue^:=Values[StartIndex^];
      inc(StartValue);   // inc increments with element size and we declared as PT, so this means inc(pbyte(startvalue),sizeof(T));
      inc(StartIndex);
    end;

理论上编译器可以进行这些优化。 C 编译器通常会在正确指示时执行此操作，但大多数 Pascal 编译器尚未达到该级别。然而，他们没有理由不能。

开始汇编程序的最佳方式是首先大量优化 Pascal 并尝试理解生成的代码。

多年来我一直在 Delphi 中进行图像分析，转而使用汇编程序只是为了手动纠正编译器没有得到它（例如，不提升或选择次优不变量），或者在注册时分配出现问题。

唯一的其他情况是 SSE 中的整幅图像操作，但这不适用于此处。

在无法使用函数 "Move" 的紧密循环中复制数据

Copying of data in a tight loop where the function "Move" can not be used

assembly

x86

freepascal