gorry@tragicomix.liu.se (Goran Rydquist) (06/05/87)
Anyone know how the lookup of the messages are done in a normal
implementation of Smalltalk, or any other OO language?
Although the concept of inheritance is very powerful, it is clearly
associated with overhead from running around hierarchies to find
methods. Couldn't that processing overhead be traded against memory?
The inheritance concept should preferably not be thrown away, but kept
conceptually. Any ideas?
gorr\/ gorry@majestix.liu.se
/anders@suadb.UUCP (06/05/87)
In article <tragicom.576> gorry@tragicomix.liu.se (Goran Rydquist) writes: >Anyone know how the lookup of the messages are done in a normal >implementation of Smalltalk, or any other OO language? > >Although the concept of inheritance is very powerful, it is clearly >associated with overhead from running around hierarchies to find >methods. Couldn't that processing overhead be traded against memory? >The inheritance concept should preferably not be thrown away, but kept >conceptually. Any ideas? > >gorr\/ gorry@majestix.liu.se > / Inheritance as such is not the cause of overhead. Dynamic binding of methods is. Simula for example has inheritance, but resolves "method" binding at compile time (except for virtual procedures). Another common misunderstanding is that strong typing and late binding are mutually exclusive. The virtual procedures of Simula provide both strong typing and late binding. --------------------- Anders Bjornerstedt Department of Information Processing & Computer Science University of Stockholm S-106 91 Stockholm Sweden UUCP:{seismo,mcvax,cernvax,diku,ircam,prlb2,tut,ukc}!enea!suadb!anders ARPA: enea!suadb!anders@seismo.arpa
mkhaw@teknowledge-vaxc.UUCP (06/06/87)
In article <576@tragicomix.liu.se> gorry@tragicomix.liu.se (Goran Rydquist) writes: >Anyone know how the lookup of the messages are done in a normal >implementation of Smalltalk, or any other OO language? _Object Oriented Programming_, by Brad Cox, Addison-Wesley, 1986, contains a pretty good exposition of method lookup in Objective-C. Mike Khaw -- internet: mkhaw@teknowledge-vaxc.arpa usenet: {hplabs|sun|ucbvax|decwrl|sri-unix}!mkhaw%teknowledge-vaxc.arpa USnail: Teknowledge Inc, 1850 Embarcadero Rd, POB 10119, Palo Alto, CA 94303
gorry@liuida.UUCP (06/07/87)
In reply to my request >Although the concept of inheritance is very powerful, it is clearly >associated with overhead from running around hierarchies to find >methods... anders@suadb.UUCP (Anders Bj|rnerstedt) wrote: >>Inheritance as such is not the cause of overhead. Dynamic binding >>of methods is. Naturally, if there is some way of providing static binding through a compiler, the problem I mentioned with inheritance certainly would not arise, as the method lookup would be replaced by a subroutine call. So, in the case of dynamic binding, inheritance sure adds to the overhead of finding a method. A typical implementation looks up the method from the hashtable belonging to the class of the object, follows the inheritance chain if not found, and repeats. To shorten these paths, some redundancy scheme might be applicable. gorry gorry@majestix.liu.se
lsr@apple.UUCP (Larry Rosenstein) (06/13/87)
In article <576@tragicomix.liu.se> gorry@tragicomix.liu.se (Goran Rydquist) writes: >Anyone know how the lookup of the messages are done in a normal >implementation of Smalltalk, or any other OO language? > >Although the concept of inheritance is very powerful, it is clearly >associated with overhead from running around hierarchies to find >methods. Couldn't that processing overhead be traded against memory? I don't know about Smalltalk, but in a typed language such as Object Pascal (or C++) you can do just that. We have been working on Object Pascal (an object-oriented version of Pascal) for several years, and have tried various message lookup schemes. The scheme that gives you the best performance (but takes a lot of space) is one in which each instance points to the method table for its class. The method table contains a pointer to each method understood by that class. Because of the type checking in Pascal, the compiler can assign an index to each understood method at compile time. A message send is just an index into this table and therefore is very fast. When you make a subclass, you copy the superclass' table and change the entries for methods that you override. If the subclass adds methods you add them to the end of the table. It is this copying that increases the space used by method tables; you have to copy the whole table even if you only override 1 method. One disadvantage of this implementation is that you cannot (in general) add methods without renumbering the other methods. Since the numbers are assigned at compile time, this means recompiling modules when methods are added/removed. We implemented this scheme in the first version of Object Pascal, but haven't used it recently because of the space requirements. The messaging schemes you might be thinking of create 1 table per class and search that table to find the selector. If the selector is not found, you have to search the superclass' table. In our most recent implementation for the Macintosh, we invert the tables. Instead of 1 table per class, we have 1 table per message. This generally makes the tables shorter, since the number of implementations of a message is generally smaller than the number of messages understood by a class. (It also permits an optimization described below.) There is no need to search more than 1 table in this case. In our implementation the entries in the table are sorted according to the class hierarchy (the method in a subclass comes before the overriden method in the superclass). The lookup does a linear search until it finds the most specific method applicable to the target instance. We also put a 1 entry method cache in the table. The optimization you can make occurs when there is only 1 implementor os a message. In that case, all sends ofthat message are statically bound and changed into direct procedure calls. (This is done by our linker.) We also statically bind calls in certain other cases. As I said at the beginning, some of these techniques work only because Pascal has type checking. In Smalltalk you can send any message to any object, and can get a doesNotUnderstand error in some cases. In Object Pascal, the compiler ensures that the object will understand every message you send it. -- Larry Rosenstein Object Specialist Apple Computer AppleLink: Rosenstein1 UUCP: {sun, voder, nsc, mtxinu, dual}!apple!lsr CSNET: lsr@Apple.com