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 operations | 2.2× | 1.0× |
| Eight threads, one per core, speed retained by each thread relative to its own single-thread speed | 86–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 suffix | Exact, case-sensitive comparison of UTF-16 code units. | Identifiers, keys, tokens, and text a program writes and reads itself. This is the fastest option. |
| Ascii | Folds 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. |
| Invariant | Uses 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. |
| Linguistic | Follows 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.
Compare | 8.0–45× | 11–65× with IgnoreCase | 6.4–153× |
Replace | 3.7–17× | 6.4–53× | 6.7–85× |
ToUpper | 5–25× | 5–26× | — |
ToLower | 5–28× | 5–28× | — |
StartsWith | 2.5–46× | 5.4–91× | 15–239× |
EndsWith | 2.3–42× | 9.8–149× | 23–350× |
Contains | 4.2–24× | 6.3–51× | 10–62× |
2. Using Substring in Delphi
- Lifetime. Use a
Substringas a local variable, parameter, or function result. Keep it out of array elements, containers, global variables,threadvarvariables, and fields. - Threads. Keep a
Substringon the thread that created it. UseToStringto hand another thread a Delphi string, orSubrangeto hand it a view. - Indices.
s[0]reads the first UTF-16 code unit. The free functions, includingPos,PosEx,LeftStr, andIsDelimiter, as well asSubrange,GetSubstring, andIndex, use 1-based positions. Every index and count is range checked. A failed check raisesESubstringRangeError. - Conversions.
Substring('text')copies text in, andToStringcopies it out. Text parameters readstring,Char,WideString, andPChardirectly. Passing anAnsiString,UTF8String,RawByteString, orShortStringraisesESubstringEncodingError. Delphi types a lone character literal from#$80to#$FFasAnsiChar. WriteChar(#$E9)to pass that character. - Unit order. Put
SubstrbeforeSystem.SysUtilsin theusesclause. Qualify calls toIntToStr,FloatToStr,StringOfChar, andBoolToStr, as inSubstr.IntToStr(5). - Parameters. When passed to functions as parameters use
constorvar
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
- Full source in pascal/asm without external dlls
- Part of MtxVec for Delphi and C++Builder
- Can be ordered immediately as a part of MtxVec