I was reading the alternative implementation of reverse in
http://git.racket-lang.org/plt/blob/HEAD:/racket/collects/racket/private/reverse.rkt
and I thought that the “car” and “cdr” could be replaced by the
“unsafe” versions.
I tried a few changes:
* Use unsafe-car and unsafe-cdr
* Remove the eval-jit-enabled check, because parameters are slow.
(Perhaps it can be checked at compile-time instead of at run-time.)
* Use begin-encourage-inline because map.rkt uses it. (But I think
that begin-encourage-inline is not very useful in reverse.rkt.)
I compared the versions (program at the bottom) The program measure
10000 times, the time to do 100 reverses of a 10000 list.
fast-reverse 168.32 (modified version)
priv-reverse 169.13 (copy of reverse.rkt)
reverse 168.95 (original version)
values 109.77 (use values instead of reverse)
Average time of n=10000 runs, sigma~=15, sigma/sqrt(n)~=0.15
In this test, the new version is 0.4% faster, but if we subtract the
time of the “values” version the improvement is 1%.
If you find this useful, I can look at map.rkt.
Gustavo
;------ fast-reverse.rkt
(module reverse '#%kernel
(#%require '#%unsafe racket/private/performance-hint)
(#%provide alt-reverse)
(begin-encourage-inline
(define-values (alt-reverse)
(let-values ([(reverse)
(lambda (l)
(if (list? l)
(void)
(raise-argument-error 'reverse "list?" l))
(letrec-values ([(loop)
(lambda (a l)
(if (null? l)
a
(loop (cons (unsafe-car l)
a) (unsafe-cdr l))))])
(loop null l)))])
reverse))))
;--- time-reverse.rkt
#lang racket/base
(require (rename-in "private-reverse.rkt" (alt-reverse priv-reverse)))
(require (rename-in "fast-reverse.rkt" (alt-reverse fast-reverse)))
(define-syntax-rule (test-time proc msg)
(begin
(display (string-append "run:" msg ": "))
(time (begin
(display (for/sum ([k (in-range 100)])
(length (proc (for/list ([i (in-range 10000)]) i)))))
(display " ")))
(display (string-append "gc3:" msg ": 0 "))
(time
(collect-garbage)
(collect-garbage)
(collect-garbage)
)
))
(collect-garbage)
(collect-garbage)
(collect-garbage)
(for ([z (in-range 10000)])
(test-time values "values ")
(test-time reverse "reverse ")
(test-time priv-reverse "priv-reverse ")
(test-time fast-reverse "fast-reverse ")
_________________________
Racket Developers list:
http://lists.racket-lang.org/dev
