Faster PluggableLists-RFC (was Re: Faster Change Browser)

Eddie Cottongim squeak-dev at lists.squeakfoundation.org
Sun Sep 15 19:29:00 UTC 2002


This is a multi-part message in MIME format.

------=_NextPart_000_0062_01C25CCC.9D6263F0
Content-Type: text/plain;
	charset="iso-8859-1"
Content-Transfer-Encoding: 7bit

Daniel's changeset provides a noticable increase on large lists. If you file
it in to the current image, be sure *not* to file in the method
ScrollPane>>unadjustedScrollRange. A recent image change conflicts and will
cause an infinite recursion.

I've been working on some speedups for PluggableLists too and my stuff is
complimentary to Daniel's. I could use some advice on one part.

Currently, when you have a ScrollPane, everything inside it, including all
the stuff that isn't visible through the viewport, is drawn. You can see all
the occluded stuff by going to TransformMorph>>drawSubmorphsOn: aCanvas and
changing the line "clippingTo: self innerBounds" to "clippingTo: self world
innerBounds". Especially with Browsers and large lists, tons of stuff is
being drawn. The TransformMorph has no way to determine which submorphs may
be visible, so it tries to draw them all. It is impressive that Morphic is
fairly fast even with all the overdraw.

I thought LayoutPolicy might be the appropriate way to handle this. Layouts
may know enough about submorph positioning to trivially reject many morphs
without a per-morph check. So I created a SimpleListLayout that takes
advantage of the simple list geometry. Now, the Transform asks the Layout,
if present, for what morphs may be visible (submorphsOf: aMorph touching:
aBox) and draws only those. (Layouts beside simpleList don't have an
"accelerated" method for this yet.)

The second thing slowing down PluggableLists is that in order to run the
scrollbars we have to know the submorph height of their contents. If there
are 10,000 morphs, bounds takes a while to compute. LayoutPolicies may be
able to use their structure to help here, too.

ScrollPane only really needs to know the submorph height, so I gave
SimpleListLayout a submorphHeight method, which it can compute very quickly.
(item count*height). But a TwoWayScollPane would need to know height and
width, and maybe someone else would need to know bounds, etc. I haven't
implemented those things yet - other than height, they would not be very
fast for SimpleListLayout (although they could be cached). Does this sound
like the right way to go? Provide fast methods for things that are fast,
slow methods for slow things(and document those), and hope people call the
method that does the least necessary work.

This changeset implements the above ideas, and a few but not all of Daniel's
improvements (his stuff will make the list creation even faster when its
in).  Its experimental, so don't use on your these image, etc, and it will
change as I understand Daniel's fixes. With it, scrolling and dragging a
10,000 element list should be very smooth.

You can gauge improvement with this code. Try dragging and scrolling the
list. NB: if you file in my code, it won't take effect on existing lists.
You need to create another list to see the change.

p:= PluggableListMorph new.
c:= OrderedCollection new.
r:= Random new. c add: 'first'.
10000 timesRepeat: [c add: r next printString]. c add: 'last'.
p list: c; color: (Color green).
p openInWorld.

Eddie


----- Original Message -----
From: <danielv at netvision.net.il>
To: <squeak-dev at lists.squeakfoundation.org>
Sent: Friday, September 13, 2002 3:18 PM
Subject: Re: Faster Change Browser

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

------=_NextPart_000_0062_01C25CCC.9D6263F0
Content-Type: application/octet-stream;
	name="PluggableListSpeed-efc.2.cs.gz"
Content-Transfer-Encoding: base64
Content-Disposition: attachment;
	filename="PluggableListSpeed-efc.2.cs.gz"

