# Trying to get a flat Set (actually just a Set<Int>)

Hi,

Given below is an example, where I am trying to get a flat set ( Set of Integers )

``````let a1 : [Set<Int>?] = [[1, 2], [2, 3], nil]
let x1 = Set(a1.flatMap { \$0 ?? [] })
``````

Questions:

1. Is there a better way to get a Set, would `reduce` be a better option ?
2. Is it better to use a `for` loop instead ?

Thanks.

Define "better"? There are tradeoffs. Personally, I'd go for the most performant, declarative option.

Here's a non-exhaustive list of options:

Using `reduce(_:)` with `union(_:)`:

``````let x2 = a1.reduce(Set<Int>()) { \$0.union(\$1 ?? []) }
``````

Using `reduce(into:)` with `formUnion(_:)`:

``````let x3 = a1.reduce(into: Set<Int>()) { \$0.formUnion(\$1 ?? []) }
``````

Using `for` with `formUnion(_:)`:

``````var x4 = Set<Int>()

for set in a1 {
x4.formUnion(set ?? [])
}
``````

Using `forEach(_:)` with `formUnion(_:)`:

``````var x5 = Set<Int>()

a1.forEach { x5.formUnion(\$0 ?? []) }
``````

Let's compare them for speed (average of 10 runs of 100000 iterations each):

1. `x4` (using `for` with `formUnion(_:)`): 0.296 s
2. `x3` (using `reduce(into:)` with `formUnion(_:)`): 0.327 s
3. `x5` (using `forEach(_:)` with `formUnion(_:)`): 0.344 s
4. `x2` (using `reduce(_:)` with `union(_:)`): 0.360 s
5. `x1` (using `Set.init(_:)` with `flatMap`): 0.694 s

Code here.

Want speed? Go for `for` with `formUnion(_:)`. Want speed and FP? Go for `reduce(into:)` with `formUnion(_:)`. The struckthrough statement is only applicable in Debug mode. In Release mode, with high optimisation settings, the differences become less pronounced.

That was fun.

4 Likes

@dennisvennink Wow !! that was awesome, thank you so much !!!

It's really cool to learn these new ways ... thanks a ton !!!

A small doubt with `x2`:
`reduce` (still learning it), has an accumulating parameter (in out), so with `union` would a new set be created for every iteration as opposed to `x3` which would mutate the set everytime ?

`reduce(into:)`'s `initialResult` (`\$0` in the closure) refers to the "same" `Set<Int>` each time. (Technically it's a bit more complicated.) Using `union(_:)` here will probably be slower as you're creating a new `Set<Int>` for each iteration. You'll also have to rewrite the closure as `{ \$0 = \$0.union(\$1 ?? []) }`.

In `reduce(_:)`'s closure you `return` a new `Set<Int>` every time. `formUnion(_:)` will not work here as `\$0` is immutable.

SE-0171 explains a bit more about `reduce(into:)`.

Iâ€˜m just on my phone so I couldnâ€˜t test the snippet.

Wouldnâ€˜t somethine like this be better?

``````Set(a1.lazy.compactMap { \$0 }.flatMap { \$0 })
``````
Just a somewhat irrelevant side note
``````import XCTest
@testable import SetUnion

