From: mks@cbmvax.commodore.com (Michael Sinz)
Newsgroups: comp.sys.amiga.misc
Subject: Re: 337 shells on an Amiga 500 - WB is **slow**
Date: 6 Apr 92 18:38:44 GMT
Reply-To: mks@cbmvax.commodore.com (Michael Sinz)
Organization: Commodore, West Chester, PA

cpmurphy@unix1.tcd.ie (Christian Murphy) writes:
> [more stuff deleted]
>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

n is actually the number of cliprects + number of layers but that is
not really it either.  (It is a bit more complex than that due to
the fact that cliprects are stacked vertically in overlapping layers, etc)

The order of the operation is more like O(n^3) in some cases and
O(n^2 log n) in others.

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

Yup.  And n can get large.  Worst case, the number of cliprects for
the display is:  n <= w^3/3 + w^2/2 +w/6.  (w is the number of layers/windows)

Now, with a simple O(n^2) you get a very big number.  Let me see, if you
had 10 windows in *worst case* overlap/size you would have
n=1000/3 + 100/2 + 10/6 = 385.  Which comes to O(n^2) = 148,225...

At 11 windows in *worst case* you would have
n=1331/3 + 121/2 + 11/6 = 506 ---> O(n^2) = 256,036...

That is one large number of iterations.

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

Other platforms do not really do it faster.  Some of the reasons
they are faster are simple, other are the fact that their layers
are simpler and the last of which is the fact that our layers are
not *yet* as fast as they can be.  (;^)

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

Well, let me just say that layers does not use any system private
structures other than those of layers itself.  (The layer, layer_info,
layer info extra, cliprects, etc.)  Layers is very self-contained,
only calling graphics and exec.

>No, I didn't think so.

I would think that most people would not want to do this.  There is
more to the issue than most people realize.  And compatibility with
programs that "assume" things about how layers works makes this much
harder than it should be.

/----------------------------------------------------------------------\
|      /// Michael Sinz  -  Senior Amiga Software Engineer             |
|     ///                   Operating System Development Group         |
|    ///   BIX:  msinz      UUNET:  rutgers!cbmvax!mks                 |
|\\\///                                                                |
| \XX/     Quantum Physics:  The Dreams that Stuff is made of.         |
\----------------------------------------------------------------------/