Corrects 25 misspellings across DocC articles, design documentation and doc comments. Prose only: no identifiers, no public API, no behaviour change. | Typo | Correction | Count | |---|---|---| | `offseting` | `offsetting` | 7 | | `valud` | `value` | 4 | | `necessarilly` | `necessarily` | 3 | | `recommmend` | `recommend` | 2 | | `Mutablility` | `Mutability` | 1 | | `childs` | `child's` | 1 | | `constaints` | `constraints` | 1 | | `destintion` | `destination` | 1 | | `explan` | `explain` | 1 | | `forcuses` | `focuses` | 1 | | `ot` | `or` | 1 | | `succcess` | `success` | 1 | | `unqiue` | `unique` | 1 | Two of these are worth a second look, since they are not pure spelling: - `_HTable+Removal.swift:18` reads "without marking it as unoccupied ot restoring the hash table's other invariants". Read as `or`, matching the sentence, and deliberately not as a prefix of `other` later on the line. - `_Node.UnsafeHandle+Deletion.swift:369` reads "reuse the left childs node". Corrected to the possessive `child's` rather than `children`, which is what a plain spellchecker suggests but does not fit the sentence. `valud` is corrected to `value` to match the wording of the equivalent parameter documentation on `swapAt(_:_:)`. One change is outside documentation: `CheckContainer.swift:476` fixes `succcess` inside a test assertion message. It is a human-readable string, not an expected value, so no test behaviour changes. Deliberately left alone: - `isDisjoint(with:)-54iy6` in `OrderedSet.md` is a DocC disambiguation hash, not a misspelling. - `Peristent` in the 2022 ShareableHashedCollections review document, which is an archived record of a past review rather than living documentation. Found with `typos-cli`, then reviewed by hand; the tool's raw output also flagged identifiers and symbol hashes, which are not included here.
4.7 KiB
BasicContainers
Overview
This module provides previews of ownership-aware reimplementations of basic data structures that have been shipping in the Swift Standard Library.
This currently consists of two noncopyable variants of the standard Array type: UniqueArray and RigidArray. Both of these allow noncopyable elements, and they store them in heap-allocated storage buffers.
Unlike Array, these new types do not support copy-on-write value semantics -- indeed, they aren't (implicitly) copyable at all, even if their element type happens to be copyable.
struct UniqueArray
UniqueArray is a dynamically self-resizing array type that automatically grows its storage as needed to accommodate inserted items. Its name highlights that unlike Array, instances of this type are always uniquely owned, never shared. Mutations of a UniqueArray therefore never need to copy their storage.
Not having to ever copy their contents means that UniqueArray can be used to hold noncopyable elements, unlike the classic Array.
Array's value semantics with the copy-on-write optimization is a powerful feature: it adds a great deal of flexibility and expressibility that tends to make it easy and comfortable to use. However, it also makes it relatively easy to accidentally write code where a series of small mutations of the "same" array all end up performing a full copy of the underlying storage -- a relatively common performance issue:
var items = Array(100 ..< 200)
for i in items.indices {
let old = items
items[i] *= 2 // 🐌
precondition(old[i] != items[i])
}
Note how preserving a copy of the array at the start of the loop forces the subscript mutation to end up copying the entire array on every iteration. Nothing distinguishes this really expensive mutation from a more typical subscript access with constant complexity -- it looks exactly the same. UniqueArray eliminates this entire class of issues by not letting you create a shared reference at all:
var items = UniqueArray(copying: 100 ..< 200)
// `- error: 'items' used after consume
for i in items.indices {
let old = items
// `- note: consumed here
items[i] *= 2
// `- note: used here
precondition(old[i] != items[i])
}
Taking away the freedom to make implicit copies forces you to think a lot more about ownership concerns when using this type -- it can feel a lot more constrained and nitpicky. In exchange though, it gets much easier to reason about the runtime performance of your code; the subscript mutation looks the same as before, but now it is guaranteed to always have constant complexity.
struct RigidArray
RigidArray goes a step even further than UniqueArray by also disabling automatic storage reallocations: it is a fixed-capacity array type. Rigid array instances get created with a specific capacity, and they never resize themselves. If they run out of room, they report a runtime error!
var items = RigidArray(capacity: 5, copying: 1 ..< 4) // 1, 2, 3
items.append(4) // OK
items.append(5) // OK
items.append(6) // runtime error: RigidArray capacity overflow
The name is apt -- that's quite inflexible behavior indeed. But sometimes this sort of inflexibility is exactly what we need! For instance, it makes it easy to ensure that the code we write will never use more memory than what we budgeted for it.
It also avoids wildly varying performance: in dynamically sized array types, append invocations usually have constant complexity, but once in a while they randomly spike to linear cost to resize the underlying storage. Of course, the use of a geometric growth strategy still allows the average complexity of an append operation to remain constant; but if a task must always complete within a strict deadline, then statistical averages may not be good enough. Some engineers with a low-level mindset may choose to work within the constraints of carefully precalculated static capacities, and may prefer to consider it a hard fault if it is ever exceeded.
Unlike InlineArray, the capacity of a RigidArray is not part of its type declaration (nor its count) -- it is still a dynamic value.
This allows RigidArray to still provide explicit resizing operations: it has a reallocate(capacity:) method that can be used to arbitrarily resize its storage, as well as the familiar reserveCapacity(_:) operation. This enables building dynamic array types on top of RigidArray; indeed, UniqueArray is a relatively simple wrapper around rigid array instance, forwarding operations to it when possible.
Topics
Types
UniqueArrayRigidArray