🚀 go-pugleaf

In article <DFBHIv.8F2@wombat.hanse.de>,
Bernd "Bernie" Meyer <root@wombat.hanse.de> wrote:
>_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.

I'm going to have to dig up that Knuth!

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

Good excuse.

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

My solution was still O(n^2), but well over a 100 times faster. All I
did was look for the 128 highest strings in each pass, keeping their
(16 bit) addresses in a page of 256 bytes. I was only in 8th grade,
by the way. Quite a bit less mature than the people working at Apple
or Microsoft.

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

Not quite a reasonable value. The machine could do about four instructions
in that time. It took two subtractions just to compare one 16 bit number
to another, involving two loads and two conditional branches. It
would take a 1Mhz 6502 more than 20 microseconds just to do the comparison.
Typical cycle counts for instructions were anywhere between 3 and 7.
If I recall correctly, a branch such as BCC would take 3 clocks if not
taken, four if taken, and an additional clock if it crossed a page boundary.
In other words, up to about 5 microseconds.

It would take at least 100us to do the check, comparison, replacement,
and loop increment, etc. You have 0.5*n^2*0.0001s = 300s. That gives you
n =~ 2450. I might have exaggerated that 5 minutes a little; say that
the wait was only 2-3 min and recompute n. You get a pretty reasonable
number of strings.

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

Not possible. 8x10000 > 48x1024, right?

The "app" was BBS software that I developed myself.
-- 
PGP key id is 0xD3C7995D.
Molybdenum 95! Got your ounce of fission byproduct yet?