Open Radar

 
Summary:
Accessing the first element in a Set appears to be extremely slow.


Take the following example:
import Cocoa

let size = 100000

func createSet() -> Set<Int> {
    var set = Set<Int>()
    for i in 0..<size {
        set.insert(i)
    }
    return set
}

let insertStart = NSDate()
var set = createSet()
println("Insert: \(NSDate().timeIntervalSinceDate(insertStart))")


let removeFirstStart = NSDate()
while !set.isEmpty {
    set.removeFirst()
}
println("RemoveFirst: \(NSDate().timeIntervalSinceDate(removeFirstStart))")


set = createSet()
let firstRemoveStart = NSDate()
while !set.isEmpty {
    let first = set.first!
    set.remove(first)
}
println("FirstRemove: \(NSDate().timeIntervalSinceDate(firstRemoveStart))")


set = createSet()
let removeLoopStart = NSDate()
for element in set {
    set.remove(element)
}
println("RemoveLoop: \(NSDate().timeIntervalSinceDate(removeLoopStart))")


set = createSet()
let removeDirectStart = NSDate()
for i in 0..<size {
    set.remove(i)
}
println("RemoveDirect: \(NSDate().timeIntervalSinceDate(removeDirectStart))")

This produces the following results on my machine (using -O):
Insert: 0.0234929919242859
RemoveFirst: 22.9310619831085
FirstRemove: 22.6014919877052
RemoveLoop: 0.0276380181312561
RemoveDirect: 0.0135889649391174

I would expect to achieve equal if not better performance using removeFirst() to remove members than using remove() but instead it is orders of magnitude slower...

Since a naive implementation of removeFirst() using Set.first and Set.remove seems to perform roughly equally bad but using Set.remove itself is fine I would expect Set.first to be the main culprit.

I have attached the example code as an Xcode project.

Forum thread: https://devforums.apple.com/thread/266229?tstart=0

Steps to Reproduce:
1. Open the attached project & run the target
2. Observe the resulting output

Expected Results:
I would expect Set.removeFirst() to perform equal to if not better Set.remove() when used to remove all the sets elements.

Actual Results:
Set.removeFirst() (and Set.remove(Set.first)) perform significantly worse.

Version:
Version 6.3 (6D554n)
Apple Swift version 1.2 (swiftlang-602.0.47.4 clang-602.0.48)
10.10.2 (14C1514)