From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!.POSTED!not-for-mail From: Nala Ginrut Newsgroups: gmane.lisp.guile.devel Subject: Re: Efficiency of `map` Date: Sat, 10 Jun 2017 12:38:34 +0800 Message-ID: References: <20170530092627.19412-1-manolis837@gmail.com> <87bmqayvx7.fsf@netris.org> <87r2z3xp6o.fsf@netris.org> <20170602083950.GB11497@tuxteam.de> <87r2z1x231.fsf@netris.org> <87poec4gbq.fsf@netris.org> NNTP-Posting-Host: blaine.gmane.org Mime-Version: 1.0 Content-Type: multipart/alternative; boundary="94eb2c1891c4a62138055193a8e7" X-Trace: blaine.gmane.org 1497069535 31637 195.159.176.226 (10 Jun 2017 04:38:55 GMT) X-Complaints-To: usenet@blaine.gmane.org NNTP-Posting-Date: Sat, 10 Jun 2017 04:38:55 +0000 (UTC) Cc: Stefan Monnier , guile-devel To: Mark H Weaver Original-X-From: guile-devel-bounces+guile-devel=m.gmane.org@gnu.org Sat Jun 10 06:38:50 2017 Return-path: Envelope-to: guile-devel@m.gmane.org Original-Received: from lists.gnu.org ([208.118.235.17]) by blaine.gmane.org with esmtp (Exim 4.84_2) (envelope-from ) id 1dJYAj-0007yL-T0 for guile-devel@m.gmane.org; Sat, 10 Jun 2017 06:38:50 +0200 Original-Received: from localhost ([::1]:57235 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1dJYAp-0008RO-38 for guile-devel@m.gmane.org; Sat, 10 Jun 2017 00:38:55 -0400 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:57621) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1dJYAb-0008R8-00 for guile-devel@gnu.org; Sat, 10 Jun 2017 00:38:42 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1dJYAZ-0004La-B3 for guile-devel@gnu.org; Sat, 10 Jun 2017 00:38:41 -0400 Original-Received: from mail-oi0-x22f.google.com ([2607:f8b0:4003:c06::22f]:33844) by eggs.gnu.org with esmtps (TLS1.0:RSA_AES_128_CBC_SHA1:16) (Exim 4.71) (envelope-from ) id 1dJYAZ-0004Gx-2i for guile-devel@gnu.org; Sat, 10 Jun 2017 00:38:39 -0400 Original-Received: by mail-oi0-x22f.google.com with SMTP id o65so37516828oif.1 for ; Fri, 09 Jun 2017 21:38:35 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :cc; bh=loB65Be5wKxtb4a065Aoq+YLD7Wm44iUOELmqW0mRw0=; b=HkqwCu1k5+kn5QwlEjQ6qPdX+PTF0rs4sGtEGfR7PDUYnBGGoSuNXW0wAp1XSWfv+w kgV9coJnpChgB6kM8KFPltlf4v27y82pkBlagqlTh4ZP1a8SpiQE9xEC9Iqj/nr5b9VR jMA/TxikF7ybDlqg5GT1IvYhTdCr9M6aJvGLnmCUhvAiAQ+WJeHBiLxRh0pvo4PC+eQb nAy0lmCeF7tnH7thLo7ekoYZObliBhhgjVVL7vH6xdF7uKVTc3AOMKTAe20/U92EMSJX m2PVlna+DALCYran8kd7OjFGnMpQDjm3y77lgkjh32unkoMXlqT2teDk1SzePvZ2rKWY fXbg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:in-reply-to:references:from:date :message-id:subject:to:cc; bh=loB65Be5wKxtb4a065Aoq+YLD7Wm44iUOELmqW0mRw0=; b=O6cJ4BujmRvTkTNR777cxrEwl+wuCOsMKb0au/6hKL1ygPSJkmUU0GcPdcg1bOrJMh QVQ2WrrgB0laJdT+BxOC7BN4cVWWqFmzKAfUyVGEJOtSAnKsRkf0aGVzD1uQxrszf57Q FpDMMjS6IrekE4AI4ZELN/B4pnykIibvYnQuE7aS8CxvvQW4F1GHNwqwJbHFugy9fHy2 ev6Lbd0O+JIiY77Rjo+v/XruO4alhUSKsyEuuDlqEV1fTq7xU9QUFdPTf0l4UiEFJycs U3j3NywEwuVv2b/Lg1vqqiqhbLXpOkwZ4Y5Qffxk7CW9HEnxOX2mGHAdp8h7487s2RZh Zwsw== X-Gm-Message-State: AODbwcB4kOn7FmWE+WOA6zp8RKqkB2lzfQJuU/FYhRQRr6tUMs6O1JyZ lRArFC54ByXgjZ4sLWZJQTrOWCCGtA== X-Received: by 10.202.5.68 with SMTP id 65mr16416507oif.199.1497069515053; Fri, 09 Jun 2017 21:38:35 -0700 (PDT) Original-Received: by 10.157.53.6 with HTTP; Fri, 9 Jun 2017 21:38:34 -0700 (PDT) Original-Received: by 10.157.53.6 with HTTP; Fri, 9 Jun 2017 21:38:34 -0700 (PDT) In-Reply-To: <87poec4gbq.fsf@netris.org> X-detected-operating-system: by eggs.gnu.org: Genre and OS details not recognized. X-Received-From: 2607:f8b0:4003:c06::22f X-BeenThere: guile-devel@gnu.org X-Mailman-Version: 2.1.21 Precedence: list List-Id: "Developers list for Guile, the GNU extensibility library" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: guile-devel-bounces+guile-devel=m.gmane.org@gnu.org Original-Sender: "guile-devel" Xref: news.gmane.org gmane.lisp.guile.devel:19196 Archived-At: --94eb2c1891c4a62138055193a8e7 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable 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=E5=B9=B46=E6=9C=8810=E6=97=A5 12:28=EF=BC=8C"Mark H Weaver" =E5=86=99=E9=81=93=EF=BC=9A > 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 lo= ng > >> 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. > > --94eb2c1891c4a62138055193a8e7 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
Hi Mark!
Do you have any advice to optim= ize it without disable GC temperaly? Or the only way is to change a better = GC?

