> Perhaps not quite as fancy as a Quadtree but about 20x faster when having
> 10k elements for lists is the attached CS. It uses a simple, specialized
> version of TransformMorph which makes a few assumptions about the layout
of
> the children (e.g., being vertically arranged) and uses binary subdivision
> in drawing. It's basically the same effect as with the Quadtree version
(it
> just doesn't have to deal with the nastyness of updating the tree etc.)
>
> Cheers,
>   - Andreas

Quadtrees definitely aren't the best way to go for lists. Although the
scrolling performance is excellent, the tree building makes them open too
slowly. I think so far, users are getting more annoyed by the slow opening
times than by scrolling speed. The only solution to both problems that is
available now that I know of is Lex Spoon's LargeLists patch.

I would be very impressed if there is a 20x overall difference between
quadtrees and this binary method. Scrolling around, I get about 70 fps on a
plain list w/100 items, about 50 fps on a 10k item list with the quadtrees,
and about 50 fps on a 10k item list with the binary subdivision. By the way,
since PluggableLists pretty much assume a constant list height, can't you
dispense with binary subdivision and calculate the visible morphs directly?
That's one of the things the LargeLists patch does.

There's at least one other possibility for List display with fast scrolling
as well as fast opening. Have your List morph contain enough StringMorphs to
fill it, and rotate the contents to give the illusion of scrolling. This has
the advantage of low memory usage as well. I talked to Lex a bit about this,
and he likes his method better :)

It would be ideal if we could delegate the problem of finding what morphs
are visible. This would also help with event handling - if event handling
isn't clued in to our smarter search strategies, then things like mouse
events will still be slow. That boils down to answering the questions "What
Morphs are touching a bounding rectangle?" for drawing and "What morphs are
touching a point?" for events. Maybe LayoutPolicy would be a good place for
this responsibility.

I can think of several useful strategies for finding the visible morphs:

Linear search: The current strategy, and the best for small numbers of
arbitrary objects ( <  100 ish )
Direct indexing: For lists of uniform height, you know in constant time
which ones to display
Binary Subdivision: For lists of non-uniform item height (could also include
things like TableLayouts)
Quadtree: For large numbers of arbitrarily located morphs.

In the meantime, maybe we can get the TransformMorph-localSubmorphBounds
caching code into the image. That gives you about 50% more speed in
PluggableLists and ScrollPanes, and its so simple that even us Squeakers
couldn't find much to argue about.

Eddie