[plt-dev] range mini benchmark

On Sat, May 2, 2009 at 7:37 PM, namekuseijin <namekuseijin at gmail.com> wrote:
> Seems to me you're measuring consing.  I'm not really a fan of
> creating intermediary lists, I enjoy iterators more.  I have my own
> version of range, here simplified:
>
> ; returns an iterator for given range
> ;  given an initial result and a reducer function, will apply it each iteration
> (define (range from to)
>  (let ((> (if (> from to) < >))
>        (+ (if (> from to) - +)))
>    (lambda (res reducer)
>      (let loop ((i from) (r res))
>        (if (> i to) r
>            (loop (+ i 1) (reducer i r)))))))
>
> So, I can:
> ((range 10 1) '() cons)
> to create a list from 1 to 10 (cons builds a reverse list)
>
> or simply
> ((range 1 10) 0 +)
> to sum it up, without creating intermediary lists.
>
> or even
> ((range 1 10) 0 (lambda (i o) (if (odd? i) (+ i o) o)))
> to sum only the odds.  Of course, I have a version of filter to work
> with iterators. :)
>
> I added it to the benchmark by adding a little twist:  it now builds a
> list by consing too.
>
> (define (range-nmk from to)
>  (let ((> (if (> from to) < >))
>        (+ (if (> from to) - +)))
>    ((lambda (res reducer)
>      (let loop ((i from) (r res))
>        (if (> i to) r
>            (loop (+ i 1) (reducer i r))))) '() cons)))
>
>
> (define ranges (list range-rbl range-ibl range-seq range-nmk))
>
> on DrScheme:
> (for ((j (in-range 5))) (range 0 1000000))
> range-rbl: cpu time: 852 real time: 851 gc time: 332
> range-ibl: cpu time: 1332 real time: 1334 gc time: 88
> range-seq: cpu time: 1052 real time: 1055 gc time: 212
> range-nmk: cpu time: 704 real time: 706 gc time: 80
>
> (for ((j (in-range 50))) (range 0 100000))
> range-rbl: cpu time: 588 real time: 585 gc time: 68
> range-ibl: cpu time: 1300 real time: 1301 gc time: 20
> range-seq: cpu time: 908 real time: 908 gc time: 72
> range-nmk: cpu time: 652 real time: 653 gc time: 20
>
> (for ((j (in-range 500))) (range 0 10000))
> range-rbl: cpu time: 544 real time: 544 gc time: 28
> range-ibl: cpu time: 1300 real time: 1297 gc time: 12
> range-seq: cpu time: 864 real time: 863 gc time: 24
> range-nmk: cpu time: 644 real time: 644 gc time: 12
>
> (for ((j (in-range 5000))) (range 0 1000))
> range-rbl: cpu time: 544 real time: 543 gc time: 20
> range-ibl: cpu time: 1300 real time: 1300 gc time: 8
> range-seq: cpu time: 864 real time: 864 gc time: 20
> range-nmk: cpu time: 648 real time: 645 gc time: 8
>
> (for ((j (in-range 50000))) (range 0 100))
> range-rbl: cpu time: 568 real time: 565 gc time: 20
> range-ibl: cpu time: 1328 real time: 1328 gc time: 12
> range-seq: cpu time: 900 real time: 902 gc time: 20
> range-nmk: cpu time: 664 real time: 664 gc time: 12
>
> The pure recursive way beats it, except for a fairly high range.  I
> wonder why...
>

heh, should not have benchmarked it while on DrScheme environment:

namekuseijin at nameku:~/dev/scheme$ mzc range-bench.scm
namekuseijin at nameku:~/dev/scheme$ mzscheme range-bench.scm
(for ((j (in-range 5))) (range 0 1000000))
range-rbl: cpu time: 728 real time: 732 gc time: 452
range-ibl: cpu time: 416 real time: 424 gc time: 236
range-seq: cpu time: 1224 real time: 1285 gc time: 440
range-nmk: cpu time: 488 real time: 503 gc time: 236

(for ((j (in-range 50))) (range 0 100000))
range-rbl: cpu time: 456 real time: 458 gc time: 196
range-ibl: cpu time: 204 real time: 207 gc time: 40
range-seq: cpu time: 952 real time: 1016 gc time: 180
range-nmk: cpu time: 292 real time: 303 gc time: 36

(for ((j (in-range 500))) (range 0 10000))
range-rbl: cpu time: 284 real time: 285 gc time: 32
range-ibl: cpu time: 180 real time: 181 gc time: 8
range-seq: cpu time: 804 real time: 851 gc time: 28
range-nmk: cpu time: 260 real time: 271 gc time: 12

(for ((j (in-range 5000))) (range 0 1000))
range-rbl: cpu time: 268 real time: 269 gc time: 12
range-ibl: cpu time: 176 real time: 176 gc time: 8
range-seq: cpu time: 836 real time: 836 gc time: 8
range-nmk: cpu time: 268 real time: 265 gc time: 4

(for ((j (in-range 50000))) (range 0 100))
range-rbl: cpu time: 276 real time: 274 gc time: 8
range-ibl: cpu time: 180 real time: 181 gc time: 4
range-seq: cpu time: 856 real time: 858 gc time: 20
range-nmk: cpu time: 272 real time: 271 gc time: 8

What's the cause of so much difference?  Going through mzscheme, the
manually named-let-written build-list really beats the socks of
builtin build-list!