Delphi优化IndexOf功能

Question

有人可以帮我加速我的Delphi函数在不使用二进制搜索的情况下在字节数组中查找值.

我把这个函数称为数千次,是否可以用汇编来优化它？

非常感谢.

function IndexOf(const List: TArray< Byte >; const Value: byte): integer;
var
  I: integer;
begin
  for I := Low( List ) to High( List ) do begin
   if List[ I ] = Value then
    Exit ( I );
  end;
  Result := -1;
end;

数组的长度约为15项.

Answer 1

好吧,让我们想一想.首先,请编辑此行:

For I := Low( List ) to High( List ) do

(你最后忘了"做").当我们在没有优化的情况下编译它时,这是这个循环的汇编代码:

Unit1.pas.29: If List [I] = Value then
005C5E7A 8B45FC           mov eax,[ebp-$04]
005C5E7D 8B55F0           mov edx,[ebp-$10]
005C5E80 8A0410           mov al,[eax+edx]
005C5E83 3A45FB           cmp al,[ebp-$05]
005C5E86 7508             jnz $005c5e90
Unit1.pas.30: Exit (I);
005C5E88 8B45F0           mov eax,[ebp-$10]
005C5E8B 8945F4           mov [ebp-$0c],eax
005C5E8E EB0F             jmp $005c5e9f
005C5E90 FF45F0           inc dword ptr [ebp-$10]
Unit1.pas.28: For I := Low (List) to High (List) do
005C5E93 FF4DEC           dec dword ptr [ebp-$14]
005C5E96 75E2             jnz $005c5e7a

这段代码远非最优:局部变量i实际上是局部变量,即:它存储在RAM中,堆栈中(你可以通过[ebp- $ 10]地址看到它,ebp是堆栈指针).

所以在每次新的迭代中我们都会看到如何将数组的地址加载到eax寄存器(mov eax,[ebp- $ 04]),然后我们将i从堆栈加载到edx寄存器(mov edx,[ebp- $ 10]),然后我们在最小负载List [i]到al寄存器中,它是eax的低字节(mov al,[eax + edx]),之后将它与从存储器再次从参数中取出的参数'Value'进行比较!

这种实现非常缓慢.

但是让我们最后改变优化!它在项目选项 - >编译 - >代码生成中完成.我们来看看新代码:

Unit1.pas.29: If List [I] = Value then
005C5E5A 3A1408           cmp dl,[eax+ecx]
005C5E5D 7504             jnz $005c5e63
Unit1.pas.30: Exit (I);
005C5E5F 8BC1             mov eax,ecx
005C5E61 5E               pop esi
005C5E62 C3               ret 
005C5E63 41               inc ecx
Unit1.pas.28: For I := Low (List) to High (List) do
005C5E64 4E               dec esi
005C5E65 75F3             jnz $005c5e5a

现在只有4行代码反复重复.

值存储在dl寄存器(edx寄存器的低字节)内,数组的第0个元素的地址存储在eax寄存器中,i存储在ecx寄存器中.

所以'if List [i] = Value'这一行转换成只有1个装配线:

005C5E5A 3A1408           cmp dl,[eax+ecx]

下一行是条件跳转,之后的3行只执行一次或从不(如果条件为真),最后有i的增量,循环变量的减少(它更容易与零比较,然后与其他任何东西)

所以,我们几乎无法做到哪个Delphi编译器没有优化器!

如果您的程序允许,您可以尝试反转搜索方向,从最后一个元素到第一个元素:

For I := High( List ) downto Low( List ) do

这样编译器很乐意将i与零进行比较以表明我们检查了所有内容(此操作是免费的:当我们减少i并且为零时,CPU零标志打开!)

但在这样的实现中,行为可能会有所不同:如果你有几个条目=值,你将得到的不是第一个,而是最后一个!

另一个非常简单的事情是将此IndexOf函数声明为内联:这样您可能在此处没有函数调用:此代码将插入您调用它的每个位置.函数调用是相当慢的事情.

在Knuth中也有一些疯狂的方法如何尽可能快地在简单数组中进行搜索,他引入了数组的"虚拟"最后一个元素,它等于你的"价值",这样你就不必检查边界了(它总会如此)在超出范围之前找到一些东西),所以在循环中只有1个条件而不是2.另一个方法是"展开"循环:你在循环内写下2或3次或更多次迭代,因此每个循环的跳转较少检查,但这有更多的缺点:它只对相当大的数组有益,而对于具有1或2个元素的数组可能会更慢.

正如其他人所说:最大的改进是了解你存储的数据类型:它经常变化或长时间保持不变,你是否寻找随机元素或者有一些"领导者"最受关注.这些元素必须与您放置它们的顺序相同,或者允许根据您的意愿重新排列它们吗？然后您可以相应地选择数据结构.如果你一直在寻找1或2个相同的条目并且它们可以重新排列,一个简单的"前移"方法就会很棒:你不只是返回索引而是首先将元素移动到第一个位置,所以它将在下次很快找到.

Answer 2

如果您的阵列很长,您可以使用x86内置的字符串扫描REP SCAS.
它采用微码编码,启动时间适中,但在CPU中进行了大量优化,并且在给定足够长的数据结构(> = 100字节)的情况下运行速度很快.
事实上,在现代CPU上,它经常优于非常聪明的RISC代码.

如果您的数组很短,那么这个例程的优化数量没有任何帮助,因为那时你的问题是代码中没有显示的问题,所以没有答案我可以给你.

请参阅:http://docwiki.embarcadero.com/RADStudio/Tokyo/en/Internal_Data_Formats_(Delphi)

function IndexOf({$ifndef RunInSeperateThread} const {$endif} List: TArray<byte>; const Value: byte): integer;
//Lock the array if you run this in a separate thread.
{$ifdef CPUX64}
asm
  //RCX = List
  //DL = byte.
  mov r8,[rcx-8]        //3 - get the length ASAP.
  push rdi              //0 - hidden in mov r,m
  mov eax,edx           //0 - rename
  mov rdi,rcx           //0 - rename
  mov rcx,r8            //0 - rename
  mov rdx,r8            //0 - remember the length
  //8 cycles setup
  repne scasb           //2n - repeat until byte found.
  pop rdi               //1 
  neg rcx               //0
  lea rax,[rdx+rcx]     //1 result = length - bytes left.
end;
{$ENDIF}
{$ifdef CPUX86}
asm
  //EAX = List
  //DL = byte.
  push edi
  mov edi,eax
  mov ecx,[eax-4]        //get the length
  mov eax,edx
  mov edx,ecx            //remember the length
  repne scasb            //repeat until byte found.
  pop edi
  neg ecx
  lea eax,[edx+ecx]      //result = length - bytes left.
end;     

计时
在我的笔记本电脑上使用1KB的数组和最后的目标字节,这给出了以下时间(使用100.0000运行的最短时间)

Code                           | CPU cycles
                               | Len=1024 | Len=16      
-------------------------------+----------+---------
Your code optimizations off    | 5775     | 146
Your code optimizations on     | 4540     |  93
X86 my code                    | 2726     |  60
X64 my code                    | 2733     |  69

加速是可以的(ish),但几乎不值得努力.

如果您的阵列很短,那么此代码对您没有帮助,您将不得不求助于更好的其他选项来优化您的代码.

使用二进制搜索时可以加速
二进制搜索是O(log n)操作,而O(n)用于天真搜索.
使用相同的数组,这将在log2(1024)*每次搜索的CPU周期= 10*20 +/- 200个周期中找到您的数据.比我的优化代码快10倍以上.