alanh@tekig4.TEK.COM (Al Hooton, the available sailing crew member) (09/04/87)
Since I've only recently gotten interested in Smalltalk, the following question may already have been hashed to death in this group. If so, I'm sure someone will let me know, and I'll quietly go crawl back under the sailboat I crawled out from. After attending a recent in-house smalltalk seminar, it seems that the concensus on using smalltalk in real-time applications is it IS possible (which I would not have previously believed). The following two approaches seemed most popular: - develop in smalltalk, the automatically/manually translate to objective-C for run-time performance. - provide a smalltalk-to-C interface so that C routines can look like smalltalk objects or lower-level primitives; then, code all the time-critical stuff in C. Since the systems are embedded, and usually don't need all the window management stuff when running in the intended application, the images are 'cloned' to remove all the user-interface code. Which of these do YOU folks like? Are there other ways that are (better|worse|different|dumb|revolutionary)? Any specific considerations that might be shared by anyone who is doing this sort of thing? Gee.... we might even get a neat discussion of this... Al Hooton ...tektronix!tekig4!alanh
johnson@uiucdcsp.UUCP (09/05/87)
I suppose that the reason why you think that Smalltalk is not suitable for real-time applications is that it is too slow. However, I knew people who wrote real-time applications in Basic on a 6502, and Smalltalk on a 68020 can run rings around that. Thus, you just have to make sure that your computer is fast enough to keep up with the real-time constraints of the problem. Assuming that you think that speed is the problem, there are lots of ways to speed up Smalltalk programs. You mentioned two of them; convert the whole program (automatically) to another language or convert the inner loops to another language. I am building an optimizing compiler for Smalltalk that should make it much faster. Other people are working on special hardware for Smalltalk that should make it much faster. Interpreters keep getting more efficient and conventional microprocessors keep getting faster, so if Smalltalk is only a factor of 2 too slow, just wait a year. There is another problem with Smalltalk that is more severe. Smalltalk uses garbage collection a lot. Garbage collection can easily interfere with real-time requirements. The solution is to go back to using the reference counting techniques that implementors are now ignoring, use parallel garbage collection, or program very carefully and ensure that no garbasge is produced. Of course, any program that produces a lot of garbage won't convert to Objective C very well, since I think that it has no garbage collector. Please correct me if I am wrong. Lisp systems also use dynamic memory management, so it would be interesting to see whether anyone has built real-time systems in Lisp and how they solved these problems. I would be surprised if nobody has tried it. I have a student who is using Smalltalk for music composition. Her system is attached to a digital signal processor. She converts her compositions into a form that is interpreted by the d.s.p. and plays them there. The best way to describe this technique might be "build special purpose programmable hardware to perform the real-time primitives and use Smalltalk to control the hardware." I suppose this is little different from building these primitives in software using C or assembler. However, special purpose hardware can be fast enough to completely eliminate any supposed speed disadvantage of Smalltalk. In addition, if Smalltalk is not directly involved in real-time decisions, a second or two of garbage collection may not make much difference.
bobr@zeus.TEK.COM (Robert Reed) (09/09/87)
In article <80500016@uiucdcsp> johnson@uiucdcsp.cs.uiuc.edu writes:
There is another problem with Smalltalk that is more severe. Smalltalk
uses garbage collection a lot. Garbage collection can easily interfere
with real-time requirements. The solution is to go back to using the
reference counting techniques that implementors are now ignoring, use
parallel garbage collection, or program very carefully and ensure that
no garbasge is produced. Of course, any program that produces a lot of
garbage won't convert to Objective C very well, since I think that it
has no garbage collector. Please correct me if I am wrong.
This comment shows a basic lack of understanding about "garbage collection"
and "reference counting." In fact, most Smalltalk implementations employ
BOTH reference counting AND garbage collection. Reference counting is used
to detect "dead" objects (i.e. objects which are no longer referenced by any
other object). The space occupied by these objects may or may not then be
moved to a free list.
Eventually, fragmentation resulting from allocation and reallocation of a
given segment of memory may require garbage collection (i.e. the relocation
of "live" objects to coalesce the free memory of the segment into one block)
in order to keep the system from going belly up. Garbage collection has
nothing particular to do with reference counting.
--
Robert Reed, Tektronix CAE Systems Division, bobr@zeus.TEKjohnson@uiucdcsp.cs.uiuc.edu (09/09/87)
In fact, most Smalltalk implementations employ BOTH reference counting AND garbage collection. Actually, most of the Smalltalk interpreters build recently do not employ reference counting. Most use generation scavenging, a particular garbage collection algorithm. Reference counting is used to detect "dead" objects (i.e. objects which are no longer referenced by any other object). This is exactly what reference counting does. Eventually, fragmentation resulting from allocation and reallocation of a given segment of memory may require garbage collection (i.e. the relocation of "live" objects to coalesce the free memory of the segment into one block) in order to keep the system from going belly up. This is compaction, not garbage collection. Garbage collection is detecting all objects that can no longer be accessed and recovering their space. An object might be referenced by another "dead" object and so not be considered garbage by a reference counting algorithm. A cycle of these dead objects will not be recovered by a reference counting algorithm and so a reference counting algorithm is usually backed up by a mark-and-sweep garbage collection algorithm or something like that. Reference counting is really a particular form of garbage collection that is fairly cheap but that occasionally misses garbage. Generation scavenging is better, at least for Smalltalk. The original article on generation scavenging was by Dave Ungar and is reprinted in the May 84 issues of SIGPLAN Notices and Software Engineering News. Tektronix uses generation scavenging in their interpreter. The only company that uses reference counting in their Smalltalk interpreter is Xerox, and I have heard that they are planning on going to generation scavenging.
robison@uiucdcsb.cs.uiuc.edu (09/10/87)
I'll put in another plug for generation scavenging. I've used it for a
Russell interpreter and was impressed that only about 3% of the running
time is spent on garbage collection. A big advantage I've noticed is in
handling upward funargs. Normally these are expensive since they require
(without extra analysis) heap allocation of stack frames, most of which
die fairly quickly anyway. With the scavenging algorithm, the frames can
allocated essentially as fast as from a stack. (The allocation requires
incrementing a pointer and writing one word.) The extra overhead (compared
with stack allocation) is during scavenging, which runs in time proportional
to the *live* frames. Hence all the dead stack frames don't hurt much.
Arch D. Robison
University of Illinois at Urbana-Champaign
CSNET: robison@UIUC.CSNET
UUCP: {ihnp4,pur-ee,convex}!uiucdcs!robison
ARPA: robison@B.CS.UIUC.EDU (robison@UIUC.ARPA)goldfain@osiris.cso.uiuc.edu (09/13/87)
Very briefly, is there a general programming discipline that one can follow in the current Smalltalk-80 that will keep you from ever seeing the garbage collection symbol come up while your method is running ? It seems that if your method doesn't call anything that allocates new space you are set. What are some of the hidden pitfalls here ?
jans@tekchips.TEK.COM (Jan Steinman) (09/15/87)
<<<Very briefly, is there a general programming discipline that one can follow in the current Smalltalk-80 that will keep you from ever seeing the garbage collection symbol come up while your method is running ? It seems that if your method doesn't call anything that allocates new space you are set.>>> The very act of "running your method" *potentially* creates a MethodContext object, which generally becomes garbage (unreferenced) as soon as the method is exited. (*Potentially*, because all high-performance interpreters cache contexts, only creating bona-fide context objects when needed.) If your method contains a block that is executed, you most certainly create a BlockContext object and one or more MethodContext objects, which become garbage (unreferenced objects) as soon as the block is exited, and are therefore subject to collection. The quick answer is that there is no way to avoid creating garbage in Smalltalk-80, and currently available Smalltalk-80 systems do not allow turning off the collection of that garbage. :::::: Software Productivity Technologies --- Smalltalk Project :::::: :::::: Jan Steinman N7JDB Box 500, MS 50-470 (w)503/627-5881 :::::: :::::: jans@tekcrl.TEK.COM Beaverton, OR 97077 (h)503/657-7703 ::::::
ken@pdn.UUCP (Ken Auer) (09/15/87)
In article <12100004@osiris.cso.uiuc.edu>, goldfain@osiris.cso.uiuc.edu writes: > Very briefly, is there a general programming discipline that one can follow in > the current Smalltalk-80 that will keep you from ever seeing the garbage > collection symbol come up while your method is running ? .... That depends upon what your definition of "the current Smalltalk-80" is. Different implementors have used different techniques for garbage collection. Therefore it is possible that a technique which may minimize the garbage collection symbol from appearing in one implementation, may not do the same for another. Many implementations do constant garbage collection with generation scavenging (see earlier articles with subject "Smalltalk for (embedded) real-time") which will take care of most small garbage objects for you. If I'm not mistaken, generation scavenging does not work at all for "large" objects (where the definition of "large" may be different from implementation to implementation). As a previous article states, eventually the "major garbage collection" must take place in order to get rid of large objects, and to compact your memory due to its tendency to become extremely fragmented. I'm not familiar with every implementor's method for GC, but I don't think you can really totally avoid it. Keeping the number of large objects to a minimum can greatly ameliorate the frequency of "the garbage collection symbol" in most implementations. It is also possible to write a routine to force garbage collection when user activity seems to be low (e.g. s/he hasn't touched the mouse or hit the keyboard in x amount of time) which could be great under certain user conditions, but useless under others. > ... It seems that if > your method doesn't call anything that allocates new space you are set. What > are some of the hidden pitfalls here ? I don't know if there are any hidden pitfalls... they all seem blatantly obvious to me. :-) Personally, I don't believe you can right any useful code (except a few small special purpose applications -- perhaps math intensive stuff) in Smalltalk which doesn't create new objects which need new space. If you are programming in such a way that the previous statement is not true, you probably aren't taking advantage of the language at all. If that's not the case, I'm sure we'd love to have you for an interview. :-) -------------------------------------------------------------------------- Ken Auer Paradyne Corporation {gatech,codas,ucf-cs}!usfvax2!pdn!ken Mail stop LF-207 Phone: (813) 530-8307 P.O. Box 2826 Largo, FL 34649-9981 "The views expressed above do not necessarily reflect the views of my employer, which by no means makes them incorrect."
graver@uiucdcsp.cs.uiuc.edu (09/15/87)
The only problem with trying to write a Smalltalk "program" that sends no messages that allocate memory is that such programs would be VERY limited in usefulness. Any message must be sent to an object, the receiver. Only if the recceiver already exists, say, in the global dictionary Smalltalk, can even the simple task of sending a message be done without allocating new memory. If one wants to program in Smalltalk using only pre-existant object and using almost none of the existing system code, good luck. I would not want to attempt such a feat.
allenw@tekchips.UUCP (09/16/87)
In article <1320@pdn.UUCP>, ken@pdn.UUCP (Ken Auer) writes: > take care of most small garbage objects for you. If I'm not mistaken, > generation scavenging does not work at all for "large" objects (where the > definition of "large" may be different from implementation to implementation). > As a previous article states, eventually the "major garbage collection" must > take place in order to get rid of large objects, and to compact your memory > due to its tendency to become extremely fragmented. I'm not familiar with > every implementor's method for GC, but I don't think you can really totally > avoid it. Keeping the number of large objects to a minimum can greatly > ameliorate the frequency of "the garbage collection symbol" in most > implementations. The reclaimation of "large objects" can be easily handled by a generation scavenging storage manager. The technique used to accomplish this in Tektronix Smalltalk is described in our OOPSLA'86 paper. While the fragmentation of memory used to store large objects could be a problem, in practice, we have not observed it to be so. Our implementations reclaim but DO NOT compact the large object area. Reclaimed storage is placed on a free list which is available for future large object allocations. If free space is unavailable because of fragmentation (or any other reason) we simply expand our virtual address space. This, of course, requires an underlying virtual memory operating system which might not be present in an embedded system implementation. In such a situation we would probably compact the large object area when necessary (or incrementally). For current Smalltalk system, the main source of "large objects" appears to be saved bitmaps used to refresh obscured windows. I suspect that many embedded applications would not require them. While large objects need not be a problem, cross-generation circularities can be. A cross-generations circularity is a circular data structure which spans more than one generation. If such a structure becomes garbage, it can not be reclaimed until all the objects of the structure have "graduated" to a common generation (the generaton of the oldest object in the structure). The worst case occurs when the circular structure includes a object in the highest (longest lived) generation. All the objects of must then graduate to the oldest generation and the oldest generation must be scavenged before any of the objects can be reclaimed. Since scavenging of the oldest generation is essentially equivalent to a stop-and-copy garbage collection of the entire object space it can be very expensive. Such problems can often be avoided by breaking circularities (via the #release message in Smalltalk-80). Unfortunately, this is the same problem that occurs with reference counting schemes and the solution (breaking circularities) has the same undesirable impact of requiring application programmers to worry about storage management. Allen Wirfs-Brock Software Productivity Technologies Tektronix, Inc. allenw%spt.tek.com@relay.cs.net