Mailing List Archive: 49091 messages
  • Home
  • Script library
  • AltME Archive
  • Mailing list
  • Articles Index
  • Site search

[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 ]