Swift under the hood: Generic implementation

It allows you to define. It’s not clear that abstracted manner. - Swift docs

Everyone who wrote on Swift used generics. Array , Dictionary , Set - the most basic options for using generics from the standard library. How are they represented inside? Let's look at how this fundamental language feature is implemented by Apple engineers.

Generic parameters can be limited to protocols as well as not limited, although, in general, generics are used in conjunction with protocols that describe what exactly you can do with method parameters or type fields.

Swift uses two approaches to implement generics:

1. Runtime way - generic code is a wrapper (Boxing).
2. Compiletime way - generic code is converted to a specific type of code for optimization (Specialization).

Boxing

Consider a simple method with an unlimited protocol, the generic parameter:

 func test<T>(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 any <T> . That is, regardless of whether we write test(value: 1) or test(value: "Hello") , the same code will be called and additionally <T> type containing all the necessary information will be transferred to the method .

Not much can be done with such unlimited protocol parameters, but to implement this method, you need to know how to copy a parameter, you need to know its size, to allocate memory for it in runtime, you need to know how to destroy it when the parameter leaves the area visibility. To store this information is used Value Witness Table ( VWT ). VWT is created at the compilation stage for all types and the compiler guarantees that such a layout of the object will be in runtime. Let me remind you that the structures in Swift are passed by value, and classes by reference, so for let copy = value with T == MyClass and T == MyStruct different things will be done.

That is, the call to the test method with the transfer of the declared structure there will look like this:

 //  ,  metadata   let myStruct = MyStruct() test(value: myStruct, metadata: MyStruct.metadata) 

Things get a little more complicated when MyStruct itself is a generic structure and takes the form of MyStruct<T> . Depending on the <T> inside MyStruct , the metadata and VWT will be different for the types MyStruct<Int> and MyStruct<Bool> . These are two different types in rantayme. But creating metadata for every possible combination of MyStruct and T extremely inefficient, so Swift goes the other way and for such cases constructs metadata in runtime on the go. The compiler creates one metadata pattern for the generic structure, which can be combined with a specific type and, as a result, get complete information on the type in runtime with the correct VWT .

 //   ,  metadata   func test<T>(value: MyStruct<T>, tMetadata: T.Type) { //       let myStructMetadata = get_generic_metadata(MyStruct.metadataPattern, tMetadata) ... } let myStruct = MyStruct<Int>() test(value: myStruct) //   test(value: myStruct, tMetadata: Int.metadata) //      

When we combine information, we get metadata that we can work with (copy, move, destroy).

It is still a bit more complicated when protocols are added to generics. For example, we limit <T> the Equatable protocol. Let it be a very simple method that compares two passed arguments. It turns out just a wrapper over the comparison method.

 func isEquals<T: Equatable>(first: T, second: T) -> Bool { return first == second } 

For the program to work properly, you must have a pointer to the static func ==(lhs:T, rhs:T) comparison method static func ==(lhs:T, rhs:T) . How to get it? Obviously, the transfer of VWT not enough, it does not contain this information. To solve this problem, there is the Protocol Witness Table or PWT . This VWT is similar to VWT and 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 

1. Two arguments are passed.
2. Passing metadata for Int so that you can copy / move / destroy objects
3. Passing the information and that Int implements Equatable .

If the restriction required the implementation of another protocol, for example, T: Equatable & MyProtocol , then the information about MyProtocol would be added with 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 it has an overhead that can be optimized.

Generics specialization

To eliminate the unnecessary need to obtain information during program execution, the so-called generics specialization approach was used. It allows you to replace the 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 "wrapper" implementation, two additional completely different versions of the method for Int and for String .

Source

To begin, create a generic.swift file and write a small generic function that we will consider.

 func isEquals<T: Equatable>(first: T, second: T) -> Bool { return first == second } isEquals(first: 10, second: 11) 

Now you need to understand what this ultimately turns into a compiler.
This can be clearly seen by compiling our .swift file in the Swift Intermediate Language or SIL .

A little bit about SIL and the compilation process

SIL is the result of one of several swift compilation steps.

The source .swift code is passed to Lexer, which creates an abstract syntax tree ( AST ) of the language, on the basis of which type checking and semantic code analysis is carried out. SilGen converts AST to SIL , called raw SIL , on the basis of which the code is optimized and an optimized canonical SIL obtained, which is transferred to IRGen for conversion to IR - a special format understandable by LLVM , which will be converted into ` .o , . , . SIL`.

And again to generics

Create a SIL file from our source code.

 swiftc generic.swift -O -emit-sil -o generic-sil.s 

We get a new file with the extension *.s . Looking inside, we will see a much less readable code than the source code, but, all the same, relatively understandable.

Find the line with the comment // isEquals<A>(first:second:) . This is the beginning of the description of our method. It ends with the comment // end sil function '$s4main8isEquals5first6secondSbx_xtSQRzlF' . You may have a slightly different name. Let's analyze the method a little.

• %0 and %1 on the 21st line are the first and second parameters respectively
• On line 24 we get information about the type and pass in %4
• At line 25 we get a pointer to the comparison method from the type information
• on line 26 Call the method on the pointer, passing both parameters and type information to it
• On line 27, we give the result.

As a result, we see that in order to perform the necessary actions in the implementation of the generic method, we need to obtain information from the type description <T> during the execution of the program.

We proceed directly to the specialization.

In the compiled SIL file immediately after the declaration of the common isEquals method follows the declaration specialized for the type Int .

On the 39th line, instead of receiving the method in runtime, the method of comparing integers "cmp_eq_Int64" immediately called from the information about the type.

In order for the method to "specialize", you need to enable optimization . Also, you need to know that

The source optimizer can be customized. ( Source )

That is, the method cannot be specialized between different Swift modules (for example, the generic method from the Cocoapods library). The exception is the standard Swift library, in which such basic types as Array , Set and Dictionary . All generic base libraries specialize in specific types.

Note: In Swift 4.2, the attributes @inlinable and @usableFromInline were implemented, which allow the optimizer to see the bodies of methods from other modules and seem to be able to specialize them, but this behavior was not tested by me ( Source )

Links

1. Generics description
2. Swift Optimization
3. More detailed and in-depth presentation on the subject.
4. Article in English