Looking for a FAST replacement for TStringList

[jdarling]

I just profiled my game engine and I'm spending about 80% of my time inside of the TStringList . I knew it would be bad, but not that bad. Anyone know of a good fast StringList replacement?

[Robert Kosek]

Well, it's not hard to make a good string array component with some functions. I don't have one on hand, but I've done some pretty similar things.

What functions of StringList are you using, may I ask? If you're looking up "Values['']" stuff, then it'll be slow, real slow.

[WILL]

Have you tried KOL? http://bonanzas.rinet.ru/

It has some pretty handy replacement libraries. And with works for both Delphi, Lazarus/Free Pascal and I believe Kylix too...

[Robert Kosek]

You might find this handy, I stumbled across it on my harddrive unintentionally. It's a code unit for InnoSetup by Jordan Russel, so credit him if you use it.

unit SimpleStringList;

interface

uses
  Windows, SysUtils;

type
  PSimpleStringListArray = ^TSimpleStringListArray;
  TSimpleStringListArray = array[0..$1FFFFFFE] of String;
  TSimpleStringList = class
  private
    FList: PSimpleStringListArray;
    FCount, FCapacity: Integer;
    function Get (Index: Integer): String;
    procedure SetCapacity (NewCapacity: Integer);
  public
    destructor Destroy; override;
    procedure Add (const S: String);
    procedure AddIfDoesntExist (const S: String);
    procedure Clear;
    function IndexOf (const S: String): Integer;

    property Count: Integer read FCount;
    property Items[Index: Integer]: String read Get; default;
  end;

implementation

{ TSimpleStringList }

procedure TSimpleStringList.Add (const S: String);
begin
  if FCount = FCapacity then
    SetCapacity (FCapacity + 8);
  FList^[FCount] := S;
  Inc (FCount);
end;

procedure TSimpleStringList.AddIfDoesntExist (const S: String);
begin
  if IndexOf(S) = -1 then
    Add (S);
end;

procedure TSimpleStringList.SetCapacity (NewCapacity: Integer);
begin
  ReallocMem (FList, NewCapacity * SizeOf(Pointer));
  if NewCapacity > FCapacity then
    FillChar (FList^[FCapacity], (NewCapacity - FCapacity) * SizeOf(Pointer), 0);
  FCapacity := NewCapacity;
end;

procedure TSimpleStringList.Clear;
begin
  if FCount <> 0 then Finalize &#40;FList^&#91;0&#93;, FCount&#41;;
  FCount &#58;= 0;
  SetCapacity &#40;0&#41;;
end;

function TSimpleStringList.Get &#40;Index&#58; Integer&#41;&#58; String;
begin
  Result &#58;= FList^&#91;Index&#93;;
end;

function TSimpleStringList.IndexOf &#40;const S&#58; String&#41;&#58; Integer;
&#123; Note&#58; This is case-sensitive, unlike TStringList.IndexOf &#125;
var
  I&#58; Integer;
begin
  Result &#58;= -1;
  for I &#58;= 0 to FCount-1 do
    if FList^&#91;I&#93; = S then begin
      Result &#58;= I;
      Break;
    end;
end;

destructor TSimpleStringList.Destroy;
begin
  Clear;
  inherited Destroy;
end;

end.

[technomage]

I would recomend not using TStringList at all, especially if you are doing string lookups and returns objects. (rather than using the values to return string=value information).

I my own projects I use a HashList, the string (or key) is converted to an integer using a hash algorithm then I use the integer to lookup the value in the hash list. It's extremely quick, certainly allot faster then searchng in TStringlist. The code isn't publicly avaialable at the moment, but if you google for "delphi hash list" or "MwHashlist Delphi" you will get some results on http://www.torry.net.

[AthenaOfDelphi]

I just profiled my game engine and I'm spending about 80% of my time inside of the TStringList . I knew it would be bad, but not that bad. Anyone know of a good fast StringList replacement?

Hi Jeremy,

You may want to try this... it improved the performance of our web server system slightly. Its easy enough to switch to since its a drop in replacement.

If you do give it a go, I'd be interested to know what kind of performance it offers.

unit faststringlist;

(*------------------------------------------------------------

  Fast String List

  Description:-

  This unit provides an enhanced string list

  See Also:-

  Version History:-

  Date       Version Label Author Description
  ========== ======= ===== ====== ===========================================
  Jan 06     0.0                  Starting Version uses code from a couple of
                                  places.  Overriden 'find' is an addition (removed)

  ------------------------------------------------------------*)

interface

uses
    classes;

type
    TFastStringList = class(TStringList)
    protected
      fAssigning : boolean;

    public
      constructor create;
      procedure sort; override;
      procedure assign(source:TPersistent); override;
      function indexOf(const s:string):integer; override;
    end;

(*------------------------------------------------------------*)

implementation

uses
    sysUtils;

(* Fast String List - From RiverSoftAVG's hints/tips section *)

constructor TFastStringList.create;
begin
     inherited;

     fAssigning:=false;
end;

procedure TFastStringList.Assign( Source: TPersistent );
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 TFastStringList.Sort;
begin
      if not FAssigning then
         inherited Sort;
end;

function TFastStringList.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;

end.

[XProger]

type TStringList = array of string;

;)

[technomage]

The main problem with TStringList is in the Find function which basically uses a sequencial find (if I remember correctly), depending on how many items you have in your list the performance will degrade the more items you have in the list. With hash lists algoritms searching is only limited to those items whose hash(string) is the same, and the slight overhead of calculating the hash. Performance does not degrade too much no matter how many items you have in the list, unless all you items have string keys that compute to the same hash value.

http://oopweb.com/Algorithms/Documen...ashTables.html

Alert Fighter uses Hash Lists for all asset management (Textures, Models, Sound, Music, Game objects) it works extremely well

I don't think array of string would give you the same functionallity if you are trying to do

Gameobject := GameObjects['Player1'];
// do stuff with object.

[jdarling]

The main problem with TStringList is in the Find function which basically uses a sequencial find (if I remember correctly), depending on how many items you have in your list the performance will degrade the more items you have in the list. With hash lists algoritms searching is only limited to those items whose hash(string) is the same, and the slight overhead of calculating the hash. Performance does not degrade too much no matter how many items you have in the list, unless all you items have string keys that compute to the same hash value.

http://oopweb.com/Algorithms/Documen...ashTables.html

Alert Fighter uses Hash Lists for all asset management (Textures, Models, Sound, Music, Game objects) it works extremely well

I don't think array of string would give you the same functionallity if you are trying to do

Gameobject := GameObjects['Player1'];
// do stuff with object.

The find is the problem that I'm running into. I had thought about using a hash table to replace all of the the strings lists but its alot of work . Made some minor tweaks to change the way that some things work and this seems to have fixed up some of the problems I was having. I'll still have to look into and implement a hash table in the end though. At least my minor changes have me back on course for Stage 4, I might even get the hash stuff in before stage 4.

Thanks for the link, I've not seen that site before and I'll have to spend some time looking at it.

[AthenaOfDelphi]

If the list is unsorted, it does indeed use a sequential search, but my understanding is that if the list is sorted, it uses binary chop. The unit I posted speeds this up by replacing the slower ansiCompareText function with plain old compareText which is faster because it doesn't take into account unicode (IIRC).

Obviously adding items to a sorted list is slower, but if you can add all the items and then sort (during a level/map load for example), you may notice a good performance increase.