Re: Efficiency of `map`

[Mark H Weaver <mhw@netris.org>]

Stefan Monnier <monnier@iro.umontreal.ca> writes:

>>   (define (map f l)
>>     (if (pair? l)
>>         (cons (f (car l))
>>               (map f (cdr l)))
>>         '()))
>>
>> whereas we used to have to write code like this in order to support long
>> lists without overflowing the stack:
>>
>>   (define (map f l)
>>     (let loop ((l l) (out '()))
>>       (if (pair? l)
>>           (loop (cdr l) (cons (f (car l)) out))
>>           (reverse out))))
>
> Ignoring stack usage, is the first version faster or slower than the second?
> [ Or is the speed difference negligible?  ]

I don't have time to perform proper benchmarks, but some admittedly
inadequate measurements on my Thinkpad X200 suggest that the first
version is about 1.5% faster, mainly because it makes a lot less work
for the GC.  See below for details of what I did.  

> How 'bout using a side-effecting `reverse!` (like Lisp's nreverse)?

We can't do that, because in the presence of first-class continuations
where the 'f' passed to map may return more than once, using mutation to
build the result list will change the result for some programs.  Both
modern scheme standards (R6RS and R7RS) explicitly specify that "If
multiple returns occur from map, the values returned by earlier returns
are not mutated".

      Mark


mhw@jojen ~$ guile
GNU Guile 2.2.2
Copyright (C) 1995-2017 Free Software Foundation, Inc.

Guile comes with ABSOLUTELY NO WARRANTY; for details type `,show w'.
This program is free software, and you are welcome to redistribute it
under certain conditions; type `,show c' for details.

Enter `,help' for help.
scheme@(guile-user)> (define (map1 f l) (if (pair? l) (cons (f (car l)) (map f (cdr l))) '()))
scheme@(guile-user)> (define (map2 f l) (let loop ((l l) (out '())) (if (pair? l) (loop (cdr l) (cons (f (car l)) out)) (reverse out))))
scheme@(guile-user)> (define var #f)
scheme@(guile-user)> (define test-list (iota 100000))
scheme@(guile-user)> ,time (let loop ((i 1000)) (when (positive? i) (set! var (map1 1+ test-list)) (loop (- i 1))))
;; 13.121194s real time, 14.072380s run time.  2.346036s spent in GC.
scheme@(guile-user)> ,time (let loop ((i 1000)) (when (positive? i) (set! var (map1 1+ test-list)) (loop (- i 1))))
;; 13.006867s real time, 13.940452s run time.  2.263353s spent in GC.
scheme@(guile-user)> ,time (let loop ((i 1000)) (when (positive? i) (set! var (map1 1+ test-list)) (loop (- i 1))))
;; 13.079656s real time, 13.946879s run time.  2.197271s spent in GC.
scheme@(guile-user)> ,time (let loop ((i 1000)) (when (positive? i) (set! var (map2 1+ test-list)) (loop (- i 1))))
;; 13.029591s real time, 15.312230s run time.  5.601020s spent in GC.
scheme@(guile-user)> ,time (let loop ((i 1000)) (when (positive? i) (set! var (map2 1+ test-list)) (loop (- i 1))))
;; 13.041985s real time, 15.306287s run time.  5.581253s spent in GC.
scheme@(guile-user)> ,time (let loop ((i 1000)) (when (positive? i) (set! var (map2 1+ test-list)) (loop (- i 1))))
;; 12.003391s real time, 13.421369s run time.  3.662504s spent in GC.
scheme@(guile-user)> ,time (let loop ((i 1000)) (when (positive? i) (set! var (map2 1+ test-list)) (loop (- i 1))))
;; 11.993404s real time, 13.367805s run time.  3.496328s spent in GC.
scheme@(guile-user)> ,time (let loop ((i 1000)) (when (positive? i) (set! var (map2 1+ test-list)) (loop (- i 1))))
;; 11.964659s real time, 13.362942s run time.  3.544227s spent in GC.
scheme@(guile-user)> ,time (let loop ((i 1000)) (when (positive? i) (set! var (map1 1+ test-list)) (loop (- i 1))))
;; 12.619559s real time, 13.153612s run time.  1.471917s spent in GC.
scheme@(guile-user)> ,time (let loop ((i 1000)) (when (positive? i) (set! var (map1 1+ test-list)) (loop (- i 1))))
;; 12.600161s real time, 13.136094s run time.  1.476574s spent in GC.
scheme@(guile-user)> ,time (let loop ((i 1000)) (when (positive? i) (set! var (map1 1+ test-list)) (loop (- i 1))))
;; 12.584059s real time, 13.142257s run time.  1.478289s spent in GC.
scheme@(guile-user)> ,time (let loop ((i 1000)) (when (positive? i) (set! var (map1 1+ test-list)) (loop (- i 1))))
;; 12.626346s real time, 13.146946s run time.  1.466499s spent in GC.
scheme@(guile-user)> ,time (let loop ((i 1000)) (when (positive? i) (set! var (map2 1+ test-list)) (loop (- i 1))))
;; 12.009064s real time, 13.361389s run time.  3.690290s spent in GC.
scheme@(guile-user)> ,time (let loop ((i 1000)) (when (positive? i) (set! var (map2 1+ test-list)) (loop (- i 1))))
;; 11.970217s real time, 13.317716s run time.  3.352065s spent in GC.
scheme@(guile-user)> 

Here are the 4 best times for each procedure:

map1:
;; 12.619559s real time, 13.153612s run time.  1.471917s spent in GC.
;; 12.600161s real time, 13.136094s run time.  1.476574s spent in GC.
;; 12.584059s real time, 13.142257s run time.  1.478289s spent in GC.
;; 12.626346s real time, 13.146946s run time.  1.466499s spent in GC.

averages of 4 best times:
;; 12.607531s real time, 13.144727s run time.  1.473320s spent in GC.


map2:
;; 12.009064s real time, 13.361389s run time.  3.690290s spent in GC.
;; 11.993404s real time, 13.367805s run time.  3.496328s spent in GC.
;; 11.964659s real time, 13.362942s run time.  3.544227s spent in GC.
;; 11.970217s real time, 13.317716s run time.  3.352065s spent in GC.

averages of 4 best times:
;; 11.984336s real time, 13.352463s run time.  3.520728s spent in GC.