One of the cool things about CLOS is that generic functions can check the type of an object, and then dispatch the proper method for those arguments.
My questions pertain to the way in which this happens:
First and foremost, I'd like to know if implementations of CLOS have the ability to look at declarations at compile-time and thus know which method should be used, in order to prevent this from being done at run-time.
Secondly, provided that the above is true, and CLOS does just that, I'd like to know whether CLOS can do something similar if only _some_ of the types are known. For example, consider a generic function which dispatches a method based on the classes of its first two arguments, each of which can be one of two classes. Thus, let's assume that this generic function has four methods, depending on the types (classes) of its first 2 arguments. Now, consider the situation where we declare one of those two types. Ideally, the compiler would be smart enough to only do run-time type-checks on the yet unknown field. I'd like to know if this is how it's actually done, or if it's done so that if anything is unknown, then the same typecase block is used.
In article <cxj90gr4ofu....@engc.bu.edu>, David Bakhash <ca...@bu.edu> wrote:
>First and foremost, I'd like to know if implementations of CLOS have >the ability to look at declarations at compile-time and thus know >which method should be used, in order to prevent this from being done >at run-time.
This generally isn't feasible. Declaring that a variable is of a specific class means that it could be any subclass of that class. This could even include subclass that don't exist at compile time. Note that this only applies to standard-class and structure-class types; builtin-class types have a known class hierarchy, and can't be subclassed by the programmer.
Dylan has the notion of "sealing" a class, which specifies that no subclasses will be defined. This allows such an optimization to be done with user-defined classes.
>Secondly, provided that the above is true, and CLOS does just that, >I'd like to know whether CLOS can do something similar if only _some_ >of the types are known. For example, consider a generic function >which dispatches a method based on the classes of its first two >arguments, each of which can be one of two classes. Thus, let's >assume that this generic function has four methods, depending on the >types (classes) of its first 2 arguments. Now, consider the situation >where we declare one of those two types. Ideally, the compiler would >be smart enough to only do run-time type-checks on the yet unknown >field. I'd like to know if this is how it's actually done, or if it's >done so that if anything is unknown, then the same typecase block is >used.
That's conceivable, although depending on the implementation of the dispatch table, it may only be feasible if certain parameters are declared. Multiple dispatch specifies a priority to different parameters (to resolve ambiguities), so it might only be able to skip the type dispatch if the type of the higher priority argument (the first, by default) is known.
In practice, I don't think any CLOS implementations perform this optimization. The main optimization in many CLOS implementations is caching the combined method for class combinations that have been used.
-- Barry Margolin, bar...@bbnplanet.com GTE Internetworking, Powered by BBN, Burlington, MA *** DON'T SEND TECHNICAL QUESTIONS DIRECTLY TO ME, post them to newsgroups. Don't bother cc'ing followups to me.
Barry Margolin <bar...@bbnplanet.com> writes: > In practice, I don't think any CLOS implementations perform this > optimization. The main optimization in many CLOS implementations is > caching the combined method for class combinations that have been used.
That's too bad that CLOS can't optimize such things. This is really evil, because I would think that declarations + generic function calls can expand into invoking the right method, despite what you said about subclasses, and that feature that Dylan has that CLOS doesn't.
Are there reasons that CLOS decided not to add that feature (i.e. sealing a class)? What are the drawbacks? I recall seeing something like this in Java, suggesting that it's there to allow for significant optimizations.
I don't think it makes much of a difference that this optimization is not performed. If you think about it, if you run the method only once, the cost to the whole program is negligible. If the method (with the same argument combinations) is invoked many times, caching should give you very similar performance, so you pay the penalty only once. The implementation wins by being able to avoid a lot of the complexity in this type of optimization.
David Bakhash <ca...@bu.edu> writes: > Barry Margolin <bar...@bbnplanet.com> writes:
> > In practice, I don't think any CLOS implementations perform this > > optimization. The main optimization in many CLOS implementations is > > caching the combined method for class combinations that have been used.
> That's too bad that CLOS can't optimize such things. This is really > evil, because I would think that declarations + generic function calls > can expand into invoking the right method, despite what you said about > subclasses, and that feature that Dylan has that CLOS doesn't.
> Are there reasons that CLOS decided not to add that feature > (i.e. sealing a class)? What are the drawbacks? I recall seeing > something like this in Java, suggesting that it's there to allow for > significant optimizations.
Barry Margolin <bar...@bbnplanet.com> writes: > In article <cxj90gr4ofu....@engc.bu.edu>, David Bakhash <ca...@bu.edu> wrote: > >First and foremost, I'd like to know if implementations of CLOS have > >the ability to look at declarations at compile-time and thus know > >which method should be used, in order to prevent this from being done > >at run-time.
> This generally isn't feasible. Declaring that a variable is of a specific > class means that it could be any subclass of that class. This could even > include subclass that don't exist at compile time. Note that this only > applies to standard-class and structure-class types; builtin-class types > have a known class hierarchy, and can't be subclassed by the programmer.
> Dylan has the notion of "sealing" a class, which specifies that no > subclasses will be defined. This allows such an optimization to be done > with user-defined classes.
This is equivalent to Java 'final' attributes.
I suppose that something like
(defclass z (x y) (<slots>) (:attributes :sealed #| or :final |# :unchangeable <other-attributes>))
:sealed (or :final) have the meaning that the class cannot be subclassed and :unchangeable has the meaning that instances of this class cannot change class.
This could be worked in the language. (Maybe this could be accommodated by meta-classes; I don't know). However the biggest problem would be to convince Franz, Harlequin and Digitool to use the same semantics and non to make it too difficult for it to be re-implemented in the PD lisps.
* David Bakhash wrote: > Are there reasons that CLOS decided not to add that feature > (i.e. sealing a class)? What are the drawbacks? I recall seeing > something like this in Java, suggesting that it's there to allow for > significant optimizations.
I'd be interested in knowing this too, if anyone who was there knows. I suspect it's because the notions of what you might want to be able to do and what might make sense to do just weren't sorted out enough at the time, and perhaps there was (is?) a notion that it should be possible to add via the MOP anyway. Now dylan has (?) sorted things out it might be easier to retrofit.
Obviously a vendor can simply add sealing to CLOS by some declarations, so it's not excluded in any case.
Tim Bradshaw <t...@aiai.ed.ac.uk> writes: > I'd be interested in knowing this too, if anyone who was there knows. > I suspect it's because the notions of what you might want to be able > to do and what might make sense to do just weren't sorted out enough > at the time, and perhaps there was (is?) a notion that it should be > possible to add via the MOP anyway. Now dylan has (?) sorted things > out it might be easier to retrofit.
> Obviously a vendor can simply add sealing to CLOS by some > declarations, so it's not excluded in any case.
IMHO, this would be the worst of possible worlds for the community as a whole.
Sunil Mishra <smis...@spanker.cc.gatech.edu> writes: > I don't think it makes much of a difference that this optimization is not > performed. If you think about it, if you run the method only once, the cost > to the whole program is negligible. If the method (with the same argument > combinations) is invoked many times, caching should give you very similar > performance, so you pay the penalty only once. The implementation wins by > being able to avoid a lot of the complexity in this type of optimization.
> Sunil
The Self project did in fact demonstrate that such optimizations could be useful. You not only reduce method resolution time but you can do further analysis in the method body with stronger assumptions about object types, potentially leading to elimination of various type checks, among other things.
However, it is not obvious that their techniques are directly applicable to Common Lisp although it should be pointed out that Self is arguably even more dynamic.
In article <cxj67bvryyp....@engc.bu.edu>, David Bakhash <ca...@bu.edu> wrote:
>Are there reasons that CLOS decided not to add that feature >(i.e. sealing a class)?
We didn't "decide not to add" it. I wasn't on the subcommittee that designed CLOS, but AFAIK the idea never actually came up (certainly never at the plenary level). CLOS was patterned mostly after New Flavors and LOOPS, and I don't think either of them had such a notion. What we have is more in keeping with Lisp philosophy, which allows extreme dynamism.
-- Barry Margolin, bar...@bbnplanet.com GTE Internetworking, Powered by BBN, Burlington, MA *** DON'T SEND TECHNICAL QUESTIONS DIRECTLY TO ME, post them to newsgroups. Don't bother cc'ing followups to me.
* Marco Antoniotti wrote: > IMHO, this would be the worst of possible worlds for the community as > a whole.
Why? A vendor can decide on some declarations or other syntax for sealing, document them, and provide a sample implementation (their own). Other vendors can use that syntax too, if they wish.
What mechanism is better than this? I seriously doubt that some group getting together and deciding on some way of specifying this in the inevitable absence of an implementation is a better way to do it.
Marco Antoniotti wrote: > This could be worked in the language. (Maybe this could be > accommodated by meta-classes; I don't know). However the biggest > problem would be to convince Franz, Harlequin and Digitool to use the > same semantics and non to make it too difficult for it to be > re-implemented in the PD lisps.
I would say instead that the biggest problem is that something like this shouldn't be standardized until someone has done a prototype implementation to debug the semantic details, to learn something about the performance gains, and to investigate what it might be like to do traditional late-everything Lisp development in such an environment. This is more-or-less how CLOS was adopted by X3J13.
Don't misunderstand -- I have long thought sealing would be a wonderful language addition and I would be eager to work on it myself.
Once some prototype is proven the language design, I don't think there would be significant problem getting vendors to implement it (especially if it could be defined to have null semantric content in conforming programs, like type declarations. and therefore ignorable in implementations that don't want to deal with it :-).
Tim Bradshaw <t...@aiai.ed.ac.uk> writes: > * Marco Antoniotti wrote:
> > IMHO, this would be the worst of possible worlds for the community as > > a whole.
> Why? A vendor can decide on some declarations or other syntax for > sealing, document them, and provide a sample implementation (their > own). Other vendors can use that syntax too, if they wish.
Especially since the proposed declaration would only be an optimization "hack", so that implementations that don't support the declaration can just ignore them (or you can conditionalize them out), and will suffer no evil consequences (apart from running a little slower, possibly)...
You just can't require all implementations to support the same things, especially optimizations.
Barry Margolin <bar...@bbnplanet.com> writes: > In article <cxj67bvryyp....@engc.bu.edu>, David Bakhash <ca...@bu.edu> wrote: > >Are there reasons that CLOS decided not to add that feature > >(i.e. sealing a class)?
> We didn't "decide not to add" it. I wasn't on the subcommittee that > designed CLOS, but AFAIK the idea never actually came up (certainly never > at the plenary level). CLOS was patterned mostly after New Flavors and > LOOPS, and I don't think either of them had such a notion. What we have is > more in keeping with Lisp philosophy, which allows extreme dynamism.
Right. When we introduced the notion of sealing in Dylan, X3J13 was already well on its way to finishing up its work. It would have been way too late, I think, to try to plug it back into that process.
At least one vendor---Digitool---has provided some sealing functionality. MCL supports a PRIMARY CLASS declaration. This restricts how a class can be used with multiple inheritance. Basically, you can only inherit from multiple primary classes if those classes inherit from each other. The result of this restriction is that slots declared in primary classes can be placed at the same offset in all instances, allowing very fast slot access. I'm not sure if MCL supports a SEALED CLASS declaration.
Finally, I should note that Dylan's SEALED CLASS declaration is different from Java's FINAL declaration in an important way. A final class in Java cannot have any subclasses. A sealed class in Dylan can have subclasses, but all of its direct subclasses must be in the same compilation unit (library) as the class itself. Thus in Dylan you can seal entire branches of the class hierarchy, not simply leaf classes. This additional functionality is important in the creation of fixed and efficient abstract interfaces. A similar distinction exists between Java's final methods and Dylan's sealed methods.
* David Bakhash <ca...@bu.edu> | This is really evil, because I would think that declarations + generic | function calls can expand into invoking the right method, despite what | you said about subclasses, and that feature that Dylan has that CLOS | doesn't. | | Are there reasons that CLOS decided not to add that feature (i.e. sealing | a class)? What are the drawbacks? I recall seeing something like this | in Java, suggesting that it's there to allow for significant | optimizations.
sealing is great for a language and environment where most of the hard stuff is done in the compiler and the program just _runs_. sealing is nigh evil for a language and environment where most of the hard stuff is done at load- or run-time and programs _evolve_ during their lifetime.
the problem is that just as we have no way to make a variable "unspecial" because of the impact on the already-compiled code, there is probably no sealing because it would be necessary to have an "unseal" mechanism, too, and that would impact already-compiled code just like special bindings.
the same goes, incidentally, for other (global) proclamations. if you declare a function's signature, should it still be possible to redefine it with, say, an additional optional argument, or with new argument types? which types should it be optimized for? should we have an UPGRADED-ARGUMENT-TYPE function?
I use Common Lisp for a reason. high performance is nice, but when its absence becomes a significant hurdle for an application, I have already figured out _where_ it matters the most by writing everything in Common Lisp and profiling the application. like, today, I reimplemented a _tiny_ part of my application as a 30-line C program, and also changed the algorithm to reduce the traffic across the interface (a pipe -- it has to be running in a separate process). it wasn't the kind of thing Common Lisp is good at, but the fact that this trivial C program takes a huge load off of the Lisp scheduler and leaves it to Linux to deal with, also means that the rest of the application can now become more complex before we need to upgrade from the 133 MHz Pentium it is currently running on. (the _only_ reason we use that kind of machine is that we have lots and lots of them. because such hardware is dirt cheap, it is also expected to die, so we use two of them in parallel, instead. we're in the curious position that the hardware may crash and burn, but the software must be kept running without noticeable interruption. this is not the kind of stuff you do in six months in C, but that's what it has taken me to do it in Common Lisp, and only now am I beginning to worry about performance. a 133 MHz Pentium isn't worth shit these days, but thanks to Linux and Allegro CL, a very significant investment in hardware can now have a _much_ longer life-span. the savings on the hardware side almost pays for my work. who'd've thought _that_ about Common Lisp?)
oh, one other thing -- by discovering this tiny CPU-intensive part, we were able to obtain a ten-fold overall system performance increase. since we had about the same factor when going from the old system to the new, the _observable_ response times have dropped to less than 100 ms, compared to 3 to 10 seconds in the old system. now, it wouldn't take a genius to spot the CPU-intensive part, but it did take Lisp to isolate it so cleanly and enable the ten-fold increase in performance. C coders just don't _do_ what what my hybrid solution does, anyway. so, for me, high performance computing on dirt cheap hardware comes with Lisp, and low performance computing on more expensive hardware was what C gave us. and isn't it perfectly ironic that because I _don't_ worry about high performance, _that's_ what I get, while the dude who wrote the previous version in C was mortally afraid of wasting cycles, and so wrote a system so slow it had to be replaced? the strangest thing is that most of what you really want from life obey the same apparent contradiction.
I'm not sure how much sealing classes would have helped in my scenario.
#:Erik -- The Microsoft Dating Program -- where do you want to crash tonight?
Tim Bradshaw <t...@aiai.ed.ac.uk> writes: > * Marco Antoniotti wrote:
> > IMHO, this would be the worst of possible worlds for the community as > > a whole.
> Why? A vendor can decide on some declarations or other syntax for > sealing, document them, and provide a sample implementation (their > own). Other vendors can use that syntax too, if they wish.
What if they *would not* wish so? Then you'd have two different implementations of basically the same thing. (..and have the nuisance of either writing less portable code or to sprinkle it with a lot of #+ and #-).
> What mechanism is better than this? I seriously doubt that some group > getting together and deciding on some way of specifying this in the > inevitable absence of an implementation is a better way to do it.
That is a very good point. A "reference implementation" (as pointed out by a private email to me) would be a very good thing indeed and probably the only way to go to convince the vendors to implement these features. However, I am throwing the stone and hiding the hand here, since I do not have the time to do such a thing.
One of the cool things about CLOS is that generic functions can check the type of an object, and then dispatch the proper method for those arguments.
My questions pertain to the way in which this happens:
First and foremost, I'd like to know if implementations of CLOS have the ability to look at declarations at compile-time and thus know which method should be used, in order to prevent this from being done at run-time.
as other people have said, sealing allows methods to be chosen statically in Dylan.
Secondly, provided that the above is true, and CLOS does just that, I'd like to know whether CLOS can do something similar if only _some_ of the types are known. For example, consider a generic function which dispatches a method based on the classes of its first two arguments, each of which can be one of two classes. Thus, let's assume that this generic function has four methods, depending on the types (classes) of its first 2 arguments. Now, consider the situation where we declare one of those two types. Ideally, the compiler would be smart enough to only do run-time type-checks on the yet unknown field. I'd like to know if this is how it's actually done, or if it's done so that if anything is unknown, then the same typecase block is used.
thanks, dave
Glenn Burke and I submitted a paper to ECOOP-99 on just this subject:
Partial Dispatch: Optimizing Dynamically-Dispatched Multimethod Calls with Compile-Time Inferred Types and Run-Time Feedback
We present a novel approach to reducing the overhead of dynamically dispatched multimethod calls by specializing call-site caches with information from compile-time inferred types, run-time profile information, and dynamic state. Dylan supports the development of reusable components using separate compilation. Unfortunately, separate compilation can starve the compiler of information necessary to perform full static dispatch of multimethod calls, for example when dispatch is performed on abstract types. Dylans sealing construct provides a way to gain back partial class hierarchy information and in this paper, we present an approach to gaining back complete class hierarchy information by delaying the construction of dispatch caches until the whole class hierarchy is available at run-time. Run-time call-site caches can then be constructed as specialized decision trees built from disjointness and concrete-subtype operations on actual arguments combined with compile-time inferred types injected into the run-time. Unnecessary decision steps can be avoided and often run-time dispatch can be completely eliminated. Furthermore, profile information gained through call-site instrumentation can be fed back to reduce space and time overhead. Finally, run-time dispatch state can be utilized to avoid multimethod dispatch steps in recursive calls. We present a mechanism for tracking this information in the face of incremental development and dynamic class creation. Together, these techniques can bring the average overhead of multimethod dispatch on par with single argument dispatch.
This can work in CLOS using just declared types (and would probably be a win), but it is much more powerful in Dylan because (1) sealing permits even higher quality type inference (especially in the face of separate compilation) permitting precise type estimates for arguments at call-sites and (2) abstract classes allow for further specialization of types inferred to be abstract classes by knowing that there can't exist direct instances of them.
* Marco Antoniotti wrote: > What if they *would not* wish so? Then you'd have two different > implementations of basically the same thing. (..and have the nuisance > of either writing less portable code or to sprinkle it with a lot of > #+ and #-).
Don't buy from that vendor! Scream and shout at them! Tell them right now that if they do something like that you will take your trade elsewhere! You are paying them real money for this stuff, they damn well ought to do what you say.
The vendors would, of course, like to tie you into their proprietary stuff, and if there was a monopoly (like in microsoftland) then users will really get tied in, and will end up living in hell. But I don't think the vendors are nearly powerful enough in the Lisp market to do this. I do think that people need to *tell* them this, often.
