I just examined Eddies code and it's very pretty. I endorse it's
inclusion into the image instead of mine (I wanted to do that, but
didn't know enough Morphic).

BTW, there's another performance problem in PluggableListMorph itself
(so it hits more tools, besides the change sorter), which is list:,
which has the same sort of problems - 
* Constant factors that can be pared off (and I submitted OptimizingList
(attached) to fix those)
* And it generates lots of morphs, which takes lots of time, and this
could be done lazily as one scrolls down.

I submitted a part of a fix to the second, and I think Lex submitted yet
another. Both should be considered, I'm willing to fix any problems in
my patch to get it in. This should making every update of every long
list (-all-, for example) significantly faster.

If people want Morphic more immidiately responsive, these should help.

Daniel Vainsencher 

Eddie Cottongim <cottonsqueak at earthlink.net> wrote:
> Daniel and I removed the same loop invariant (a repeated call to scroller
> submorphs, which forces a big copy) that was using almost 70% of the time
> originally. This gets scrolling up to about 5 refreshes/second up from less
> than 1 refresh/second originally. [this is on my p3-600 machine and test set
> of about 280 methods).
> 
> I removed an additional loop invariant (color blacker) which was using 16%
> of the time after the first problem was fixed.
> 
> At this point it was usable, but not smooth scrolling. It was still drawing
> the highlight rectangles and doing a bounds transformation for every
> selected item, even those which were not visible (on a large list, thats
> most of them). See the comment  in the original code, "NOTE: should be
> optimized to only visible morphs". My solution was to find the first visible
> one and the last, and only draw selection highlights for the ones in
> between. We can do this because the list of selected items is in order.
> After this improvement, the list scrolls smoothly.
> 
> So if N is the number of list items and K is the number of visible items,
> Daniel's fix improves the original code from O(N*N) to O(N), and mine
> improves it to O(K), which is helpful when K is significantly smaller than
> N.
> 
> Eddie
> 
> ----- Original Message -----
> From: "Scott Wallace" <scott.wallace at squeakland.org>
> To: "Eddie Cottongim" <cottonsqueak at earthlink.net>
> Cc: <squeak-dev at lists.squeakfoundation.org>; <danielv at netvision.net.il>
> Sent: Friday, September 13, 2002 11:41 AM
> Subject: Re: Faster Change Browser
> 
> 
> > Hi, Eddie,
> >
> > Note that Daniel Vainsencher contributed a speedup for large
> PluggableListMorphOfMany a year ago, which finally made its way into the
> internal (3.3a) update stream just this month, but has not yet been
> externalized.  His focus was on factoring out a loop invariant, and his code
> modified precisely the same method as yours.
> >
> > I attach the update here for your inspection -- please compare it with
> your work and let us know what you find.
> >
> > Cheers,
> >
> >  -- Scott
> >
> >
> > At 3:38 AM -0400 9/13/02, Eddie Cottongim wrote:
> > >I've noticed that if you "Browse Changes" on a changeset and then select
> > >many items, the change browser becomes painfully slow while scrolling.
> The
> > >following changeset improves this to make scrolling selected items nearly
> as
> > >smooth as with nothing selected.
> > >
> > >The culprit was PluggableListMorphofMany>>drawOn; the solution should
> help
> > >other users of that class, too.
> > >
> > >Eddie
> > >--
> > >
> > >"Change Set:  ChangeBrowserSpeedup-efc
> > >Date:   13 September 2002
> > >Author:   Eddie Cottongim
> > >
> > >When many list items are selected (such as in a change browser) in a
> > >PluggableListMorphOfMany, scrolling is extremely slow. This speeds up the
> > >redraw by
> > >1: removing loop invariants
> > >2: drawing highlight bars for visible list items only.
> > >"
> > >
> > > filename="ChangeBrowserSpeedup-efc.1.cs.gz"
> > >
> > >Attachment convertedChangeBrowserSpeedup-efc.1.cs.g (????/----)
> (00087AB1)
> >
-------------- next part --------------
A non-text attachment was scrubbed...
Name: OptimizingList.cs
Type: application/octet-stream
Size: 4403 bytes
Desc: not available
Url : http://lists.squeakfoundation.org/pipermail/squeak-dev/attachments/20020913/ed9c8af7/OptimizingList.obj