The High Performance String Library

A faster string

Substring, in the MtxVec Substr unit, is a UTF-16 string type for local variables. It is designed for text processing that avoids allocations inside loops and scales linearly with thread count. It achieves performance with three methods

  • By clearly separating the unicode string functions by their purpose, ASCII, Invariant and Lingustic, as defined by the operating system.
  • Providing a mechanism to completely avoid memory allocation inside of hot loops. Not as a special design construct, but a drop in replacement.
  • Optimizing the string processing kernels for vectorized processing making use of AVX2 and AVX512 instruction sets and including 76.000 lines of assembler.
One thread, geometric mean across 271 operations2.2×1.0×
Eight threads, one per core, speed retained by each thread relative to its own single-thread speed86–99%7%

Of the 271 operations measured on one thread, 233 were at least as fast with Substring as with Delphi string. A benchmark converting floating point numbers to strings, ran 43x faster on 16 cores.

1. Choosing how to match text

The suffix on a routine tells you how it ignores or maps case. The same convention applies to comparison, searching, replacement, and case conversion. Choose the least expensive routine that gives the result the text requires.

No suffixExact, case-sensitive comparison of UTF-16 code units.Identifiers, keys, tokens, and text a program writes and reads itself. This is the fastest option.
AsciiFolds only A–Z and a–z, without an operating system call. Every other character matches only itself.Format keywords and protocol tokens that need ASCII case folding. Examples include CompareAscii, ContainsAscii, and ToUpperAscii.
InvariantUses the operating system's locale-independent case table. Its uppercase and lowercase mappings round-trip.File names, paths, environment variables, registry keys, and other names exchanged between programs. Examples include CompareInvariant, ContainsInvariant, and ToUpperInvariant.
LinguisticFollows the default locale or a supplied LocaleID. Matching can ignore soft hyphens and treat composed and decomposed accents as equivalent. Casing can expand sharp s to ss and can fail to round-trip.Human-language text that needs locale-specific matching, casing, or sort order. Examples include CompareLinguistic, ContainsLinguistic, and ToUpperLinguistic.

The unsuffixed Replace uses exact matching and raises ESubstringCaseError if passed rfIgnoreCase. For case-insensitive replacement, use ReplaceAscii, ReplaceInvariant, or ReplaceLinguistic according to the rules you need.

1.1 The cost of case and locale rules

Across the measured operations, the Ascii routines took 1.2–3.2× the time of their unsuffixed equivalents. On text that differs in case, the Invariant routines took 2.3–46× the time of Ascii, and the Linguistic routines took 4.5–149× the time of Ascii. These case benchmarks used Win64, AVX2, the en-US locale, and texts of 30–512 characters. The gap grows with the amount of text the routine reads. With eight threads, each thread retained 93–100% of its single-thread speed while its data fit in 1 MB of L2 cache.

Each cell below gives the time of the more expensive routine divided by the time of the corresponding baseline. All numbers are for a single thread.

Compare8.0–45×11–65× with IgnoreCase6.4–153×
Replace3.7–17×6.4–53×6.7–85×
ToUpper5–25×5–26×—
ToLower5–28×5–28×—
StartsWith2.5–46×5.4–91×15–239×
EndsWith2.3–42×9.8–149×23–350×
Contains4.2–24×6.3–51×10–62×

2. Using Substring in Delphi

  • Lifetime. Use a Substring as a local variable, parameter, or function result. Keep it out of array elements, containers, global variables, threadvar variables, and fields.
  • Threads. Keep a Substring on the thread that created it. Use ToString to hand another thread a Delphi string, or Subrange to hand it a view.
  • Indices. s[0] reads the first UTF-16 code unit. The free functions, including Pos, PosEx, LeftStr, and IsDelimiter, as well as Subrange, GetSubstring, and Index, use 1-based positions. Every index and count is range checked. A failed check raises ESubstringRangeError.
  • Conversions. Substring('text') copies text in, and ToString copies it out. Text parameters read string, Char, WideString, and PChar directly. Passing an AnsiString, UTF8String, RawByteString, or ShortString raises ESubstringEncodingError. Delphi types a lone character literal from #$80 to #$FF as AnsiChar. Write Char(#$E9) to pass that character.
  • Unit order. Put Substr before System.SysUtils in the uses clause. Qualify calls to IntToStr, FloatToStr, StringOfChar, and BoolToStr, as in Substr.IntToStr(5).
  • Parameters. When passed to functions as parameters use const or var

2.1 Tokenize a line without copying its fields

FirstDelimitedText and NextDelimitedText move a window over the original text. Here, ToInteger reads each field through that window.

uses Substr;

procedure SumFields;
var
  Line: Substring;
  Sum: Integer;
begin
  Line := Substring('12,30,-2,60');
  Sum := 0;
  if Line.FirstDelimitedText(',') then
    repeat
      Sum := Sum + Line.ToInteger;
    until not Line.NextDelimitedText(',');
  Assert(Sum = 100);
end;

2.2 Build a line in an allocation-free loop

Reserve room before entering the loop with Capacity or Resize. During testing, enable SubstringAllocCheck to raise ESubstringAllocError if an operation allocates outside those two calls.

uses Substr;

procedure BuildLine;
var
  Line: Substring;
  k: Integer;
begin
  Line.Capacity := 1000;
  SubstringAllocCheck := True;
  try
    for k := 1 to 100 do
    begin
      Line.AppendInt(k);
      Line.Append(';');
    end;
  finally
    SubstringAllocCheck := False;
  end;
  Assert(Line.StartsWith('1;2;3;'));
  Assert(Line.Length = 292);
end;

2.3 Scan the characters at Delphi string speed

Use s[i] to read one character in place. For a loop over many characters, pass s.Data and s.Length to a routine that declares no Substring. Read Data using the supplied length, and use ToPChar when the caller needs null-terminated text.

uses Substr;

function SumOfChars(const P: PChar; const Len: Integer): Integer;
var
  j: Integer;
begin
  Result := 0;
  for j := 0 to Len - 1 do
    Result := Result + Ord(P[j]);
end;

procedure ScanCharacters;
var
  s: Substring;
begin
  s := Substring('abc');
  Assert(SumOfChars(s.Data, s.Length) = 294);
end;

3. Order details