Subject: Re: map function (tail recursive version)
From: rpw3@rpw3.org (Rob Warnock)
Date: Tue, 27 Apr 2004 00:14:46 -0500
Newsgroups: comp.lang.scheme,comp.lang.functional
Message-ID: <KZydna3S54LbcRDdRVn-jg@speakeasy.net>
Anton van Straaten <anton@appsolutions.com> wrote:
+---------------
| Taylor Campbell wrote:
| > That is, it saves _space_, not _time_ (and because of its
| > increased complexity, it can _consume_ time as well).
| 
| I'm curious as to whether you've observed REVERSE! being slower
| in practice, and under what circumstances or implementations.
+---------------

Certainly one case in which it could be slower is if the implementation
uses an generational GC and the MAP-allocated cells happen to be pushed
out of the nursery just before the REVERSE! runs. In that case, the
REVERSE! will pay the cost of whatever write-barrier is being used
for each CONS cell.

Note that if the MAP-allocated list is still in the nursery when REVERSE!
is called this effect will not normally be seen, since the write barrier
doesn't have to record anything if the new value being stored is a pointer 
into the nursery. In this case, REVERSE! *will* be faster than REVERSE,
since it reduces pressure on the allocator.


-Rob

p.s. For GCs not using the Ungar fixed-location nursery trick, replace
"nursery" everywhere above with "generation #0".

-----
Rob Warnock			<rpw3@rpw3.org>
627 26th Avenue			<URL:http://rpw3.org/>
San Mateo, CA 94403		(650)572-2607