[plt-dev] coding

On May 14, Matthias Felleisen wrote:
> 
> Aha. I finally discovered this comment in the original file, miles
> away:
> 
> ;; take/drop-right are originally from srfi-1, uses the same lead- 
> pointer trick

It comes immediately before the three functions that do that trick.


On May 14, Sam Tobin-Hochstadt wrote:
> On Fri, May 14, 2010 at 10:42 AM, Jay McCarthy <jay.mccarthy at gmail.com> wrote:
> > And how is the performance after the fix? Is the opaque coding
> > worth it?
> 
> Eli's version is about 40-50% faster than Matthias':

That trick should definitely not be attributed to me in any way.


On May 14, Ryan Culpepper wrote:
> The docs for 'split-at-right' say this:
> 
>    Returns the same result as
> 
>      (values (drop-right lst pos) (take-right lst pos))
> 
>    except that it can be faster.

Note the "can".


> On my machine, the naive version is marginally slower on short lists
> (10) and faster (real time) on longer lists. Here are my timings:

The ratios might have changed, but in general short lists are more
common than long ones, which is why I went with the current version.

The thing that makes this problem interesting is that if you want to
avoid two loops you have to pipe the two values through the loop:

  (define (split-at-right.v2 list n)
    (let loop ([list list]
               [lead (or (drop* list n) (error 'drop-right))])
      ;; could throw an error for non-lists, but be more like `drop'
      (if (pair? lead)
        (let-values ([(pfx sfx) (loop (cdr list) (cdr lead))])
          (values (cons (car list) pfx) sfx))
        (values '() list))))

IIRC, this used to be much slower than it is now -- it's still slower
for most lists, but it beats the current version in the 20k-item list.
An obvious way to make it faster is to avoid the values penalty with a
`set!':

  (define (split-at-right.v3 list n)
    (let ([tail #f])
      (values
       (let loop ([list list]
                  [lead (or (drop* list n) (error 'drop-right))])
         ;; could throw an error for non-lists, but be more like `drop'
         (if (pair? lead)
           (cons (car list) (loop (cdr list) (cdr lead)))
           (begin (set! tail list) '())))
       tail)))

which beats all versions consistently (with the largest payoff for
smaller lists).  If this function is important enough, then this last
one should be used instead.


On May 14, Matthias Felleisen wrote:
> How can anyone possibly predict that two nearly identical loops over
> the 'lead' ptr structure beat one loop over the same S-exp plus a
> tiny bit of reverse?
> 
> Here is my guess at an answer: v1 CONSes as it traverses 'lead' and
> neither v0 does. Then v1 reverses, functionally, which means it
> conses even more.

Right -- the two things that this depends on is racket being very fast
with very deep stacks on one side, and the lack of `reverse!' and
`reverse' allocating a new result even when the reversed list is a
throwaway one.

(Usual disclaimer on sufficiently smart compilers turning a `reverse'
to a `reverse!'; in addition to a sufficiently smart compiler that
proves that the second value in the loop propagates as is from the
bottom up and turn it into the above code.)


> As Dan used to say, count the CONSes is you wish to predict your
> performance.
> 
> If this is correct, I am blown away at how fast traversals of lists
> are. My oh my.
> 
> If this is correct, our switch to purely functional cons starts to
> scare me.

But put that against the last non-functional version beating the
others.

-- 
          ((lambda (x) (x x)) (lambda (x) (x x)))          Eli Barzilay:
                    http://barzilay.org/                   Maze is Life!