F# Set.union argument order performance

Question

Is there any recommended way to call a Set.union if I know one of the two sets will be larger than the other?

Set.union large small

or

Set.union small large

Thanks

Answer 1

Internally, sets are represented as ballanced tree (you can check the source online). When calculating the union of sets, the algorithm splits the smaller set (tree) based on the value from the root of the larger set (tree) into a set of smaller and a set of larger elements. The splitting is always performed on the smaller set to do less work. Then it recursively unions the two left and right subsets and performs some re-ballancing.

The summary is, the algorithm does not really depend on which of the sets is the first and which of them is the second argument. It will always choose the better option depending on the size of set (which is stored as part of the data structure).