I’m recently investigating a VS feedback on compilation time.
There are some interesting findings during the investigation and I’d like to share them in this blog post.
Here is the repro to demonstrate the issue.
In the code, we define 512 classes. We also provide a global operator<< for each class.
The problem here is the definition of operator<<. The definition will call operator<< and this forces the compiler to do overload resolution.
The candidates includes,
- All member operator<< defined in std::ostream
- All global operator<<
- All operator<< defined in std namespace which are found via ADL (argument dependent lookup)
Unfortunately, when we add more global operator<<, the candidate set of 2 also grows. This leads to O(n^2) time complexity (n is the number of global operator<< we add, which is 512 in the repro).
For each candidate, we need to validate whether the conversion from ‘float’ (the type of ‘s()’) or ‘const char ’ (the type of ‘””‘) to the class is valid.
This is expensive because the class has a constructor which requires the compiler to validate its default template argument (it involves std::decay, which may furthur specialize 10+ other type traits).
While the code is conformant, there is room to improve its compile time with simple tweaks. Here are three possible ways,
- If you know the exact type of the variable you want to serialize, you can call the member operator<< directly. This reduces the time complexity to O(n).
- If you can group some classes into separate namespaces and define the operator<< in these namespaces, it will reduce the candiate set in 2. This reduces the time complexity to O(n^2/m) if m is the number of namespaces and each namespace contains n/m classes.
- A more general solution is to use hidden friend. They can only be found via ADL, so they will not participate in the overload resolution of the operator<< for other classes. This also reduces the time complexity to O(n).
It may also be a good idea to put the definition of these operator<< to a separate .inl file and only include it if you need serialization. You don’t want to pay cost to things you don’t need :-).
BTW, in VC2017, we implement /permissive- which disables some non-conformant behaviors. One side effect of the new option is that it improves the compile time when there are lots of global operators / hidden friends.
The following is a table comparing the compile time using VC2017:
|Baseline||/permissive-||/permissive- + /DOPT|