PDA

View Full Version : Looking for a FAST replacement for TStringList



jdarling
10-03-2006, 10:47 PM
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
10-03-2006, 10:54 PM
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
10-03-2006, 11:17 PM
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
11-03-2006, 01:59 AM
You might find this handy, I stumbled across it on my harddrive unintentionally. ;) It's a code unit for InnoSetup (http://jrsoftware.org/isinfo.php) by Jordan Russel (http://jrsoftware.org/), 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
11-03-2006, 08:25 AM
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
11-03-2006, 09:35 AM
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;

&#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.

XProger
11-03-2006, 01:47 PM
type TStringList = array of string;

;)

technomage
11-03-2006, 05:23 PM
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/Documents/Sman/Volume/HashTables.html

Alert Fighter (http://alertfighter.mirthmedia.co.uk) uses Hash Lists for all asset management (Textures, Models, Sound, Music, Game objects) it works extremely well :D

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
11-03-2006, 06:30 PM
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/Documents/Sman/Volume/HashTables.html

Alert Fighter (http://alertfighter.mirthmedia.co.uk) uses Hash Lists for all asset management (Textures, Models, Sound, Music, Game objects) it works extremely well :D

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
11-03-2006, 07:19 PM
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.

technomage
11-03-2006, 09:17 PM
As Athena said, load your data and sort the list, you searches would be allot quicker.

I will have to withdraw from this thread now I'm afraid as being a Judge in the competition it could be seen as a confilict of interest. :oops:

I hope you manage to find a solution.

Dean

jdarling
11-03-2006, 10:35 PM
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.

Actually I've already optimized Delphi AnsiCompareText and CompareText methods with PChar based assembly versions that are MUCH faster. In fact my AnsiCompareText is faster then the default CompareText (thats what direct memory and assembly can do for you).

Unfortunately sorting would really slow things down. In the end I've moved to pointer management instead of string management. This gives an almost 1:n improvement in speed. In fact my lookups are now at 1.2 average (the .2 comes from when a sprite type has never been used before). Guess thats an advantage to a scripted engine, I can change to pointers w/o changing anything else.

Before I was pulling about 120 fps and now I'm back up to my approved 230 fps. While the engine is locked at 20 fps the higher fps makes sure it works on slower and lower end machines. I do wish that the judges would post up info on how each run went and what the average fps produced was so we could benchmark against something :P .