From: cpmurphy@unix1.tcd.ie (Christian Murphy)
Newsgroups: comp.sys.amiga.misc
Subject: Re: 337 shells on an Amiga 500 - WB is **slow**
Date: 6 Apr 92 12:26:42 GMT
Organization: Trinity College, Dublin

In <1992Apr4.211256.4019@athena.mit.edu> kdmiller@m4-035-16.MIT.EDU (Kenneth D Miller) writes:

>In article <1992Mar27.035009.26192@marlin.jcu.edu.au> cpca@marlin.jcu.edu.au (Colin Adams) writes:
>>In article <bmccnnll.701572148@unix1.tcd.ie> bmccnnll@unix1.tcd.ie (Barry McConnell) writes:
>>>Would anyone else like to perform the "20-window test"? ;-)  Who has an '040?
>>>Who's brave enough to try it on a non-expanded A500+ with no fast RAM??
>>
>>>BTW Having just closed all the windows, the time taken seems to decrease
>>>dramatically fairly quickly - the 19th window was about 12 seconds to close.
>>>I'm sure it all depends on exactly what is where onscreen, but for the
>>>whole machine to hang for that length of time - crazy!!
>>
>>Sounds like an O(n^2) problem to me.  I've heard the problem was in the
>>layers.library, and since 2.04 this has been made much faster.  When/If
>>we will get the faster routines is anyones guess.

>Sounds about right:

>Okay, you close a window.  Bing!  Layers.library goes in and redraws every
>other window, regardless of whether or not it's visible.  And layers, while
>very useful, does all sorts of hideous computations which have to be repeated
>for each window moved/closed/sized.  So, yes, it is probably O(n^2).

I think you're slightly wrong. layers.library _works_ out _which_
layers need to be redrawn. The algorithm that does this is (so
people seem to think) is O(n^2), where n is presumably the number
of windows. My guess is that it has a list of windows (because
_everything_ is a linked list on the Amiga) which it goes through,
one by one (from back to front?), working out if they're (at least
partially) visible. That makes the algorithm at least O(n). If
layers.library does more than O(1) computations per window that
would make it worse. Checking against every other window would
make it O(n^2).

>Unless C= recodes layers to be either 1. way faster (can you say "assembler"?)
>or 2. smart enough to know when a window is obscured completely, things will
>stay O(n^2).

The point is, it's going to be O(whatever) whether its coded in
assembler, BASIC, fortran, custom micro-code or hardware. Once n
gets larger than (some small number, such as 28), it doesn't matter
what you code in, that is _no_longer_ the bottleneck.

Does anyone out there know how they actually do it? And, also, how
other platforms do it faster (apart from the trivial answer of
faster processor). Coding layers.library in assembler isn't going
to gain you much over a reasonable C compiler, compared to a change
in algorithm. I think you're going to have to sacrifice some space
(ie. memory) to gain time (unless the algorithm they use is truly
atrocious).

Anyone care to do a SetFunction() patch for layers.library? Dunno
if you're going to have to delve in system-private structures or
re-implement clipped rendering (hack graphics.library?) as well.
No, I didn't think so.

Until then, the only answer is, don't open too many windows. Which
means, don't use Workbench. At least with a shell, you don't need
a window for _every_ directory you have on the path down to that
file. "Misc:src/ixem/library>" is much more managable on a prompt
than the workbench equivalent. Maybe if Workbench were better
designed for deep/large directory trees (such as: don't force us
to open a window for every step) things wouldn't be as bad.
Shell windows are as slow as Workbench windows, but you need
fewer of them and you don't open or close them very often.

>kdmiller@athena.mit.edu   |  Yep, it's KENNY MILLER... 

Christian "Workbench is for wimps anyway" Murphy

--
Christian Murphy, Trinty College, Dublin, Ireland  cpmurphy@vax1.tcd.ie
cpmurphy%vax1.tcd.ie@pucc.princeton.edu  ..uunet!ukc!tcdcs!vax1!cpmurphy
Newsgroups: comp.sys.amiga.misc