Faster Change Browser

Eddie Cottongim squeak-dev at lists.squeakfoundation.org
Fri Sep 13 18:17:31 UTC 2002


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





More information about the Squeak-dev mailing list