Hello,
I am about to implement some routines that have to do with arithmetic.
Having [a book with] the right algorithms, language-specific details are
what I care about next, mainly how to write the loops.
I know the mantra "code using the LOOP macro is at least as efficient as
hand-written loops" but I would like to be sure that this is true, in
general, for routines where the loops are simple and easy to write with
DO and friends, and time-critical. I have mixed feelings about the LOOP
facility but I would prefer to write coherent code using either the LOOP
style or the DO style, so I should pick one. What is your advice?
Regards,
-- Xavier
In article <··································@4ax.com>,
F. Xavier Noria <···@retemail.es> wrote:
> I know the mantra "code using the LOOP macro is at least as efficient
as
> hand-written loops" but I would like to be sure that this is true, in
> general, for routines where the loops are simple and easy to write
with
> DO and friends, and time-critical.
On my experience with ACL, for simple iterative constructions DO is
more efficient than LOOP, at least in terms of the resulting code
length. But if you have a complicated loop with various kinds of
iteration and termination tests in it (numeric, over lists, etc), LOOP
may beat hand-coded equivalent. Finally, LOOP is usually more legible
than DO and friends, so unless you are going to implement simple inner
cycle, consider using LOOP. Just my opinion.
--
Eugene.
Sent via Deja.com http://www.deja.com/
Before you buy.
Centuries ago, Nostradamus foresaw a time when F. Xavier Noria would say:
>Hello,
>
>I am about to implement some routines that have to do with arithmetic.
>Having [a book with] the right algorithms, language-specific details are
>what I care about next, mainly how to write the loops.
>
>I know the mantra "code using the LOOP macro is at least as efficient as
>hand-written loops" but I would like to be sure that this is true, in
>general, for routines where the loops are simple and easy to write with
>DO and friends, and time-critical. I have mixed feelings about the LOOP
>facility but I would prefer to write coherent code using either the LOOP
>style or the DO style, so I should pick one. What is your advice?
Write some expressions containing both sorts of loops, and use the
macroexpand macro to see what the loops you're trying expand to.
For instance, with CLISP, look at the following sample (largely
"stolen" from the HyperSpec):
> (macroexpand-1 '(loop for i from 1 to 10
when (oddp i)
collect i))
produces:
(MACROLET
((LOOP-FINISH NIL (SYSTEM::LOOP-FINISH-ERROR)))
(BLOCK NIL
(LET
((#:G1141 NIL))
(LET
((I 1))
(MACROLET
((LOOP-FINISH
NIL
'(GO SYSTEM::END-LOOP)))
(TAGBODY
SYSTEM::BEGIN-LOOP
(PROGN (WHEN (> I 10) (LOOP-FINISH))
(PROGN
(IF (ODDP I)
(PROGN
(SETQ #:G1141
(CONS I #:G1141))) NIL)))
(PROGN (PSETQ I (+ I 1))) (GO SYSTEM::BEGIN-LOOP)
SYSTEM::END-LOOP
(MACROLET
((LOOP-FINISH NIL
(SYSTEM::LOOP-FINISH-WARN)
'(GO SYSTEM::END-LOOP)))
(RETURN-FROM NIL
(SYSTEM::LIST-NREVERSE #:G1141)))))))))
In CMU-CL, the same expression produces:
(LET ((I 1))
(DECLARE (TYPE REAL I))
(ANSI-LOOP::WITH-LOOP-LIST-COLLECTION-HEAD
(#:G844 #:G845)
(BLOCK NIL
(ANSI-LOOP::LOOP-BODY
NIL
(NIL NIL NIL NIL)
((IF
(ODDP I)
(ANSI-LOOP::LOOP-COLLECT-RPLACD
(#:G844
#:G845)
(LIST I))))
(NIL
(ANSI-LOOP::LOOP-REALLY-DESETQ
I
(1+ I))
(WHEN
(> I '10)
(GO ANSI-LOOP::END-LOOP))
NIL)
((RETURN-FROM
NIL
(ANSI-LOOP::LOOP-COLLECT-ANSWER
#:G844)))))))
Both appear to be not outrageously inefficient; you'll have to decide
for yourself the quality of the results that come out of your
implementation's (LOOP) as well as from (DO). Note that LOOP can make
use of all sorts of interesting structuring rules, notably including
jumping out of of control structures using (RETURN) and (GO). This
may be an outright benefit...
--
If ignorance is bliss, you must be orgasmic.
········@ntlug.org - - <http://www.hex.net/~cbbrowne/lsf.html>
F. Xavier Noria <···@retemail.es> writes:
> I know the mantra "code using the LOOP macro is at least as efficient as
> hand-written loops" but I would like to be sure that this is true, in
> general, for routines where the loops are simple and easy to write with
> DO and friends, and time-critical. I have mixed feelings about the LOOP
> facility but I would prefer to write coherent code using either the LOOP
> style or the DO style, so I should pick one. What is your advice?
FWIW, my advice would be:
a) Why choose between DO.* and LOOP? I routinely use both, depending on
which will yield "clearer" code: If something is most naturally
written as a dolist, I probably won't bother to use LOOP, unless I
suspected that the loop might get hairier in the end. And I still
find some things can be put much more succinctly using DO than
using LOOP.
b) If something is really speed critical, you'll have to profile and
time it anyway, and be prepared to rewrite it a number of times.
Changing from LOOP to DO or vice-versa is little work, should that
prove necessary/advantageous. But first write the code in a way
that seems natural to you.
c) Play with LOOP and DO a little in the implementations that you use
and look at the generated code. That way you'll get a much better
understanding on how to write code in a way that makes it optimal
for the instances where speed is very critical.
d) Should you come across instances where the code generated by LOOP
is sub-optimal compared to an _equivalent_ DO loop or other
iteration construct, then work that out with your respective
vendor.
Regs, Pierre.
--
Pierre Mai <····@acm.org> PGP and GPG keys at your nearest Keyserver
"One smaller motivation which, in part, stems from altruism is Microsoft-
bashing." [Microsoft memo, see http://www.opensource.org/halloween1.html]
In article <··············@orion.dent.isdn.cs.tu-berlin.de>,
Pierre R. Mai <····@acm.org> wrote:
>d) Should you come across instances where the code generated by LOOP
> is sub-optimal compared to an _equivalent_ DO loop or other
> iteration construct, then work that out with your respective
> vendor.
DOLIST is faster in ACL than LOOP FOR ... IN ..., but only because
DOLIST is (contrary to the standard) implemented to assume the list is
a proper list (terminated by NIL), while the LOOP form tests for
termination with ENDP.
So I suppose the proper response of the vendor here is to slow
down DOLIST. :)
Paul
In article <··································@4ax.com>,
F. Xavier Noria <···@retemail.es> wrote:
> I know the mantra "code using the LOOP macro is at least as efficient as
> hand-written loops" but I would like to be sure that this is true, in
> general, for routines where the loops are simple and easy to write with
> DO and friends, and time-critical. I have mixed feelings about the LOOP
> facility but I would prefer to write coherent code using either the LOOP
> style or the DO style, so I should pick one. What is your advice?
If you use LOOP, and performance is critical, be sure to use the
OF-TYPE clause for the loop index variable:
(LOOP FOR I OF-TYPE FIXNUM FROM 1 TO N DO ...)
ACL is not smart enough to figure out that I should be
a fixnum even if N is declared to be a fixnum.
The same caveat applies to DO, btw. In that case, write:
(DO ((I 1 (1+ I)))
((> I N))
(DECLARE (FIXNUM I))
...)
These produce essentially identical code under ACL.
Paul Dietz
······@email.mot.com
Paul Dietz wrote:
> ACL is not smart enough to figure out that I should be
> a fixnum even if N is declared to be a fixnum.
>
> The same caveat applies to DO, btw. In that case, write:
>
> (DO ((I 1 (1+ I)))
> ((> I N))
> (DECLARE (FIXNUM I))
> ...)
In my experience, there is a difference in this matter between DO and
LOOP. DO, DOTIMES etc. seems to recognize all applicable declarations,
while LOOP recognizes the ones declared inside itself.
Compare, then move array type declaration to the outer DEFUN form
similarly to the DOTIMES test.
(defun loop-collect-3 (vector)
(declare (optimize speed (safety 0)))
(loop for element of-type (signed-byte 32)
across (the (simple-array (signed-byte 32) (*)) vector)
sum element of-type (signed-byte 32)))
(defun dotimes-collect (vector &aux (result 0))
(declare (optimize speed (safety 0))
(type (simple-array (signed-byte 32) (*)) vector))
(dotimes (i (length vector) result)
(incf (the (signed-byte 32) result) (aref vector i))))
Robert