[Top][All Lists]

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

Optimization of applicable smobs

From: Mikael Djurfeldt
Subject: Optimization of applicable smobs
Date: 06 Dec 2000 19:04:20 +0100
User-agent: Gnus/5.0807 (Gnus v5.8.7) Emacs/20.7

At the end of the first letter, you'll find the suggested
optimization.  I included the second letter F.Y.I.

Best regards,

Subject: Topics

   Re: Applicable smobs & guile-vm
   Applicable smobs & guile-vm

--- Begin Message --- Subject: Re: Applicable smobs & guile-vm Date: 31 Aug 2000 05:47:59 +0200
Keisuke Nishida <address@hidden> writes:

> >   But in order to achieve this, we need to support tail-recursion!
> >   Otherwise, we'll not have Scheme semantics.
> I don't understand how Guile handles tail-recursion.

Essentially by a jump back to `loop:' in SCM_CEVAL.

In Guile, this makes closures properly tail-recursive.  And everything
else which is properly tail-recursive makes use of this.

For example, `apply' is defined like this:

  (set! apply (lambda (fun . args) (@apply fun (apply:nconc2last args))))

where @apply is a tail-recursive form.

(BTW, it is essential that the call/cc in your VM is tail-recursive.
 Guile's call/cc is defined like this:

  (define (call-with-current-continuation proc)
    (@call-with-current-continuation proc))

 where @call-with-current-continuation is a tail-recursive form which
 simply "replaces itself" with proc.)

> Why do applicable smobs suffer from it?

Because invoking them involves a call to a C function.  This call
leaves a return address on the stack---the stack grows.  If the smob
then calls another function, the stack grows even more.  Proper tail
calls doesn't cause the stack to grow.  In Scheme, iterative processes
should be possible to write using tail calls.  If the stack would
grow, the maximum stack size would set a limit to the number of

This is no problem as long as the smob application never invokes user
closures, but it is a problem if it invokes programs of your VM,
because the user expects a closure compiled to byte code to be
properly tail-recursive.

> I think applicable objects are better, too.  Are they already
> available?

Yes, but the current objects are based upon structs which are
generally awkward to handle.  You could probably use them, but instead
of using your program mark function, you would have to produce an
object layout (prurprprur etc, where "p" means protected word).

If you do this, your programs should be instances of the class
<program> which itself should be a subclass of <operator-class>.

You use `set-object-procedure' on <program> to set the operator
procedure (the VM interpreter).

> Do they optimize tail-recursion?

If the operator procedure is a closure, and the closure is
tail-recursive, then the operator itself is tail-recursive.

If you, for example, embed the call to the byte-code interpreter in
macro and let the interpreter return the tail-call form, then you can
make the thing tail-recursive.

But, probably, Michael Livshin's suggestion is better: to have a
special type for tail-calls.  In this case, we should implement a new
type of applicable GOOPS object for this.

> By the way, why do procedure-with-setters exist?  Aren't procedures +
> setter properties sufficient?

1. Setter properties can be implemented efficient or inefficient.  An
   efficient implementation means adding a `setter' field to
   closures.  We don't want that because closures should be extrely
   lightweight.  We don't want an inefficient implementation at all.

2. It is natural to be able to set properties.  We can't allow this
   because the association of the setter to the procedure needs to be
   permanent.  This is because the compiler should be able to
   eliminate the setter invocation construction entirely, leaving only
   the actual mutating code.  For example, the compiler should be able
   to cut through the setter-construction, the GF invocation and the
   method closure in order to convert the GOOPS expression

     (set! (counter object) 0)


     SCM_SLOT (object, 3) = 0;

> If Guile is supporting applicable smobs, I'll optimize them.

An applicable smob representation of gsubrs is much more attractive
than the current cclo implementation.  For gsubrs, it *is* actually
nice that the applicable smobs are so lightweight.

Also, I just made a benchmark indicating that the interpreter is at
least as fast as before introducing applicable smobs.  (I again
noticed the funny phenomenon that the interpreter seems to get faster
every time we extend the switch statements in SCM_CEVAL...)

Therefore, I suggest that we keep the applicable smobs at least until
we have lightweight applicable GOOPS objects (which might take some
time) and implement gsubrs using these.  After introducing the new
GOOPS object representation we can still keep the smob API for a
while, just replacing the internals of smobs.

