Optimizing Delphi Lists and Strings

By: Marco Cantu

Abstract: Lists, strings, and string lists are among the most commonly used Delphi data structures, so obtaining some extra speed from them can benefit most applications. This presentation also helps you figure out how to port similar code to Delphi for the Microsoft .NET Framework.

Marco is the author of the best-selling series Mastering Delphi, of Essential Pascal, and of a Delphi 8 ebook. He teaches Delphi and XML classes and is a frequent speaker at Delphi and other developers conferences worldwide. He can be reached on www.marcocantu.com.


#2132: Optimizing Delphi Lists and Strings

Marco Cantù, www.marcocantu.com

Lists, strings, and string lists are among the most commonly used Delphi data structures, so obtaining some extra speed from them can be a benefit for most applications. This presentation also help you figure out how to port similar code to Delphi for the Microsoft .NET Framework.


Delphi’s RTL includes a set of ready-to-use data structures, ranging from the commonly used lists and string lists to the lesser known hash-tables. This presentation describes the available data structures, their quirks and bottlenecks, and examines a few solutions to speed them up (or replace them altogether) in Delphi for Win32 and Delphi for .NET. Beside lists, a particular focus is given to strings as even the most trivial string concatenation operation (str1 := str1 + str2) has an astonishingly different performance in Delphi 6, Delphi 7, and Delphi for .NET (up to 100 times from one to the other!). Actually strings can be considered a very simple data structure, but given the frequency of their use, it is a simple structure worth a second thought.

The Example Domain

Most of the examples presented in this paper relate to the generation of XML documents (or where adapter from it), an interesting case in which you need to process large chucks of data and have CPU constraints (particularly on a server with hundreds of active users). In XML processing I often use string lists to handle single items of a large XML documents, particularly when the XML structure is flat. When I need no further processing, at times I just put all of the XML in a string and than save the string (or return it from a web site dynamically). I've tried to keep the examples generic, but you'll see this is the background of most of my demos.

Poor man timing

As I'm looking for rather large optimizations (not really for fine tuning) I've used some rather unprecise timing techniques. On Windows I tend to use the GetTickCount API, which executes faster and so interferes less with the test code, while for portability to Linux I often use the time (the Now function). Moving from Win32 to .NET I noticed that while GetTickCount is faster on both platforms (again causing less overhead), while the Now functions yields closer results as it is slower on both platforms. I've actually written a self test example (I mean, an example testing the test code), which is called TimingTest in the presentation examples.

What I do is generally use a "timing" class so that I can easily change the timing technique without affecting the rest of the code. This is the declaration of the TTimeTest class (of which I have different versions in different units):

  TTimeTest = class
    // omitted
    constructor Create;
    function Elapsed: string;
    destructor Destroy; override;

In any case, by making a large number of iterations all of these timing approaches still gives a rough idea of the actual situation, although more precise timing techniques are available for each specific platform.

Moving to Microsoft .NET

Most of my XML work is still based on Win32 and Linux, but I'm exploring .NET solutions. At the moment my ideal solution is one which is good enough on all three platforms. There are two areas to consider: first, the Delphi RTL has a .NET RTL counterpart, so you might find more efficient code by switching away from Delphi compatibility; second, with strings being immutable on .NET the string concatenation code has to be modified. With this in mind, there will not be a specific section of the presentation devoted to .NET efficiency (which would be a very broad topic and quite a different one), but I'll introduce comparisons and alternatives whenever relevant.

On the whole, the .NET version of the same memory-bound algorithm is often a little slower (10 to 20 percent) but the timing of a single algorithm varies much more than on Win32, probably due to the fact that memory operations are less linear (due to the fact that the garbage collector kicks in very often) and probably other factors I'm still investigating.

You've Got Speed

Along with some other disclaimers like "I've tried this code only on my computer, which might be flaky", before I start I want to underline the fact that in-memory data processing in whichever version of Delphi is so fast that most of the times you might not really care too much about optimizing. But, as I mentioned, things change when you move code from a client application with an entire CPU for its own to a server application having hundreds of requests to perform on a very little time before the remote users gets annoyed.

Introducing Delphi Lists

