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?
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?
- Jeremy
http://www.eonclash.com/
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.
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...
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 (FList^[0], FCount); FCount := 0; SetCapacity (0); end; function TSimpleStringList.Get (Index: Integer): String; begin Result := FList^[Index]; end; function TSimpleStringList.IndexOf (const S: String): Integer; { Note: This is case-sensitive, unlike TStringList.IndexOf } var I: Integer; begin Result := -1; for I := 0 to FCount-1 do if FList^[I] = S then begin Result := I; Break; end; end; destructor TSimpleStringList.Destroy; begin Clear; inherited Destroy; end; end.
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>
Hi Jeremy,Originally Posted by jdarling
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; (*------------------------------------------------------------ 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.
:: AthenaOfDelphi :: My Blog :: My Software ::
;)Code:type TStringList = array of string;
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>
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.Originally Posted by technomage
Thanks for the link, I've not seen that site before and I'll have to spend some time looking at it.
- Jeremy
http://www.eonclash.com/
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 ::
Bookmarks