🚀 go-pugleaf

c2a192@ugrad.cs.ubc.ca (Kazimir Kylheku) writes:

>In article <nevin-1709951616450001@mac-nevin.cs.arizona.edu>,
>Nevin ":-]" Liber <nevin@CS.Arizona.EDU> wrote:

>>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. 

>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?

By different definitions of "affordable"? I mean, it's not like your
averge dentist could buy a PDP-11 in the 70s, while the mac (once it
was out) was such even a teacher could afford it.... There is two
classes of computers --- those costing more than a cheap car, and
those costing less. The first class is definitely not affordable by
my definition :-)

>>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.

_Everything_ in MacOS is meant to reduce crashes. However, reducing crashes
isn't something you can do by clever algorithms. Reducing fragmentation
is just another piece of engineering. 
BTW, I just had to learn about fragmentation for an exam --- there is
the so called "Knuth's 50% rule" which says that, after extended usage,
only 2/3 of the memory will hold meaningful data and the rest is lost
to fragmentation. Think about it before you call a scheme to reduce
fragmentation stupid on a machine that often has several thousand dollars
worth of RAM in it.

>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?

Because there weren't multiple applications when MacOS was written?

>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.

And now for your solution, please..... It's no good calling something stupid
without giving at least a hint at a better solution.

>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.

If every single check takes about 20 microseconds (a reasonable value
for that old machine) and we assume 0.5*n^2 checks, that n would have
to be more than 5000. On the 48k of the typical Apple II, this will
leave you with about 10 bytes per string (assuming your app doesn't
need any RAM). You lose two for the administration (keeping the list up 
to date), so your average string is of length 8.

Somehow, I haven't ever seen any app that uses 10000 strings of length
8. I'd be interested in which one that was.

Bernie

-- 
==============================================================================
I'm using an experimental version of "nn" to read news. So if anything seems
strange about the headers of this mail or post, please inform me. Thanks!