If you want to carry out the optimization I suggested (or a better one
which you have thought of) you should do it so that we can re-use the
code for the gsubrs.

For example, in my suggested optimization, you need to "compile" a
certain procedure arity into four different trampolines (including the
potential no-trampoline direct call cases).

If we represent gsubrs using applicable smobs, these, in turn, need
four trampolines stored in the actual object.  The gsubr smob
trampoline (which corresponds to the current scm_gsubr_apply) would
simply hand over the arguments to the trampoline of the gsubr

With such a construction, note that the code for compiling an arity to
four trampolines can be re-used to compute the trampolines of the
gsubr instance.

--- End Message ---
--- Begin Message --- Subject: Applicable smobs & guile-vm Date: Fri, 25 Aug 2000 23:35:07 +0200
I vacillated back and forth many times this night on the point of
whether it was a good decision or not to add applicability to smobs.

In any case:

- It is not a good solution to your problem, Keisuke.
  Before integrating the VM fully, one should be able to take an
  arbitrary closure, compile it to a program, and then have it
  interact with the rest of the Scheme as if it hadn't been compiled
  at all, right?
  But in order to achieve this, we need to support tail-recursion!
  Otherwise, we'll not have Scheme semantics.
  We need to think about this.  We could learn from how RScheme
  achieves tail-recursion, from the closure `apply' (which calls the
  syntactic form address@hidden' internally, and from GOOPS methods and
  compiled closures.

- I feel a little uncomfortable extending the Guile API without a
  strong motivation.  Smobs are supposed to be a way to add basic,
  light-weight types.  We are supposed to use the *new* (unfortunately
  non-existing) GOOPS object representation for representing all other
  new types.  The only real motivation for using smobs instead of
  GOOPS objects is when we want instance creation to be really simple
  and where we want memory overhead to be small.  This is not
  generally the case for applicable objects.

- By adding `scm_set_smob_apply', we are at the same time promising to
  support this in the future... There are now tons of applicable
  things in the evaluator, and since these things are part of the
  Guile API, any new interpreter or compiler needs to support them:
  subrs, cclos, structs, GFs, pwses (and I've probably omitted

- We can probably not use applicable smobs as the basic representation
  for cclos because of the tail-recursiveness problem, so we can't
  motivate them because they can eliminate the use of cclos.  (If we
  find a smart solution to the tail-recursiveness problem, they
  actually might.)

- Same goes for pwses (procedure-with-setters).

On the other hand:

+ As I said before, applicable smobs could be a natural representation
  for many internal Guile things, such as Guardians and standard eval

+ In fact, they would be a much better representation for gsubrs than
  the current use of cclo.

+ In the future, we might want to eliminate smobs, replacing them with
  a super-lightweight form of GOOPS object which has the class pointer
  stored in a table.

+ Maybe, after all, applicability is a natural thing to support.

In any case, here's a point on the current applicable smobs:

   It's possible to optimize the current smob dispatch mechanism
   according to the following:

   Currently, the role of the scm_apply_smob_X functions is to
   translate the shape of the call to a shape which fits the function
   installed in the smob type.

   The structure of the scm_apply_smob_X functions is as switch
   statements which select an appropriate translation form.  Let's
   call such a form a "trampoline".

   Currently, we dynamically do all of the job to select the correct
   trampoline at each call, when a lot of this job could actually be
   performed once and for all in scm_set_smob_apply.

   Here's a suggestion for a more efficient approach:

   * We replace the current gsubr_type field in the smob descriptor
     with the fields trampoline0, trampoline1, trampoline2, and,

   * Instead of having the trampolines in switch statements, we
     implement them as separate C functions.

   * Instead of calling the *generic* function (not in the OO sense!)
     scm_apply_smob_0 in the evaluator, we call the function stored in
     trampoline0.  This field is *ahead of time* prepared with a
     trampoline function which translates a zero arg call to the shape
     appropriate for the function stored in the `apply' field.

   * scm_set_smob_apply in a sense "compiles" the type by selecting
     the appropriate trampolines at type creation time.

   * Note now the possibility for a nice optimization:

     If the function stored in `apply' takes, for example, two
     required arguments, then the *function itself* can be stored in
     `trampoline2', and we have eliminated one level of indirection.

--- End Message ---

reply via email to

[Prev in Thread] Current Thread [Next in Thread]