Set - Collection has quadratic complexity

The problem is that we want to keep the order of the elements as well if you for example do the call on a LinkedHashSet. Any kind of hashing on our side that does not keep the order would thus destroy the order. Also our test for the elements to be unique or not depends on a Groovy compare, thus we have to handle for example arrays and list at the same time or simply Comparable. I don't know how such a hashing method would look like for Comparable. We would also have to do our own structure, since we would need to know if the element has been added in the end or not.

For the next major Groovy version we should discuss if we still want to use the number aware comperator or not, so I use that as fix target for now. The alternative would be to close it as "Won't fix", since I consider this a breaking change.

I've thought you were combating Groovy being slow. Quadratic complexity beats any low-level optimizations.
To keep the order of elements isn't it enough to copy everything to a LinkedHashSet before removing? And produce LinkedHashSet as the result by default.

Peter, I already explains that elements Groovy considers being the same is not reflected by the hashcode. If all elements of your Set are from the same type, then your approach is ok. We could maybe do a prerun and check each element for being of a certain class. In such a case we won't need the groovy compare anymore and can get still the fast remove. But if you have a mixed Set with for example 1.0,1, meingin an Integer and a BigDecimal. Groovy considers them by == to be the same. Their hashcodes have nothing to do with each other. The result is that LinkedHashSet won't help here at all. If you want the fast version, then you have to get away from using the groovy compare. And that is for 3.0 to be discussed

I see. Maybe use a temporary internal set with a custom number-aware hashing strategy?

To use a number-aware hashing strategy you have to create identical hash values for different objects. To have this half way efficient we would indeed require a custom set... but this makes imho only sense if the sense is not temporary. You have to imagine, that in the worst case, you have to create a helper object for each entry. This would then not be fast. Sure... given a good hashing method you can be faster than n² compares even if you have to create n objects first, but that might be a big n, since creating objects is not cheap at all. Do you have an idea how to avoid that?

I don't see why there has to be created a helper object for each entry. Collections with custom hashing strategies exist, in Trove4j or (IIRC) Guava.

Helper objects still would have linear complexity instead of quadratic, though indeed much slower.

Your idea with a quick class check might also work to prevent the helper object creation in case it's not necessary. Although it would still be much slower than just an equivalent call of HashSet.removeAll.

And as for me, I don't need that number-aware comparison. I don't need for arrays to be equal either, although this feature seems to be more useful to me. If I needed those features, I'd think about it anyway by using a special data structure, like a map/set with a custom hashing strategy, and reserve "-" just as a handy syntactic sugar for copy+removeAll.

But that's only my preference. Maybe others think differently.