[Openmcl-devel] Optimization

[Gary Byers]

On Sat, 11 Dec 2004, Dan Knapp wrote:

>    A recent improvement to clisp caused a large-percentage speed
> increase.  Of
> course, that's a very different architecture and it may not make sense
> to add it
> to openmcl, if it's not already there, but:  Any local variable which
> is actually a
> constant, gets an implicit type declaration, without specific programmer
> intervention.  This got me thinking.
>

? (defun foo ()
    (let* ((x 3))
       (1+ x)))

;; [ People don't often write code like this, but macros often do.]

That generates code like:

  (TWNEI NARGS 0)		; trap if not exactly 0 args
  (MFLR LOC-PC)			; build a stack frame
  (BLA .SPSAVECONTEXTVSP)	;  saving calling function, return address
  (LI ARG_Y '1)			; add 1
  (LI ARG_Z '3)			; and 3
  (BLA .SPRESTORECONTEXT)	; restore that stack frame
  (MTLR LOC-PC)			; and return address
  (BA .SPBUILTIN-PLUS)		; do arg_z = arg_x + arg_y at runtime

Adding two constants together at runtime (when their values were known at
some point during compile-time) is certainly silly, as is building a
stack frame so that it can be torn down almost immediately.  The OpenMCL
compiler will usually get rid of trivial bindings (things bound to constants,
some cases of things whose value doesn't change over the extent of the
binding) but doesn't do this in a way/at a time that makes subsequent
optimization (constant-folding, in this case) easy.  There are lots of
similar cases (many of which arise in the expansion of SETF/INCF and
friends) where something similar to a COMPILER-MACRO - that operated
on a slightly-lower-level representation of the program than the source.

In OpenMCL's compiler, that slightly-lower-level representation is
opaque and irregular and effectively write-only.  There are a few ad-hoc
things done at this level, but it's very hard to generalize or offer
a mechanism for extension.  (For the constant case above, you'd like
to be able to say "if you have an operator like + in the parse tree,
and its operands are all constants (however they got there), replace
the whole operation with the result of doing the operation at compile
time, and repeat the process on the parent node in the tree ...".

There's some limit on what you can do at the tree level (unless you
have some notion of control flow - where the tree starts to become
a graph - it's harder to be able to prove things (like "X is definitely
constant-valued at the point where someone calls (1+ X), even though
X is assigned other values at other points in the program"), but I
think that a -lot- of things could be caught in the parse tree (if
the parse tree was a little simpler, more regular, and easier to
traverse.)

Uh, I don't know if I'm answering your question ...

>    I don't have anything in the docs, even the implementation section,
> about what
> sorts of optimization OpenMCL does.  I also don't have anything about
> how
> developers can profile their own programs, apart from using (time) all
> over the
> place.  I'd like to add this kind of information.
>

As far as profiling goes: Shark (or CHUD-based tools, in general, on
OSX) is probably going to do a better job of sampling-based tools than
much of anything else will.  CHUD/Shark will (by default) sample about
once a millisecond, and the sampling happens via a kernel extension.

Most other ways of doing sampling are based on the idea of timer
signals (SIGALRM or SIGPROF, IIRC) being delivered to some thread in
the application.  This usually happens (theoretically) no more than
once every 10 milliseconds (1/100 sec, or 1 tick of most OS scheduler
clocks).  The issues of which thread gets the signal and of how
reliably it gets delivered (and with what latency) make it hard to use
this sort of facility to generate meaningful sampling results (though
many tools are still based on some combination of this and call-counting
instrumentation.)

Tools like Shark generally need some way of mapping a range of PC addresses
to a meaningful function name.  Shark provided a means of doing this,
but it was broken until fairly recently.  (Hamilton Link nagged the Shark
people at Apple - and provided them with a test case that showed that
things were broken - and they fixed it.)

>    What can you tell me about it?  Where in the source can I look for
> more
> information?

I'd be tempted to point you to the "ccl:compiler;" directory ...


>
> -- Dan Knapp
>
> _______________________________________________
> Openmcl-devel mailing list
> Openmcl-devel at clozure.com
> http://clozure.com/mailman/listinfo/openmcl-devel
>
>