-
Notifications
You must be signed in to change notification settings - Fork 3
/
Copy pathlazy-sequences-in-swift-and-how-they-work.html
405 lines (356 loc) · 23 KB
/
lazy-sequences-in-swift-and-how-they-work.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
<!DOCTYPE html>
<html lang="en">
<head>
<script src="https://use.fontawesome.com/afd448ce82.js"></script>
<!-- Meta Tag -->
<meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<meta http-equiv="X-UA-Compatible" content="IE=edge">
<!-- SEO -->
<meta name="author" content="Bruno Rocha">
<meta name="keywords" content="Software, Engineering, Blog, Posts, iOS, Xcode, Swift, Articles, Tutorials, OBJ-C, Objective-C, Apple">
<meta name="description" content="Usage of high-order functions like map and filter are very common in Swift projects, as they are simple algorithms that allow you to convert extensive ideas into simple one-liners. Unfortunately, they don't solve every issue - at least not in their default implementations.">
<meta name="title" content="Lazy Sequences in Swift And How They Work">
<meta name="url" content="https://swiftrocks.com/lazy-sequences-in-swift-and-how-they-work">
<meta name="image" content="https://swiftrocks.com/images/thumbs/thumb.jpg?4">
<meta name="copyright" content="Bruno Rocha">
<meta name="robots" content="index,follow">
<meta property="og:title" content="Lazy Sequences in Swift And How They Work"/>
<meta property="og:image" content="https://swiftrocks.com/images/thumbs/thumb.jpg?4"/>
<meta property="og:description" content="Usage of high-order functions like map and filter are very common in Swift projects, as they are simple algorithms that allow you to convert extensive ideas into simple one-liners. Unfortunately, they don't solve every issue - at least not in their default implementations."/>
<meta property="og:type" content="website"/>
<meta property="og:url" content="https://swiftrocks.com/lazy-sequences-in-swift-and-how-they-work"/>
<meta name="twitter:card" content="summary_large_image"/>
<meta name="twitter:image" content="https://swiftrocks.com/images/thumbs/thumb.jpg?4"/>
<meta name="twitter:image:alt" content="Page Thumbnail"/>
<meta name="twitter:title" content="Lazy Sequences in Swift And How They Work"/>
<meta name="twitter:description" content="Usage of high-order functions like map and filter are very common in Swift projects, as they are simple algorithms that allow you to convert extensive ideas into simple one-liners. Unfortunately, they don't solve every issue - at least not in their default implementations."/>
<meta name="twitter:site" content="@rockbruno_"/>
<!-- Favicon -->
<link rel="icon" type="image/png" href="images/favicon/iconsmall2.png" sizes="32x32" />
<link rel="apple-touch-icon" href="images/favicon/iconsmall2.png">
<link rel="preconnect" href="https://fonts.googleapis.com">
<link rel="preconnect" href="https://fonts.gstatic.com" crossorigin>
<link href="https://fonts.googleapis.com/css2?family=Source+Sans+3:ital,wght@0,200..900;1,200..900&display=swap" rel="stylesheet">
<!-- Bootstrap CSS Plugins -->
<link rel="stylesheet" type="text/css" href="css/bootstrap.css">
<!-- Prism CSS Stylesheet -->
<link rel="stylesheet" type="text/css" href="css/prism4.css">
<!-- Main CSS Stylesheet -->
<link rel="stylesheet" type="text/css" href="css/style48.css">
<link rel="stylesheet" type="text/css" href="css/sponsor4.css">
<!-- HTML5 shiv and Respond.js support IE8 or Older for HTML5 elements and media queries -->
<!--[if lt IE 9]>
<script src="https://oss.maxcdn.com/html5shiv/3.7.3/html5shiv.min.js"></script>
<script src="https://oss.maxcdn.com/respond/1.4.2/respond.min.js"></script>
<![endif]-->
<script type="application/ld+json">
{
"@context": "https://schema.org",
"@type": "BlogPosting",
"mainEntityOfPage": {
"@type": "WebPage",
"@id": "https://swiftrocks.com/lazy-sequences-in-swift-and-how-they-work"
},
"image": [
"https://swiftrocks.com/images/thumbs/thumb.jpg"
],
"datePublished": "2018-10-26T13:42:07+00:00",
"dateModified": "2020-04-12T14:00:00+02:00",
"author": {
"@type": "Person",
"name": "Bruno Rocha"
},
"publisher": {
"@type": "Organization",
"name": "SwiftRocks",
"logo": {
"@type": "ImageObject",
"url": "https://swiftrocks.com/images/thumbs/thumb.jpg"
}
},
"headline": "Lazy Sequences in Swift And How They Work",
"abstract": "Usage of high-order functions like map and filter are very common in Swift projects, as they are simple algorithms that allow you to convert extensive ideas into simple one-liners. Unfortunately, they don't solve every issue - at least not in their default implementations."
}
</script>
</head>
<body>
<div id="main">
<!-- Blog Header -->
<!-- Blog Post (Right Sidebar) Start -->
<div class="container">
<div class="col-xs-12">
<div class="page-body">
<div class="row">
<div><a href="https://swiftrocks.com">
<img id="logo" class="logo" alt="SwiftRocks" src="images/bg/logo2light.png">
</a>
<div class="menu-large">
<div class="menu-arrow-right"></div>
<div class="menu-header menu-header-large">
<div class="menu-item">
<a href="blog">blog</a>
</div>
<div class="menu-item">
<a href="about">about</a>
</div>
<div class="menu-item">
<a href="talks">talks</a>
</div>
<div class="menu-item">
<a href="projects">projects</a>
</div>
<div class="menu-item">
<a href="software-engineering-book-recommendations">book recs</a>
</div>
<div class="menu-item">
<a href="games">game recs</a>
</div>
<div class="menu-arrow-right-2"></div>
</div>
</div>
<div class="menu-small">
<div class="menu-arrow-right"></div>
<div class="menu-header menu-header-small-1">
<div class="menu-item">
<a href="blog">blog</a>
</div>
<div class="menu-item">
<a href="about">about</a>
</div>
<div class="menu-item">
<a href="talks">talks</a>
</div>
<div class="menu-item">
<a href="projects">projects</a>
</div>
<div class="menu-arrow-right-2"></div>
</div>
<div class="menu-arrow-right"></div>
<div class="menu-header menu-header-small-2">
<div class="menu-item">
<a href="software-engineering-book-recommendations">book recs</a>
</div>
<div class="menu-item">
<a href="games">game recs</a>
</div>
<div class="menu-arrow-right-2"></div>
</div>
</div>
</div>
<div class="content-page" id="WRITEIT_DYNAMIC_CONTENT">
<!--WRITEIT_POST_NAME=Lazy Sequences in Swift And How They Work-->
<!--WRITEIT_POST_HTML_NAME=lazy-sequences-in-swift-and-how-they-work-->
<!--WRITEIT_POST_SITEMAP_DATE_LAST_MOD=2020-04-12T14:00:00+02:00-->
<!--WRITEIT_POST_SITEMAP_DATE=2018-10-26T13:42:07+00:00-->
<!--Add here the additional properties that you want each page to possess.-->
<!--These properties can be used to change content in the template page or in the page itself as shown here.-->
<!--Properties must start with 'WRITE_IT_POST'.-->
<!--Writeit provides and injects WRITEIT_POST_NAME and WRITEIT_POST_HTML_NAME by default.-->
<!--WRITEIT_POST_SHORT_DESCRIPTION=Usage of high-order functions like map and filter are very common in Swift projects, as they are simple algorithms that allow you to convert extensive ideas into simple one-liners. Unfortunately, they don't solve every issue - at least not in their default implementations.-->
<title>Lazy Sequences in Swift And How They Work</title>
<div class="blog-post">
<div class="post-title-index">
<h1>Lazy Sequences in Swift And How They Work</h1>
</div>
<div class="post-info">
<div class="post-info-text">
Published on 27 Aug 2018
</div>
</div>
<p>Usage of high-order functions like <code>map</code> and <code>filter</code> are very common in Swift projects, as they are simple algorithms that allow you to convert extensive ideas into simple one-liners. Unfortunately, they don't solve every issue - at least not in their default implementations. High-order functions are <i>eager</i>: they use the closure immediately and return a new array, regardless if you need an early return or only going to use specific elements. When performance is important, you might be cornered into writing specialized helper methods to avoid the <i>eager</i> nature of high-orders:</p>
<pre><code>let addresses = getFirstThreeAddresses(withIdentifier: "HOME")
func getFirstThreeAddresses(withIdentifier identifier: String) -> [Address] {
//Not using .filter{}.prefix(3) because we need an early return
var addresses = [Address]()
for address in allAddresses where address.identifier == identifier {
addresses.append(address)
if addresses.count == 3 {
break
}
}
return addresses
}</code></pre>
<div class="sponsor-article-ad-auto hidden"></div>
<p>Fortunately, Swift has a way to use high-order functions while still keeping the improved performance of the helper methods - Lazy versions of the Swift Standard Library <code>Sequences</code> and <code>Collections</code> can be accessed through the <code>lazy</code> property.</p>
<p>These lazy variations work just like their regular counterparts, but with one twist: they have custom implementations of methods like <code>map</code> and <code>filter</code> in order to make them work <b>lazily</b> - meaning that the actual computations will only happen <b>where and when you need them.</b></p>
<pre><code>let allNumbers = Array(1...1000)
let normalMap = allNumbers.map { $0 * 2 } // The entire Sequence will be mapped, regardless of what you need to do.
let lazyMap = allNumbers.lazy.map { $0 * 2 } // Nothing happens here.
print(lazyMap[0]) // Prints 2, but everything else is still untouched!</code></pre>
<p>While somewhat scary at first, they allow you to reduce most <code>for</code> loops with early returns into one-liners. For example, here's how it compares to other methods when used to find the first element that fulfills a predicate:</p>
<pre><code>// allAddresses in an [Address] with 10000 elements, and a "HOME" address is placed at the beginning
let address = allAddresses.filter { $0.identifier == "HOME" }.first // ~0.15 seconds
// Versus
func firstAddress(withIdentifier identifier: String) -> Address? {
// Nowadays you can use the Standard Library's first(where:) method,
// but lets pretend that doesn't exist.
for address in allAddresses where address.identifier == identifier {
return address
}
return nil
}
let address = firstAddress(withIdentifier: "HOME") // Instant
// Versus
let address = allAddresses.lazy.filter { $0.identifier == "HOME" }.first // Also instant with much less code!</code></pre>
<p>Besides writing shorter code, they can also be very useful for delaying operations in general to make your code easier to read. Let's say you have a shopping app which displays offer incentives from a local database if the user's taking too long to finish a purchase:</p>
<pre><code>let offerViews = offersJson.compactMap { database.load(offer: $0) }.map(OfferView.init) // O(n)
var currentOffer = -1
func displayNextOffer() {
guard currentOffer + 1 < offerViews.count else {
return
}
currentOffer += 1
offerViews[currentOffer].display(atViewController: self)
}</code></pre>
<p>While this solution works, it has a major flaw: I am eagerly mapping the entire offer json into <code>OfferViews</code>, even though there's no guarantee that the user will see any of these offers. This isn't really an issue if <code>offerJson</code> is a small array, but with large data sets, pulling all the offers from a database can quickly become a problem.</p>
<p>You can map only the necessary <code>OfferViews</code> by moving the parsing logic to <code>displayNextOffer()</code>, but your code quality might become harder to understand since you now have to keep the raw offer data around:</p>
<pre><code>let offersJson: [[String: Any]] = //
var currentOffer = -1
func displayNextOffer() {
guard currentOffer + 1 < offerViews.count else {
return
}
currentOffer += 1
guard let offer = database.load(offer: offersJson[currentOffer]) else {
return
}
let offerView = OfferView(offer: offer)
offerView.display(atViewController: self)
}</code></pre>
<p>By using <code>lazy</code>, the current <code>offerView</code> will only be mapped when the array position is accessed in <code>displayNextOffer()</code>, keeping the reading quality of the first implementation with the performance of the second one!</p>
<pre><code>let offerViews = offersJson.lazy.compactMap { database.load(offer: $0) }.map(OfferView.init) // Nothing happens here!
var currentOffer = -1
func displayNextOffer() {
guard currentOffer + 1 < offerViews.count else {
return
}
currentOffer += 1
offerViews[currentOffer].display(atViewController: self) // Mapping only happens here, for the desired element only.
}</code></pre>
<p>Note, however, that Lazy Sequences have no caching. This means that if <code>offerViews[0]</code> is accessed twice, <b>the entire mapping process will also happen twice.</b> If you need to access elements more than once, move them to a regular array.</p>
<h2>Why this works?</h2>
<p>While they look like magic when used, the internal implementation of Lazy Sequences aren't as complicated as it looks.</p>
<p>If we print the type of our second example, we can see that even though our lazily mapped <code>Collection</code> works like a regular <code>Collection</code>, we are dealing with different types:</p>
<pre><code>let lazyMap = Array(1...1000).lazy.map { $0 * 2 }
print(lazyMap) // LazyMapCollection<Array<Int>, Int>
let lazyMap = Array(1...1000).lazy.filter { $0 % 2 == 0 }.map { $0 * 2 }
print(lazyMap) // LazyMapCollection<LazyFilterCollection<Array<Int>>, Int>
//In this case, the first generic argument is the inner Collection of the lazy operation, while the second one is the transformation function of the map operation.</code></pre>
<p>Looking at Swift's source code, we can see that the non-eagerness comes from the fact that these methods don't actually do anything besides return a new type:</p>
<p>(I'll be using <code>LazySequence</code> code examples instead of <code>LazyCollections</code> ones because they are much simpler in nature. If you don't know how regular <code>Sequences</code> work, <a href="https://developer.apple.com/documentation/swift/sequence">take a look at this Apple page.</a>)</p>
<pre><code>extension LazySequenceProtocol {
/// Returns a `LazyMapSequence` over this `Sequence`. The elements of
/// the result are computed lazily, each time they are read, by
/// calling `transform` function on a base element.
@inlinable
public func map<U>(_ transform: @escaping (Elements.Element) -> U) -> LazyMapSequence<Self.Elements, U> {
return LazyMapSequence(_base: self.elements, transform: transform)
}
}</code></pre>
<p>The magic comes from the internal implementation of these specialized types. If we take a look at <code>LazyMapSequence</code> and <code>LazyFilterSequence</code>, for example, we can see that they are nothing more than regular <code>Sequences</code> that stores an operation and applies their counterpart eager functions only when iterated:</p>
<pre><code>// _base is the original Sequence
extension LazyMapSequence.Iterator: IteratorProtocol, Sequence {
@inlinable
public mutating func next() -> Element? {
return _base.next().map(_transform)
}
}</code></pre>
<pre><code>extension LazyFilterSequence.Iterator: IteratorProtocol, Sequence {
@inlinable
public mutating func next() -> Element? {
while let n = _base.next() {
if _predicate(n) {
return n
}
}
return nil
}
}</code></pre>
<h2>LazyCollection Performance Traps</h2>
<p>If would be nice if the article ended here, but it's important to know that Lazy Sequences have flaws - specifically when the underlying type is a <code>Collection</code>.</p>
<p>In the opening example, our method gets the first three addresses that fulfill a certain predicate. By chaining lazy operations together, this can also be reduced to an one-liner:</p>
<pre><code>let homeAddresses = allAddresses.lazy.filter { $0.identifier == "HOME" }.prefix(3)</code></pre>
<p>However, look how this specific example performs when compared to the eager counterpart:</p>
<pre><code>allAddresses.filter { $0.identifier == "HOME" }.prefix(3) // ~0.11 secs
Array(allAddresses.lazy.filter { $0.identifier == "HOME" }.prefix(3)) // ~0.22 secs</code></pre>
<p>Even though the <code>lazy</code> version stops as soon as the three addresses are found, it performs twice as bad as the eager one!</p>
<p>The unfortunate reason comes from the subtle differences between <code>Sequences</code> and <code>Collections</code>. While prefixing a <code>Sequence</code> is as simple as moving the desired elements to a separate <code>Array</code>, slicing operations on <code>Collections</code> require knowing the <code>end</code> index of the desired slice:</p>
<pre><code>public func prefix(_ maxLength: Int) -> SubSequence {
_precondition(maxLength >= 0, "Can't take a prefix of negative length from a collection")
let end = index(startIndex, offsetBy: maxLength, limitedBy: endIndex) ?? endIndex
return self[startIndex..<end]
}
@inlinable
public subscript(bounds: Range<Index>) -> Slice<Self> {
_failEarlyRangeCheck(bounds, bounds: startIndex..<endIndex)
return Slice(base: self, bounds: bounds)
}</code></pre>
<p>The problem is that in <code>Collection</code> lingo, an <code>endIndex</code> isn't the index of the last element, but the index <b>after</b> the last element (<code>index(startIndex, offsetBy: maxLength)</code>). For our lazy <code>filter</code>, this means that in order to slice the first three home addresses, we must find <b>four</b> of them - which may not even exist.</p>
<p>The documentation of <a href="https://github.com/apple/swift/blob/master/stdlib/public/core/PrefixWhile.swift#L106">certain lazy types</a> states this issue:</p>
<pre><code>/// - Note: The performance of accessing `endIndex`, `last`, any methods that
/// depend on `endIndex`, or moving an index depends on how many elements
/// satisfy the predicate at the start of the collection, and may not offer
/// the usual performance given by the `Collection` protocol. Be aware,
/// therefore, that general operations on `${Self}` instances may not have
/// the documented complexity.
public struct LazyPrefixWhileCollection<Base: Collection> {</code></pre>
<p>To make it worse, since a <code>Slice</code> is a mere window to the original <code>Collection</code>, the casting to <code>Array</code> will invoke functions that call the lazy filtered <code>Collection</code>'s <code>count</code> properties - but since the <code>lazy.filter(_:)</code> operation doesn't conform to <code>RandomAccessCollection</code>, <code>count</code> can only be found by iterating the entire <code>Collection</code> - again.</p>
<p>Due to the Lazy Sequence's lack of caching, this results in the entire filtering/slicing process happening <b>again</b>. Thus, if the fourth element doesn't exist or is too far from the third one, the <code>lazy</code> version will perform twice as worse as the original one.</p>
<p>The good news is that this can be avoided - if you're not sure your lazy operation will run in reasonable time, you can guarantee it by treating the result as a <code>Sequence</code>. This has the downside of losing the reverse-iteration capabilities of a <code>BidirectionalCollection</code>, but guarantees that forward operations will be fast again.</p>
<pre><code>let sequence: AnySequence = allAddresses.lazy.filter { $0.identifier == "HOME" }.prefix(3)
let result = Array(sequence) // ~0.004 secs!</code></pre>
<h2>Conclusion</h2>
<div class="sponsor-article-ad-auto hidden"></div>
<p>Usage of <code>lazy</code> objects can allow you to write high-performance complicated things very quickly - at the cost of requiring some understanding of Swift internals to prevent major issues. Like all features, they have great advantages with equal downsides, and in this case knowledge of the main differences between <code>Sequences</code> and <code>Collections</code> is required to extract the best of them. Once mastered, mapping specific elements becomes very simple and intuitive.</p>
<p>Follow me on my Twitter - <a href="https://twitter.com/rockbruno_">@rockbruno_</a>, and let me know of any suggestions and corrections you want to share.</p>
<h2>References and Good reads</h2>
<a href="https://github.com/apple/swift/blob/master/stdlib/public/core/Filter.swift">Filter.swift</a>
<br>
<a href="https://bugs.swift.org/browse/SR-4164">SR-4164</a>
<br>
<a href="https://developer.apple.com/documentation/swift/lazyprefixwhilecollection">LazyPrefixWhileCollection</a>
<br>
<a href="https://developer.apple.com/documentation/swift/lazysequenceprotocol">LazySequenceProtocol</a>
<br>
<a href="https://developer.apple.com/documentation/swift/sequence">Sequence</a>
<br>
</div></div>
<div class="blog-post footer-main">
<div class="footer-logos">
<a href="https://swiftrocks.com/rss.xml"><i class="fa fa-rss"></i></a>
<a href="https://twitter.com/rockbruno_"><i class="fa fa-twitter"></i></a>
<a href="https://github.com/rockbruno"><i class="fa fa-github"></i></a>
</div>
<div class="footer-text">
© 2025 Bruno Rocha
</div>
<div class="footer-text">
<p><a href="https://swiftrocks.com">Home</a> / <a href="blog">See all posts</a></p>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
<!-- Blog Post (Right Sidebar) End -->
</div>
</div>
</div>
<!-- All Javascript Plugins -->
<script type="text/javascript" src="js/jquery.min.js"></script>
<script src="https://cdn.jsdelivr.net/npm/[email protected]/dist/js/bootstrap.bundle.min.js" integrity="sha384-MrcW6ZMFYlzcLA8Nl+NtUVF0sA7MsXsP1UyJoMp4YLEuNSfAP+JcXn/tWtIaxVXM" crossorigin="anonymous"></script>
<script type="text/javascript" src="js/prism4.js"></script>
<!-- Main Javascript File -->
<script type="text/javascript" src="js/scripts30.js"></script>
<!-- Google tag (gtag.js) -->
<script async src="https://www.googletagmanager.com/gtag/js?id=G-H8KZTWSQ1R"></script>
<script>
window.dataLayer = window.dataLayer || [];
function gtag(){dataLayer.push(arguments);}
gtag('js', new Date());
gtag('config', 'G-H8KZTWSQ1R');
</script>
</body>
</html>