[PATCH] Delete performance improvement

[extropy]

Improved delete selected objects performance.

[bastiK]

Your patch looks a little strange.

                List<Node> copy = new ArrayList<Node>(this.getNodesCount() - nodesToRemove); 

Isn't nodesToRemove the same as getNodesCount(), so you get 0?

[extropy]

Replying to bastiK:

Your patch looks a little strange.

                List<Node> copy = new ArrayList<Node>(this.getNodesCount() - nodesToRemove); 

Isn't nodesToRemove the same as getNodesCount(), so you get 0?

This method is called from DeleteCommand.

No, nodesToRemove is a list of nodes to delete - possibly a list of selected nodes that is only a part of all ways nodes.

[bastiK]

isn't it and integer rather than a list?

[anonymous]

Replying to bastiK:

isn't it and integer rather than a list?

It certainly is. The idea is to initialize the list to the needed size. The default size is 10. This avoids reallocation if there are more than 10 items and saves memory as the array is precisely as long as needed.

See ​http://download.oracle.com/javase/1.4.2/docs/api/java/util/ArrayList.html#ArrayList%28int%29

[bastiK]

You can replace

        302	            int nodesToRemove = 0; 
 	303	            for (Node n: nodes) { 
 	304	                nodesToRemove ++; 
 	305	            } 

by

        	            int nodesToRemove = nodes.size(); 

so why is this needed?

[extropy]

Fixed nodes counter

[extropy]

That is a bug :(.

Uploaded fixed version.

[bastiK]

Are you sure, counting nodesToRemove in advance is a performance gain? Calling contains() can be expensive (compared to the other stuff)...

[extropy]

The initial counting may indeed be removed, it just optimizes memory consumption.

About performance: let's do a full analysis.
Let A = number of nodes in way, B = number of objects in selection

Old code:

• For each node in selection, call removeNode.
• RemoveNode works O(A)
• Total complexity is O(A*B)

New code:

• For each node in way test if it is not in selection and if so add to the new nodes list.
• selection.contains() on a Set should be O(1). In reality it is a hash set and it actually is O(1).
• Total complexity is O(A)

Now let's assume we want to delete Y ways, containing X nodes.

• Old code would work in O(X*X).
• New code would work in O(X).

Hope this helps.

[bastiK]

In [3630/josm]:

applied #5552 (patch by extropy) - Delete performance improvement

[bastiK]

Ok, I removed initial counting - but not because it has a great impact on performance, but simply to keep the code slim. Every line of code that is not needed can contain bugs. See above for an example. ;)

[extropy]

Fine.

I'm just generally concerned about memory consumption. Ways are basic primitives and usually there are tens of thousands of them in a dataset, so every byte counts.

[bastiK]

Long term memory consumption is not an issue, because setNodes() takes care of the correct Array size. Otherwise you are right, of course.