brock%tuvie.UUCP@mcvax (Inst.f.Prakt.Info 1802) (04/08/89)
1. Does anybody know some reports about its realisation? 2. Immutable objects seem to be an ideal area to implement much more sophisticated storage allocation mechanisms than simple GC-algs: Consider two independently created sequences, structures or oneofs which are occasionally identical. The GC could remove one of them as one can be replaced with no effect by the others. This would be a very costly process indeed when one has to consider all existing objects. However, when one restricts this kind of "data compression" to some specific types the overhead would be locally limited. I am not shure if such a mechanism could be implemented in CLU itself, however has anybody considered this problem? Ulrich Neumerkel (ulrich@vip.UUCP UUCP: ...!mcvax!tuvie!vip!ulrich)
rcbc@honir.cs.cornell.edu (Robert Cooper) (04/10/89)
In article <677@tuvie> brock%tuvie.UUCP@mcvax (Inst.f.Prakt.Info 1802) Ulrich Neumerkel asks: > 1. Does anybody know some reports about its realisation? There is an internal MIT report: Sharon E. Perl "VAX CLU Implementation Notes" MIT Laboratory for Computer Science, DSG Note 124, 29 November 1984. This describes many aspects of the VAX CLU implementation including the mark-sweep garbage collector. You could obtain this from Barbara Liskov's group at MIT. > 2. Immutable objects seem to be an ideal area to implement much more > sophisticated storage allocation mechanisms than simple GC-algs: Consider > two independently created sequences, structures or oneofs which are > occasionally identical. The GC could remove one of them as one can be > replaced with no effect by the others. ... has anybody considered this > problem? I have not seen this suggested for CLU, but it has been proposed for functional languages. In particular see: William Stoye "The Implementation of Functional Languages Using Custom Hardware" University of Cambridge Computer Laboratory Technical Report 81, (Thesis), December 1985, p 4.7. A different approach is the hashing cons provided in some functional language systems. > Ulrich Neumerkel (ulrich@vip.UUCP UUCP: ...!mcvax!tuvie!vip!ulrich) Robert Cooper (rcbc@cs.cornell.edu)
scc@cl.cam.ac.uk (Stephen Crawley) (04/11/89)
> 1) Does anybody know some reports about [CLU GC's] realisation? There is a MIT internal document on the implementation of CLU. I can't remember its title (and my copy has gone walkabout), but the author is Sharon Pearl. Among the gems of useful information in this note are a description of CLU object formats and an outline of the garbage collection algorithm. > 2) [Suggestion to have the GC replace identical instances of an imutable > type with one instance] In most real cases this optimisation would give little space saving. On the down side, the runtime cost would be considerable. Every heap node would need a type field which would need to be initialised, the GC would need to do extra work for every node (i.e. to check if it was immutable). Finally for each immutable type (with N instances), it will cost a minumum of order N (when all instamces are identical) and probably Nlog(N) to eliminate the duplicates. The duplicate elimination algorithm would need to be applied of times to get optimal space saving. There are also "theological" issues here. Are two equal valued but distinct instances of an immutable type truely identical? If you stick to the operations defined in the CLU RM, they probably are. But if you use some of the other code supplied by MIT (e.g. the _cvt function), equal valued instances of an immutable type are distinguishable. [I admit it ... I'm a hacker :-)] -- Steve