Efficiency of TList and TStringList
Home Up Feedback Search

Products
Order
Downloads
Support
Articles & Tips
Recommended Links
About

 
 

 
Other Links:

A long time ago, I got interested in the performance of the TList and TStringList classes in Delphi.  With the help of Jeff Hosler, I developed linked lists, new string lists, stacks, queues, etc and tested their efficiency.  The results were very enlightening.  The following text is from an email message I sent out to the Delphi 3D mailing list back in April 1998; what's interesting is that it is still valid today with Inprise's latest, Delphi 5.


1. TList is an extremely fast class.  If you are thinking of implementing a linked list class, don't even bother.  Borland did a really good job with this class.
         a. The overhead of creating nodes for a linked list makes it
 slower.
         b. An interesting thing I found out is that TList is FASTER traversing its list (using IndexOf), than my linked list class is traversing nodes.
         c. The only thing I can get the linked list to beat TLIST in is with deletes from the front of the list with a huge list, i.e., someone recommended (in another message)
         while Count > 0 do
                 Delete(0);
         which is actually slower than
         while Count > 0 do
                 Delete(Count-1);
         I believe that this is because Tlist is moving or copying more memory when you delete from the front.  This only comes into play when you get to THOUSANDS of items.  So, if you want large queues you may want to code your own, but otherwise don't bother.

The biggest problem with TList is that it is really hard to override.

2.  TStringList is another great class but it could be better.  Basically, everything I said about TList applies to TStringList.  There is one bottleneck though... if you are assiging a SORTED TStringList to another SORTED TStringList, TStringList is dog slow.  The reason this occurs is that TStringList inherits its assignment behavior from TStrings and does not take advantage of the fact that both StringLists are sorted.  It performs a binary search every time a new item is added to find the correct place which always is the end!  Borland could fix this easier because they have access to private fields, but you can really speed up TStringLists behavior by adding one private field (fAssigning) and overriding two methods:

procedure TSFCList.Assign( Source: TPersistent );
{ Override the assign to speed up an assign of a Sorted StringList to a Sorted
   StringList }
begin
      if Sorted and
         (Source is TStringList) and
         (TStringList(Source).Sorted) then
      begin
           BeginUpdate;
           try
              Sorted := False;
              FAssigning := True;
              inherited Assign( Source );
           finally
              Sorted := True;
              FAssigning := False;
              EndUpdate;
           end;
      end
      else
          inherited Assign( Source );
end;

procedure TSFCList.Sort;
begin
      if not FAssigning then
         inherited Sort;
end;

         One last note about TStringList... if you don't care about the international market, override IndexOf because IndexOf uses a VERY slow function called AnsiCompareText which uses locale information to perform a compare.  The function CompareText is 13 TIMES faster!  Like so:

function TSFCList.IndexOf(const S: string): Integer;
begin
      if not Sorted then
      begin
           for Result := 0 to Count - 1 do
               if CompareText(Strings[Result], S) = 0 then Exit;
           Result := -1;
      end
      else if not Find(S, Result) then
           Result := -1;
end;

Send mail to webmasterNO@SPAMRiverSoftAVG.com with questions or comments about this web site.
Copyright © 2002-2010 RiverSoftAVG
Last modified: September 20, 2010