An (Swift) Array is contiguous block of memory which has
n number of elements of same type, represented by generic type
Element. Since the memory which holds the elements is contiguous any individual element can be accessed in O(1) time.
To create an array we need these things as bare minimum :
- Pointer to allocated memory (or the buffer)
- Capacity : capacity is the number of elements that can be stored in the current buffer
- Count : count is number of elements that are actually stored inside the current buffer so count <= capacity
_SwiftArrayBodyStorage (C Struct)
Swift declares a C struct in its SwiftShim’s module inside GlobalObject.h called
countis the number of elements currently stored in the buffer
_capacityAndFlagsis used to store two things:
- first is the capacity of the buffer
- second “Is the Element type bitwise-compatible with some Objective-C class?”
The most right bit of the unsigned int is used to store this boolean flag and rest of the bits are used to store the capacity of the array. This is done to store this information in a compressed way.
_ArrayBody is a struct defined in the stdlib which is a swift wrapper over
- keeps an instance of
_SwiftArrayBodyStorageinside a variable called
- provides option to set & get capacity, count and the flag (elementTypeIsBridgedVerbatim)
ManagedBufferPointer<Value, Element> (struct)
- Creates fixed size contiguous storage for type Element
- Stores one instance of the type Value which acts as a header to that storage to keep the meta data about that storage. For Array Value is
- Provides methods which will give pointers to Value and Element which can be used to operations like dealloc/destroy elements in buffer or change modify data of Value object
- Tells if the buffer is being uniquely referenced
- This struct heavily uses
Builtinwhich is basically voodoo which compiler understands directly
- This struct is basically the buffer which is used by Array. It keeps an instance of
ManagedBufferPointer<_ArrayBody, Element>in its
- It initializes the
_ArrayBodywith capacity, count and the flag
- To keep things simpler, I’ll focus on non-ObjC runtime (flag will obviously always be false for that)
_ArrayBodycan be intialized using the
_valuePointerproperty exposed by
ManagedBufferPointer(since it only allocated by the buffer pointer)
- The count and capacity values can be asked from
_ArrayBodyvia value property.
All operations on the storage can be done using the pointer to element. The element pointer is exposed via
_ContiguousArrayBufferhas a computed property
firstElementAddresswhich returns the
- Any element is accessible using the first element address and element position
- Subscript provides easy access to set and get the elements at arbitrary index
ibut ofcourse it should be less than the capacity.
- And finally, also need to know if the buffer is uniquely referenced for the copy-on-write feature 😀
- gyb stands for generate your (own) boilerplate. It’s a preprocessor system written for swift which is used to generate repetitive code.
- Array is declared in a file called Arrays.swift.gyb because
ArraySliceshare a lot of same code.
utils/gybinside swift’s source can be used to generate the .swift file from a .gyb file
- Array declares different buffer for ObjC and non ObjC runtime.
_ArrayBufferprovides a bridged storage so it can be converted into NSArray if needed. We’re focusing on above mentioned
_getElementis used to get the element out of the buffer by using the
getElementmethod on the buffer.
then subscript calls the above
- Appending an element :
- The first method called is
_makeUniqueAndReserveCapacityIfNotUniquewhich is :
_slowPathis a method which hints the optimizer that expected value of the bool which is being passed is
- so basically this is hinting the optimizer that if this method is being called, its most likely that the array is already mutable and unique
- if not,
_copyToNewBuffermethod creates a new buffer and initialize it with elements of current buffer then replaces the current buffer with new buffer
_forceCreateUniqueMutableBuffercreates a new empty buffer and increases the capacity by factor of 2 if needed by :
- Now that we have a unique buffer for sure, just append the new element at end and update the count