consider code of the following form:
class C {
var prop1: Int
var prop2: Int
var prop3: Int
// ...
var propN: Int
}
now suppose we implement the init method to assign default values to all the properties as so:
init() {
prop1 = 0
prop2 = 0
prop3 = 0
// ...
propN = 0
}
if we let the number of properties grow – how does the compile time scale? here are some empirical results for examples of this form, doubling the number of properties at each step[1]:
| property count | 2 | 4 | 8 | 16 | 32 | 64 | 128 | 256 | 512 | 1024 | 2048 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| avg compile time (s) | 0.17 | 0.17 | 0.18 | 0.18 | 0.19 | 0.21 | 0.26 | 0.41 | 1.2 | 23 | 272 |
if we profile the compiler process while compiling one of these long-running examples, it looks like this:
which indicates that the vast majority of compilation time is spent within the getLivenessAtInst method. digging into the source reveals that this method resides in DefiniteInitialization.cpp, which (unsurprisingly) appears responsible for the 'definite initialization' logic that ensures all values are initialized before use.
in the case of a class initializer with many stored properties, the getLivenessAtInst method seems to perform a 'look back' that loops backward over all the instructions produced by SILGen within the initializer's 'basic block'. this inner loop doesn't appear to terminate until reaching the very beginning of the block. so in the limiting case, it makes sense that the compilation time would become dominated by this inner looping logic, since it presumably confers quadratic complexity in its current form.
to test the theory that the compilation time scales based on the initializer's maximum basic block length, we can alter the initializer code to force additional basic blocks to be produced. one way i found of doing this is by introducing a switch statement that only has a default case, e.g.
init() {
switch () {
default:
prop1 = 0
}
switch () {
default:
prop2 = 0
}
// ...
switch () {
default:
propN = 0
}
}
in applying this technique to the 2048-property example from above, the average compile time was reduced from ~4.5 minutes to ~1.8 seconds.
so this finally brings us to my (jumble of) questions:
- what is the backward scanning logic in
getLivenessAtInstdoing exactly? - if that logic is necessary, could it be altered to improve the runtime performance?
- if it cannot be meaningfully improved, what's the best way to convince SILGen to emit new basic blocks so that the performance bottleneck can be worked around?
- what/where is the best documentation on the definite init algorithm? i tried searching the codebase for design docs or something that discuss it in more depth, but have yet to find anything super relevant-seeming.
data was collected via
hyperfine -w 1 -r 4 'swiftc <file>'using the Swift 5.10 compiler shipped with XCode 15.4. ↩︎