Re: I need the fastest routine
Q Correll
Thanks.
I hadn't realized that the Delphi optimizer was that good these days. <g>
--
Q
07/05/2008 11:43:37
XanaNews Version 1.17.5.7 [Q's Salutation mod]
Rudy Velthuis [TeamB]
> Rudy,
>
> Thanks.
>
> I hadn't realized that the Delphi optimizer was that good these days.
> <g>
I doesn't surprise me one bit. The optimizer does this since early
versions (4 or 5, perhaps even earlier) already.
--
Rudy Velthuis [TeamB] http://www.teamb.com
"Wit makes its own welcome and levels all distinctions."
-- Ralph Waldo Emerson (1803-1882)
Q Correll
| I doesn't surprise me one bit. The optimizer does this since early
| versions (4 or 5, perhaps even earlier) already.
It's been quite a few years since I had a need to look deep into the
compiled executable code to see what the compiler and optimizer had done.
<g>
--
Q
07/05/2008 16:46:11
Rudy Velthuis [TeamB]
> Rudy,
>
> > I doesn't surprise me one bit. The optimizer does this since early
> > versions (4 or 5, perhaps even earlier) already.
>
> It's been quite a few years since I had a need to look deep into the
> compiled executable code to see what the compiler and optimizer had
> done. <g>
One doesn't need the need to do that. <g>
--
Rudy Velthuis [TeamB] http://www.teamb.com
"I criticize by creation - not by finding fault."
-- Cicero (106-43 B.C.)
Rudy Velthuis [TeamB]
> MinMaxTest2.dpr
I get values close to:
0.18 (using pointers)
0.18 (using indices)
0.30 (indices, but fetching value once)
0.19 (unrolled loops)
I wonder why routine 2 is so slow here, but not when I use RDTSC (and
don't change priority, since that is not a normal scenario, IMO).
FWIW, on my machine (Core 2 Quad, Vista Home Premium), the effect of
SetRealPriority is nada. I commented out the code in the two routines,
and nothing changed.
--
Rudy Velthuis [TeamB] http://www.teamb.com
"Behind every successful man is a woman, behind her is his wife."
-- Groucho Marx
Nenad Trkulja
>I wonder why routine 2 is so slow here
Value := aArray[I]; <<< probably because of this assignment
if Value > aMax then
aMax := Value;
if Value < aMin then
aMin := Value;
> but not when I use RDTSC and don't change priority
Maybe the OS desides to switch to another thread at that moment? No clues.
>since that is not a normal scenario, IMO
You are right, microbenchmarking is not always a good idea.
MinMaxTest3 values for Athlon 64 X2 4400+ // A[I] := I; - sorted
Original code
0,630671 s
Using pointers
0,270799 s
Using indices
0,267431 s
Reading array value once
0,275809 s
Nenad Trkulja - loop unrolling
0,259742 s
Hubert Seidel - local min and max
0,198207 s
Pierre le Riche - boolean trick
0,449036 s
Trkulja/Seidel - loop unrolling and local min and max
0,184594 s
//Random(10 * 1000 * 1000);
Original code
0,629651 s
Using pointers
0,268593 s
Using indices
0,266845 s
Reading array value once
0,276029 s
Nenad Trkulja - loop unrolling
0,260110 s
Hubert Seidel - local min and max
0,198036 s
Pierre le Riche - boolean trick
0,448887 s
Trkulja/Seidel - loop unrolling and local min and max
0,184434 s
Rudy Velthuis [TeamB]
> Rudy Velthuis [TeamB] wrote:
>
> > I wonder why routine 2 is so slow here
>
> Value := aArray[I]; <<< probably because of this assignment
> if Value > aMax then
> aMax := Value;
> if Value < aMin then
> aMin := Value;
Why?
I just posted my values.
The fact that the random test gives similar values as the sorted test
comes from the fact that in the sorted array, it immediately finds the
min value and won't do any assignment to iMin anymore, while it must
assign to iMax for each of the array values. The random array will have
more assignments for the iMin value, but fewer for the iMax value.
These seem to equal each other out, more or less.
--
Rudy Velthuis [TeamB] http://www.teamb.com
"I failed to make the chess team because of my height."
-- Woody Allen
miab
> Rudy Velthuis [TeamB] wrote:
>
>>
>>> Rudy Velthuis [TeamB] wrote:
>>>
>>
>> MinMaxTest3.dpr
>
> MinMaxTest4.dpr
Why not?:
procedure MinMaxArray4_1(const aArray: array of Integer;
out aMax, aMin: Integer);
var
I: Integer;
Value: Integer;
iMin, iMax: Integer;
begin
iMax := MinInt;
iMin := MaxInt;
for I := 0 to High(aArray) do
begin
Value := aArray[I];
if Value > iMax then
iMax := Value else //<-- else
if Value < iMin then
iMin := Value;
end;
aMax := iMax;
aMin := iMin;
end;
miab
Rudy Velthuis [TeamB]
> Why not?:
>
> procedure MinMaxArray4_1(const aArray: array of Integer;
> out aMax, aMin: Integer);
> var
> I: Integer;
> Value: Integer;
> iMin, iMax: Integer;
> begin
> iMax := MinInt;
> iMin := MaxInt;
> for I := 0 to High(aArray) do
> begin
> Value := aArray[I];
> if Value > iMax then
> iMax := Value else //<-- else
> if Value < iMin then
> iMin := Value;
> end;
> aMax := iMax;
> aMin := iMin;
> end;
If the minimum and maximum are the same (say, an array [3, 3, 3] ),
that will never set iMin.
--
Rudy Velthuis [TeamB] http://www.teamb.com
"I have spoken many a word, therefore, it is fact."
-- Eric the Verbose
miab
And now?
procedure MinMaxArray4_2(const aArray: array of Integer;
out aMax, aMin: Integer);
var
I: Integer;
Value: Integer;
iMin, iMax: Integer;
begin
iMax := aArray[0];
iMin := iMax;
for I := 1 to High(aArray) do
begin
Value := aArray[I];
if Value > iMax then
iMax := Value else //<-- else
if Value < iMin then
iMin := Value;
end;
aMax := iMax;
aMin := iMin;
end;
miab
Rudy Velthuis [TeamB]
> And now?
>
> procedure MinMaxArray4_2(const aArray: array of Integer;
> out aMax, aMin: Integer);
> var
> I: Integer;
> Value: Integer;
> iMin, iMax: Integer;
> begin
> iMax := aArray[0];
> iMin := iMax;
> for I := 1 to High(aArray) do
> begin
> Value := aArray[I];
> if Value > iMax then
> iMax := Value else //<-- else
> if Value < iMin then
> iMin := Value;
> end;
> aMax := iMax;
> aMin := iMin;
> end;
Worth a try.
--
Rudy Velthuis [TeamB] http://www.teamb.com
"Humor is always based on a modicum of truth. Have you ever heard
a joke about a father-in-law?" -- Dick Clark
Q Correll
| One doesn't need the need to do that. <g>
No, not anymore. But,... there was a time... ;-)
--
Q
07/06/2008 09:55:48
Nenad Trkulja
> I'll post the latest to .attachments (MinMaxTest6.dpr)
MinMaxTest6 values:
--------------------
Athlon 64 X2 4400+
Clément Doss - original code
0,632462 s
Stig Johansen - using pointers
0,321077 s
Stig Johansen - using pointers (16/loop)
0,221324 s
Rudy Velthuis - using indices
0,279519 s
Rudy Velthuis - reading array value once
0,321571 s
Nenad Trkulja - loop unrolling (4/loop)
0,233353 s
Hubert Seidel - local min and max
0,324099 s
Pierre le Riche - boolean trick
0,456405 s
Trkulja/Seidel - loop unrolling and local min and max
0,171004 s
Hubert Seidel - BASM v4
0,186529 s
-----------------------------------------------------------------
P4 3.4
Clément Doss - original code
1,078392 s
Stig Johansen - using pointers
0,211856 s
Stig Johansen - using pointers (16/loop)
0,105763 s
Rudy Velthuis - using indices
0,216428 s
Rudy Velthuis - reading array value once
0,213586 s
Nenad Trkulja - loop unrolling (4/loop)
0,176850 s
Hubert Seidel - local min and max
0,160644 s
Pierre le Riche - boolean trick
0,692411 s
Trkulja/Seidel - loop unrolling and local min and max
0,124645 s
Hubert Seidel - BASM v4
0,309205 s
-------------------------------------------------------------------
Xeon 1.8 (2x Dual Cores)
Clément Doss - original code
1,464513 s
Stig Johansen - using pointers
0,389362 s
Stig Johansen - using pointers (16/loop)
0,321520 s
Rudy Velthuis - using indices
0,394475 s
Rudy Velthuis - reading array value once
0,388516 s
Nenad Trkulja - loop unrolling (4/loop)
0,346528 s
Hubert Seidel - local min and max
0,364836 s
Pierre le Riche - boolean trick
0,888160 s
Trkulja/Seidel - loop unrolling and local min and max
0,329946 s
Hubert Seidel - BASM v4
0,451858 s
---------------------------------------------------------------------
P3 1.0 (dual box)
Clément Doss - original code
4,121788 s
Stig Johansen - using pointers
2,105126 s
Stig Johansen - using pointers (16/loop)
1,239946 s
Rudy Velthuis - using indices
2,090043 s
Rudy Velthuis - reading array value once
2,094523 s
Nenad Trkulja - loop unrolling (4/loop)
2,001213 s
Hubert Seidel - local min and max
2,002496 s
Pierre le Riche - boolean trick
4,155704 s
Trkulja/Seidel - loop unrolling and local min and max
1,913412 s
Hubert Seidel - BASM v4
1,962977 s
-----------------------------------------------------------------
Pentium M 1.6
Clément Doss - original code
1,791784 s
Stig Johansen - using pointers
0,489965 s
Stig Johansen - using pointers (16/loop)
0,343560 s
Rudy Velthuis - using indices
0,490542 s
Rudy Velthuis - reading array value once
0,490591 s
Nenad Trkulja - loop unrolling (4/loop)
0,412156 s
Hubert Seidel - local min and max
0,547418 s
Pierre le Riche - boolean trick
1,702197 s
Trkulja/Seidel - loop unrolling and local min and max
0,381433 s
Hubert Seidel - BASM v4
0,426382 s
Rudy Velthuis [TeamB]
> Rudy Velthuis [TeamB] wrote:
>
> > I'll post the latest to .attachments (MinMaxTest6.dpr)
>
> MinMaxTest6 values:
Thanks.
--
Rudy Velthuis [TeamB] http://www.teamb.com
"I hope life isn't a big joke ... because I don't get it."
-- Unknown
W. van Wezel
"Rudy Velthuis [TeamB]" <newsg...@rvelthuis.de> wrote in message
news:xn0fsdqo1hdh1p...@rvelthuis.de...
> Somehow I can't read the .dpr. Must try saving the message and using
> winzip or IzArc to read it.> "He managed to stupid himself right into the White House."
> -- Charles Appel about George W. Bush
W. van Wezel
Wout
"Rudy Velthuis [TeamB]" <newsg...@rvelthuis.de> wrote in message
news:xn0fsbtntfq812...@rvelthuis.de...
> Rudy Velthuis [TeamB] wrote:
>
>> I'll post my test to .attachments.
Rudy Velthuis [TeamB]
winzip or IzArc to read it.
--
Rudy Velthuis [TeamB] http://www.teamb.com
"He managed to stupid himself right into the White House."
Rudy Velthuis [TeamB]
Original code
0,552489 s min: 782 max: 999999032
Using threads
0,050376 s min: 782 max: 999999032
That is pretty impressive. I wonder how well this works in single core
machines.
--
Rudy Velthuis [TeamB] http://www.teamb.com
"Attention to health is life's greatest hindrance."
-- Plato (427-347 B.C.)
Rudy Velthuis [TeamB]
--
Rudy Velthuis [TeamB] http://www.teamb.com
"If you think it's simple, then you have misunderstood the
problem." -- Bjarne Stroustrup [lecture at Temple U., 11/25/97]
IvKo
| Original code
| 0,552489 s min: 782 max: 999999032
|
| Using threads
| 0,050376 s min: 782 max: 999999032
|
| That is pretty impressive. I wonder how well this works in single core
| machines.
|
| --
| Rudy Velthuis [TeamB] http://www.teamb.com
|
| "Attention to health is life's greatest hindrance."
| -- Plato (427-347 B.C.)
HP Omnibok 4400 / Intel Pentium 4 / 2GHz / 2GB RAM
== MinMaxTestThreads.dpr ==
Original code
2,019969 s min: 87 max: 999996313
Using threads
0,323841 s min: 87 max: 999996313
== MinMaxTest6.dpr ==
Cl?ment Doss - original code
1,986093 s
Stig Johansen - using pointers
0,360391 s
Stig Johansen - using pointers (16/loop)
0,302527 s
Rudy Velthuis - using indices
0,381953 s
Rudy Velthuis - reading array value once
0,362320 s
Nenad Trkulja - loop unrolling (4/loop)
0,320319 s
Hubert Seidel - local min and max
0,317887 s
Pierre le Riche - boolean trick
0,809712 s
Trkulja/Seidel - loop unrolling and local min and max
0,308982 s
Hubert Seidel - BASM v4
0,450417 s
Regards,
IvKo
Rudy Velthuis [TeamB]
> HP Omnibok 4400 / Intel Pentium 4 / 2GHz / 2GB RAM
Is that multithreading? I assume not?
--
Rudy Velthuis [TeamB] http://www.teamb.com
"To understand a man you should walk a mile in his shoes. If what
he says still bothers you that's ok because you'll be a mile away
from him and you'll have his shoes." -- Unknown
IvKo
| IvKo wrote:
|
| > HP Omnibok 4400 / Intel Pentium 4 / 2GHz / 2GB RAM
|
| Is that multithreading? I assume not?
|
| --
| Rudy Velthuis [TeamB] http://www.teamb.com
|
It is a single core CPU, old (5-6 years old) notebook. I just compile (D6)
the projects and run compiled applications..
IvKo
Philipp Pammler
the results when running the program on my machine:
cpu: Q9300 (4x2,67GHz, 2x6mb lvl2 cache)
ram: 8GB
Original code
0,501592 s min: 613 max: 999998308
Using threads
0,038725 s min: 613 max: 999998308
regards,
philipp
Q Correll
| That is pretty impressive. I wonder how well this works in single core
| machines.
3.4 GHz P4 Hyperthreading (Dell Optiplex GX520)
Original code 1.107673 s min: 782 max: 999999949
Using threads 0.298736 s min: 782 max: 999999949
2.2 GHz Core2/Duo (Dell Precision M6300)
Original code 0.298736 s min: 782 max: 999998733
Using threads 0.133408 s min: 782 max: 999998733
Both tests run in the IDE.
--
Q
07/07/2008 09:40:57
Rudy Velthuis [TeamB]
> Rudy,
>
> > That is pretty impressive. I wonder how well this works in single
> > core machines.
>
> 3.4 GHz P4 Hyperthreading (Dell Optiplex GX520)
>
> Original code 1.107673 s min: 782 max: 999999949
>
> Using threads 0.298736 s min: 782 max: 999999949
>
> 2.2 GHz Core2/Duo (Dell Precision M6300)
>
> Original code 0.298736 s min: 782 max: 999998733
>
> Using threads 0.133408 s min: 782 max: 999998733
>
> Both tests run in the IDE.
I see enormous differences. I don't mean in overall speed, but in
speeds relative to each other. Of course the threading model will work
better for multiple core machines or hyperthreading CPUs, but this is
very interesting. Why is the orginal code so fast on the 2.2 GHz Core 2
Duo, I wonder.
--
Rudy Velthuis [TeamB] http://www.teamb.com
"If electricity comes from electrons, does that mean that
morality comes from morons?" -- Unknown
Q Correll
| Why is the orginal code so fast on the 2.2 GHz Core 2 Duo, I wonder.
I had the same wonder.
I don't have a good profiler that might be able to shed some light as to
why.
--
Q
07/07/2008 14:19:22
Q Correll
[Second reply.]
| Why is the orginal code so fast on the 2.2 GHz Core 2
| Duo, I wonder.
I think the speed calcs may not be correct when run using F9 in the IDE.
I just re-ran the .exe directly and got the following results:
2.2 GHz Core2/Duo (Dell Precision M6300)
Original code 0.537450 s min: 782 max: 999999949
Using threads 0.077437 s min: 782 max: 999999949
I get slightly varying results each time it runs. The above results were
the first run of the executable.
--
Q
07/07/2008 14:23:05
Rudy Velthuis [TeamB]
> Rudy,
>
> [Second reply.]
>
> > Why is the orginal code so fast on the 2.2 GHz Core 2
> > Duo, I wonder.
>
> I think the speed calcs may not be correct when run using F9 in the
> IDE.
That could be.
--
Rudy Velthuis [TeamB] http://www.teamb.com
"A low voter turnout is an indication of fewer people going to
the polls." -- George W. Bush
Q Correll
3.4 GHz P4 Hyperthreading:
Original code
5.443988 s min: 599 max: 999997361
Using threads / Hubert Seidel - local min and max
0.936184 s min: 599 max: 999997361
Using threads / Stig Johansen - using pointers (16/loop)
0.559328 s min: 599 max: 999997361Original code
2.2 GHz Core2/Duo:
Original code
4.229453 s min: 747 max: 999999815
Using threads / Hubert Seidel - local min and max
0.392567 s min: 747 max: 999999815
Using threads / Stig Johansen - using pointers (16/loop)
0.288125 s min: 747 max: 999999815
Both run from a Command Box using the .exe.
--
Q
07/07/2008 16:50:06
Eric Grange
You get a significant overhead per thread created when running from the
IDE (unless you turn off debugging completely).
Eric
Rudy Velthuis [TeamB]
I usually run such things without debugging, second item in the Run
menu.
--
Rudy Velthuis [TeamB] http://www.teamb.com
"Anything that is too stupid to be spoken is sung."
-- Voltaire (1694-1778)
Q Correll
| You get a significant overhead per thread created when running from the
IDE (unless you turn off debugging completely).
Thanks.
That's kind of what I thought. And why I started running the tests from a
Command Box.
--
Q
07/08/2008 15:25:29
Philipp Pammler
1 mil. random numbers test
0,483280s 0 9999982 Original
0,156911s 0 9999982 Original - optimized
0,179350s 0 9999982 Using pointers
0,119460s 9999982 0 Using pointers (8/loop) !!! BUG !!!
0,207864s 0 9999982 Using indices
0,292992s 0 9999982 Reading array value once
0,216456s 0 9999982 Nenad Trkulja - loop unrolling
0,133787s 0 9999982 Hubert Seidel - local min and max
0,505553s 0 9999982 Pierre le Riche - boolean trick
0,140752s 0 9999982 Trkulja/Seidel - loop unrolling and local min
and max
0,125380s 0 9999982 Gilberto Saraiva 8 ASM
0,126354s 0 9999982 Gilberto Saraiva 16 ASM
0,158094s 0 9999982 Hubert Seidel ASM
0,227625s 0 9999982 Hubert Seidel 8 PAS + ASM !!! BUG !!!
0,136967s 0 9999982 Hubert Seidel ASM V1
0,241751s 0 9999982 Hubert Seidel ASM V2
0,160158s 0 9999982 Hubert Seidel ASM V3
0,193075s 0 9999982 Hubert Seidel ASM Rollup 8
0,484654s 0 9999982 Clement Doss PAS 1
0,156519s 0 9999982 Clement Doss PAS 2
0,178901s 0 9999982 Sasa Zeman - pointers PAS
0,193256s 0 9999982 Sasa Zeman - indices (1) for PAS
0,248238s 0 9999982 Sasa Zeman - indices (2) while PAS
0,178639s 0 9999982 Sasa Zeman - indices (3) while PAS
0,241915s 0 9999982 Sasa Zeman - indices (4) while local 4 PAS
0,191636s 0 9999982 Sasa Zeman - indices (5) while local 8 PAS
0,219436s 0 9999982 Sasa Zeman - indices (6) while local 16 PAS
started from outside the ide
cpu: 4*2.50 GHz (Q9300)
ram: 8192 MB (DDR2 800MHz)
os: vista64 business sp1
regards
philipp
Sasa Zeman
> i unno if you still need sum numbers :)
Thank you. It is interesting only informative. I have no time for further
development nor to improve functions.
> started from outside the ide
> cpu: 4*2.50 GHz (Q9300)
> ram: 8192 MB (DDR2 800MHz)
> os: vista64 business sp1
This is with or witout maximum priority set (functions from SZTimer)?
If test is provided with maximim priority, problem can be in measuring time
for any function, especially outside (the first and the last).
If compiled and run with setting maximum priority, diffrence is probably
related with different CPUs. BTW, I compiled it with D7, started outside
the ide and os is W2K. Results are prosted in BASM group.
Hubert Seidel
"Sasa Zeman" <sas...@mail.ru> schrieb im Newsbeitrag
news:4883...@newsgroups.borland.com...
> MinMaxTest6.dpr
I can't send with attachments :-(
Outlook Express konnte den Beitrag nicht bereitstellen. Betreff 'Re: I need
the fastest routine', Konto: 'news.t-online.de', Server: 'news.t-online.de',
Protokoll: NNTP, Serverantwort: '441 437 Binary in non-binary group ',
Port: 119, Secure (SSL): Nein, Serverfehler: 441, Fehlernummer: 0x800CCCA9
)
MinMaxTest7 (split functions into separate libraries) with some increments
based on MinMaxTest6.
download possible http://www.hubert-seidel.eu/downloads/minmaxarray.zip
mfg.
Herby
--
http://www.hubert-seidel.de
Pieter Zijlstra
> I can't send with attachments :-(
> Outlook Express konnte den Beitrag nicht bereitstellen. Betreff 'Re:
> I need the fastest routine', Konto: 'news.t-online.de', Server:
> 'news.t-online.de', Protokoll: NNTP, Serverantwort: '441 437 Binary
> in non-binary group ', Port: 119, Secure (SSL): Nein, Serverfehler:
> 441, Fehlernummer: 0x800CCCA9 )
>
You seem to be posting on the news server of t-online you should be
able to post attachments when you connect directly to the CodeGear news
server
news:\\newsgroups.codegear.com\borland.public.attachments
--
Pieter
David J Taylor
> MinMaxTest6.dpr
Thanks for that, but it fails to compile - it needs SZtimer. It would be
better to include this in the Zip file rather than make people go and
chase around for it.
W h y i s i t a l l d o u b l e - s p a c e d v e r t i ca l l
y?
David
Sasa Zeman
> Thanks for that, but it fails to compile - it needs SZtimer. It would be
> better to include this in the Zip file rather than make people go and
> chase around for it.
You are welcome.
I simply have had no time for that, but have nothing agains to be included
in the zip. I simply use SZTimer all the time when need small interval
benchmarking.
> W h y i s i t a l l d o u b l e - s p a c e d v e r t i ca l l
> y?
It seems the source was vasted by KNode parser (Linux news reader clien).
David J Taylor
Thanks, Sasa. I did get the extra unit, and the source code compiles and
runs correctly. Sorry to hear about the Linux newsreader problems.
Cheers,
David
David J Taylor
> include all is necessary for compilation. No point for futher
> development, BTW.
Thanks,
David
Hubert Seidel
"Sasa Zeman" <sas...@mail.ru> schrieb im Newsbeitrag
news:4887...@newsgroups.borland.com...
> David J Taylor wrote:
>
> > Thanks, Sasa. I did get the extra unit, and the source code compiles
and
> > runs correctly. Sorry to hear about the Linux newsreader problems.
>
> This is a bit better version MinMaxTestSZ (based on MinMaxTest6) and
include
> all is necessary for compilation. No point for futher development, BTW.
Thanks a lot. Please to fix the array-initialization "step down". It works
as "step up".