20= 17=E5=B9=B46=E6=9C=8810=E6=97=A5 12:28=EF=BC=8C"Mark H Weaver" &l= t;mhw@netris.org>=E5=86=99=E9=81= =93=EF=BC=9A
Stefan = Monnier <monnier@iro.umontre= al.ca> writes:

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

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.=C2=A0 See below for details of what I did.

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

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

=C2=A0 =C2=A0 =C2=A0 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.=C2=A0 2.346036s spent in GC.<= br> 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.=C2=A0 2.263353s spent in GC.<= br> 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.=C2=A0 2.197271s spent in GC.<= br> 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.=C2=A0 5.601020s spent in GC.<= br> 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.=C2=A0 5.581253s spent in GC.<= br> 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.=C2=A0 3.662504s spent in GC.<= br> 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.=C2=A0 3.496328s spent in GC.<= br> 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.=C2=A0 3.544227s spent in GC.<= br> 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.=C2=A0 1.471917s spent in GC.<= br> 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.=C2=A0 1.476574s spent in GC.<= br> 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.=C2=A0 1.478289s spent in GC.<= br> 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.=C2=A0 1.466499s spent in GC.<= br> 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.=C2=A0 3.690290s spent in GC.<= br> 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.=C2=A0 3.352065s spent in GC.<= br> scheme@(guile-user)>

Here are the 4 best times for each procedure:

map1:
;; 12.619559s real time, 13.153612s run time.=C2=A0 1.471917s spent in GC.<= br> ;; 12.600161s real time, 13.136094s run time.=C2=A0 1.476574s spent in GC.<= br> ;; 12.584059s real time, 13.142257s run time.=C2=A0 1.478289s spent in GC.<= br> ;; 12.626346s real time, 13.146946s run time.=C2=A0 1.466499s spent in GC.<= br>
averages of 4 best times:
;; 12.607531s real time, 13.144727s run time.=C2=A0 1.473320s spent in GC.<= br>

map2:
;; 12.009064s real time, 13.361389s run time.=C2=A0 3.690290s spent in GC.<= br> ;; 11.993404s real time, 13.367805s run time.=C2=A0 3.496328s spent in GC.<= br> ;; 11.964659s real time, 13.362942s run time.=C2=A0 3.544227s spent in GC.<= br> ;; 11.970217s real time, 13.317716s run time.=C2=A0 3.352065s spent in GC.<= br>
averages of 4 best times:
;; 11.984336s real time, 13.352463s run time.=C2=A0 3.520728s spent in GC.<= br>
--94eb2c1891c4a62138055193a8e7--