Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP Path: utzoo!mnetor!seismo!ut-sally!im4u!rutgers!ames!amdahl!nsc!voder!apple!lsr From: lsr@apple.UUCP (Larry Rosenstein) Newsgroups: comp.lang.smalltalk Subject: Re: Messages? Message-ID: <1021@apple.UUCP> Date: Fri, 12-Jun-87 18:42:35 EDT Article-I.D.: apple.1021 Posted: Fri Jun 12 18:42:35 1987 Date-Received: Sun, 21-Jun-87 01:44:41 EDT References: <572@tragicomix.liu.se> <574@tragicomix.liu.se> <576@tragicomix.liu.se> Reply-To: lsr@apple.UUCP (Larry Rosenstein) Organization: Advanced Technology Group, Apple Computer Lines: 71 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