The code responsible for deciding whether to convert the second operand to a Set was quite difficult to read.However, as it turned out, this optimization was quite problematic for a few reasons: When the operand is a known implementation of Collection that doesn’t override contains (currently only ).When the operand was not implementing a Collection interface (meaning it could not override its contains method).That is why the optimization was applied only in specific cases: This could lead to some errors that are difficult to debug. With this change, we can no longer rely on our custom contains implementation because the initial collection is now of another type. Kotlin then converts it under the hood to a different type - a HashSet. The problem was that a collection could override its contains method causing some unexpected behavior down the road.įor instance, imagine we pass a collection with overridden contains method that we count on (for example, an IdentitySet). To check whether an item is present in the set, it is enough to compute its hash code.įor that specific reason, Kotlin tried to introduce this optimization any time it could to improve the performance. On the other hand, that complexity is reduced to a constant time for sets. We have to go through each item one by one. Typically, the complexity of checking for the existence of an item in a regular list or array is linear. But how does it know that a specific item is not present in that collection? By calling its contains method. It does that by filtering the first collection to keep only the items that are not in the second collection. It returns a list consisting of elements from the first collection that are not present in the second collection. In many cases, when running some of the Collection operations (such as aforementioned intersect, minus, removeAll or retainAll), Kotlin tried to optimize them by converting their second operands to a Set under the hood.
That’s why it might be worth providing a little story behind this issue: Before Kotlin 1.6 ¶ In prior versions, both of those tested variants ( x intersect y and y intersect x) would yield the same results. Moreover, this problem only exists starting with Kotlin 1.6. Overall, as I dig deeper into the topic (including the source code of the intersect function), I realized that the problem is not the order of the operands itself, but rather the fact that the second operand in the slower variant was not of type Set. What’s more, the bigger the y collection, the greater the time difference between those two variants. average ())Īs you can see, the outcome is quite surprising. Val results = mutableListOf () repeat ( 20 ) print ( results.
0 kommentar(er)