Let's start from the very beginning. Delphi's RTL includes since the very beginning a few data structures like TList and TStringList, and has had for a few versions also a small set of container classes. Let's take a short overview of what's available. Then I'll start showing examples with some good and some bad practices and also highlight a few problems.

Lists in Delphi are represented by the generic list of objects/pointers, TList, and by the two lists of strings, TStrings and TStringList. Beside these code structures there are collections and container classes (defined in the Contnrs unit):

  • TList defines a list of pointers, which can be used to store objects of any class. A TList is more flexible than a dynamic array, because it is expanded automatically, simply by adding new items to it. The advantage of dynamic arrays over a TList, instead, is that dynamic arrays allow you to indicate a specific type for contained objects and perform the proper compile-time type checking, but type safety in lists is another story worth a separate talk. The TList class can be used to represent a large set: its Assign method, in fact, can perform set operations on the two lists, including and, or, and xor.
  • TStrings is an abstract class to represent all forms of string lists, regardless of their storage implementations. This class defines an abstract list of strings. For this reason, TStrings objects are used only as properties of components capable of storing the strings themselves, such as a list box.
  • TStringList, a subclass of TStrings, defines a list of strings with their own storage. You can use this class to define a list of strings in a program. TStringList (and TStrings) objects have both a list of strings and a list of objects associated with the strings. This opens up a number of different uses for these classes. For example, you can use them for dictionaries of associated objects or to store bitmaps or other elements to be used in a list box.
  • TStringList Name/Value pairs: The TStringList class has always had another very nice feature, namely support for name-value pairs, which can be considered a separate data structure. If you add to a list a string like ‘lastname=john’ you can then search for the existence of the pair using the IndexOfName function or the Values array property. For example, you can retrieve the value ‘john’ by calling Values [‘lastname’]. You can use this feature to build much more complex data structures, like dictionaries, and still benefit also from the possibility of attaching an object to the string.
  • Collections in Delphi are based on two classes, TCollection and TCollectionItem. TCollection defines a homogeneous list of objects, which are owned by the collection class. The objects in the collection must be descendants of the TCollectionItem class. If you need a collection storing specific objects, you have to create both a subclass of TCollection and a matching subclass of TCollectionItem. Collections are used to specify values of properties of components.
  • The TObjectList class represents a list of objects. The basic difference between TList and the new TObjectList class, for example, is that the latter is defined as a list of TObject objects, not a list of pointers. Even more important, however, is the fact that if the object list has the OwnsObjects property set to True, it automatically deletes an object when it is replaced by another one and deletes each object when the list itself is destroyed.
  • The inherited class TComponentList represents a list of components, with full support for destruction notification (an important safety feature when two components are connected using their properties; that is, when a component is the value of a property of another component).
  • The TClassList class is a list of class references. It inherits from TList and requires no destruction.
  • The classes TStack and TObjectStack represent lists of pointers and objects, from which you can only extract elements starting from the last one you’ve inserted. A stack follows the LIFO order (Last In, First Out). The typical methods of a stack are Push for insertion, Pop for extraction, and Peek to preview the first item without removing it. You can still use all the methods of the base class, TList.
  • The classes TQueue and TObjectQueue represent lists of pointers and objects, from which you always remove the first item you’ve inserted (FIFO: first in, first out). The methods of these classes are the same as those of the stack classes but behave differently.
  • TBucketList and TObjectBucketList are are associative lists, which means they have a key and an actual entry. The key is used to identify the items and search for them. These lists are also based on a hash system. The lists create an internal array of items, called buckets, each having a sub-list of actual elements of the list. As you add an item, its key value is used to compute the hash value, which determines the bucket to add the item to. When searching the item, the hash is computed again, and the list immediately grabs the sublist containing the item, searching for it there. This makes for very fast insertion and searches, but only if the hash algorithm distributes the items evenly among the various buckets and if there are enough different entries in the array. In fact, when many elements can be in the same bucket, searching gets slower.
  • Delphi includes also a THashedStringList class, which inherits from TStringList. This class has no direct relationship with the hashed lists and is even defined in a different unit, IniFiles. The hashed string list has two associated hash tables (of type TStringHash), which are completely refreshed every time the content of the string list changes. So this class is useful only for reading a large set of fixed strings, not for handling a list of strings changing often over time. On the other hand, the TStringHash support class seems to be quite useful in general cases, and has a good algorithm for computing the hash value of a string.
  • Finally, there is another in-memory list you can use very effectively in Delphi programs for complex structures, the ClientDataSet components. Although seldom considered to be part of this groups of container classes, the CDS can really be used in place of string lists and similar data structures.

