Re: "No aliasing = no garbage collection"

[tjoccam@xxxxxxxxxxxxx (Lawrence Dickson)]

Ruth,
   I think you have some interesting points, but are taking some things
for granted - a problem everywhere now that programming is such a
"mature" discipline... I'm attaching a note from Peter Welch which seems
very relevant (it's not clear to me who is getting what message)...
   Comments follow.

> To: java-threads@xxxxxxxxx, occam-com@xxxxxxxxx
> Subject: Re: "No aliasing = no garbage collection"
> Message-Id: <E13cW7g-0003W3-00@xxxxxxxxxxxxxxxx>
> From: "P.H.Welch" <P.H.Welch@xxxxxxxxx>
> Date: Fri, 22 Sep 2000 17:56:28 +0100
>
>
> < ... forwarding ... >
>
> From: Ruth Ivimey-Cook <Ruth.Ivimey-Cook@xxxxxxxxxx>
> Subject: Re: "No aliasing = no garbage collection"
> In-Reply-To: <E13cRxu-0004sG-00@xxxxxxxxxxxxxxxx>
> Mime-Version: 1.0
> Content-Type: text/plain; charset="us-ascii"; format=flowed
>
> At 13:30 22/09/00 +0100, you wrote:
> >} In my opinion, garbage collection is an efficiency mechanism.
> >} Conclusion (assuming I remembered correctly that the proof can be done):
> >}   if you are not bothered with performance, use a garbage collector,
> >}   and save on memory budget, use virtual memory as well.
> >}
> >}   if you are bothered with performance, buy twice as much memory, and
> >}   do not use a garbage collector, nor virtual memory.  Simply, use
> >}   enough memory.
> >Yes, I agree...
> >
> >The temptation to attach every bell and whistle is a strong one.
> >But that problem becomes an opportunity when you remember that
> >implies that the niche of clean, understandable simplicity is
> >almost unoccupied.
> >Larry
>
> I am slightly worried by this view. The experience of many ARM
> customers, working in the embedded space, is that memory is definitely
> not cheap. The reasons are:
>
> 1. What memory you have must be on-chip with the processor, which
> mostly limits it to small quantities of SRAM and slightly larger
> quantities of ROM or EPROM.

I once had great fun making a decimation TRAM (for radar use) out of 4
16-bit Transputers with only their tiny allotment of on-chip memory.
All in occam and assembly - it required tight coding of course.

>
> 2. The cost of many consumer items is a multiple of the manufacturing
> cost. That is, if it costs $5 to build, it costs $50 at the retailer
> (and that is perhaps understating the multiple). Consequently, adding a
> $10 DRAM to a design is not an option -- it would add $100 to the
> selling price.

But that applies to CPUs too! Microchip Technologies PIC processors
that zip along in assembly are much cheaper than ones that use C,
which in turn are cheaper than Java native chips using object oriented
language... occam natives should be somewhere between assembly and C
here...

>
> 3. Items like mobile phones typically have huge memory requirements --
> 3-5MB ROMS is not unusual, and RAM is also needed in large quantity.
> And yet if you look inside these devices you find only a couple of
> chips. Doubling the physical space required for memory is not possible
> -- it doesn't fit.

A clean small language ought to nicely reduce that ROM, and I'm not
sure you couldn't halve your RAM needs in many cases... not all, of
course... things like phone lists do need to be pretty dynamic. BUT
SEE PETER'S NOTE, BELOW. Real usable information is usually pretty
"flat" and probably could qualify for the alias control he describes!

>
> I believe there should be a garbage collection scheme added to occam.
> It is a great language for many things, but it is let down in areas
> which people care about intensely.
>
> Regards,
>
> Ruth

I think that 90% of the utility could be achieved by a linked list
management PROGRAM without damaging the roots of the language. I heard
that the Apollo program got to the moon on 38K of memory. I think real
time and embedded coding needs a foundational rework to bring it back
in that direction. (A DOS-like OS can give you total control of the
resources and then get out of your way... and occam program modules
can communicate as state machines correctly with just one layer of
dynamic resource allocation.)

Larry Dickson

Peter's note follows:

> To: Oyvind.Teig@xxxxxxxxxxxx, java-threads@xxxxxxxxx, occam-com@xxxxxxxxx
> Subject: Re: "No aliasing = no garbage collection"
> Message-Id: <E13cSOC-0005N3-00@xxxxxxxxxxxxxxxx>
> From: "P.H.Welch" <P.H.Welch@xxxxxxxxx>
> Date: Fri, 22 Sep 2000 13:57:16 +0100
>
>
> Ovind asked:
>
> >    Tom Locke (PhD student au UKC) said something like "if we
> >    remove aliasing, we also remove garbage collection, because
> >    we will not have non-parental objects floating around."
> >
> >    A somewhat weaker predicate might be "if we have aliasing
> >    under control, GC may also be under controll, in a predictive
> >    way." Is this true? Objects would still be taken from the
> >    heap, the heap would still be fragmented and a need to
> >    defragment it would arise? Or could objects be taken from
> >    the stack (possible in RT-Java) in that case?
>
> Tom discussed the various and very different ways in which we use
> references in OO systems.  These differences are alarming for what
> seems to be the same mechanism - he showed examples where that
> mechanism causes great harm (e.g. by breaking data encapsulation and
> making component based design unsafe).
>
> One major class of the use of references can be put under occam-like
> alias control - not all, of course (e.g. for graph data structures like
> doubly linked lists).
>
> Those that can be controlled are guaranteed to only have one reference.
> When that reference is lost (e.g. overwritten) the space for that
> object can be automatically de-allocated.  Using Brinch-Hansen's
> algorithms for parallel recursion workspace allocation - as modified by
> David Wood and presented in his paper at CPA 2000 - alias controlled
> single reference objects can be allocated and de-allocated in *unit*
> time with an average space wastage of only 25% ... which looks like a
> big win for real-time systems ...  the new rt-java draft specification
> for a real-time Java API just ducks the whole issue (they have unit
> time allocation and *no* de-allocation - if I follow it right - which
> is going to lead to memory efficiency problems or very tedious user
> code to get around it) ...
>
> But alias control can't be done with Java or C# or ... a better
> language is needed that takes these issues seriously.
>
> Peter.