*ListMorphs

Eddie Cottongim cottonsqueak at earthlink.net
Mon May 5 04:54:05 UTC 2003


I agree, Large Lists by Lex Spoon  is your best bet for a simple fix.

One thing I'll point out is that Squeak isn't going to be the environment of
the next thousand years or whatever if it can't handle displaying list
items, by default, in a scalable way. This question has come up several
times and each time we point the innocent off to some patch needed to make
lists run as well as they should by default. Morphic has been around for a
while now, and there isn't much excuse for such a serious kink to exist
despite several available patches and extensive discussion in the past. If
Morphic is only a temporary solution to be replaced "soon" by the next big
thing, thats fine, but I don't know that this is the case.

We need to either make LargeLists part of the standard distribution or
commission a group to implement a universally palatable solution that will
be adopted as standard.

Here are the causes of the slowdown as I understand (LargeLists mostly
addresses these, I believe)
1) Lists are slow to create and populate because the StringMorphs are
created all at once. This can be alleviated by creating them lazily (which
is a bit tricky afaik). LargeLists does this. This is the more minor problem
imo, but still annoying if, for example, you want to open a list of 5000
email messages.
2) Lists are slow to scroll because:
    a) ScrollPanes draw every submorph, not just the visible ones. Yes,
StringMorph has an early out, but the performance remains O( total items)
instead of O ( viewable items). I haven't figured out a better way for
general morph layouts, but for lists, its very easy to draw only the visible
ones. Maybe ScrollPane should have more than one policy for drawing
submorphs (general, slow policy, and fast specialized policies)
    b) ScrollPane is asked to find the bounds of all its submorphs for every
scroll update. This is very easy to cache. (5-liner, adds an instance var.)

Given of List of n items, where k are viewable at one time, the scrolling
performance can be as good as O(k), but the current version is O(n), leading
to poor scalability on a big enough list. If I want a list of a billion
items, with a window big enough for 10 of them, it should be just as fast as
if there were 20 items total.

I hope that doesn't sound too harsh, but I think people tend not to take
Morphic seriously if we don't.

I remember some people being mad that Java's Swing was slow with more than
20,000 menu items.. I'm not that picky! But 20,000 list items is a real
possibility.

Sincerely,
Eddie

Macus Said:

http://map2.squeakfoundation.org/sm/package/ee1e9026-1d3f-4092-971b-bd42b3d1
4670
Large Lists
Summary: A replacement PluggableListMorph and friends that performs well
with very large lists
Author: Lex Spoon


--
Marcus Denker marcus at ira.uka.de  -- Squeak! http://squeak.de






More information about the Squeak-dev mailing list