Merging OSM layers very slow

[SpeedEvil]

Merging two multi-thousand node layers takes several minutes.

[Gabriel Ebner <ge@…>]

Several questions:

• What areas are you trying to merge? Are they disjunct, subsets, ...? Please attach them if you can.
• What machine are you on?
• What java VM are you using?

It takes under 10 seconds on my laptop to merge two layers with 8k nodes (using any of java 5, 6, 7).

(Yes, I know that even that is quite crappy performance. I guess we could speed that up by one or two orders of magnitude just by using hashtables instead of linked lists.)

[SpeedEvil]

Sorry for the delay.
JRE 1.6, duron 1300 - yes, it's slow, but...

​http://www.mauve.plus.com/testfiles.osm.tar.gz

(around a meg)
decompress.
Load into JOSM, now press 'merge layer' 25 times.
It's not finished for me after 25 mins of CPU time.
It's not a tiny bit of the map - but there are only on the order of
44000 nodes and 3000 ways.

[SpeedEvil]

It took 80 CPU minutes, or on the order of 4000 instructions per node, assuming that the complexity is nodes²

[Gabriel Ebner <ge@…>]

I hope I improved the situation a bit in r478. I modified the merge button so that in your case you merge small layers into an increasingly big layer (which is faster than the other way round).

But I don't think there are other low-hanging fruits there for disjunct layers, as we need to check for conflicts (e.g. if we have a new way, we need to check all other ways if they are equal to the new way in order to prevent duplicate uploads).

[SpeedEvil]

While it's now by no-means snappy (8 cpu-minutes), that's a whole lot better than the previous 80.
Thanks!