Sorted String Lists

Suppose you have a string list with a tens of thousands of entries and you need to find a value. As all Delphi programmers know, the standard way to perform this operation is to use the IndexOf method of the TStringList class. What not all of the programmers know, however, is that IndexOf has two different implementations, depending on whether the string list is sorted or not:

function TStringList.IndexOf(const S: string): Integer;
  if not Sorted then 
    Result := inherited IndexOf(S) 
    if not Find(S, Result) then 
      Result := -1;

Find uses a simple binary search (nothing fancy) but this is fast enough that at times it is more convenient to sort the string list and than look for the value than using IndexOf on the unsorted list in the first place. The sorting operation uses binary search as well, but in case you have to sort a large number of strings (maybe read from a file) it is much faster to populate the string list while it is not sorted and than sort it rather than doing the opposite (set the sorted property first and than add each string). Even when adding many new values to a string list you might want to temporarily disable sorting. By the way, notice that sorted string list have also the option of checking for duplicates, with the Duplicates property (having values: dupIgnore, dupAccept, or dupError). This is checked when you add a string to a sorted string list.

In the StringListSpeed demo I've actually copied the string list from a base one to a sorted one, to avoid affecting the original data (which might be relevant in same cases). If the speed difference between a sorted and unsorted string is probably expected, you might be surprised to see that the difference between writing:

    sSorted := TStringList.Create;
    // copy then sort
    sSorted.AddStrings (sourceList);
    sSorted.Sorted := True;


    sSorted := TStringList.Create;
    // sort and then copy
    sSorted.Sorted := True;
    sSorted.AddStrings (sourceList);

is quite relevant: on 100,000 strings I got a timing of 1,342 for the first snippet, 11,597 for the second. That's an order of magnitude.

A totally different alternative (which is my opinion is worth exploring) is the usage of ClientDataSet (CDS) as a data structure for managing even a simple string list. Populating a CDS with a single string field is more expensive than populating a string list, however activating an index and searching is generally much faster. This is visible in the StringListSpeed demo. Of course, the large advantage of this approach comes when you have complex data structures (strings with multiple values, as an XML document) and you want to be able to search or sort on multiple possible entries. Although string lists allows for the name/value pair structure, the value part is generally not sorted, with the exception of hashed string lists.

Fixing Hash Tables

Delphi's THashedStringList class, found in the IniFiles unit (as described earlier) provides extra speed when you need to perform multiple find operations on a non-changing string list. As the class is used to implement TMemIniFile, the idea that the data seldom changes fits properly. But for a generic use, this class falls short. In fact, if THashedStringList performs great while searching an existing list, it is so slow to become unusable if the string list changes over time, as the entire hash table is recalculated every time a string in the list changes.

Here are some sample timings, from the ubiquitous StringListSpeed demo: on 50,000 strings, “sort and find” takes 2,413 compared to hash sort that takes only 111 (this is for 1,000 find operations). However, if we keep modifying the list each time, for a mere 1,000 entries hash sort takes 3,495, compared to a 20 of the “sort and find” approach.

For this reason I've developed my own class, TMyHashedStringList, which has a very similar implementation to the original one from Borland, but is not adversely affected by code that adds strings to the list, as the hash entires are computed incrementally and not refreshed each time. The result is that my hash string list is invariably faster than the “sort and find” approach, whichever the number of strings and regardless of the fact that new strings are added to the list.

Delphi actually has another hashed container, the TObjectBucketList class. Again, this is affected by a severe problem. As you create the TObjectBucketList you can specify the number of entries for the list, using the parameter of the constructor, choosing a value between 2 and 256. The value of the bucket is determined by taking the first byte of the pointer (or number) passed as key and doing a bitwise and operation with a number corresponding to the entries. I don’t find this algorithm very convincing for a hash system, because creating a number of objects in sequence you often get them from the same memory area, thus with the same first byte. What you need to do is to replace the code by overriding the BucketFor virtual function and eventually changing the number of entries in the array, by setting a different value for the BucketCount property.

