[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Compiling DOTIMES



    Date: Thu, 19 Jul 90 15:56 EDT
    From: bud%cleves@gte.com (Bud Frawley)

    While using code to generate possibilities, Tack Fu of GTE noted that
    compiling nested DOTIMESs took considerably more time that compiling
    "equivalent" LOOPs. We've tried a few depths of nesting; it quickly
    gets out of hand. 

Here are some of the comments that precede the definition of DOTIMES:

  ;The code generated by this macro has been carefully arranged to turn into
  ;the best sequence of macroinstructions: only one branch inside the loop,
  ;end at the end, avoid binding a variable to the countform if it is
  ;simple and loop-invariant.

This macro actually does quite a bit of analysis and optimization.
Rather than the naive 5-10 line definition, it is 69 lines long.  LOOP
isn't quite as aggressive about optimizing (it tends to be used for more
complex loops, where such micro-optimization would be lost in the
noise).

In particular, after it has constructed the PROG form that implements
the loop, it then does a code walk and substitutes the limit form for
the gensym'ed limit variable (in cases where the limit is a small
constant this replaces local variable references with immediate
operands).  The code walker has to recursively macroexpand the body, and
this gets nested pretty deep and conses huge environments.

However, it does a special check for the iteration variable being named
IGNORE or IGNORED.  In this case it actually uses the gensym'ed limit
variable as the iteration variable, and doesn't do this recursive
macroexpansion.  Renaming all the iteration variables in your example to
IGNORE results in it taking 1.3 seconds on my 3640.  Compiling this
version results in 1/18th as much list consing and 1/4 as much structure
consing.

Clearly it would help if it also recognized IGNORE declarations.  I'm
not so sure about calls to the IGNORE function, though, since it would
require a code walk to find them, which is what we're trying to avoid.

                                                barmar