"Fossies" - the Fresh Open Source Software Archive

Member "swift-swift-5.1.2-RELEASE/docs/Arrays.rst" (7 Nov 2019, 10263 Bytes) of package /linux/misc/swift-swift-5.1.2-RELEASE.tar.gz:


As a special service "Fossies" has tried to format the requested source page into HTML format (assuming markdown format). Alternatively you can here view or download the uninterpreted source code file. A member file download can also be achieved by clicking within a package contents listing on the according byte size field.

orphan

The Swift Array Design

Author

Dave Abrahams

Date

2014-04-10

Goals

  1. Performance equivalent to C arrays for subscript get/set of non-class element types is the most important performance goal.
  2. It should be possible to receive an NSArray from Cocoa, represent it as an Array<AnyObject>, and pass it right back to Cocoa as an NSArray in O(1) and with no memory allocations.
  3. Arrays should be usable as stacks, so we want amortized O(1) append and O(1) popBack. Together with goal #1, this implies a std::vector-like layout, with a reserved tail memory capacity that can exceed the number of actual stored elements.

To achieve goals 1 and 2 together, we use static knowledge of the element type: when it is statically known that the element type is not a class, code and checks accounting for the possibility of wrapping an NSArray are eliminated. An Array of Swift value types always uses the most efficient possible representation, identical to that of ContiguousArray.

Components

Swift provides three generic array types, all of which have amortized O(1) growth. In this document, statements about ArrayType apply to all three of the components.

Mutation Semantics

The ArrayTypes have full value semantics via copy-on-write (COW):

var a = [1, 2, 3]
let b = a
a[1] = 42
print(b[1]) // prints "2"

Bridging Rules and Terminology for all Types

Array Type Conversions

From here on, this document deals only with Array itself, and not Slice or ContiguousArray, which support a subset of Array's conversions. Future revisions will add descriptions of Slice and ContiguousArray conversions.

Kinds of Conversions

In these definitions, Base is AnyObject or a trivial subtype thereof, Derived is a trivial subtype of Base, and X conforms to _BridgedToObjectiveC:

Note

Both checked and forced downcasts may be combined with trivial bridging back in conversions from NSArray.

Maintaining Type-Safety

Both upcasts and forced downcasts raise type-safety issues.

Upcasts

TODO: this section is outdated.

When up-casting an [Derived] to [Base], a buffer of Derived object can simply be unsafeBitCast'ed to a buffer of elements of type Base--as long as the resulting buffer is never mutated. For example, we cannot allow a Base element to be inserted in the buffer, because the buffer's destructor will destroy the elements with the (incorrect) static presumption that they have Derived type.

Furthermore, we can't (logically) copy the buffer just prior to mutation, since the [Base] may be copied prior to mutation, and our shared subscript assignment semantics imply that all copies must observe its subscript assignments.

Therefore, converting [T] to [U] is akin to resizing: the new Array becomes logically independent. To avoid an immediate O(N) conversion cost, and preserve shared subscript assignment semantics, we use a layer of indirection in the data structure. Further, when T is a subclass of U, the intermediate object is marked to prevent in-place mutation of the buffer; it will be copied upon its first mutation:

image

Deferred Checking for Forced Downcasts

In forced downcasts, if any element fails to have dynamic type Derived, it is considered a programming error that may cause a trap. Sometimes we can do this check in O(1) because the source holds a known buffer type. Rather than incur O(N) checking for the other cases, the new intermediate object is marked for deferred checking, and all element accesses through that object are dynamically typechecked, with a trap upon failure (except in -Ounchecked builds).

When the resulting array is later up-cast (other than to a type that can be validated in O(1) by checking the type of the underlying buffer), the result is also marked for deferred checking.



  1. This copy() may amount to a retain if the NSArray is already known to be immutable. We could eventually optimize out the copy if we can detect that the NSArray is uniquely referenced. Our current unique-reference detection applies only to Swift objects, though.↩︎