Optimization quirk with OrderedSet init

Using Swift
, , , ,
1

I’m investigating the performance of OrderedSet initialization from Swift Collections and am seeing some surprising results.

To keep things simple, let’s focus on creating an OrderedSet with one or two elements. There are many ways to initialize an OrderedSet with two elements, and their performance differs by a multiple. The fastest version I’ve found is this:

 @inlinable public init(elements first: Element, _ second: Element) {
    if _fastPath(first != second) {
      self.init(uncheckedUniqueElements: [first, second])
    } else {
      self.init(uncheckedUniqueElements: [first])
    }
} // ~357 ms. for 10mln. inits on M1 pro

Now compare this with two variants that initialize an OrderedSet with a single element:

@inlinable public init(element: Element) {
    self.init(uncheckedUniqueElements: [element])
} // 393 ms.
  
@inlinable  public init(element: Element) {
    self.init(uncheckedUniqueElements: CollectionOfOne(element))
} // 432 ms.

Surprisingly, initializing an OrderedSet with one element is slower than initializing it with two elements.

Things get even stranger if I “misuse” the two-element initializer to actually create a one-element set:

 @inlinable public init(elements first: Element, _ second: Element) {
    if _fastPath(first != second) {
      self.init(uncheckedUniqueElements: [first]) // ! add only first
    } else {
      self.init(uncheckedUniqueElements: [first])
    }
} //  87 ms.

for index in 1...10_000_000 {
    blackHole(OrderedSet.init(elements: 0, index)) // 0 is constant
}

The "strange" way to initialize with 1 element is ~4.5x faster than normal initializer with one direct call of self.init(uncheckedUniqueElements: [element].

This is because first element is a constant, but anyway, while the array literals themselves are optimized, it seems that OrderedSet builtin initializer with uncheckedUniqueElements also optimized excellently.

So there are 3 questions:

  • What is the reason for such a big performance difference between these initializers?
  • Are there ways to further optimize single-element OrderedSet initialization?
  • Why is OrderedSet(elements: 1, 2) faster than OrderedSet(element: 1)? – both for constants (70 ms. vs 83 ms.) and for runtime values (357 ms. vs 393 ms.)?
1 Like