[racket-dev] Use unsafe in reverse.rkt ?

From: Gustavo Massaccesi (gustavo at oma.org.ar)
Date: Thu May 1 12:05:20 EDT 2014

I was reading the alternative implementation of reverse in
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.


;------ fast-reverse.rkt
(module reverse '#%kernel
  (#%require '#%unsafe racket/private/performance-hint)
  (#%provide alt-reverse)


    (define-values (alt-reverse)
      (let-values ([(reverse)
                    (lambda (l)
                      (if (list? l)
                        (raise-argument-error 'reverse "list?" l))
                      (letrec-values ([(loop)
                                       (lambda (a l)
                                         (if (null? l)
                                           (loop (cons (unsafe-car l)
a) (unsafe-cdr l))))])
                        (loop null l)))])

;--- 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)
    (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 "))


(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 ")

Posted on the dev mailing list.