final class SetUnionTests: XCTestCase {
let a1: [Set<Int>?] = [[1, 2], [2, 3], nil]
let n = 100000

func testX1 () {
self.measure {
for _ in 1...self.n {
_ = Set(self.a1.flatMap { \$0 ?? [] })
}
}
}
...
``````

Can we be sure that the optimizer (of a future Swift version) won't remove this for-in loop by dead code elimination?

I ran your `SetUnionTests.swift` (the gist of the above link) on my

• MacBook Pro (Retina, 15-inch, Late 2013), 2 GHz Intel Core i7
• in Xcode 9.4, default toolchain, Test Scheme Build Configuration set to Release

Here are the test results I got compared to yours (along with times relative to x1):

``````// +------------------------------------+------------------------------------+
// | My Results                         | Your Results                       |
// +------------------------------------+------------------------------------+
// | x1: 0.097 s   0.097 / 0.097 = 1.00 | x1: 0.694 s   0.694 / 0.694 = 1.00 |
// | x2: 0.108 s   0.097 / 0.108 = 0.89 | x2: 0.360 s   0.694 / 0.360 = 1.93 |
// | x3: 0.075 s   0.097 / 0.075 = 1.29 | x3: 0.327 s   0.694 / 0.327 = 2.12 |
// | x4: 0.068 s   0.097 / 0.068 = 1.43 | x4: 0.296 s   0.694 / 0.296 = 2.34 |
// | x5: 0.073 s   0.097 / 0.073 = 1.33 | x5: 0.344 s   0.694 / 0.344 = 2.02 |
// +------------------------------------+------------------------------------+
//  (x6: 0.247 s  <-- I added Adrian Zubarev's snippet as testX6, apparantly
//                  lazy is slow for this particular piece of code & context.)
//
// +------------------------------+
// | So, my test results are this |
// | many times faster than yours |
// +------------------------------+
// | x1:  0.694  /  0.096  =  7.2 |
// | x2:  0.360  /  0.108  =  3.3 |
// | x3:  0.327  /  0.075  =  4.4 |
// | x4:  0.296  /  0.068  =  4.4 |
// | x5:  0.344  /  0.073  =  4.7 |
// +------------------------------+
``````

As I find it hard to believe that your machine and/or Xcode version compiles and/or runs these tests between 3.3 and 7.2 slower than on my MBP late 2013, 2 GHz i7 with Xcode 9.4, my guess is that, unless I'm missing something here, you ran the test in Debug. : )

3 Likes

You're right! I ran the tests in Debug mode on a 17-inch Late 2011 MacBook Pro with a 2.4 GHz Intel Core i7, being held together by duct tape (don't ask), in Xcode Version 10.0 beta (10L176w).

Here are my results using Release (`-Os`):

`x1`: 0.131 s
`x2`: 0.117 s
`x3`: 0.120 s
`x4`: 0.120 s
`x5`: 0.121 s
`x6`: 0.193 s

Very peculiar.

1 Like

Just so you know, the optimizer currently breaks horribly on lazy compactMaps, it works fine if you do `.lazy.flatMap({ \$0 ?? [] })`

2 Likes

Thanks for the clarification, I didn't realise there were 2 overloads.

Thanks @DevAndArtist, looks like so many possibilities.

Just curious, since there is a dot operator and functions are chained together, would that mean there would be 1 scan to remove nil (`compact`) and 1 more scan to flatten it (`flatMap`) ?

Note: My knowledge is very limited, so I could be completely wrong.

Thanks a lot @Jens, this is comprehensive comparison !

I was expecting `x3` to be faster than `x2` as it mutates, does the compiler do any optimisation for `x2` to be faster ?

Thanks @TellowKrinkle, wow I am learning a lot from this thread.

I didn't know that you could use `lazy` while chaining.

BTW I filed the `compactMap` issue as a bug since if nothing else it's a regression from Swift 4.0.3

2 Likes

No. The `.lazy` means the method chain should produce instances conforming to `LazySequenceProtocol` that wrap each other and fuse into a single pass over the `a1`. This happens inside the `Set.init` in this case.

2 Likes

That's pretty cool !!, thanks a lot for clarifying, probably I should use it in my code while I am chaining multiple statements like that.

1 Like

This is weird, my intuition would tell me that `x3` should be the fastest since it mutates in-place.

Well, it is one of the three fastest ones. x3, x4 and x5 are about the same (around 0.07 s in a release build on my machine), they are faster than x1, x2 and x6. But as demonstrated here, the optimizability is highly context dependent, in ways that makes it very hard, if not impossible, to build an intuition for performance in current Swift.

I can recommend you these three books here, especially the one about collections. ;)

https://www.objc.io/books/bundles/everything-swift/

It will explain why and where you should use `lazy` and tons of other optimizations.

2 Likes

cool, thanks @DevAndArtist