Benchmarking alternatives
[1/4] from: joel:neely:fedex at: 6-Nov-2001 15:49
Hi, all,
The comment was made a little while back (my apologies for not
taking the time to track down the source) suggesting that EITHER
would be probably be faster than IF/ELSE. Since I've been in a
benchmarking mode lately, I went ahead and tackled that one...
Based on a test of 100_000_000 iterations, the results seem fairly
stable. I repeated the same suite of tests for two blocks (one
empty and the other rather trivial), to try to factor out the
time required for actual control function evaluation independent
of the time for the controlled expression. The expression schemata
in the left column were iterated via LOOP for the two blocks above
the second and third columns, which give raw times.
actual blocks
----------------
Schemata [] [v: 1]
----------------------- ------- -------
[?] 3.145 22.753
[do [?]] 66.615 84.832
[either true [?] [?]] 93.134 114.074
[if/else true [?] [?]] 101.686 124.398
[either false [?] [?]] 92.683 114.094
[if/else false [?] [?]] 101.857 124.339
Subtracting out the various bits of overhead, these numbers support
the following conclusions about performance:
1) Neither decision function (EITHER or IF/ELSE) is biased in favor
of a true or false condition.
2) EITHER takes approximately 35%-40% more time than DO for the same
evaluated (controlled) block.
3) IF/ELSE takes approximately 10% more time than EITHER.
While still in the benchmarking frame of mind, I pondered the fact
that one can set a word to a block and then use that word wherever
that block is required (e.g., LOOP numvar blkvar). One can also:
* cause the block to be evaluated with DO (e.g., DO blkvar),
* convert the block to a PAREN! value (which sort of automagically
DOes itself), or
* use the block as the body of a parameterless function with no
local variables (as in DOES).
Hmmm... four different ways to do the same thing? Let's see how
they compare in performance!
As before, there are several schemata, which can be tested with
various block values to separate the cost of the schema from the
cost of the controlled expression(s). The timings are as follows:
actual blocks
---------------------------
Schemata [] [v: 1] [v: v + 1]
---------- ------ ------- ----------
[?] 3.105 22.753 57.413
[do [?]] 69.069 85.713 121.504
(?) 15.062 35.090 76.951
func [][?] 31.385 49.181 90.390
Again subtracting out the various overheads, we find substantial amounts
of variation. I probably need to run a much longer test, and try some
other blocks to try to track down the variation. However, at a first
glance, we find that:
1) On average, DOing a block takes about four and a half times as long
as evaluating a paren constructed from the same block.
2) On average, evaluating a function (from DOES) takes about twice the
amount of time as evaluating an equivalent paren.
Conclusion? Instead of writing (for expression re-use)
bv: [...some expressions...]
...
... do bv ...
or
dv: does [...some expressions...]
...
... dv ...
we would prefer to write
pv: to-paren [...some expressions...]
...
... pv ...
if speed is of the essence.
-jn-
--
This sentence contradicts itself -- no actually it doesn't.
-- Doug Hofstadter
joel<dot>neely<at>fedex<dot>com
[2/4] from: greggirwin:mindspring at: 6-Nov-2001 15:27
WOW! Great information Joel!
[3/4] from: ryanc:iesco-dms at: 6-Nov-2001 16:31
Good find Joel. Do you know of a way I can take advantage of this gain
inside a block?
>> blk: []
== []
>> append/only blk to-paren [1 + 1]
== [(1 + 1)]
>> b/1
== (1 + 1)
>> append/only blk does [1 + 1]
== [(1 + 1) func [][1 + 1]]
>> b/2
== 2
>>
--Ryan
[4/4] from: joel:neely:fedex at: 6-Nov-2001 14:54
Ryan Cole wrote:
> ... Do you know of a way I can take advantage of this gain
> inside a block?
<<quoted lines omitted: 9>>
> == 2
> >>
(I assume you meant to use BLK instead of B, which interestingly
seems to be synonymous??? Oh, well, back to your question...)
I don't know any way to get the paren evaluated without some
additional overhead, which (of course) defeats the whole idea.
Obviously, given
>> blk: []
== []
>> append/only blk to-paren [1 + 1]
== [(1 + 1)]
>> append/only blk does [2 + 2]
== [(1 + 1) func [][2 + 2]]
one could use any of the following
>> reduce blk
== [2 4]
or
>> do blk/1
== 2
or, oddly enough,
>> x: blk/1
== (1 + 1)
>> x
== 2
Maybe someone else has a trick or two that can help here...
Meanwhile, my target was the kind of thing where one constructs or
selects a block to be DOne later, or uses such a block to build
a DOES function. A dinky example might help illustrate...
Consider the task of summing up the reciprocals of some positive
integers *or* summing the reciprocals of their squares (depending
on the presence of a switch). The brute-force solution
tally-inside: func [limit [integer!] /squares /local t] [
n: t: 0
while [n < limit] [
n: n + 1
either squares [
t: 1.0 / n / n + t
][
t: 1.0 / n + t
]
]
t
]
keeps making the same decision over and over and over and ...
The first (commonly-seen) optimization is to move the decision
out of the loop by constructing/selecting a block to be repeated,
doing this prior to the beginning of the loop.
tally-outside: func [limit [integer!] /squares /local t incr] [
incr: either squares [[
t: 1.0 / n / n + t
]][[
t: 1.0 / n + t
]]
n: t: 0
while [n < limit] [n: n + 1 do incr]
t
]
This give a time savings of a few percent. OTOH, constructing a
paren to hold (and evaluate) the appropriate expression, as in:
tally-paren: func [limit [integer!] /squares /local t incr] [
incr: to-paren either squares [[
t: 1.0 / n / n + t
]][[
t: 1.0 / n + t
]]
n: t: 0
while [n < limit] [n: n + 1 incr]
t
]
saves more. Interestingly enough, using the paren for only a
*part* of the expression, as in:
tally-recip: func [limit [integer!] /squares /local t term] [
term: to-paren either squares [[ 1.0 / n / n ]][[ 1.0 / n ]]
n: t: 0
while [n < limit] [n: n + 1 t: term + t]
t
]
provides yet another competitive option.
Of course, I'm well aware that there are other ways to perform
this *particular* computation, but the point was to focus on how
to pull a decision out of a loop. I chose a simple example, not
because I couldn't think of other ways to do this piece of
arithmetic, but to illustrate the refactoring without bogging
down in a complicated example.
-jn-
--
It's amazing how polific Ibid was.
-- Amy Johnson
joel'dot'neely'at'FIX'PUNCTUATION'fedex'dot'com
Notes
- Quoted lines have been omitted from some messages.
View the message alone to see the lines that have been omitted