[josm-dev] Optimizations for larger data sets

[Gabriel Ebner]

On Sat, Dec 08, 2007 at 04:16:07PM +0100, Petr Nejedly wrote:
> These changes are, so far, more local optimizations than real scalability changes,
> but it may change in future. I'd like to be as little intrusive as possible,
> at least initially.

Frederik wants to do some optimizations anyhow, so this is the way to go.

> I'll try to split and submit my changes in digestible pieces for better review-ability
> and smaller granularity of potential disagreements. I just wanted to post a heads-up
> in advance so we can clear up any misunderstanding early.
> 
> Overview of changes done so far (for usage w/o mappaint):
>    1. Paint arrow on selection even when arrows are disabled.
>    2. Avoid duplicate Strings in data (reduces memory used
>       by czechia.osm 260MB->160MB)
>    3. Different implementation of tags Map in OsmPrimitive.
>       HashMap is unnecessarily expensive for such few entries
>       OSM primitives typically carry. Czechia.osm: 160MB->106MB
>    4. Use ArrayLists instead of LinkedLists in DataSet. They are
>       cheaper memory-wise and faster to iterate. 106MB-> <100MB
>    5. Rewritten MergeVisitor to avoid O(N^2) algorithm.
>       Otherwise updating a window from the server takes looong
>       time and you'd like to do such an update before you push
>       your few-days-old-snapshot based changes back to the server.
>    6. Reasonable offscreen filtering in SimplePaintVisitor, limit usage
>       of floats during painting, limit doing the same transformation
>       twice, don't paint too small objects.

Looks all fine to me.

> These changes were possible and effective without the need to encapsulate
> data fields in the dataset. I have few more ideas that would require
> encapsulating the data inside the DataSet, but such a change would be
> incompatible with current plugins. If there is a will, we could do this
> in phases: first introduce API replacing direct field and collection access,
> then rewrite plugins to the API and finally make the fields private and
> implement the improvements:
>   *) Order the nodes in the collection along single axis. This would
>      allow faster (typically O(sqrt(N)) painting of nodes in close-zoom cases.

If we keep an index on the nodes, IMHO it would be better to go the whole way
to an R-tree or tiles (like in the server).

>   *) Keep precomputed bbox of complete ways:
>      This allows faster painting of ways both in close-zoom (you filter out
>      the complete way quickly if it is off-screen) and wide-view (you filter
>      out/dot-replace small ways) cases.

Frederik has been talking about adding a "presentation layer" for some while
now.  That would presumably include a better representation for drawing.

  Gabriel.