-
Notifications
You must be signed in to change notification settings - Fork 3
/
Copy pathfaster-swift-array-operations-with-collectionofone.html
319 lines (274 loc) · 15.6 KB
/
faster-swift-array-operations-with-collectionofone.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
<!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="CollectionOfOne is a type inside the Swift Standard Library that defines a <b>collection of a single element.</b> While this sounds a bit weird, there's a good reason for this to exist. Let's check out why.">
<meta name="title" content="Faster Array Operations With CollectionOfOne in Swift">
<meta name="url" content="https://swiftrocks.com/faster-swift-array-operations-with-collectionofone">
<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="Faster Array Operations With CollectionOfOne in Swift"/>
<meta property="og:image" content="https://swiftrocks.com/images/thumbs/thumb.jpg?4"/>
<meta property="og:description" content="CollectionOfOne is a type inside the Swift Standard Library that defines a <b>collection of a single element.</b> While this sounds a bit weird, there's a good reason for this to exist. Let's check out why."/>
<meta property="og:type" content="website"/>
<meta property="og:url" content="https://swiftrocks.com/faster-swift-array-operations-with-collectionofone"/>
<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="Faster Array Operations With CollectionOfOne in Swift"/>
<meta name="twitter:description" content="CollectionOfOne is a type inside the Swift Standard Library that defines a <b>collection of a single element.</b> While this sounds a bit weird, there's a good reason for this to exist. Let's check out why."/>
<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/faster-swift-array-operations-with-collectionofone"
},
"image": [
"https://swiftrocks.com/images/thumbs/thumb.jpg"
],
"datePublished": "2019-12-23T06:00:00+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": "Faster Array Operations With CollectionOfOne in Swift",
"abstract": "CollectionOfOne is a type inside the Swift Standard Library that defines a <b>collection of a single element.</b> While this sounds a bit weird, there's a good reason for this to exist. Let's check out why."
}
</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=Faster Array Operations With CollectionOfOne in Swift-->
<!--WRITEIT_POST_HTML_NAME=faster-swift-array-operations-with-collectionofone-->
<!--WRITEIT_POST_SITEMAP_DATE_LAST_MOD=2020-04-12T14:00:00+02:00-->
<!--WRITEIT_POST_SITEMAP_DATE=2019-12-23T06:00:00+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 'WRITEIT_POST'.-->
<!--Writeit provides and injects WRITEIT_POST_NAME and WRITEIT_POST_HTML_NAME by default.-->
<!--WRITEIT_POST_SHORT_DESCRIPTION=CollectionOfOne is a type inside the Swift Standard Library that defines a <b>collection of a single element.</b> While this sounds a bit weird, there's a good reason for this to exist. Let's check out why.-->
<title>Faster Array Operations With CollectionOfOne in Swift</title>
<div class="blog-post">
<div class="post-title-index">
<h1>Faster Array Operations With CollectionOfOne in Swift</h1>
</div>
<div class="post-info">
<div class="post-info-text">
Published on 23 Dec 2019
</div>
</div>
<p><code>CollectionOfOne</code> is a type inside the Swift Standard Library that defines a <b>collection of a single element.</b> While this sounds a bit weird, there's a good reason for this to exist. Let's check out why.</p>
<h2>Operating on single elements</h2>
<div class="sponsor-article-ad-auto hidden"></div>
<p>Personally, I am guilty of creating single-element arrays to make simple operations like this:</p>
<pre><code>someArray += [someElement]</code></pre>
<p>I used to do things like this for readability reasons (as you may or may not agree that this looks better than an <code>append()</code> call in some cases), but it turns out <b>this is bad</b> for multiple reasons. Here's what happens internally when you do something like this:</p>
<p>* The compiler translates the array literal into <code>Array's</code> <code>ExpressibleByArrayLiteral</code> initializer.</p>
<p>* The array initializer will create a buffer to hold the single element.</p>
<p>* The single element is copied into that buffer.</p>
<p>* += is a wrapper for <code>appendContents(of:)</code>, which first increases the buffer's capacity based on the number of elements being added.</p>
<p>* Finally, the elements are copied from their original buffer to the one of the array they're being added to.</p>
<p>That's an enormous amount of stuff for something as simple as dealing with a single element! We're creating the entire stack for an array structure just for a simple <code>append()</code> when all we needed to do was get a hold of the single element and copy it into the original buffer.</p>
<p>Usually, this sort of innocent mistake is optimized by the compiler, but in this case, even with higher optimization levels, the <b>compiler does not appear to know how to optimize the array allocation part out of single-element operations.</b> If we extract the SIL out of that line of code, we'll get multiple references for array allocations:</p>
<pre><code>// function_ref _allocateUninitializedArray<A>(_:)</code></pre>
<h2>CollectionOfOne - Collections, but not really</h2>
<p>To treat cases like this where the operation relies on a collection but you're only dealing with one element, the <code>CollectionOfOne</code> type can be used to efficiently represent these elements without having to worry about anything else that would normally come from the <code>Collection</code> protocol.</p>
<p>The way this works is straight-forward: the <code>CollectionOfOne</code> type implements <code>Collection</code>, meaning that it's able to respond to iterations and more. But instead of implementing these things with buffers like in an <code>Array</code>, the <code>CollectionOfOne</code> type simply holds a reference to the element:</p>
<pre><code>@frozen // trivial-implementation
public struct CollectionOfOne<Element> {
@usableFromInline // trivial-implementation
internal var _element: Element
/// Creates an instance containing just the given element.
///
/// - Parameter element: The element to store in the collection.
@inlinable // trivial-implementation
public init(_ element: Element) {
self._element = element
}
}</code></pre>
<p>Because it doesn't need to rely on buffers and all of that, it can directly return the element when being iterated:</p>
<pre><code>public mutating func next() -> Element? {
let result = _elements
_elements = nil
return result
}</code></pre>
<p>And because we're dealing with a single element, we don't need to worry about moving indexes or keeping track of element counts:</p>
<pre><code>public var startIndex: Index {
return 0
}
public var endIndex: Index {
return 1
}
public func index(after i: Index) -> Index {
_precondition(i == startIndex)
return 1
}
public func index(before i: Index) -> Index {
_precondition(i == endIndex)
return 0
}
public var count: Int {
return 1
}</code></pre>
<p>This makes <code>CollectionOfOne</code> a very efficient way to represent a single element. If we modify the original example to use <code>CollectionOfOne</code>, we can give our app a small performance boost.</p>
<pre><code>// Adding 10 million elements
someArray += [someElement] // 8 seconds
someArray += CollectionOfOne(someElement) // 6.9 seconds</code></pre>
<p><b>Note:</b> Adding to an array was used as the example because I believe it's the most common way of reaching this problem, but this is actually a bad use case of <code>CollectionOfOne</code>. In this case, the best performance you can get is by using <code>append()</code> directly as that'll ensure the element is directly copied into the array's buffer without any overhead.</p>
<pre><code>someArray.append(someElement) // 4.9 seconds</code></pre>
<p>The cases where using <code>CollectionOfOne</code> is the best approach possible is when you are forced to operate on <code>Collections</code>. In the Standard Library for example, <code>CollectionOfOne</code> is used to insert elements in specific positions of an <code>Array</code>:</p>
<pre><code>public mutating func insert(_ newElement: __owned Element, at i: Int) {
_checkIndex(i)
self.replaceSubrange(i..<i, with: CollectionOfOne(newElement))
}</code></pre>
<div class="sponsor-article-ad-auto hidden"></div>
<p>Because <code>replaceSubrange</code> replaces a <code>Collection</code> with another one, cases where the replacement is only a single element can greatly benefit from using <code>CollectionOfOne</code>.</p>
<h2>Conclusion</h2>
<p>When the performance gain isn't very high, I believe you should always value readability and maintainability over the gain. However, its always a good idea to understand the possible options and their trade-offs. Even if you never use <code>CollectionOfOne</code> directly, knowing of its existence and why it exists may help you make better decisions in the future.</p>
<h2>References and Good Reads</h2>
<a href="https://github.com/apple/swift/blob/master/stdlib/public/core/Array.swift">Array.swift</a>
<br>
<a href="https://github.com/apple/swift/blob/master/stdlib/public/core/CollectionOfOne.swift">CollectionOfOne.swift</a>
<br>
<a href="https://github.com/apple/swift">The Swift Source Code</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>