H4sIAAAAAAAAAK1YXXPbthJ91gP/w1p5kHVrK5IdpzfstNPEjm98p0k8lW/64LE9EAlJaEiCIUjb
6uTH37MA+CHJTpNJM+OIJBaLxdndswsMTgud0vRTJcXHw9HBQqSpID2nyRH9V2SVKFZ0MB4f0GUi
SmlKqvIYDyE9efbvox+vSGcsOZV5KdOZLJysKOkgPHwejp9Tng52gv7xUmQLCbEy7PX25TwKTlhJ
r9ebHG5MDl5W5VIXPPY6jpWkY12WOluoNAjOk2qxELNE/qZM+VYX+ZJMLmVc5SYMJkMYk6woLsQd
JRAgBbWGyiXMEYWkW2UU5gYHQ6qMxHcYpNLcaftNrHRVUqlprrKYTFToJKGZrrLY0KdKRR+TVRBs
yS9lkhvC0ygI+jtB4D6f60RFKzLVLEqEMQBrc2LQU5kpRRbJD6JQvKV3IpWQHAyCnp30wPdc6+RE
RaXSGQYbaSC50MUKbxYSFe27NQyQD3a2TI50msqsnJYizTEHzqAXTydHT63nxgfh0dGA8kLBBTTe
Cc4oESveoEcTkSEcuqXOGa4Zuyfdo0TOS/qzMqWaKxmP6LWIlnbOwAAltVhCgyH5qRLJHqXio8oW
+MlWFIkkqhBc2JWhuTDliM5IpM6ZplIlo0BzXRBvwvvT++dWFqWCAkha8X1MLWRZFRmsvBWJiuu1
Z9jBTC8qQ3cqLpdWX2pdlDJoxn6wwQRPnmtjQ4XjZF4lJO/zQuKTtRBysT4rCb+AKSvP2PfTsqgi
rCvDgNiz8N6k1ytXuaT9/RpyEjMbYwi8vCpyjSAEnLV4M/Hg2yYeBMErGQkOaecijnWLs9+72aM7
CZizOo4plpGKJd0hVpYAThpK4TiaSZs8GTQDvoW6lRmSRt7luoBTPkhQAcc7I8IorGWjGSHYgp21
+E8lMjk2pxxKg8SODMg8FnfPniNeG3+8n4ckXIqXuoqWCBd8eKXvg/7vzsGt6zgmvWid69gBLKxn
2okjmupU+vCQMfnJKcIbG+d8ASYjulgiTBcyk4WKyOYOe8CGJ/wuTTaAI4AEQr+Qf8oI6yGInbKf
mpSXjWIbvRCW87mKFFQBfz8x1QAdC+/r+T58uz/T97VVmIC1C33rXMJ7yGUB1FPmjD0yCj8u5oEx
XN/M6+yYMoRz49UR9YPg2gPVgLdD1m9Tm0/nIpPrXltIYIbtPua3ybPw8Ah+4+yHsYXT8zuzfdCr
PcVxi40r+MXlLRtY2IqQqqwyViCqisKhwyEHu+FGMepDi5uD8pBopPrUW/7KUbOav1NJSJfXNL4a
9SnoXdOukckcSJQQbs0BN3g294xQ8NuFDsmKu0VOZFKKN3Z8CAfegwIDi9CjACE4qi+AM34BcKpM
xMyMMn4UHm+TvC853RHQ/LGQkUQSFmDQxl+MyOfm1YPgcos+Bz3/dEMtaJ2MHDUCgE2XjNwlIOvt
+q8guVxDIaPypF7DwcH5OGTZnppfFJUML6/9pG25Zu0rLMh/G+aGP9PX+5Q9ujHflZzAh+4DTcGa
h1SmSoVS8JfN4S8Q0BETEJe20Ba493OQOiLVYNd9dC6bLrFFUBguGpGteUgvuMYayqbQkjcHJorl
PYg841qFDTNHk5jKBAwAioLPGiwKmSKHXibJW+dqeIv13GyYU8PzsihAMZm8u6ollXmd5uWKvIvo
0oW2LKdtdJsR0bWPeWuEjO1yIWUqYU39d+8vXodcMu4USuyd4PrjSgc5ExzIjCuQNkYsQEi5K5kr
kqgaCBNUrplimr1TqLb8sbQFC7UahBmzvGJ/QB0ieq6zstmXfbmh80LOJSghApdyqxSLImZcTzHM
draQ3rjtoN5X8v38vNCgyhL90BPG+tiKce1+a6NibWa9ZFfXE2HcNt8XF8hHXqr1qfMF3JkwdJgZ
Su5z4MWedewN8fuofbU/nrrDNgwaCWV4kU5e0WUXZExgRkCrZ6UZmtD+TzLNl8IojOzaofr9JQQm
wyun8VQk5qtVXvFWd9vQfBTWGZyodcaG18JINSSxi9sh763mF7bjssUv1oxZSsgTekBN2GYGW4Pc
YAuWIJaEyaUxrase2mOZtBg/MoXj0CW2f2yMsgv10bnULS5IrdNYcrTWkQsKSLm3YCqo0xbhuwRW
7R7nquDsd4zet+bwsmdQ7jiyz/kKarih8a/jtfBag8eSHdzLoq4whPQC/35dDpHDTgH//wPtjvHN
Eu1DrB9uH3NAGl1pEccN63SAAS58TmH+8rGwkOWxq9MOV2TVGY+PvKc2GGV3183+mcbEzr10r790
wDLqL3k1bBmLSYjawG0FBXZvp18N29XWia3e0StR8NgHDlxU8NG4bnI2YfiGBhW1fPIj1wcr1fSm
KgvhqPugW5SNZ/7PbeEzAHCz8/pHoq5zfvnWqGunfmfUYRsX6OZgmcrh0KW+Czt2sYPdQcmR0E9R
Mer7nur7/DE+7BwY2u7D4Rz0cRRcP/OAdtFuuoN/Pa0GjM8zArayQRY39Fldj34OvuzK6931HQ//
tdv5Iiwn+7WG37/58WE4Pvq60xLi0kYGx8FmtFzwCZ49x8TpPn1wdyQ2qUEiGx8+t03ro6cvf+zx
ly34hj57sbTG9P8uIXobKDJxNNxwed0MMtW1hjeamk+nuNL6QxcJF/t2991ssR6pRxmHmw4Stic9
1wjZC/2fRKNOhR0Qce9RT1wD5wZ0t9s4Icd5o1E+pKdPabdV4QNhSCsM/UATVDF72JjYBn1b7/Zi
yD6/lA9gLLCl3x1x/pejnZ/Y3j1lulqHmO+tWmD7wXYqD7wrw8HeAzHSyew9GrDM1ga6yU+c/UG7
ILqRfMXuCh/QXYKXNrXVVN5paL6q249vcaV58HTynDNoTAeH4dEEGcTif6AdOG6aIuFU+75InK73
WvXTMXqOhiv9mv50gqvOGAQN2dvyjXvmuM+53ayNk7YLTWyTdWx/Z4mIPo58J3zj1sVrvR43lp2l
MYLnUx1VPDLnYun6WrsJnu92UVdK23+/2TasHn9wJ6PgAbDt7cYm5O4mE76Vf4M6boWfAfXoe9Ce
bcO8rGH2B5sZJkXv5B39I+59fEGPz0XNHA/Eo4givjnMFl/ici5kfEczbfgceSqORXYrDMqQP2j7
PJx2ilLQnvdtwV876/uxnjvkXG7P7xIiDgydO4EHRDdO+7bk+IuWuuB4oGxL4K1vWfUV+tDmhQ+I
icpzTGtuYFSGOzcXeRiOq8LqRF+y8qr4kNXrbZlWSD7fyRMd+h6mlsc9ZXICVH0zmvKZiP9MqnXp
LG4erSf/Dx9kHWELGQAA

------=_NextPart_000_0062_01C25CCC.9D6263F0--





More information about the Squeak-dev mailing list