[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [PATCH] use tail pointer for LOOP
From: |
David Kastrup |
Subject: |
Re: [PATCH] use tail pointer for LOOP |
Date: |
Fri, 18 Jun 2010 09:07:06 +0200 |
User-agent: |
Gnus/5.13 (Gnus v5.13) Emacs/24.0.50 (gnu/linux) |
Stefan Monnier <address@hidden> writes:
>> Reverse: (1.006534 3 0.682734)
>> Tail pointer: (1.305476 4 0.9159619999999986)
>
>> Still, reversing seems to be worth it (by some 30 percent). Unless we
>> find some way to streamline the tail pointer better.
>
> That's really not surprising: count the number of function calls and
> you'll see that the nreverse way is likely to win every time, simply
> because it suffers about half as much from the interpretation overhead.
nreverse is also cons-neutral. The only situation where I'd expect it
to be able to lose is under virtual memory pressure, where the nreverse
approach has to cons the list forwards when building, and again
backwards when reversing the conses. A tail pointer approach will
traverse the list just once. So if it does not fit in real memory, tail
pointers may cause half the page faults than nreverse does.
--
David Kastrup
- Re: [PATCH] use tail pointer for LOOP (Was: Re: O(N^2) behavior in LOOP), tomas, 2010/06/16
- Re: [PATCH] use tail pointer for LOOP, David Kastrup, 2010/06/16
- Re: [PATCH] use tail pointer for LOOP, tomas, 2010/06/17
- Re: [PATCH] use tail pointer for LOOP, Thien-Thi Nguyen, 2010/06/17
- Re: [PATCH] use tail pointer for LOOP, tomas, 2010/06/17
- Re: [PATCH] use tail pointer for LOOP, Thien-Thi Nguyen, 2010/06/17
- Re: [PATCH] use tail pointer for LOOP, tomas, 2010/06/17
- Re: [PATCH] use tail pointer for LOOP, Thien-Thi Nguyen, 2010/06/17
- Re: [PATCH] use tail pointer for LOOP, Thien-Thi Nguyen, 2010/06/17
- Re: [PATCH] use tail pointer for LOOP, Stefan Monnier, 2010/06/17
- Re: [PATCH] use tail pointer for LOOP,
David Kastrup <=
- Re: [PATCH] use tail pointer for LOOP, Stefan Monnier, 2010/06/18