From: Jeff Dalton
Subject: Optimization list (was Re: Response to sort question)
Date:
Message-ID: <8765@skye.ed.ac.uk>
In article <············@early-bird.think.com> ······@think.com (Barry Margolin) writes:
>In article <······················@ida.liu.se> ·····@ida.liu.se (Jalal Maleki) writes:
>>or perhaps better
>>
>>(sort '((Brown 71) (Edwards 27) (Smith 56) (Jones 30))
>> #'(lambda (x y) (> (second x) (second y))))
>
>The version using :KEY is probably more readable and maintainable, and may
>even be more efficient.
>
> [...]
>
>Efficient: The above version requires SECOND to be called twice for each
>comparison. An optimized version of SORT might arrange for the key
>function to be called only once for each element, with the results being
>cached.
On the other hand, it might not, and the calls to second in the
predicate might be compiled in-line while the :KEY would be funcalled.
So it's certainly possible that using the :KEY parameter would be
slower.
I agree that it's better to use :KEY, for all the reasons given,
but how many implementations actually perform the optimization?
I'm tempted to start an "optimization list" in which we, the readers
of Comp.lang.lisp, can collect what we know about what optimizations
are actually performed. ... Anyway, I'll try using "optimization
list" as a subject line and see how that goes.
Here are two questions to start it off. What implementations
1. Arrange for a SORT :KEY to be called only once for each element?
2. Optimize (REMOVE item list :COUNT 1)? Or is it better to define
my own function for the cases I need to be fast?
-- jd
From: Barry Margolin
Subject: Re: Optimization list (was Re: Response to sort question)
Date:
Message-ID: <1tj499INNd5t@early-bird.think.com>
In article <····@skye.ed.ac.uk> ····@aiai.ed.ac.uk (Jeff Dalton) writes:
>In article <············@early-bird.think.com> ······@think.com (Barry Margolin) writes:
>>Efficient: The above version requires SECOND to be called twice for each
>>comparison. An optimized version of SORT might arrange for the key
>>function to be called only once for each element, with the results being
>>cached.
>
>On the other hand, it might not, and the calls to second in the
>predicate might be compiled in-line while the :KEY would be funcalled.
>So it's certainly possible that using the :KEY parameter would be
>slower.
And, in fact, you're right on all the implementations I tried: Genera 8.1
on a Symbolics 3650, Lucid 4.1, CMUCL 16d, and WCL 2.1 all on a
Sparcstation 2. They all call the :KEY function exactly twice as many
times as the comparison function. The improvement from calling an
inlinable key directly in the comparison ranged from about 1.25x to 5x!
Actually, on most of the implementations it appears that it's mostly the
use of :KEY that slows things down, since there's almost as much
improvement when a non-inlinable key function is used. Lucid is the only
one where :KEY #'MY-CAR is no slower than calling MY-CAR from the
comparison function.
Another optimization opportunity arises when you call the key function
directly: you can provide declarations, e.g.
(sort list #'(lambda (x y)
(declare (cons x y))
(< (the fixnum (car x)) (the fixnum (car y)))))
>I agree that it's better to use :KEY, for all the reasons given,
>but how many implementations actually perform the optimization?
>I'm tempted to start an "optimization list" in which we, the readers
>of Comp.lang.lisp, can collect what we know about what optimizations
>are actually performed. ... Anyway, I'll try using "optimization
>list" as a subject line and see how that goes.
>
>Here are two questions to start it off. What implementations
>
> 1. Arrange for a SORT :KEY to be called only once for each element?
>
> 2. Optimize (REMOVE item list :COUNT 1)? Or is it better to define
> my own function for the cases I need to be fast?
>
>-- jd
--
Barry Margolin
System Manager, Thinking Machines Corp.
······@think.com {uunet,harvard}!think!barmar
|> In article <····@skye.ed.ac.uk> ····@aiai.ed.ac.uk (Jeff Dalton) writes:
|> >...
|> > 2. Optimize (REMOVE item list :COUNT 1)? Or is it better to define
|> > my own function for the cases I need to be fast?
|> >-- jd
Yes. Common Lisp has so many functions and capabilities that it is not possible
to spend time making them all as fast as they could be. Many people use
this as a criticism of CL. However, there is nothing that says you have
to use the CL functions. If speed is critical for some piece of code,
like inner loops, you are better off writing it yourself in such a way
that you provide the compiler with constructs that it DOES optimize,
such as highly type-declared, non-safe-declared, inline lisp code.
Write your app, find where it spends it's time, and then start rewriting
those pieces to go fast. I like to say that C programmers spend 100% of their
time optimizing 100% of their programs, instead of just the critical sections.
A bit off the point, but I recall a case where someone needed unique
identifiers that had values in their program. Lisp Symbols right?
But they complained that symbols took up so much space
that they switched to C instead, and then built their own
code to handle their symbols. They didn't even consider that they
could write the same special-purpose code in Lisp also.
-Kelly