Compiler Optimization with Lazy Sequences

It is clear that using lazy can allow the Swift compiler to more aggressively optimize operations like map and filter, especially when those operations are expensive or unnecessary.

What is less clear is whether lazy can have negative effects on performance or memory usage (putting aside operations that outright break). The documentation of LazySequenceProtocol includes the following sentence.

When you use the lazy property, you give the standard library explicit permission to store the closure and the sequence in the result, and defer computation until it is needed.

This implies that the compiler will perform either lazy or eager evaluation depending on which is more optimal. If that’s the case, everything should be marked lazy unless it must be evaluated eagerly to work, as that gives the compiler more freedom for optimization.

If, on the other hand, lazy sequences are always evaluated lazily, then users must consider whether the increased overhead is justified.

As an example, I am writing a function that needs to apply a CollectionDifference to a given String. The CollectionDifference is always the same, so I am storing it as a private static property.

extension UUID {
  private static let hyphenation = CollectionDifference<String.Element>(
    stride(from: 8, through: 23, by: 5).lazy
      .map { .insert(offset: $0, element: "-", associatedWith: nil) }
  )!

  init?(unhyphenatedUUIDString: String) {
    … // applies `hyphenation` to `unhyphenatedUUIDString` once
  }
}

While this is obviously a trivial example, I would like to know whether using .lazy may be detrimental with larger sequences. All elements are going to be accessed if any are, and it will work whether evaluation is eager or lazy.

With eager evaluation, the program will iterate through the sequence of indices to map them to CollectionDifference.Change values, then iterate through them again to apply said changes.

With lazy evaluation, the program will map and apply changes in the same initial iteration. I’m not sure whether that justifies the overhead (it almost certainly doesn’t in this specific case), and I want to know if the compiler will determine that.

Your example isn't lazy, really:

Here .lazy returns a LazySequence<StrideThrough<Int>> which has two available .map() methods to choose from:

func map<U>((Base.Element) -> U) -> LazyMapSequence<Base, U>  // #1
func map<T>((Base.Element) -> T) -> [T]  // #2

but the compiler is going to choose #2 in this case, which means an array is going to be allocated right away with all the elements in it and you lose the potential for laziness. You'd be better off not using .lazy at all.

Now, why does it choose #2 instead of #1? Because it is forced to by the CollectionDifference's initialiser which requires a Collection:

init?<Changes>(_ changes: Changes) where Changes : Collection, Changes.Element == CollectionDifference<ChangeElement>.Change

Since LazyMapSequence is not a collection unless Base is also a collection, which is not the case because Base is StrideThrough which is not a collection, it cannot choose #1.

1 Like

Does .lazy make it worse, or are they equivalent in practice?

I would think eventually, in the future, the compiler might be able to optimize away and both options would lead to the same optimal machine instructions, but I highly doubt it is able to do so today. That said, in practical terms I think it should really make almost no difference and maybe even be almost indistinguishable. And in your case it should matter even less, performance- and memory-wise, since that code will only run at most once in the entire lifetime of your program, i.e. hyphenation only gets initialised once.

I chose a deliberately simple example.

You do say the CollectionDifference is always the same, so you only create it once, and for its creation you only run

stride(from: 8, through: 23, by: 5).lazy
      .map { .insert(offset: $0, element: "-", associatedWith: nil) }

once as well. Using .lazy or not in there will lead to the allocation of a (possibly big) intermediate Array anyways from the .map, which probably outweighs the (probably very small) performance cost of .lazy in this case.

Note:
Even if you run that piece of code very often, in a tight loop, I highly doubt having .lazy in there or not would make a difference; almost all of the time would be spent in the allocation, initialisation and freeing of the intermediate array in both cases, specially the more elements it has.

I'm not sure what you're basing this doubt on. The compiler is often able to eliminate this kind of thing today.

1 Like

Honestly, it wasn't based on any actual proof, just my personal thought. If that is the case then I'm very happy to be wrong! Thank you for clearing that up.

Edit:
I did check the output on godbolt for both options and it generated different machine instructions, but I was not able to assess whether they were relatively equally optimal or not, so I erred on the side of caution and assumed that they were not, my bad.

Edit2:
I checked the godbolt output and apparently I had forgotten to compile with optimisations turned on. With them on the exact same output is generated in both cases which is amazing.

Terms of Service

Privacy Policy

Cookie Policy