Re: Efficiency of `map`

[Mark H Weaver]

Nala Ginrut  writes:
> Do you have any advice to optimize it without disable GC temperaly?

Temporarily disabling the GC would merely postpone reclamation work that
needs to be done eventually, and at the risk of allocating a potentially
huge amount of garbage while the GC is disabled, in the worst case.
Sounds like a bad idea to me.

If I knew how to make our 'map' faster, I would do it.  Andy rewrote the
versions of 'map' in boot-9 and srfi-1 to take advantage of the
expanding stacks, and he seems quite skilled at writing efficient code.
I have no reason to think I could do better, and no spare time to make
the attempt.

> Or the only way is to change a better GC?

I don't know how to make Boehm GC faster without making it more
difficult to write C code that manipulates heap objects, and without
adding more restrictions on the use of existing C libraries.

  Mark

Re: Efficiency of `map`

[Nala Ginrut]

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" 写道：

> Stefan Monnier  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 10))
> 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 

Re: Efficiency of `map`

[Mark H Weaver]

Stefan Monnier  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 10))
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 

Efficiency of `map` (was: [PATCH] On Hurd, don't use not implemented madvise())

[Stefan Monnier]

>   (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?  ]

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


Stefan