Delphi:有哪些更快的纯 Pascal 方法可以查找 Unicode 字符串中字符的位置？

Question

背景

稍后添加

我制作了一个纯 Pascal 函数来查找 Unicode 字符串中字符的位置，如下所示:

function CharPosEx(const chChr: Char; const sStr: string;
    const iOffset: Integer=1): Integer;
var
  PStr   : PChar;
  PRunIdx: PChar;
  PEndIdx: PChar;
  iLenStr: Integer;

begin
  Result := 0;
  iLenStr := Length(sStr);
  if (iLenStr = 0) or (iOffset <= 0) or (iOffset > iLenStr) then Exit;

  PStr := Pointer(sStr);
  PEndIdx := @PStr[iLenStr - 1];
  PRunIdx := @PStr[iOffset - 1];

  repeat
    if PRunIdx^ = chChr then begin
      Result := PRunIdx - PStr + 1;
      Exit;
    end;
    Inc(PRunIdx);
  until PRunIdx > PEndIdx;
end;

我决定不使用内置的 StrUtils.PosEx() 因为我想基于 的优化纯 Pascal 函数创建一个 UTF16_CharPosEx 函数CharPosEx。我正在尝试找到更快的通用解决方案，例如 Fastcode Project 的纯 Pascal 方法.

原始陈述

根据已接受的问题答案， Delphi: fast Pos with 64-bit ，查找字符串中子字符串位置最快的纯 Pascal 函数是 Fastcode Project 的 PosEx_Sha_Pas_2() .

对于最快的纯 Pascal 函数来查找字符串中字符的位置，我注意到 Fastcode Project具有用于从左到右匹配的 CharPos()、CharPosIEx() 和 CharPosEY()，以及 CharPosRev () 用于从右到左匹配。

但是，问题是所有 Fastcode 函数都是在 Delphi 2009 之前开发的，Delphi 2009 是第一个支持 Unicode 的 Delphi 版本。

我对 CharPos() 和 CharPosEY() 感兴趣。我想重新对它们进行基准测试，因为现在有些优化技术已经没用了，例如偶尔在 Fastcode 函数中实现的循环展开技术。

但是，我无法为每个 CharPos 系列挑战重新编译基准项目，因为我在这里一直使用 Delphi XE3，因此我无法断定哪一个是最快的。

问题

这里有人知道或可以得出结论，对于上述每个 Fastcode 挑战，尤其是 CharPos() 和 CharPosEY()，哪一个是最快的纯 Pascal 实现？

Fastcode Project 之外的其他方法欢迎解决。

注释

• 我在这里使用的Unicode字符串术语是指类型为UnicodeString的字符串，无论其编码方案如何。
• 如果编码方案很重要，我指的是固定宽度 16 位编码方案 (UCS-2)。

Answer 1

在快速代码示例中，许多在字符串中查找字符的解决方案都使用一种技术将字符串以较大的 block 读入寄存器，然后分析寄存器字节是否匹配。当字符是单字节时，这可以正常工作，但当字符是 16 位 unicode 时，这并不是最佳选择。

一些示例甚至使用查找表，但这在 unicode 字符串搜索中也不是最佳选择。

我发现 fastcode purepascal PosEx_Sha_Pas_2 字符串搜索例程在 32/64 位模式下工作得非常好，甚至对于单字符搜索也是如此。 您不妨使用该例程。

---

我将 PosEx_Sha_Pas_2 中不需要的部分剥离到 CharPosEx_LU_Pas 中，并在执行时间上获得了一些百分比:

function CharPosEx_LU_Pas(c: Char; const S: string; Offset: Integer = 1): Integer;
var
  len: Integer;
  p, pStart, pStop: PChar;
label
  Loop0, Loop4,
  TestT, Test0, Test1, Test2, Test3, Test4,
  AfterTestT, AfterTest0,
  Ret;
begin;
  p := Pointer(S);

  if (p = nil) or (Offset < 1) then
  begin;
    Exit(0);
  end;

  len := PLongInt(PByte(p) - 4)^; // <- Modified to fit 32/64 bit
  if (len < Offset) then
  begin;
    Exit(0);
  end;

  pStop := p + len;
  pStart := p;
  p := p + Offset + 3;

  if p < pStop then
    goto Loop4;
  p := p - 4;
  goto Loop0;

Loop4:
  if c = p[-4] then
    goto Test4;
  if c = p[-3] then
    goto Test3;
  if c = p[-2] then
    goto Test2;
  if c = p[-1] then
    goto Test1;
Loop0:
  if c = p[0] then
    goto Test0;
AfterTest0:
  if c = p[1] then
    goto TestT;
AfterTestT:
  p := p + 6;
  if p < pStop then
    goto Loop4;
  p := p - 4;
  if p < pStop then
    goto Loop0;
  Exit(0);

Test3:
  p := p - 2;
Test1:
  p := p - 2;
TestT:
  p := p + 2;
  if p <= pStop then
    goto Ret;
  Exit(0);

Test4:
  p := p - 2;
Test2:
  p := p - 2;
Test0:
  Inc(p);
Ret:
  Result := p - pStart;
end;

我声称此代码片段没有原创性，因为从 PosEx_Sha_Pas_2 中删除不需要的代码部分是一项简单的任务。

Benchmark 32 bit (101 character string, last character matches): 50000000 repetitions.

System.Pos:       1547 ms
PosEX_Sha_Pas_2:  1292 ms
CharPosEx:        2315 ms
CharPosEx_LU_Pas: 1103 ms
SysUtils.StrScan: 2666 ms

Benchmark 64 bit (101 character string, last character matches): 50000000 repetitions.

System.Pos:      20928 ms
PosEX_Sha_Pas_2:  1783 ms
CharPosEx:        2874 ms
CharPosEx_LU_Pas: 1728 ms
SysUtils.StrScan: 3115 ms