From: Nikodemus S. <nik...@ra...> - 2007-08-14 10:15:53
|
I'm currently working on adding slot location sealing to SBCL. Concepts: Set of Superclasses: the set of classes reachable from a class via CLASS-DIRECT-SUPERCLASSES links. Set of Subclasses: the set of classes reachable from a class via CLASS-DIRECT-SUBCLASSES links. These are my workaround for the slightly nutty class linearization in CLOS for the purposes of this work. There are other parts to this, which build on this, but I'd like to first focus on the restrictions seen here in the main interface: generic function SEAL-DIRECT-SLOT-LOCATIONS class &optional slot-names Seals the locations of the direct instance allocated slots identified by SLOT-NAMES in CLASS, ensuring that all effective slot definitions with these names in the set of 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. Signals an error if any class in the set of subclasses of CLASS has sealed direct slot locations, or has a non-empty set of superclasses with sealed direct slot locations, unless those superclasses are also in the set of superclasses for CLASS. Signals an error if any class in the set of subclasses of CLASS has a non-instance allocated slot with a name matching any of the names indicated by SLOT-NAMES. 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 cause either CLASS, or a class in the set of subclasses of CLASS to gain a class in its set of superclasses with sealed slot locations, unless that class is already in the set of superclasses for CLASS. 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 class in its set of subclasses. 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 for sealed slots. .... Comments and questions more then welcome, -- Nikodemus |
From: Christophe R. <cs...@ca...> - 2007-08-15 11:08:43
|
"Nikodemus Siivola" <nik...@ra...> writes: > I'm currently working on adding slot location sealing to SBCL. > generic function SEAL-DIRECT-SLOT-LOCATIONS class &optional slot-names > Comments and questions more then welcome, I wonder if this kind of functional interface is the right one, actually. Both CLISP and Allegro, I believe, have an additional direct slot definition initarg to request a specified location for that slot, which has obvious advantages from the point of view of bootstrapping and avoiding metacircularities in the regular build. Those slots are (in your terminology, I guess) implicitly sealed, though I suppose it might be possible to override that sealing by introducing another direct slot definition. In any case, I think we ignore that prior art at our peril. Another piece of prior art is Gerd's approach to inline slot access, which is not a property of the class or its slots (a global property) but a property of the lexical context: a declaration requests inlining slot access, rather than having an all-or-nothing per-slot flag. This allows the user to specify inlining in cases where it's not provably safe. (Also, this looks a bit like a metalevel function, so I suspect consistency would demand slot definitions rather than slot names.) Some thoughts. Cheers, Christophe |
From: Nikodemus S. <nik...@ra...> - 2007-08-15 12:55:44
|
On 8/15/07, Christophe Rhodes <cs...@ca...> wrote: > I wonder if this kind of functional interface is the right one, > actually. Both CLISP and Allegro, I believe, have an additional > direct slot definition initarg to request a specified location for > that slot, which has obvious advantages from the point of view of > bootstrapping and avoiding metacircularities in the regular build. I can't find anything like that in the ACL docs, and while Clisp docs have a LOCATOR slot option in the DEFCLASS examples, it's not explained anywhere. Does anyone have a decent reference? As for bootstrapping issues, I haven't had any trouble so far. :) Seriously speaking, I did consider a slot option to set the location or request sealing a location, but that is error-prone and requires modification of source, so I don't consider it a good option: if you have a large program you don't want to grovel all over the source fixing locations once you think things are stable enough -- and conversely, once you discover that you do need to change things after all, you don't want to have to edit all your class definitions to refix the slot locations. Using a non-standard metaclass also doesn't seem like the right answer: sealing slot locations provides no new behaviour, just a set of additional guarantees. While the additional _restrictions_ can be considered new behaviour, I feel they are incidental. Furthermore, slot location sealing can be orthogonal from metaclasses, so that non-standard metaclasses can benefit from the same optimizations. > Those slots are (in your terminology, I guess) implicitly sealed, > though I suppose it might be possible to override that sealing by > introducing another direct slot definition. In any case, I think we > ignore that prior art at our peril. Definitely. I just seem to have trouble finding that prior art. :) > Another piece of prior art is Gerd's approach to inline slot access, > which is not a property of the class or its slots (a global property) > but a property of the lexical context: a declaration requests inlining > slot access, rather than having an all-or-nothing per-slot flag. This > allows the user to specify inlining in cases where it's not provably > safe. Yes. It's also nicely orthogonal from slot location sealing, and has support for automatic recompilation of things. I'm not sure sure about the provably unsafe bit, though: it seems to me CMUCL will just say "sorry, no can do" if the slot is not at a constant location in all subclasses. > (Also, this looks a bit like a metalevel function, so I suspect > consistency would demand slot definitions rather than slot names.) Quite possible, > Some thoughts. Many thanks! Some further thoughts: there is an underlying protocol here, which I have not yet discussed. Much more tentative then the restrictions on sealing (which have evolved a bit already), but the SEAL-FOO functions are only one half of the system. generic function COMPILE-SLOT-VALUE-USING-CLASS instance-form slot-name-form class env Called by the compiler for SLOT-VALUE forms for which a superclass of the instance argument is known at compile-time. Must return two values: if the secondary return value is true, the primary return value is the form to use in place of the SLOT-VALUE form. If the secondary return value is false, the compiler should use a normal call that goes through SLOT-VALUE-USING-CLASS. Default method returns the results of calling COMPILE-STANDARD-SLOT-VALUE-USING-CLASS with the same arguments if and only if the class of CLASS is EQ to either STANDARD-CLASS or FUNCALLABLE-STANDARD-CLASS, and NIL, NIL otherwise. Authors of metaobject classes can override this behaviour for their own classes, or use the standard optimizations by calling COMPILE-STANDARD-SLOT-VALUE-USING-CLASS. Note that the form retuned by this generic function must implement the same semantics as SLOT-VALUE-USING-CLASS for objects of the given metaclass. generic function CONSTANT-SLOT-LOCATION-USING-CLASS slot-name class If all instances of all subclasses of CLASS have an instance allocated slot identified by SLOT-NAME in constant location, returns it, NIL otherwise. Standard method calls CONSTANT-STANDARD-SLOT-LOCATION with the same arguments if and only if the class of CLASS is EQ to either STANDARD-CLASS or FUNCALLABLE-STANDARD-CLASS. Authors of metaclasses can override this for their own metaclasses. Cheers, -- Nikodemus |
From: Rudi S. <ru...@co...> - 2007-08-15 15:18:05
|
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 On 15.08.2007, at 14:55, Nikodemus Siivola wrote: > On 8/15/07, Christophe Rhodes <cs...@ca...> wrote: > >> I wonder if this kind of functional interface is the right one, >> actually. Both CLISP and Allegro, I believe, have an additional >> direct slot definition initarg to request a specified location for >> that slot, which has obvious advantages from the point of view of >> bootstrapping and avoiding metacircularities in the regular build. > > I can't find anything like that in the ACL docs, and while Clisp docs > have a LOCATOR slot option in the DEFCLASS examples, it's not > explained > anywhere. Does anyone have a decent reference? The thing that came to (my) mind is acl's def-stream-class for defining simple-streams. The documentation is mostly silent about its exact semantics, but essentially "known" slots in the simple- streams basic classes are given constant locations in their subclasses. Note that there are accompanying operators with-stream- class and sm for slot access. I suspect accessing simple-stream slots via slot-value is not optimized, but do not know either way. > Many thanks! Some further thoughts: there is an underlying protocol > here, which I have not yet discussed. Much more tentative then the > restrictions > on sealing (which have evolved a bit already), but the SEAL-FOO > functions are > only one half of the system. Random thought: would it be possible to have the corresponding UNSEAL- FOO functions as well, for the case when the class layout was not as finished as the programmer thought? It would be nice to be able to unseal classes, redefine them and then seal again instead of restarting the world. Cheers, Rudi -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.7 (Darwin) iD8DBQFGwxiv765FppppCGcRAtdZAKCp1Hlu3oHr8WxTCbBactzmAUeh4wCgpeP0 esg5ZvFLZa5b4u8ynBI7pdI= =kNNT -----END PGP SIGNATURE----- |
From: Nikodemus S. <nik...@ra...> - 2007-08-15 15:35:31
|
On 8/15/07, Rudi Schlatte <ru...@co...> wrote: > -----BEGIN PGP SIGNED MESSAGE----- > Hash: SHA1 > > > On 15.08.2007, at 14:55, Nikodemus Siivola wrote: > > > On 8/15/07, Christophe Rhodes <cs...@ca...> wrote: > > > >> I wonder if this kind of functional interface is the right one, > >> actually. Both CLISP and Allegro, I believe, have an additional > >> direct slot definition initarg to request a specified location for > >> that slot, which has obvious advantages from the point of view of > >> bootstrapping and avoiding metacircularities in the regular build. > > > > I can't find anything like that in the ACL docs, and while Clisp docs > > have a LOCATOR slot option in the DEFCLASS examples, it's not > > explained > > anywhere. Does anyone have a decent reference? > > The thing that came to (my) mind is acl's def-stream-class for > defining simple-streams. The documentation is mostly silent about > its exact semantics, but essentially "known" slots in the simple- > streams basic classes are given constant locations in their > subclasses. Note that there are accompanying operators with-stream- > class and sm for slot access. I suspect accessing simple-stream > slots via slot-value is not optimized, but do not know either way. > > > Many thanks! Some further thoughts: there is an underlying protocol > > here, which I have not yet discussed. Much more tentative then the > > restrictions > > on sealing (which have evolved a bit already), but the SEAL-FOO > > functions are > > only one half of the system. > > Random thought: would it be possible to have the corresponding UNSEAL- > FOO functions as well, for the case when the class layout was not as > finished as the programmer thought? It would be nice to be able to > unseal classes, redefine them and then seal again instead of > restarting the world. No fundamental reason not to -- you'll just lose the safety nets and need to recompile everything that needs recompiling. Some part of the recompilation can be automated, but automating all of it is on par with automatic recompilation of functions in general. Note that classes _can_ be redefined while they are sealed in one way or another: there are just restrictions to the manner in which they can be redefined -- wide-scale refactoring will generally need unsealing (or restarting the world), but incremental work should be generally possible: you can still add slots, subclasses, and superclasses as long as you don't violate the small print. Cheers, -- Nikodemus |
From: Rudi S. <ru...@co...> - 2007-08-15 15:39:04
|
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 On 15.08.2007, at 17:35, Nikodemus Siivola wrote: > On 8/15/07, Rudi Schlatte <ru...@co...> wrote: >>>> >> Random thought: would it be possible to have the corresponding >> UNSEAL- >> FOO functions as well, for the case when the class layout was not as >> finished as the programmer thought? It would be nice to be able to >> unseal classes, redefine them and then seal again instead of >> restarting the world. > > No fundamental reason not to -- you'll just lose the safety nets and > need to recompile everything that needs recompiling. Some part of the > recompilation can be automated, but automating all of it is on par > with > automatic recompilation of functions in general. Or, I imagine, automatic recompilation of functions when a macro is redefined. > Note that classes _can_ be redefined while they are sealed in one way > or another: there are just restrictions to the manner in which they > can > be redefined -- wide-scale refactoring will generally need unsealing > (or restarting the world), but incremental work should be generally > possible: > you can still add slots, subclasses, and superclasses as long as > you don't > violate the small print. That's good to hear. Will violating the small print lead to loud warnings or silent breakage? Idly curious mind wants to know ... Cheers, Rudi -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.7 (Darwin) iD8DBQFGwx4H765FppppCGcRAlOOAKCbpY7KOfR8CpQIUfLptMLtmnEfNACePNLx 97XFNCuk8bYuCfD0hg8+U5o= =zP27 -----END PGP SIGNATURE----- |
From: Pascal C. <pc...@p-...> - 2007-08-18 16:03:44
|
On 14 Aug 2007, at 12:15, Nikodemus Siivola wrote: > Comments and questions more then welcome, Hm, I have the impression that the interface you suggest is too low- level and too fine-grained. I think something simpler would be sufficient. Here are some suggestions, as a starting point for brainstorming: (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. 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). 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. Dylan seems to have something like (3) and (4), and maybe (5) (but I don't completely understand the Dylan specification in that regard). EuLisp seems to have something like (1), (2), (4) and (5). 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. 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. 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? Pascal -- Pascal Costanza, mailto:pc...@p-..., http://p-cos.net Vrije Universiteit Brussel, Programming Technology Lab Pleinlaan 2, B-1050 Brussel, Belgium |
From: Nikodemus S. <nik...@ra...> - 2007-08-18 18:49:51
|
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." |
From: Pascal C. <pc...@p-...> - 2007-08-20 19:39:59
|
On 18 Aug 2007, at 20:49, Nikodemus Siivola wrote: > 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? Yes, I think these are basically the two options. > I'm currently looking at sealing from the first point, though I have > no quarrel with the second as a desire. It may even make sense to use the first point as the low-level starting point on which semantically interesting properties can be based. > 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!) I have a hard time imagining that sealing slot locations or sealing types really buy that much. Types may be interesting for machine types (like fixnum), but apart from that, I don't think they are interesting from an efficiency perspective. What's more interesting on modern CPUs, I guess, is that caches are rarely invalidated and that variables used in combination are close to each other in memory. That's the case anyway for objects. Efficiency because of fixed slot locations sounds really 80's to me. ;) Declaring that a slot is never unbound seems to me to be more likely to buy something, but I am not sure here. > 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. I am surprised to hear this. Is efficiency really that important at development time? Maybe I am too old-fashioned, but I am thinking about optimization as being typically one of the last steps during development... >> (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. This may be useful for optimizing generic function dispatch, though. For example, it may become feasible to perform call-site dispatch without the need to recompile code because of potential changes in class hierarchies. > 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? If you close a hierarchy from a certain class downwards _and_ ensure that the respective classes cannot be redefined anymore, you can define and fix "optimal" slot locations for all involved classes. This is basically what defstruct gives you (without closing hierarchies, but determining "optimal" slot locations for single inheritance is much easier anyway). >> 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. I hope 1-3 is clearer. I understand your argument, but as I said, I find the idea weird of sealing some slot locations while the overall class definition isn't fixed yet. >> 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. I recall reading a paper about a suggestion for EuLisp to distinguish between classes and mixins. In CLOS, mixins is "just" a programming style enabled by multiple inheritance, whereas if you would make the distinction between classes and mixins explicit, you could get some benefits (including simpler linearization). I guess that almost all uses of multiple inheritance in CLOS are actually uses of mixins. (But of course, it's dangerous to make such statements, because nobody knows all CLOS programs...) >> 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. Thanks for reformulating. I don't understand the second and the fifth error condition. Aren't they too restrictive? Shouldn't the signal only an error if the set of sealed slots for different classes in the same precedence list overlap _and_ have different locations? Also, the final note for COMPUTE-CLASS-PRECEDENCE-LIST is redundant. C-C-P-L must return a list that contains the class and all direct and indirect superclasses in question, and all exactly once, anyway. (But maybe it's a good idea to keep this.) >> 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. You could define a new :allocation (like :hidden) that implies that an error is signalled when such a slot is accessed. (Hm, maybe that's too gross - just brainstorming...) Pascal -- Pascal Costanza, mailto:pc...@p-..., http://p-cos.net Vrije Universiteit Brussel, Programming Technology Lab Pleinlaan 2, B-1050 Brussel, Belgium |
From: Thomas F. B. <tf...@oc...> - 2007-08-21 20:35:06
|
> On 18 Aug 2007, at 20:49, Nikodemus Siivola wrote: > > > 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? > > Yes, I think these are basically the two options. Although I would say from a usability perspective, (a) is overstated. You want your promises to be easily comprehensible so you can remember the state of your running system and not get confused. It's no fun having to do a find . -name '*.fasl' | xargs rm && sbcl --load load.lisp just because your image state got too wacky compared to the written code. > I have a hard time imagining that sealing slot locations or sealing > types really buy that much. Types may be interesting for machine > types (like fixnum), but apart from that, I don't think they are > interesting from an efficiency perspective. >From my experience with Python and defstruct, higher-level type declarations can be very helpful in aiding the type inferencer, which leads to both the removal of various assertions as well as the ability to correctly infer the efficiency relevant types of rather indirect expressions. > > 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. > > I am surprised to hear this. Is efficiency really that important at > development time? Maybe I am too old-fashioned, but I am thinking > about optimization as being typically one of the last steps during > development... How many programs have gotten to their last steps, besides TeX? A lot of development goes in cycles, and in those cases where efficiency is actually needed, yes, it's often needed at development time as well. I find two major reasons for that in my work: first, you want to avoid making changes that cause performance regressions. Second, once you've gotten to evaluating your code on the sorts of data sets that run intolerably slow unless your code is highly tuned, you need your incremental changes to run efficiently as well. Otherwise you fall into a batch-language style edit-compile-debug cycle. |
From: Nikodemus S. <nik...@ra...> - 2007-08-20 22:27:05
|
On 8/20/07, Pascal Costanza <pc...@p-...> wrote: > > 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!) > > I have a hard time imagining that sealing slot locations or sealing > types really buy that much. Types may be interesting for machine > types (like fixnum), but apart from that, I don't think they are > interesting from an efficiency perspective. Sealing types definitely buys something. No numbers yet, as I haven't gotten to it, but it will allow inlining the type check, which will allow the compiler to do a much better job of it, and even elide it completely. Sealing locations is also a definite win: for slot-access dominated things (such code _does_ exists, eg. initialization of large objects.) We're talking about a 30% speedup. > What's more interesting on modern CPUs, I guess, is that caches are > rarely invalidated and that variables used in combination are close > to each other in memory. That's the case anyway for objects. > Efficiency because of fixed slot locations sounds really 80's to me. ;) Very true -- even the 80's bit, I think this should have been done already ;) One of the places where sealing helps is with caches (when combined with instance vector lifting), as you can get by with zero instead of two memory indirects before the actual access. > Declaring that a slot is never unbound seems to me to be more likely > to buy something, but I am not sure here. I'll let you know when I get there. :) > > 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. > > I am surprised to hear this. Is efficiency really that important at > development time? Maybe I am too old-fashioned, but I am thinking > about optimization as being typically one of the last steps during > development... Without getting into questions of development cycles and styles, the important thing is that if you want/need the benefit of sealing for your code, you need to know you _can_ seal your code. Performance tuning is also development, and being able to refactor things while running benchmarks and whatnot while things are sealed is a win. > >> (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. > > This may be useful for optimizing generic function dispatch, though. > For example, it may become feasible to perform call-site dispatch > without the need to recompile code because of potential changes in > class hierarchies. Gotcha, yes. > > 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? > > If you close a hierarchy from a certain class downwards _and_ ensure > that the respective classes cannot be redefined anymore, you can > define and fix "optimal" slot locations for all involved classes. > > This is basically what defstruct gives you (without closing > hierarchies, but determining "optimal" slot locations for single > inheritance is much easier anyway). Yes, though if you're inheriting from multiple classes with slots you don't have constant locations anymore -- so I'd be somewhat surprised if you could beat the permutation vectors using this approach. (Though optimizing accessor functions is a different question.) > I hope 1-3 is clearer. I understand your argument, but as I said, I > find the idea weird of sealing some slot locations while the overall > class definition isn't fixed yet. Fixed doesn't mean "will never change". :) This is a bit of strawman, but say that during performance tuning you realize that you might want to memoize something in a slot. So you need to add the slot, but everything is already sealed because you're doing performance tuning. Full rebuild takes 15 minutes. How many times does this or similar situation need to arise for selective sealing to be of value? > > 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. > > I recall reading a paper about a suggestion for EuLisp to distinguish > between classes and mixins. In CLOS, mixins is "just" a programming > style enabled by multiple inheritance, whereas if you would make the > distinction between classes and mixins explicit, you could get some > benefits (including simpler linearization). > > I guess that almost all uses of multiple inheritance in CLOS are > actually uses of mixins. (But of course, it's dangerous to make such > statements, because nobody knows all CLOS programs...) I think that's a fair characterization. I was positively surprised when In A Certain Large CLOS Program I was able to seal the slot locations of almost all classes with a given metaclass. There was just one measly exception, and it didn't even have any slots! (This was using a slightly earlier version of the sealing then the one I documented, which was had a bug that enforced the restrictions even when there were no slots actually sealed.) Trying to seal things in McCLIM would be an interesting exercise. > Thanks for reformulating. I don't understand the second and the fifth > error condition. Aren't they too restrictive? Shouldn't the signal > only an error if the set of sealed slots for different classes in the > same precedence list overlap _and_ have different locations? You mean sealing all of A1, A2, and AN should be possible here? (defclass a1 () (a)) (defclass a2 () (a)) (defclass an (a1 a2) (a)) Hum. Makes sense. I wonder how to state that in a way that is understandable. > Also, the final note for COMPUTE-CLASS-PRECEDENCE-LIST is redundant. > C-C-P-L must return a list that contains the class and all direct and > indirect superclasses in question, and all exactly once, anyway. (But > maybe it's a good idea to keep this.) Oh, good. I was rereading "A Monotonic Superclass Linearization for Dylan" when I wrote that and was having nightmares about someone doing Baker's global linarization in CLOS... > >> 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. > > You could define a new :allocation (like :hidden) that implies that > an error is signalled when such a slot is accessed. (Hm, maybe that's > too gross - just brainstorming...) Heh, -- Nikodemus |
From: Pascal C. <pc...@p-...> - 2007-08-21 18:00:33
|
On 21 Aug 2007, at 00:27, Nikodemus Siivola wrote: > On 8/20/07, Pascal Costanza <pc...@p-...> wrote: > >> I have a hard time imagining that sealing slot locations or sealing >> types really buy that much. Types may be interesting for machine >> types (like fixnum), but apart from that, I don't think they are >> interesting from an efficiency perspective. > > Sealing types definitely buys something. No numbers yet, as I haven't > gotten to it, but it will allow inlining the type check, which will > allow the compiler to do a much better job of it, and even elide > it completely. > > Sealing locations is also a definite win: for slot-access dominated > things > (such code _does_ exists, eg. initialization of large objects.) > We're talking > about a 30% speedup. OK, that's indeed interesting. I wouldn't have expected that. >> Declaring that a slot is never unbound seems to me to be more likely >> to buy something, but I am not sure here. > > I'll let you know when I get there. :) Good. ;) >>> 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. >> >> I am surprised to hear this. Is efficiency really that important at >> development time? Maybe I am too old-fashioned, but I am thinking >> about optimization as being typically one of the last steps during >> development... > > Without getting into questions of development cycles and styles, the > important thing is that if you want/need the benefit of sealing for > your code, you need to know you _can_ seal your code. > > Performance tuning is also development, and being able to refactor > things > while running benchmarks and whatnot while things are sealed is a win. OK, I give in. ;) >> Thanks for reformulating. I don't understand the second and the fifth >> error condition. Aren't they too restrictive? Shouldn't the signal >> only an error if the set of sealed slots for different classes in the >> same precedence list overlap _and_ have different locations? > > You mean sealing all of A1, A2, and AN should be possible here? > > (defclass a1 () (a)) > (defclass a2 () (a)) > (defclass an (a1 a2) (a)) > > Hum. Makes sense. I wonder how to state that in a way that is > understandable. CLOS already has to specify other features as a combination of multiple slot definitions. So I guess 7.5.3 in the HyperSpec would be a good starting point. Hm, this gives me an idea: Wouldn't something like the following be a better interface for sealing slots? (defclass c () ((s :sealed t))) The idea is that on class redefinition, :sealed cannot be set to 'nil anymore. I have something similar in ContextL, and I have the impression that it works well. The advantage of such an interface is that slot sealing would be clearly documented in the defclass form. (According to the entry for 'defclass in the HyperSpec, an implementation is allowed to extend the defclass form in such a way.) >> Also, the final note for COMPUTE-CLASS-PRECEDENCE-LIST is redundant. >> C-C-P-L must return a list that contains the class and all direct and >> indirect superclasses in question, and all exactly once, anyway. (But >> maybe it's a good idea to keep this.) > > Oh, good. I was rereading "A Monotonic Superclass Linearization for > Dylan" > when I wrote that and was having nightmares about someone doing > Baker's > global linarization in CLOS... That C-C-P-L has to obey this is a direct consequence of the fact that 'subtypep doesn't need a precedence list to determine whether one class is subtypep of another. Pascal -- Pascal Costanza, mailto:pc...@p-..., http://p-cos.net Vrije Universiteit Brussel, Programming Technology Lab Pleinlaan 2, B-1050 Brussel, Belgium |
From: Nikodemus S. <nik...@ra...> - 2007-08-21 18:27:00
|
On 8/21/07, Pascal Costanza <pc...@p-...> wrote: > > You mean sealing all of A1, A2, and AN should be possible here? > > > > (defclass a1 () (a)) > > (defclass a2 () (a)) > > (defclass an (a1 a2) (a)) > > > > Hum. Makes sense. I wonder how to state that in a way that is > > understandable. > > CLOS already has to specify other features as a combination of > multiple slot definitions. So I guess 7.5.3 in the HyperSpec would be > a good starting point. > > Hm, this gives me an idea: Wouldn't something like the following be a > better interface for sealing slots? > > (defclass c () > ((s :sealed t))) > > The idea is that on class redefinition, :sealed cannot be set to 'nil > anymore. I have something similar in ContextL, and I have the > impression that it works well. The advantage of such an interface is > that slot sealing would be clearly documented in the defclass form. > (According to the entry for 'defclass in the HyperSpec, an > implementation is allowed to extend the defclass form in such a way.) I'm seriously considering something like this, but there are catches: inheritance must be finalized before slot locations can be sealed. (Well, one could detect violations of the requirements at finalization time as well, but then you very easily end up with partially finalized class objects, which is just icky to my mind.) Similarly, it seems plausible that the functional interface should be SEAL-DIRECT-SLOT-DEFINITION-LOCATION|TYPE. > That C-C-P-L has to obey this is a direct consequence of the fact > that 'subtypep doesn't need a precedence list to determine whether > one class is subtypep of another. Ah, sanity. :) Apropos, I did get around to taking a quick look at TinyCLOS, and while the instance structure protocol it specifies is on the surface faster then the AMOP one, it is not clear to me that it is amenable to equally aggressive optimizations: since there are no slot locations, but getter and setter functions it's not clear to me that it would beat the permutation vector system PCL uses -- unless you manage to inline / open code the getters and setters at call sites. Quite interesting, still. Cheers, -- Nikodemus |