Prev: declaring 'ignore' inside a loop using destructuring
Next: The Best gift for this year christmas day!
From: Don March on 25 Nov 2009 23:48
A function I'm writing has a section like this:

(dolist (x long-list)
(do-some-stuff)
(push (if fn
(funcall fn x)
x)
new-list))

Which is fine, but if long-list is actually long, it's silly and
possibly slow to evaluate the "(if fn..." stuff every time. I came up
with the following 2.5 alternatives:

;; option 1 (probably implemented with macros to avoid duplicate code)
(if fn
(dolist (x long-list)
(do-some-stuff)
(push (funcall fn x) new-list))
(dolist (x long-list)
(do-some-stuff)
(push x new-list)))

;; option 2a
(let ((push-lambda (if fn
(lambda (x) (funcall fn x))
(lambda (x) x))))
(dolist (x long-list)
(do-some-stuff)
(push (funcall push-lambda x) new-list)))

;; option 2b
(let ((push-exp (if fn
'(funcall fn x)
'x)))
(dolist (x long-list)
(do-some-stuff)
(push (eval push-exp) new-list)))

Questions:
* Which of these is to be preferred? Am I missing another option?
* This is a pattern I'm running into a lot: almost duplicate chunks of
code with small changes, but those changes have to be determined at
run-time. Is there a more general way of dealing with this problem?
* Assuming either 2a or 2b had to be chosen, which is "best"? I'm
still unclear about when eval can be used without somebody saying it's
inappropriate.
From: Tamas K Papp on 26 Nov 2009 01:54
On Wed, 25 Nov 2009 20:48:13 -0800, Don March wrote:

> A function I'm writing has a section like this:
>
> (dolist (x long-list)
> (do-some-stuff)
> (push (if fn
> (funcall fn x)
> x)
> new-list))
>
> Which is fine, but if long-list is actually long, it's silly and
> possibly slow to evaluate the "(if fn..." stuff every time. I came up

Not at all. It is not silly because it is easy to understand
(compared to the alternatives), and whether it is slow is something
that you would have to benchmark, but I doubt that it makes a big
difference.

> with the following 2.5 alternatives:
>
> ;; option 1 (probably implemented with macros to avoid duplicate code)
> (if fn
> (dolist (x long-list)
> (do-some-stuff)
> (push (funcall fn x) new-list))
> (dolist (x long-list)
> (do-some-stuff)
> (push x new-list)))
>
> ;; option 2a
> (let ((push-lambda (if fn
> (lambda (x) (funcall fn x))
> (lambda (x) x))))
> (dolist (x long-list)
> (do-some-stuff)
> (push (funcall push-lambda x) new-list)))
>
> ;; option 2b
> (let ((push-exp (if fn
> '(funcall fn x)
> 'x)))
> (dolist (x long-list)
> (do-some-stuff)
> (push (eval push-exp) new-list)))
>
> Questions:
> * Which of these is to be preferred? Am I missing another option? *
> This is a pattern I'm running into a lot: almost duplicate chunks of
> code with small changes, but those changes have to be determined at
> run-time. Is there a more general way of dealing with this problem? *
> Assuming either 2a or 2b had to be chosen, which is "best"? I'm still
> unclear about when eval can be used without somebody saying it's
> inappropriate.

Option 2b is ugly, eval is totally unnecesary and it is slow. So your
optimization made your code ugly and slow. There is a lesson in there
:-)

If you insist on doing these optimizations and they come up all the
time, use macros to generate something like 1. But I don't think it
is worth it. Benchmark/profile things first, this is unlikely to be
your bottleneck.

HTH,

Tamas


From: Frode V. Fjeld on 26 Nov 2009 02:31
Don March <don.march(a)gmail.com> writes:

> A function I'm writing has a section like this:
>
> (dolist (x long-list)
> (do-some-stuff)
> (push (if fn
> (funcall fn x)
> x)
> new-list))
>
> Which is fine, but if long-list is actually long, it's silly and
> possibly slow to evaluate the "(if fn..." stuff every time.

You can bind fn to (or fn #'identity) and factor that out of the loop,
but I'd be somewhat surprised to find an implementation where that
version is any faster than your original version. I would expect the
original if-test to be compiled quite efficiently, with the main
performance hit coming from CPU pipeline stalls due to failed branch
prediction(s) -- which should happen at most once if your branch
prediction (buffer) is worth its salt, which again means that in effect
the CPU will automatically and dynamically factor out of the loop the
(performance cost of the) if-test for you. But by now we are long gone
into microoptimization-land where I would be very wary to trust any
intuition about what performs better. And if you really were interested
in performance at this level, you should rather study your lisp
implementation's performance optimization guide.

In other words, I think your original function is clearly superior,
certainly in terms of readability, and very likely also in (overall)
performance.

--
Frode V. Fjeld
From: joswig on 26 Nov 2009 05:04
On 26 Nov., 05:48, Don March <don.ma...(a)gmail.com> wrote:
> A function I'm writing has a section like this:
>
> (dolist (x long-list)
>   (do-some-stuff)
>   (push (if fn
>             (funcall fn x)
>             x)
>         new-list))
>
> Which is fine, but if long-list is actually long, it's silly and
> possibly slow to evaluate the "(if fn..." stuff every time.  I came up
> with the following 2.5 alternatives:
>
> ;; option 1 (probably implemented with macros to avoid duplicate code)
> (if fn
>     (dolist (x long-list)
>       (do-some-stuff)
>       (push (funcall fn x) new-list))
>     (dolist (x long-list)
>       (do-some-stuff)
>       (push x new-list)))
>
> ;; option 2a
> (let ((push-lambda (if fn
>                        (lambda (x) (funcall fn x))
>                        (lambda (x) x))))
>   (dolist (x long-list)
>     (do-some-stuff)
>     (push (funcall push-lambda x) new-list)))
>
> ;; option 2b
> (let ((push-exp (if fn
>                     '(funcall fn x)
>                     'x)))
>   (dolist (x long-list)
>     (do-some-stuff)
>     (push (eval push-exp) new-list)))
>
> Questions:
> * Which of these is to be preferred?  Am I missing another option?
> * This is a pattern I'm running into a lot: almost duplicate chunks of
> code with small changes, but those changes have to be determined at
> run-time.  Is there a more general way of dealing with this problem?
> * Assuming either 2a or 2b had to be chosen, which is "best"?  I'm
> still unclear about when eval can be used without somebody saying it's
> inappropriate.

Another way would be something like this:

(macrolet ((iter (ob)
`(dolist (x long-list)
(do-some-stuff)
(push ,ob new-list))))
(if fn
(iter (funcall fn x))
(iter x)))

From: Pascal J. Bourguignon on 26 Nov 2009 05:32
Don March <don.march(a)gmail.com> writes:

> A function I'm writing has a section like this:
>
> (dolist (x long-list)
> (do-some-stuff)
> (push (if fn
> (funcall fn x)
> x)
> new-list))
>
> Which is fine, but if long-list is actually long, it's silly and
> possibly slow to evaluate the "(if fn..." stuff every time. I came up
> with the following 2.5 alternatives:
>
> ;; option 1 (probably implemented with macros to avoid duplicate code)
> (if fn
> (dolist (x long-list)
> (do-some-stuff)
> (push (funcall fn x) new-list))
> (dolist (x long-list)
> (do-some-stuff)
> (push x new-list)))

Notice that any compiler worth its bits will do that transformation
automatically (moving constant computations outside of loops), perhaps
with (declaim (optimize (speed 3) (space 1))).

Otherwise if you have to do it yourself, use a macrolet as indicated
by joswig.


--
__Pascal Bourguignon__
 |  Next  |  Last
Pages: 1 2
Prev: declaring 'ignore' inside a loop using destructuring
Next: The Best gift for this year christmas day!