Re: [Sbcl-devel] Sealing slot locations

[Nikodemus S. <nik...@ra...>]

On 8/18/07, Pascal Costanza <pc...@p-...> wrote:

I think there mainly two ways to approach sealing:

a) From the point of view of "what promises do I need to make to
   get efficient code"?

   Looking at things this way, you want to commit to as little
   restrictions as possible (to retain development flexibilty),
   as long as they are sufficient to allow the desired efficiencies.

b) From the point of view of "I'm doing something tricky here,
   and additional restrictions make it easier".

   In this case you want to be as restrictive as possible as long
   as those restrictions serve your needs.

I there some sort of consensus on these points?

I'm currently looking at sealing from the first point, though I have
no quarrel with the second as a desire.

>From that POV, I currently find the following things most promising

 * Sealing direct slot locations, types, and boundpness selectively.

   Sealing direct slots because when you seal effective slots
   you restrict features of the superclass: it cannot suddenly
   lose those slots anymore.

   Sealing selectively, so that when you are working on the system
   you can add slots to an already sealed class, and remove them
   again as long as you don't seal them in between.

   Sealing slot features, as they help making various slot
   accessors fast. (Though I've discovered that the permutation
   vector system PCL uses for slot-accesses inside method bodies
   is hard to beat with a decent margin!)

 * Sealing either subclass or superclass inheritance while allowing
   adding new classes to the heterarchy.

   Sealing subclass inheritance when you also seal the slots allows
   all method specializing on the subclasses to benefit from sealed
   slot features. There is no need to prohibit adding new classes
   to get the benefit. (This has proven quite convenient so far.)

   Sealing superclass inheritance when you subclass a class that
   has sealed slot features -- but where for one reason or another
   sealing subclass inheritance of the superclass is not appropriate
   -- allows you the again get the same benefits for the inherited
   slots. (I _think_ this is a reasonable want, but I freely admit
   I don't have horribly realistic use cases for this.)

 * Sealing generic functions in different ways (I have not spent
   much time on thinking about this yet.)

I cannot stress the value of being able to still modify the class
hierarchy in various way too much: otherwise you cannot seal things
at all for normal development, and your performance measurements
will not be correct.

> (1) I may want to say that a particular class should not be redefined
> anymore.
>
> (2) I may want to say that a particular class and all its current subclasses
> should not be redefined anymore. [Can easily be expressed if we have (1).]
>
> (3) I may want to say that the class hierarchy from a certain class
> downwards is closed - i.e., it should not be allowed to add more subclasses
> to that subtree.

All sound reasonable to me, but I'm not seeing huge optimization benefits
from them. Being able to infer that X holds true for all subclasses of
C is quite valuable. Knowing the full set of subclasses, or _all_
aspects of C seems less useful.

Contrariwise, these are not sufficient guarantees to make faster slot accesses
possible: ideally

 (defmethod foo ((bar bar)) (setf (slot-value bar 'x) (slot-value bar 'y)))

can compile into something like

 (setf (svref #:slots 0) (svref #:slots 1))

but this is possible only with stronger guarantees -- but doesn't require
locking _everything_ down -- just having a way to ensure that all subclasses
of BAR have X at location 0, and Y at location 1, and being able to know this
when the method is compiled.

Am I missing something here?

> While we're at it:
>
> (4) I may want to say that a particular generic function should not be
> redefined anymore (methods should not be added or removed).
>
> (5) I may want to say that the set of specializers covered by a particular
> generic function is complete (methods may be redefined, but methods for new
> specializers shouldn't be acceptable anymore).

Definitely!

> I think these are the kinds of things one may want to say because they are
> semantically meaningful, and at the same time, they should allow
> implementors to create more efficient code.

I'm there with you on 4 and 5, but as said I'm not sure 1-3 give the kind of
guarantees some optimizations require, and I also find them overly restrictive
when considering working with code that uses sealing.

> Dylan seems to have something like (3) and (4), and maybe (5) (but I don't
> completely understand the Dylan specification in that regard).

Actually, Dylan has one _very_ interesting feature: primary classes. You
are only allowed to inherit from a single primary class -- basically the
same restriction that I need to impose when sealing slot locations.

Doing things what way would certainly lead to a simpler interface, but
the behavior wrt. redefinitions (which I want, as long as they are
congruent) might get tricky.

> What's important, I think, is that the interface for sealing should be
> simple enough that the effects are easily predictable and should avoid
> potential hard-to-find bugs. I am not convinced that Nikodemus's suggestion
> is simple enough in that regard.

I sort of hoping this is due to my awful prose...

I've appended the cleaned up version of the SEAL-DIRECT-SLOTS docstring at the
end of this email -- it's even longer but the language is hopefully better.

> Tiny CLOS (both the Scheme and the Common Lisp versions) has a different
> instance structure protocol. I think it should be possible to integrate that
> new protocol with CLOS without violating the CLOS MOP (but I am not 100%
> sure), and get some improved efficiency out of it. It seems to me that parts
> of Nikodemus's suggestion goes in the same direction.

Thanks for the TinyCLOS pointer. I'll read up on it.

> With the current CLOS MOP, sparse instances should be possible: Just add
> more slots in compute-slots with gensymmed names. Or am I missing something?

Yes and no. Certainly doable that way, but not really sparse, in the sense
that those gensym-named slots are there, and if you ask the class for it's
slots you can get at those gensyms and therefore at the slots.

Cheers,

 -- Nikodemus

Appendix: SEAL-SLOT-VALUES, take 2:

   "Ensures that locations of the direct instance allocated slots identified
by SLOT-NAMES are sealed in CLASS, ensuring that all effective slot
definitions with these names in all subclasses of CLASS have the same slot
location.

SLOT-NAMES must either be a list of symbols naming direct instance allocated
slots of CLASS, or the symbol T (the default) to indicate that all current
direct instance allocated slots should have their locations sealed.

Returns immediately without doing anything else if all indicated direct slots
already have their slot locations sealed. Otherwise:

 * Signals an error if any subclass of CLASS has a non-instance allocated slot
   with a name matching any of the names indicated by SLOT-NAMES.

 * Signals an error if any subclass of CLASS has sealed direct slot
   locations, or has superclasses with sealed direct slot locations, unless
   those superclasses with sealed slot locations are also superclasses of CLASS.

 * Causes future redefinitions of CLASS to signal an error if they would
   remove any of the direct slots of CLASS whose locations have been sealed.

 * Causes future class definitions and redefinitions to signal an error if
   they would specify non-instance allocation for a slot whose name is
   indicated in SLOT-NAMES in either CLASS or any of its subclasses.

 * Causes future class definitions and redefinitions to signal an error if
   they would cause either CLASS or any subclass of CLASS to gain a superclass
   with sealed slot direct locations, unless that class is already a
   superclass of CLASS.

 * Causes the specified primary method on COMPUTE-SLOTS to sort it's results
   in a way that preserves the sealed locations.

Results are undefined if there is a non-specified COMPUTE-SLOTS method that is
applicable to CLASS that does not call the specified primary method and retain
the order of the slots it produces.

Results are undefined if the is a non-specified COMPUTE-CLASS-PRECEDENCE-LIST
method that is applicable to CLASS that returns a list that is not set equal
with the list the specified primary method would have returned."