Delphi: What are faster pure Pascal approachs to find the position of a character in a Unicode string?

Question

Background

Added Later

I have made a pure Pascal function to find the position of a character in a Unicode string as follows:

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;

I decide to not use the built-in StrUtils.PosEx() because I want to create a UTF16_CharPosEx function based on an optimized pure Pascal function of CharPosEx. I'm trying to find a faster generic solution like the pure Pascal approachs of the Fastcode Project.

The Original Statements

According to the accepted answer to the question, Delphi: fast Pos with 64-bit, the fastest pure Pascal function to find the position of a substring in a string is PosEx_Sha_Pas_2() of the Fastcode Project.

For the fastest pure Pascal function to find the position of a character in a string, I noticed that the Fastcode Project has CharPos(), CharPosIEx(), and CharPosEY() for a left-to-right matching, as well as CharPosRev() for a right-to-left matching.

However, the problem is that all Fastcode functions were developed before Delphi 2009, which was the first Delphi release that supports Unicode.

I'm interested in CharPos(), and CharPosEY(). I want to re-benchmark them because there are some optimization techniques that are useless nowadays, such as loop unrolling technique that was occasionally implemented in Fastcode functions.

However, I cannot recompile the benchmark project for each of the CharPos family challenges because I have been using Delphi XE3 here, therefore I cannot conclude which one is the fastest.

Questions

Anyone here know or can conlude which one is the fastest pure Pascal implementations for each of the mentioned Fastcode challenges, especially for CharPos() and CharPosEY()?

Other approaches out of the Fastcode Project solution are welcome.

Notes

• The Unicode string term I used here refers to a string whose the type is UnicodeString regardless its encoding scheme.
• If encoding scheme matters, what I mean is the fixed-width 16-bit encoding scheme (UCS-2).

Answer 1

Many of the solutions to find a character in a string amongst the fastcode examples, uses a technique to read the string in in larger chunks into a register and then analyze the register bytes for a match. this works fine when the characters are single bytes, but are not optimal when characters are 16 bit unicode.

Some examples even use a lookup table, but that is also not optimal in a unicode string search.

I find that the fastcode purepascal PosEx_Sha_Pas_2 string search routine works very good both in 32/64 bit mode even for single character search. You might as well use that routine.

---

I stripped out some parts not needed out of the PosEx_Sha_Pas_2 into CharPosEx_LU_Pas and gained some percent in execution time:

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;

I claim no originality to this snippet as it was a simple task to strip out those code parts not needed from 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