🚀 go-pugleaf

In article <nevin-1709951616450001@mac-nevin.cs.arizona.edu>,
Nevin ":-]" Liber <nevin@CS.Arizona.EDU> wrote:
>In article <43d484INNlge@keats.ugrad.cs.ubc.ca>, c2a192@ugrad.cs.ubc.ca
>(Kazimir Kylheku) wrote:
>
>> One thing that's "good" about PMT that's often overlooked is that it
>> doesn't allow the programmer to make assumptions about whether real
>> or apparent concurrency is going on. You have to use synchronization
>> mechanisms which scale well to multi-processors.  The way cooperative
>> multitasking is done on the Mac is particulary bad, because it is
>> based on ad-hoc methods.
>
>Er, the original MacOS was never, never designed to run on multiple CPUs. 
>It was designed for a machine with no MMU, no hard drive, 64K of ROM, 128K
>of RAM, run fairly fast, concentrate on teh interface, and only run one
>app at a time; in other words, affordable hardware in the early 1980s. 
>After that, keeping the OS backwards compatible was a major goal (and a
>very necessary one from a business standpoint).

Well that's all true and fine, of course. However, having been implemented
on affordable hardware in the early to mid 70's didn't stop UNIX from
entering the age of SMP.  How do you explain that?

>> Here is where the stupidity comes in: the system
>> re-arranges the allocated blocks in order to defragment the free space,
>> by physically pushing their contents around memory. If you store pointer
>> references to data within a block that has been moved, they will no longer
>> be valid.
>
>Unless, of course, you lock down the handle.

But if you lock down handles, you are fighting the OS in its efforts to
eliminate fragmentation.

>> The reason this scheme can work is because of the "cooperative"
>> multitasking.
>
>> You see, as long as you don't give up the CPU, memory will
>> not be moved on you. After your program returns from an explicit "yield"
>> call, it has to take steps to ensure that all accesses to global blocks
>> go to the right places, by dereferencing the right handles. Not only
>> is the CPU not virtualized, but neither is storage. 
>
>Given you were designing the Mac in the early 80s with the above
>constraints, how would you have done it?  Only a Pinhead would virtualize
>CPUs on a machine designed only to run one app at a time.

A pinhead or someone with enough sense to think about future issues, and
to think in terms of useful abstractions?  I should point out that It's
consistent with your reasonging to crown as geniuses the designers of
MS-DOS.

>> The Mac system programmers should have read the volumes of The Art of
>> Computer Programming by Donald Knuth, in particular the sections on heap
>> management where it is argued that it's better to coalesce adjacent free
>> blocks into larger blocks than to try to do garbage collection.
>
>And what happens when your 128K of RAM is totally fragmented??  Your way
>is shit out of luck, reboot.  The Macs way is do some garbage collection

Rebooting is the Mac way of life, so what's your point? I don't believe
that there is anything in the MacOS design that is intended to reduce
reboots due to crashes.

Why didn't Apple take the garbage collection paradigm "all the way",
then, and have the OS also move around running applications to eliminate
gaps between memory partitions?

>and continue on.  Have you ever even bothered to map out typical
>allocations in a Mac application to see if Knuth's reasoning is
>applicable?  Of course it's better (in terms of run-time efficiency) to
>coalesce adjacent free blocks, but in a typical windowing-based or

No, Knuth claims that it's not for run-time efficiency. For run-time efficiency
you can use other methods like the "quick fit". Coalescing buddy blocks does
mean that you have to keep your list of blocks ordered by address, which
does introduce some overhead.

>object-based system that has lots of heap allocations, it just doesn't buy
>you very much in terms of the amount of memory you get back (actually, it
>still gets done anyway, because it doesn't cost very much to do).  What is
>your solution to keeping the application and the machine running when this
>doesn't give you a big enough chunk of memory back, and you don't have an
>MMU and a hard drive to play VM tricks with to delay this problem?

I still think that coalescing is a far better solution, because it
doesn't force programmrs into exercising all kinds of needless
discipline in manging pointers.  This is the reason that Knuth cites as
an argument against garbage collection.  Believe me, run-time efficiency
isn't one of the strong points of garbage collection anyway. You still have
to have a list of blocks ordered by address so that you can move them
together. Plus, all that extra discipline on the part of the application
interferes with generation of efficient application code.

If you want garbage collection, you can do it with a garbage collection
library within the application.

I fail to see why a modern Macintosh computer should be constrained by
some software design hacked thrown together over a decade ago.  If
that's not an example of pinhead thinking, I don't know what is.

>> I
>> suspect that the programmers probably had experience implementing
>> BASIC interpreters (kind of like Billy Gates), and applied similar
>> strategies to OS programming. ("Let's do garbage collection like old
>> Applesoft BASIC did on strings!")
>
>And why did they do garbage collection on strings in the first place? 
>Because the heap strings are allocated out of tends to get fairly
>fragmented, and memory in those days was a very, very limited resource. 
>This was still true when the Mac came out, and for a number of years after
>that.

I once had to re-write that pathetic Apple II garbage collection routine
in 6502 assembly language because I needed it to work faster.  I hope
that the programmers who implemented the ROM routine don't work at Apple
any longer (or do you suppose that the code was a legacy of the connection
between Applesoft BASIC and Microsoft BASIC?).

Their strategy was to do:

while there are strings to be moved
	linearly search for the one with the highest address
		move it to the highest available heap addresss

Clearly, this is an O(n^2) algorithm.

As a result, a string-intensive program could wait as much as 5 minutes
for garbage collection to complete once it kicked in.  Apparently, they
never considered the user's time to be a limited resource.
-- 
Finger c2a192@keats.ugrad.cs.ubc.ca for PGP public key. Or contact
one of the public key servers -- the key id is 0xD3C7995D.
Microsoft users: crash test dummies?