Hi Mark! Do you have any advice to optimize it without disable GC temperaly? Or the only way is to change a better GC?
2017年6月10日 12:28，"Mark H Weaver" <m...@netris.org>写道： > Stefan Monnier <monn...@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. > >
