Swift under the hood: Generic implementation
Generic code enables you to write flexible, reusable functions and types that can work with any type, subject to requirements that you define. You can write code that avoids duplication and expresses its intent in a clear, abstracted manner. - Swift docs
Everyone who wrote on Swift used generics. Array, Dictionary, Set- the most basic uses of generics of the standard library. How are they represented inside? Let's see how this fundamental feature of the language is implemented by Apple engineers.
Generic parameters can be either limited by protocols or not limited, although, basically, generics are used in conjunction with protocols that describe what exactly can be done with method parameters or type fields.
To implement generics, Swift uses two approaches:
- Runtime-way - generic code is a wrapper (Boxing).
- Compiletime-way - generic code is converted to a specific type of code for optimization (Specialization).
Boxing
Consider a simple method with an unlimited protocol with a generic parameter:
func test(value: T) -> T {
let copy = value
print(copy)
return copy
} The swift compiler creates one single block of code that will be called to work with anyone test(value: 1)or test(value: "Hello"), the same code will be called and additionally type information
Little can be done with parameters with such unlimited protocols, but already to implement this method, you need to know how to copy a parameter, you need to know its size in order to allocate memory for it in runtime, you need to know how to destroy it when the parameter leaves the field visibility. To store this information, use Value Witness Table( VWT). VWTIt is created at the compilation stage for all types and the compiler guarantees that in runtime there will be just such a layout of the object. Let me remind you that the structures in Swift passed by value and by reference classes, so let copy = valuewhen T == MyClassand T == MyStructto be made different things.
That is, a method call testwith passing the declared structure there will eventually look something like this:
// Приблизительный псевдокод, параметр metadata добавляется компилятором
let myStruct = MyStruct()
test(value: myStruct, metadata: MyStruct.metadata)Things get a little more complicated when MyStructit is itself a generic structure and takes on a look . Depending on the inside , the metadata will be different for the types and . These are two different types in runtime. But to create metadata for each possible combination and very inefficient, so the Swift goes the other way, and for such cases in the runtime constructs metadata on the fly. The compiler creates one metadata pattern for the generic structure, which can be combined with a specific type and, as a result, receive complete type information in runtime with the correct one .MyStructMyStructVWTMyStructMyStructMyStructTVWT
// Опять же псевдокод, параметр metadata добавляется компилятором
func test(value: MyStruct, tMetadata: T.Type) {
// Комбинируем информацию и получаем итоговые метаданные
let myStructMetadata = get_generic_metadata(MyStruct.metadataPattern, tMetadata)
...
}
let myStruct = MyStruct()
test(value: myStruct) // Исходный код
test(value: myStruct, tMetadata: Int.metadata) // Примерно вот в это компилируется When we combine information, we get metadata that you can work with (copy, move, destroy).
It is still a bit more complicated when protocol restrictions are added to generics. For example, restrict the Equatable. Let it be a very simple method that compares the two arguments passed. The result is just a wrapper over the comparison method.
func isEquals(first: T, second: T) -> Bool {
return first == second
} For the program to work properly, you must have a pointer to a comparison method static func ==(lhs:T, rhs:T). How to get it? Obviously, the transfer is VWTnot enough, it does not contain this information. To solve this problem exists Protocol Witness Tableor PWT. This label is similar to VWTand is created at the compilation stage for the protocols and describes these protocols.
isEquals(first: 1, second: 2) // Исходный код
// Примерно во что превращается
isEquals(first: 1, // 1
second: 2,
metadata: Int.metadata, // 2
intIsEquatable: Equatable.witnessTable) // 3- Two arguments passed
- We transfer metadata for
Int, so that you can copy / move / destroy objects - We transmit information and that
IntimplementsEquatable.
If the restriction required the implementation of another protocol, for example T: Equatable & MyProtocol, then information about MyProtocolwould be added by the following parameter:
isEquals(...,
intIsEquatable: Equatable.witnessTable,
intIsMyProtocol: MyProtocol.witnessTable)Using wrappers to implement generics allows you to flexibly implement all the necessary features, but has an overhead that can be optimized.
Generic specialization
To eliminate the unnecessary need to obtain information during program execution, the so-called generic specialization approach was used. It allows you to replace a generic wrapper with a specific type with a specific implementation. For example, for two calls isEquals(first: 1, second: 2)and isEquals(first: "Hello", second: "world"), in addition to the main "wrapping" implementation, two additional completely different versions of the method for Intand for will be compiled String.
Source
First, create a generic.swift file and write a small generic function that we will consider.
func isEquals(first: T, second: T) -> Bool {
return first == second
}
isEquals(first: 10, second: 11) Now you need to understand what it eventually turns into a compiler.
This can be clearly seen by compiling our .swift file in the Swift Intermediate Language or SIL.
A bit about SIL and the compilation process
SIL is the result of one of several stages of compiling swift.
The source code .swift is passed to Lexer, which creates an abstract syntax tree ( AST) of the language, based on which type checking and semantic analysis of the code is performed. SilGen converts ASTto SIL, called raw SIL, on the basis of which the code is optimized and optimized is obtained canonical SIL, which is passed in IRGenfor conversion to IR- a special format that is understandable LLVM, which will be converted to ` .o файлы, собранные под конкретную архитектуру процессора. Во что превращается наш дженериковый код можно посмотреть как раз на этапе созданияSIL`.
And again to the generics
Create a SILfile from our source code.
swiftc generic.swift -O -emit-sil -o generic-sil.sGet a new file with the extension *.s. Looking inside, we will see much less readable code than the original, but still relatively clear.
Find the line with the comment . This is the beginning of the description of our method. It ends with a comment . Your name may be slightly different. Let's analyze the method description a bit.// isEquals(first:second:)// end sil function '$s4main8isEquals5first6secondSbx_xtSQRzlF'
%0and%121 are linefirstandsecondparameters respectively- On line 24 we get type information and pass it to
%4 - On line 25 we get a pointer to a comparison method from type information
- on line 26 We call the method by pointer, passing it both parameters and type information
- On line 27 we give the result.
As a result, we see: in order to perform the necessary actions in the implementation of the generic method, we need to obtain information from the type description during program execution
We proceed directly to specialization.
In the compiled SILfile, immediately after the declaration of the general method isEquals, the declaration of the type-specialized follows Int.
On line 39, instead of getting the method in runtime from the type information, the method for comparing integers is immediately called "cmp_eq_Int64".
In order for the method to "specialize", optimization must be enabled . You also need to know that
The optimizer can only perform specialization if the definition of the generic declaration is visible in the current Module ( Source )
That is, the method cannot be specialized between different Swift modules (for example, the generic method from the Cocoapods library). An exception is the standard Swift library, in which such basic types as Array, Setand Dictionary. All generics of the base library specialize in specific types.
Note: Attributes @inlinableand were implemented in Swift 4.2 @usableFromInline, which allow the optimizer to see the bodies of methods from other modules and it seems like there is an opportunity to specialize them, but I have not tested this behavior ( Source )
