id	summary	reporter	owner	description	type	status	priority	milestone	component	version	resolution	keywords	cc
8643	[patch] Very slow Purge command - O(N^2)	bilbo	team	"There is bad algorithm used in Purge command, with complexity O(N^2^), causing purge with about 176000 ways to take over 15 minutes. 

Problem is in toposort, where the algorithm restart iteration over the hashset after every deleted way, but in Javaadoc for HashMap it says:

Iteration over collection views requires time proportional to the ""capacity"" of the HashMap instance (the number of buckets) plus its size (the number of key-value mappings). 

As the capacity still remains the same as the collection becomes more and more empty, this effectively is O(N^2) algorithm, as it takes longer and longer time to iterate to first way (not mentioning skipping all the nodes again and again before encountering a corresponding way).

The patch fixes the topopSort and reduces the time it needs to process the data

For purging collection of about 176000 ways and 800000 nodes the time for toposort is reduced from about 17 minutes to 500 milliseconds."	defect	closed	normal		Core	latest	fixed	patch