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. :+1:

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. :thinking:

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. ;)

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

2 Likes

cool, thanks @DevAndArtist