Page 1 of 2 12 LastLast
Results 1 to 10 of 12

Thread: Looking for a FAST replacement for TStringList

  1. #1

    Looking for a FAST replacement for TStringList

    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?

  2. #2

    Looking for a FAST replacement for TStringList

    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.

  3. #3
    Co-Founder / PGD Elder WILL's Avatar
    Join Date
    Apr 2003
    Location
    Canada
    Posts
    6,107
    Blog Entries
    25

    Looking for a FAST replacement for TStringList

    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...
    Jason McMillen
    Pascal Game Development
    Co-Founder





  4. #4

    Looking for a FAST replacement for TStringList

    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.

    Code:
    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.

  5. #5

    Looking for a FAST replacement for TStringList

    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.
    <A HREF="http://www.myhpf.co.uk/banner.asp?friend=139328">
    <br /><IMG SRC="http://www.myhpf.co.uk/banners/60x468.gif" BORDER="0">
    <br /></A>

  6. #6
    PGD Community Manager AthenaOfDelphi's Avatar
    Join Date
    Dec 2004
    Location
    South Wales, UK
    Posts
    1,246
    Blog Entries
    2

    Re: Looking for a FAST replacement for TStringList

    Quote Originally Posted by 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?
    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.

    Code:
    unit faststringlist;
    
    &#40;*------------------------------------------------------------
    
      Fast String List
    
      Description&#58;-
    
      This unit provides an enhanced string list
    
      See Also&#58;-
    
      Version History&#58;-
    
      Date       Version Label Author Description
      ========== ======= ===== ====== ===========================================
      Jan 06     0.0                  Starting Version uses code from a couple of
                                      places.  Overriden 'find' is an addition &#40;removed&#41;
    
      ------------------------------------------------------------*&#41;
    
    interface
    
    uses
        classes;
    
    type
        TFastStringList = class&#40;TStringList&#41;
        protected
          fAssigning &#58; boolean;
    
        public
          constructor create;
          procedure sort; override;
          procedure assign&#40;source&#58;TPersistent&#41;; override;
          function indexOf&#40;const s&#58;string&#41;&#58;integer; override;
        end;
    
    &#40;*------------------------------------------------------------*&#41;
    
    implementation
    
    uses
        sysUtils;
    
    &#40;* Fast String List - From RiverSoftAVG's hints/tips section *&#41;
    
    constructor TFastStringList.create;
    begin
         inherited;
    
         fAssigning&#58;=false;
    end;
    
    procedure TFastStringList.Assign&#40; Source&#58; TPersistent &#41;;
    begin
          if Sorted and
             &#40;Source is TStringList&#41; and
             &#40;TStringList&#40;Source&#41;.Sorted&#41; then
          begin
               BeginUpdate;
               try
                  Sorted &#58;= False;
                  FAssigning &#58;= True;
                  inherited Assign&#40; Source &#41;;
               finally
                  Sorted &#58;= True;
                  FAssigning &#58;= False;
                  EndUpdate;
               end;
          end
          else
              inherited Assign&#40; Source &#41;;
    end;
    
    procedure TFastStringList.Sort;
    begin
          if not FAssigning then
             inherited Sort;
    end;
    
    function TFastStringList.IndexOf&#40;const S&#58; string&#41;&#58; Integer;
    begin
          if not Sorted then
          begin
               for Result &#58;= 0 to Count - 1 do
                   if CompareText&#40;Strings&#91;Result&#93;, S&#41; = 0 then Exit;
               Result &#58;= -1;
          end
          else if not Find&#40;S, Result&#41; then
               Result &#58;= -1;
    end;
    
    end.
    :: AthenaOfDelphi :: My Blog :: My Software ::

  7. #7

    Looking for a FAST replacement for TStringList

    Code:
    type TStringList = array of string;
    ;)

  8. #8

    Looking for a FAST replacement for TStringList

    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.
    <A HREF="http://www.myhpf.co.uk/banner.asp?friend=139328">
    <br /><IMG SRC="http://www.myhpf.co.uk/banners/60x468.gif" BORDER="0">
    <br /></A>

  9. #9

    Looking for a FAST replacement for TStringList

    Quote Originally Posted by 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.
    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.

  10. #10
    PGD Community Manager AthenaOfDelphi's Avatar
    Join Date
    Dec 2004
    Location
    South Wales, UK
    Posts
    1,246
    Blog Entries
    2

    Looking for a FAST replacement for TStringList

    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.
    :: AthenaOfDelphi :: My Blog :: My Software ::

Page 1 of 2 12 LastLast

Bookmarks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •