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;