Another interesting feature, not available for lists, is the ForEach method, which allows you to execute a given function on each item contained in the list. You pass to the ForEach method a pointer to data of your own and a procedure, which receives four parameters, including your custom pointer, each key and object of the list, and a Boolean parameter you can set to False to stop the execution. In other words, these are the two signatures:

  TBucketProc = procedure(AInfo, AItem, AData: Pointer;
    out AContinue: Boolean);

function TCustomBucketList.ForEach(AProc: TBucketProc;
  AInfo: Pointer): Boolean;

This was interesting until Diamondback came along with its specific support for iterators, with the for in keyword, even on the Win32 side.

List and String Lists and Hash Codes on Microsoft .NET

Let's now move to the Microsoft .NET side. A possibility is to keep using the Delphi RTL, porting the code we're used to as it is. The performance on average will suffer a little bit, but not every time. For example, the IndexOf code is considerably faster on the .NET side. Of course, I had to tweak the code a little to avoid performance problems, for example in the string generation code (for string-related issues see the second part of the paper).

The alternative to this approach is to use the container classes of the Framework Class Library (FCL). This is relevant only if backward compatibility is not a issue for you, of course. Although there isn't a specific string list class, the generic ArrayList container is well suited for our purposes. With methods like Clear, Add, IndexOf, a property like Count and the possibility to use the square brackets to access individual items of the array, porting the code from a string list to an array list is quite trivial. There are some false friends, though. For example IndexOf performs invariably a linear search, while you can use the BinarySearch method for a faster search in a sorted array list. As an alternative, you can use the SortedList class, that is invariably sorted and implements the IndexOf method as a binary search. As none of these classes inherits from another, you'd better choose upfront, as moving from a solution to the other is much more expensive than in case of Delphi (although the use of interfaces will certainly help, I don't find it a complete substitute for a good class hierarchy).

In the StringListSpeedNet demo you can see that the FCL solutions are constantly faster than the Delphi RTL solutions. This means they are invariably faster than their Win32 counterpart. In same cases (such as in the plain search) the different is relevant, although there are areas like sorting the array that suffer some performance penalty. The table below doesn't show a precise benchmark, but should give you a rough idea of the timings (on my PC):


Delphi's RTL


Populate with 100,000



Populate with 1,000,000



Linear find on 100,000



Sort and binary find on 10,000



Sort and binary find on 100,000



Getting back to hash codes it is relevant to mention that in .NET every object has its own Hash function (available in the base Object class), which comes very handy when implementing any hashed data structure. Of course, there is a container based on this features, called Hashtable. It is an associative array with an key and a value, both represented by generic objects. The Hashtable is different from an array as you cannot access data with a positional notation (that is, the square brackets), unless you use the index as the value, which seems rather pointless to me. You can use the ContainsKey method to check for a key and use the Add method to add only unique keys (there is no option to accept duplicate keys, which seems correct to me). Again, the speed is optimal but you need to change the code considerably to take advantage of it. It is true that interfaces such as IList provide a unified access to many collections, but for example this excludes the Hashtable container.

All of this is demonstrated again by the StringLitSpeednet example. I've avoided listing its sample code here, beside a few relevant bits, simply because you'll better understand it by looking at the actual code!


Core Issues with Strings

Let's now move to the second part of this talk, strings. Although strings are not often seen as data structures, they originally where part of this category (as characters arrays). My rationale for considering strings is that I often produce XML files (even large ones) by building large strings and streaming them out. Even if they seem trivial to use at first, strings might reserve surprises, particularly when moving from Win32 to .NET. In Delphi Win32 strings use reference counting and copy-on-write semantics. In (Delphi) .NET strings are immutable and garbage collected.

Using const string parameters

It has been mentioned many times that passing const strings make Delphi code faster. The reason is that if the string parameter is const there is no need to increment and later decrement the reference count for the string. This is why, for example, Delphi adds const when expanding string properties. But which is the actual speed difference? And does this affect .NET as well?

The actual effect can be verified with this silly function, that does nothing but call one of the fastest string manipulation functions available (if you consider that Length does not scan the string but returns the length from the header):

function GetL (s: string): integer;
  Result := Length (s);

function GetL2 (const s: string): integer;
  Result := Length (s);

In this extreme scenario the effect is very relevant: for 10,000,000 iterations timing changes from 580 to 100. For a single call, well, you'll never notice it! Still, using this approach extensively will save quite some time. Finally, is "const" relevant also on .NET? Let's try: Same code above times about 200 in both cases. So the answer is a clear "no".

A related technique, even more important, is to avoid functions that take strings as parameters and return a modified strings unless you need to keep the original. Modifying the string directly without duplicating it can save a lot for a large string (although you have to consider the string concatenation issues discussed later):

function Redo (const s: string): string;
  Result := s + '*';

procedure Redo2 (var s: string);
  s := s + '*';

For 50,000 iterations the speed difference it 3,335 to 20, with is over two orders of magnitude.

String Concatenation

String concatenation is another very relevant issue when managing large chunks of data in RAM. It is true that (at least on Win32) you can access a data block using PChars, but the code concatenating strings with the + sign is so easy to write and readable that you need a very serious reason to use a different approach. In the early days of Delphi, string concatenation had a faster alternative in the form of the AppendStr method, which tried to append the second string to the first one in place, that is making room in the base memory location with no need to copy both strings into a new memory area. Although AppendStr has long been declared obsolete (and now actually gone from Delphi's .NET RTL) its behavior is now simulated by the plain string concatenation code.

String concatenation used to be reasonably fast in Delphi 4 and 5 (provided you called SetLength appropriately), but when trying to optimize it for Delphi 6 things went totally wrong and the runtime kept copying both strings for each concatenation operation. Delphi 7, instead, properly attempts to expand the string buffer in place, adding the additional data at the end of the buffer used by the first string. This takes place automatically when the destination and the first string of the concatenation are the same (that is in s := s + t; not when you write s := t + v) and if the target string has no other standing references (that is, if the reference count is 1). Moreover, there is no need for you to call SetLength or perform any other extra operation. It just works. Timing shows that the difference between D6 and D7 for concatenating strings over 1 MB is about hundred times! And the situation gets only worse (or better, depending on your point of view) with the size of the string, with an exponential trend. An example I have written, StringConcatSpeed, demonstrates the various cases and shows their speed.

The solution I used for quite some time to maintain compatibility between Delphi 6 and Delphi 7 code was to use a string list (adding strings to it) and than grab the Text of the string list. In Delphi 7 this solution takes about twice the time, compared to plain string concatenation, so even if this slips into the code it is acceptable (although in critical places I sadly put IFDEFs in the code).

The “funny” thing is that now with Delphi for .NET the situation is more or less back to the Delphi 6 stage, even if for a different reason: it is not Borland's fault!

String Concatenation in .NET

Strings in .NET are immutable. This means that string concatenation is slow when done with the classic + sign (and the already obsolete AppendStr routine is now gone, as mentioned earlier). In fact, a new string has to be created in memory copying the content of the two strings being added, even if the effective result is adding some more characters to one of the strings. To overcome this slow implementation, the .NET framework provides a specific class for string concatenation, called StringBuilder.

For example, if you have a procedure like PlainStringConcat below that creates a string with the first 20,000 numbers, you should rather re-implement it using a StringBuilder object like in the following UseStringBuilder function:

function PlainStringConcat: Integer;
  str: string;
  i, ms: Integer;
  t: tDateTime;
  t := Now;
  str := '';
  for I := 1 to 20000 do
    str := str + IntToStr (i) + ' - ';
  ms := trunc (MilliSecondSpan(Now, t));
  writeln (str[100]);
  Result := ms;

function UseStringBuilder: Integer;
  st: StringBuilder;
  str: string;
  i, ms: Integer;
  t: tDateTime;
  t := Now;
  st := StringBuilder.Create;
  for I := 1 to 20000 do
    st.Append (IntToStr (i) + ' - ');
  str := st.ToString;
  ms := trunc (MilliSecondSpan(Now, t));
  writeln (str[100]);
  Result := ms;

function UseStringList: Integer;
  sl: TStringList;
  str: string;
  i, ms: Integer;
  t: tDateTime;
  t := Now;
  sl := TStringList.Create;
  for I := 1 to 20000 do
    sl.Add (IntToStr (i) + ' - ');
  str := sl.Text;
  ms := trunc (MilliSecondSpan(Now, t));
  writeln (str[100]);
  Result := ms;

If you run the StringConcatSpeed demo that includes the two functions above you'll see the time taken by each of the two approaches,and the difference will be striking! This is the output (you should try out with different ranges of the for loop counter):

String builder:19 
Plain concat:10235

This means that the string builder takes a few milliseconds while the string concatenation takes about 10 seconds. The conclusion is that you have to get rid of all of the lengthy string concatenations in your code using either a StringBuilder or a string list. The second approach is a little slower (takes almost twice as much as the StringBuilder, which seems acceptable for most tasks) but has the advantage of maintaining your code compatible with Delphi 7. You can certainly obtain the same compatibility by writing a StringBuilder class for Delphi 7, but using a string list seems a better approach to me if you need backward compatibility (or still have Delphi 6 boxes sitting around).

In case you are interested in building a custom solution, you might want to have a look at the cross-platform Delphi StringBuilder class built by Hallvard Vassbotn and discussed in the issue 100 (December 2003) of The Delphi Magazine and referenced also in the “Delphi for .NET Developer's Guide” book by Xavier Pacheco.

Streaming Large Strings to Files

When you are writing the string data sequentially (and don't need to do extra processing on it) instead of write all of the data to a string and than save the string to a stream you can as well use a memory or file stream and copy to it directly. With some fine tuning of the buffer size, you can probably achieve the best performance, or so one might think. Let's make a reality check (also to figure out if the different approaches make a real difference or just a minimal one).

In the StreamingTest example I've generated an XML file using 4 different techniques: (i) concatenating a string and saving it to a file stream at the end, (ii) saving the data to a stringstream and copying it to the file stream at the end, (iii) saving the data to a memory stream and than copying it to a file stream at the very end, and (iv) writing directly to the file stream. Not surprisingly the first two solutions are almost identical in speed, as the string is maintained behind the scenes. But these first two solutions are way way slower (about 50 times for 10,000 XML items) than the latter two. Comparins these faster solutions, the difference starts showing up only for files over a MB, when keeping the entire set of data in memory becomes more expensive in terms of memory allocations. At 100,000 XML items the direct file operation is twice as fast, at 200,000 items four times, at 400,000 items ten times, and at one million items about 25 times. At this point, the program creates files of 20 MB in size, with the direct file streaming taking about 4 seconds on my portable computer.

Alternative String Routines (FastStrings and other Libraries)

Finally, although I don't want to get into too much details on this area, consider that there are some relevant third party (and free) collections of string routines. One of the best known is the FastStrings unit by Peter Morris (http://www.droopyeyes.com). FastStrings aim, as the name implies, is to make existing Delphi routines like Pos or Replace faster. If you are looking more for additional routines you can look into JclStrings.pas of Project JEDI Code Library (JCL) or into the StStrL.pas unit and other units of the TurboPower SysTools. (I'm just referring to a few third party libraries I've used myself, there are certainly many others I don't know of or had no chance to test.)


Although I've touched on a number of different subjects, like string lists and other container classes, strings, and streaming, the aim of this paper was to give you some general guidance and suggestions for testing the speed of Delphi frequently used Delphi data types and classes. Delphi has always been about speed, even if not primarily, and getting to know some quirks or some bad programming practices can help you gain all of the power the tool has to offer. Delphi for .NET provides also the challenge of a new platform, so that some of your standard habits that still produce working code have become suboptimal.

Rather than focusing on the details of the generated assembly code or IL (which is another way to study the effect of the slightly different coding techniques) I've decided instead to compare some rough timing and focus on broadly alternative approaches. I think the fine-tuning makes sense only for specific projects, while a broad assessment of the speed of some general techniques can be handy for every Delphi programmers, as I hope I've demonstrated in the examples discussed.


Marco Cantù is the author of the bestselling Mastering Delphi series and an expert in Delphi and XML technologies. Marco has written books also on C++ and advanced Delphi programming, many articles, and spoken to developer's conferences around the world, including 10 Borland US Conferences. Marco lives in Italy, but you can easily reach him on www.marcocantu.com.

  Latest Comments  View All Add New RSS ATOM

Move mouse over comment to see the full text

Server Response from: ETNASC02