How slow is sorted TStringList really?
dk_sz
and I am doing 25 search for each add... (specifics
can vary, e.g. more items and more inserts and/or searchs)
Should I be looking at a hashed TStringList?
As I never remove strings I suppose I could,
from time to time, create a hashed stringlist
- and always search that first? (thereby making
the sorted stringlist smaller and better for additions)
It is also worth mentioning that I do not know
the counts before-hand. Items may only be 1000 (but then
speed does not matter much) or perhaps even 100,000.
best regards
Thomas Schulz
Roy Lambert
When you start getting to those numbers I'd look at a memory table - kbMemoryTable or DBISAM. Slightly bigger footprint but better facilities.
Roy Lambert
dk_sz
> When you start getting to those numbers I'd look at a memory table -
> kbMemoryTable or DBISAM.
Well, I need no more functionality! :-)
It is merely speed that has my interest :-)
It is always the same "key" (a webaddress url)
-- data is located in the associated "object".
So I just need as fast a possible
search/add combination (but not delete).
That should either be a hash or sorted
list I think -- perhaps a combination?
best regards
Thomas Schulz
John Herbster
"dk_sz" <dk...@hotmail.com> wrote
> If I have a sorted stringlist containing 10,000 items,
> and I am doing 25 search for each add...
DK,
Have you tried speed tests such as the following?
Rgds, JohnH
procedure TForm1.T_StringList_1_bClick(Sender: TObject);
var SL: TStringList; i,j,k,m,n: integer; s: string; c0,c1: Int64;
begin
n := StrToInt(Edit1.Text);
SL := TStringList.Create;
SL.Sorted := true;
SL.Duplicates := dupError;
c0 := GetCpuClockCycleCount;
For i := 0 to n-1 do begin
k := random(n);
s := IntToStr(k);
j := SL.IndexOf(s);
If j < 0
then SL.Add(s);
end;
c1 := GetCpuClockCycleCount;
SL.Free;
Memo1.Lines.Add(Format('n=%0.6D, CPU cycles=%0.12D',[n,(c1-c0)]));
end;
(*
n=000001, CPU cycles=000000007532
n=000010, CPU cycles=000000061672
n=000100, CPU cycles=000000765548
n=001000, CPU cycles=000012578184
n=010000, CPU cycles=000224181216
n=100000, CPU cycles=008762587452
*)
John Herbster
function GetCpuClockCycleCount: Int64;
{ Reads 64-bit TSC counter running at
CPU clock speed. From Torjei Kvinen }
asm
dw $310F // opcode for RDTSC
end;
Roy Lambert
I'd definitely look at an in-memory table, just for speed with large numbers, that is unless you feel like building your own b-tree indexing system <g>
Roy Lambert
Peter Below (TeamB)
> If I have a sorted stringlist containing 10,000 items,
> and I am doing 25 search for each add... (specifics
> can vary, e.g. more items and more inserts and/or searchs)
>
> Should I be looking at a hashed TStringList?
A hash table would certainly perform faster, both for additions and
searching. Do you need to iterate over the strings in sort order as
well? If yes, do you do that often or only rarely? If the latter i
would use a combination of hashtable and (unsorted) stringlist. The
hashtable is used for the searching, the stringlist is only sorted
before you need to iterate over it in sort order.
--
Peter Below (TeamB)
Don't be a vampire (http://slash7.com/pages/vampires),
use the newsgroup archives :
http://www.tamaracka.com/search.htm
http://groups.google.com
http://www.prolix.be
Peter Below (TeamB)
>
> When you start getting to those numbers I'd look at a memory table -
> kbMemoryTable or DBISAM. Slightly bigger footprint but better facilities.
But slower than a sorted stringlist in a search. BInary search in a sorted array
is pretty efficient and scales the same as search in a binary search tree
with the number of items.
dk_sz
> searching. Do you need to iterate over the strings in sort order as
Even if hitting collisions? As items are web urls collected under website
scan
I am most likely within 500 to 50,000 (speed only matters for high numbers)
> searching. Do you need to iterate over the strings in sort order as
> well? If yes, do you do that often or only rarely? If the latter i
Only once at the very end of website scan / crawl.
> would use a combination of hashtable and (unsorted) stringlist. The
Thanks for the suggestion! I have Julian's book (long time since
I have read it though), so I will use that as starting point unless
someone can recommend an efficient hash TStringList replacement.
best regards
Thomas Schulz
Brian Evans
CPU cycles/n would be useful as well. At 100 000 it works
out to 87625 per. While just over 10x the single n value
isn't that bad of an increase.
Brian Evans
John Herbster
"Brian Evans" <NOS...@rogers.com> wrote
> CPU cycles/n would be useful as well. ...
Brian, Good idea!
Best viewed with fixed width font like Courier:
N CPU Cycles Cyc/N Cyc/N/Log(N)
10 61,672 6,167 6,167
100 765,548 7,655 3,828
1,000 12,578,184 12,578 4,193
10,000 224,181,216 22,418 5,605
100,000 8,762,587,452 87,626 17,525
I guess somewhere before 100,000 something like
memory thrashing started.
Regards, JohnH
John Herbster
> CPU cycles/n would be useful as well. ...
So, I did. You might want to report your results,
if you see any difference at the 100000 run.
--JohnH
function GetCpuClockCycleCount: Int64;
asm dw $310F end; // RDTSC
procedure TForm1.T_StringListSort_1_bClick(Sender: TObject);
var SL: TStringList; i,j,k,m,n: integer; s: string; cc: Int64; a,b:
double;
begin
Memo1.Lines.Add(' N CPU_cyc Cyc/N Cyc/N/log2(N)');
N := 10;
Repeat
Screen.Cursor := crHourGlass;
Try
SL := TStringList.Create;
SL.Sorted := true;
SL.Duplicates := dupError;
cc := GetCpuClockCycleCount;
For i := 0 to n-1 do begin
k := random(n);
s := IntToStr(k);
j := SL.IndexOf(s);
If j < 0
then SL.Add(s);
end;
cc := GetCpuClockCycleCount - cc;
Finally
SL.Free;
Screen.Cursor := crDefault;
End;
a := cc/n; b := a/log2(n);
Memo1.Lines.Add(Format('%7D %11D %6.0F %6.0F',[n,cc,a,b]));
If N >= 100000
then Break;
N := N*10;
Until false;
(* Athlon/XP 512MB RAM Win2K D7
N CPU_cyc Cyc/N Cyc/N/log2(N)
10 47563 4756 1432
100 474025 4740 713
1000 7836078 7836 786
10000 136643600 13664 1028
100000 13869985345 138700 8351 *)
end;
Brian Evans
Changed to start N at 128 and double each time
and I get the following on a Pentium 640
(3.2ghz, 2mb cache):
(the #'s vary a lot between runs but the trend
and magnitude of the numbers stay the same)
N CPU_cyc Cyc/N Cyc/N/log2(N)
128 1238184 9673 1382
256 2981440 11646 1456
512 6931040 13537 1504
1024 16077520 15701 1570
2048 42520800 20762 1887
4096 86687696 21164 1764
8192 211857672 25862 1989
16384 549833088 33559 2397
32768 1423148704 43431 2895
65536 4183721400 63839 3990
131072 13352995192 101875 5993
Not a bad performance degradation curve but if
inserting so many items small decreases in the per N
cycle count would mean meaningful gains overall.
Brian Evans
Andrew
Andrew
eg:
uses FastCodeCompareTextUnit, FastCodeStrCompUnit;
TFastStringList = class(TStringList)
protected
function CompareStrings(const S1, S2: string): Integer; override;
end;
function TFastStringList.CompareStrings(const S1, S2: string): Integer;
begin
if CaseSensitive then
begin
if (S1 = '') then
begin
if (S2 = '') then
Result := 0
else
Result := -1;
end
else if (S2 = '') then
Result := 0
else
Result := StrCompFastcodeBlended(PChar(S1), PChar(S2));
end
else
Result := CompareTextFastcodeBlended(S1, S2);
end;
Alex
more accurate test
SL := TStringList.Create;
SL.Capacity := n; // Add this to avoid SL expansion due execution, it earn a
lot of time
Alex
"John Herbster" <herb-sci1_at_sbcglobal.net> wrote in message
news:445615cf$1...@newsgroups.borland.com...
John Herbster
"Alex" <zenc...@pivotcube.com> wrote
> ... but I suggest you to add next code ...
> SL.Capacity := n;
Good idea!
I will add it as an option, if I run the test again!
--JohnH
dk_sz
>> SL.Capacity := n;
>
> Good idea!
> I will add it as an option, if I run the test again!
But TStringList automatically increases capacity more
and more AFAIK? At least that is how I remember it.
best regards
Thomas
Alex
1 allocate new buffer (Old buffer + 50%),
2 call FastMove to copy data from old buffer
3 free old buffer
All operations take a time. So if you want to test SORTING you need to
minimize influence from memory reallocations, I think.
Just count, start size is 10, you want to insert 1,000,000 strings - how muc
reallocations it will take.
1. 10
2. 15
3. 22
4 33
...
?
"dk_sz" <dk...@hotmail.com> wrote in message
news:4457...@newsgroups.borland.com...
Wayne Niddery [TeamB]
>>> ... but I suggest you to add next code ...
>>> SL.Capacity := n;
>
> and more AFAIK? At least that is how I remember it.
Yes, but that's the point, it must reallocate memory constantly when adding
a lot of items. Setting capacity tells the TStringlist to allocate that much
up front and thus avoids all the reallocation and memory copies.
--
Wayne Niddery - Logic Fundamentals, Inc. (www.logicfundamentals.com)
RADBooks: http://www.logicfundamentals.com/RADBooks.html
"The only reason some people get lost in thought is because it's
unfamiliar territory." - Paul Fix
dk_sz
> much up front and thus avoids all the reallocation and memory copies.
Sure, but then the test does not mimic a case where
one does not know upfront the amount of items :-)
best regards
Thomas
John Herbster
"dk_sz" <dk...@hotmail.com> wrote
>> ... Setting capacity tells the TStringlist to allocate that much up front
>> and thus avoids all the reallocation ...
> Sure, but then the test does not mimic a case where
> one does not know upfront the amount of items :-)
No; but the programmer can program a guess, or maybe
even reuse the TStringList object w/o disposing of the
string and object pointer arrays.
--JohnH
Alex
about internal works. But if you expect a thousands items, you should know
about it. Even if you do not know real (precision) amount, you may use own
way based on your expectations.
For example I do not use embedded way, but make increment by 1000 pointers -
it will slowly than embedded but may save a lof of memory. For better
perfomance you may double capacity every time when it exceeded.
Better way - make test with and without capacity optimization and see
difference. It will ground to make decision - can you use it or you need to
find something else (B-Tree, Lists etc)
Alex
"dk_sz" <dk...@hotmail.com> wrote in message
news:4457...@newsgroups.borland.com...
Peter Below (TeamB)
>
> > A hash table would certainly perform faster, both for additions and
> > searching. Do you need to iterate over the strings in sort order as
>
> Even if hitting collisions?
Depends on how much collision you have, which in turn depends on the size of
the hash array storage and your hashing algorithm. This part can be tuned to
the problem, although finding the optimal hash function for a given set of
strings is more art than science <g>.
dk_sz
Hmm..... Interesting... Albeit... Does not support ANSI
as far as I recall... So wouldn't work with e.g. French? etc.
best regards
Thomas
Wayne Niddery [TeamB]
>
> Sure, but then the test does not mimic a case where
> one does not know upfront the amount of items :-)
Averages. If you know that *typically* there'll be at least x items loaded,
then set capacity to at least x. If x is exceeded, the Stringlist will
revert to reallocating as needed at that point.
--
Wayne Niddery - Logic Fundamentals, Inc. (www.logicfundamentals.com)
RADBooks: http://www.logicfundamentals.com/RADBooks.html
"Some see private enterprise as a predatory target to be shot, others
as a cow to be milked, but few are those who see it as a sturdy horse
pulling the wagon." - Winston Churchill
Jolyon Smith
says...
> dk_sz wrote:
> >
> > Sure, but then the test does not mimic a case where
> > one does not know upfront the amount of items :-)
>
> Averages. If you know that *typically* there'll be at least x items loaded,
> then set capacity to at least x. If x is exceeded, the Stringlist will
> revert to reallocating as needed at that point.
And the behvaiour that it "revert"s to can be quite illuminating when it
comes to choosing a useful initial capacity.
Behaviour is (as of D5 VCL source which is the most current I have to
hand) to set an initial capacity of 4, then to 8 then to 32 then to 64
then on each subsequent increment to 125% of current capacity.
So set a capacity of 1000, and you will need only two memory allocations
to get to a 1250 item list (the initial 1000 slot allocation and the
allocation to "grow" the capacity to 1250).
Allowing capacity to grow "as normal" would involve memory allocations
(which may of course be an alloc new block->copy block->free old block
sequence) at:
1st item
4th item
8th item
16th item
32nd item
64th item
80th item
100th item
125th item
195th item
244th item
305th item
381st item
476th item
596th item
745th item
931st item
1164th item
The final list capacity being 1455 items.
I would suggest that "averages" is not always the right approach to
choosing your list capacity. "Worst case" might be a better methodology
(in most circumstances where performance is a concern).
e.g. processing a set of input text files. On average your files might
contain only 1000 lines, but every now and then you get a file with
20,000 lines. If you set capacity for processing the average 1000 line
files, those 20,000+ line files will -really- hurt.
But having a list with capacity for 20,000 lines, even if it only ever
processes 1000 lines, will not be a problem (unless you are VERY
constrained by memory).
+0.02
--
Jolyon Smith
dk_sz
> as far as I recall... So wouldn't work with e.g. French? etc.
But thinking more about it (and asking in winsock) ...
urls are (with a rare exception) always US/UK ascii...
And since I am merely using this as a search "already
there?" list... Ascii stuff ought'a be fine... EVEN if I
were to encounter e.g. multibyte characters...
Then again, it is over 6am and I still
haven't slept so maybe I am rambling :-)
best regards
Thomas
dk_sz
> of items and start with that as the default capacity.
OK, I estimate that I will usually have
2 * 50 to 200 * 100,000 searches :-)
However... It depends, because if I include
the auxillerary stuff... (smaller stringlists) ...
One can probably double those numbers.
I will most likely have between:
200 and 40,000,000 searches.
Anyways, I was just making a general point.
I like stuff that scales well. But perhaps
I missed what was being tested
(I realize most have different needs from mine).
best regards
Thomas
Andrew
One other point is that the fastcode project do have routines for ANSI character sets (not sure about Unicode yet) so if you really want ...
Andrew