Modify

Opened 12 years ago

Closed 12 years ago

Last modified 12 years ago

#5552 closed enhancement (fixed)

[PATCH] Delete performance improvement

Reported by: extropy Owned by: team
Priority: normal Milestone:
Component: Core Version:
Keywords: Cc:

Description

Improved delete selected objects performance.

Attachments (2)

deleteSpeed.diff (1.8 KB) - added by extropy 12 years ago.
deleteSpeed-2.diff (1.9 KB) - added by extropy 12 years ago.
Fixed nodes counter

Download all attachments as: .zip

Change History (14)

Changed 12 years ago by extropy

Attachment: deleteSpeed.diff added

comment:1 Changed 12 years ago by bastiK

Summary: Delete performance improvement[PATCH] Delete performance improvement

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?

comment:2 in reply to:  1 Changed 12 years ago by 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.

comment:3 Changed 12 years ago by bastiK

isn't it and integer rather than a list?

comment:4 in reply to:  3 Changed 12 years ago by 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

comment:5 Changed 12 years ago by 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?

Changed 12 years ago by extropy

Attachment: deleteSpeed-2.diff added

Fixed nodes counter

comment:6 Changed 12 years ago by extropy

That is a bug :(.

Uploaded fixed version.

comment:7 Changed 12 years ago by bastiK

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

comment:8 Changed 12 years ago by 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.

comment:9 Changed 12 years ago by bastiK

Resolution: fixed
Status: newclosed

In [3630/josm]:

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

comment:10 Changed 12 years ago by 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. ;)

comment:11 Changed 12 years ago by 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.

comment:12 Changed 12 years ago by bastiK

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

Modify Ticket

Change Properties
Set your email in Preferences
Action
as closed The owner will remain team.
as The resolution will be set.
The resolution will be deleted.

Add Comment


E-mail address and name can be saved in the Preferences.

 
Note: See TracTickets for help on using tickets.