[REBOL] Re: Shamless request for improving function speed.
From: joel:neely:fedex at: 28-Mar-2002 7:34
Hi, Alan,
alan parman wrote:
> This group is really good at tweaking functions to make them
> faster.
>
While I have absolutely nothing to say on the subject of
cryptography ;-) your email reminded me of an interesting
question in REBOL data structure manipulation that I had
thought about some time ago. So I dusted off a few ideas
that I had left on a mental shelf and did a little bit of
benchmarking...
The REBOL data structure manipulation question is this:
What is a fast way to iterate through two series
values in parallel, cycling the shorter one as
needed, and producing a result that is some function
of corresponding pairs of values, one from each
series?
Interestingly enough, the fastest way seems to be to make
a new series, rather than updating the longer one in place,
as shown by the following test cases:
CYCLES0 - uses FOREACH to iterate across the first (assumed
to be the longer) argument, and explicitly plays
with the second series to cycle it through its positions.
CYCLES1 - uses FOREACH on the first/longer series, but uses
explicit indexing on the second/shorter one. The
mod-and-add-one
trick cycles an integer counter through
the set of values from one to the modulus.
CYCLES2 - uses explicit indexing on both series arguments.
All of the above variations create a new series to hold the
result, so...
CYCLES3 - modifies the first/longer series in place, rather
than taking up the storage for a modified copy.
8<----------begin code----------
cycles0: func [b0 [block!] b1 [block!] /local r] [
r: make block! length? b0
foreach a b0 [
insert tail r a + b1/1
if empty? b1: next b1 [b1: head b1]
]
r
]
cycles1: func [b0 [block!] b1 [block!] /local j y r] [
r: make block! length? b0
y: length? b1
j: 1
foreach a b0 [
insert tail r a + b1/:j
j: j // y + 1
]
r
]
cycles2: func [b0 [block!] b1 [block!] /local i j x y r] [
r: make block! length? b0
x: length? b0
y: length? b1
i: j: 1
while [i <= x] [
insert tail r b0/:i + b1/:j
i: i + 1
j: j // y + 1
]
r
]
cycles3: func [b0 [block!] b1 [block!] /local j y] [
y: length? b1
j: 1
forall b0 [
change b0 b0/1 + b1/:j
j: j // y + 1
]
b0
]
8<-----------end code-----------
The timings went as follows (with line-wrapping for email
formatting):
8<-------begin transcript-------
>> x: make block! 500000
for i 0 499999 1 [insert tail x i]
print length? x
500000
>> y: make block! 10
for i 0 9 1 [insert tail y i]
print length? y
10
>> t: now/time/precise z: cycles0 x y now/time/precise - t
== 0:00:30.65
>> t: now/time/precise z: cycles1 x y now/time/precise - t
== 0:00:25.43
>> t: now/time/precise z: cycles2 x y now/time/precise - t
== 0:00:33.28
>> t: now/time/precise z: cycles3 x y now/time/precise - t
== 0:00:40.86
>> copy/part z 50
== [0 2 4 6 8 10 12 14 16 18 10 12 14 16 18 20 22 24 26 28
20 22 24 26 28 30 32 34 36 38 30 32 34 36 38 40 42 44 46 48
40 42 44 46 ...
8<--------end transcript--------
Note that the longer series was made long enough to really
require some time (on a slower box, at least...), and the
shorter series was made short enough that its manipulation
was stressed (and so that the result could be examined by
eye for correctness).
My conclusions (based on preliminary testing only, the usual
disclaimers about benchmarks apply...) are as follows:
- Explicit indexing wins over series manipulation for the
shorter series.
- WHILE loses to FOREACH (duh. included for completeness).
- Preallocation is already known to be necessary for speed.
- Constructing a new series wins over modifying the original
series in place.
Of course, these tests were performed using blocks, so it is
only an assumption that the same performance trade-offs would
apply to other series types.
-jn-
--
; Joel Neely joeldotneelyatfedexdotcom
REBOL [] do [ do func [s] [ foreach [a b] s [prin b] ] sort/skip
do function [s] [t] [ t: "" foreach [a b] s [repend t [b a]] t ] {
| e s m!zauafBpcvekexEohthjJakwLrngohOqrlryRnsctdtiub} 2 ]
