sugar start-up profiling

[Eben Eliason]

Spread layout should:
* Position icons so as to minimize overlap
* Support a suggested location for the position of a given icon
* Support both addition and removal of nodes
* Support in-place scaling of nodes, both growing and shrinking
* Have a low big-O (O(n)? O(nlogn)? But, as we've seen, it also needs a
fairly low constant)

I noticed after glancing at the code in place now that you don't actually
follow my algorithm (which is technically O(n), I think, but with a (really)
large constant) because you recurse on the collision checks.  Removing that
recursion is one small step in the right direction.  However, the overhead
of maintaining the weights array seems to be a bottleneck on the laptops.

I discussed a few possible options with Michael the other day. One option is
to use a quad tree to isolate nodes hierarchically, to minimize the amount
of collision checking needed and to prevent the need for a weights array.
 Instead, the nodes of the quad tree are assigned weights which represent
the sum total of weights in their subtrees.  This is really nothing more
than an optimization of the current algorithm, but it could help a fair
amount.

Another potentially interesting solution is a pseudo-spring algorithm, by
which we detect some numbers of neighbors (O(n)) and then we "push" those
neighbors away with some force vector, the magnitude of which is weighted
based on the size of the nodes, and the direction of which is calculated as
the angle between them.  This solution doesn't, in theory, yield results
that are as good as the other options (since it pushes away at a fixed
angle, instead of towards nearby positions with ow weights), but it should
be really quick.

I'm sure there are other options, or combinations of these, that we could
explore as well.

- Eben

PS.  I did a review of the current algorithm a while back, but lost the
notes on it.  I'll go back through it again, because there did seem to be a
bit of unnecessary work being done when I looked at it before.



On Fri, Aug 1, 2008 at 6:30 AM, Tomeu Vizoso <tomeu at tomeuvizoso.net> wrote:

> On Fri, Aug 1, 2008 at 7:55 AM, riccardo <riccardo.lucchese at gmail.com>
> wrote:
> > On Thu, 2008-07-31 at 17:27 +0100, Tomeu Vizoso wrote:
> >> On Tue, Jul 29, 2008 at 3:15 PM, riccardo <riccardo.lucchese at gmail.com>
> wrote:
> >>
> >> I guess that's for the mesh and friends view?
> > Oh, right!
> > +1 for changing the algorithm.
>
> Eben, can you write down a list of requirements for the spread layout?
>
> Thanks,
>
> Tomeu
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.laptop.org/pipermail/devel/attachments/20080801/4d8b9768/attachment.html>