[josm-dev] Optimizations for larger data sets

[Gabriel Ebner]

On Sat, Dec 08, 2007 at 08:06:22PM +0100, Frederik Ramm wrote:
> Hi,
> 
> >>    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.
> 
> Gabriel, haven't you done something in the MergeVisitor a few days ago?

Nothing earth-shaking.  I mainly speeded up merging of identical objects
(since you often download overlapping areas) while trying to figure out what
the code is actually supposed to do. :-)

E.g. I figured out that we don't even try to merge tags.  So if you extend a
way by one node, and someone else adds a tag and you download that before you
upload like you're supposed to do, you'll actually remove the tag again.

> >>   *) 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.
> 
> Yes, sadly I haven't done a thing yet but it has always been my plan to 
> add an extra layer of objects above the current data objects, and to 
> keep display caching stuff in these. That would require a good deal more 
> memory but I would avoid cluttering the OSM data objects with stuff like 
> indexes and bounding boxes. But I'm open to other suggestions.

I don't think this would require much more memory.  Say we'd add a tile index
for the nodes, this would require just a bit more than one pointer per node,
that's just 8M for a million nodes.  Similarly, if we cache ways as polylines,
we wouldn't need to duplicate all the indirections, we could just store them
as arrays of doubles, so for a million nodes that might cost us just 18M.

  Gabriel.