[SR-8314] Very slow compile times for static large yet simple static arrays

[swift-ci]

Previous ID	SR-8314
Radar	rdar://problem/42400460
Original Reporter	alanQuatermain (JIRA User)
Type	Improvement

Attachment: Download

Additional Detail from JIRA

| | | |------------------|-----------------| |Votes | 0 | |Component/s | Compiler | |Labels | Improvement, Performance, TypeChecker | |Assignee | @gregomni | |Priority | Medium | md5: bfd1ab26fa738a651634af78f66fe43e

Issue Description:

I've attached an SPM project which consists of a single (edited) source file, but which takes a very long time to compile, despite containing essentially one function and some static data.

In Xcode, I see a compilation time of 53.4 seconds. Using swift build on the terminal, it takes 40.3 seconds, with the following output from time -l:

Compile Swift Module 'slow_swift_compilation' (1 sources)
       40.33 real        38.03 user         2.16 sys
4368084992  maximum resident set size
         0  average shared memory size
         0  average unshared data size
         0  average unshared stack size
   1356239  page reclaims
         0  page faults
         0  swaps
         0  block input operations
         0  block output operations
         0  messages sent
         0  messages received
         0  signals received
        23  voluntary context switches
     14126  involuntary context switches

...and yes, that's a 4.3GB maximum resident set. Conversely, my entire swift-nio-http2 fork build takes 14.3 seconds and uses a maximum resident set of 159MB:

time -l swift build
Compile CNIOSHA1 c_nio_sha1.c
Compile CNIOAtomics src/c-atomics.c
...
Compile Swift Module 'NIOHPACK' (13 sources)
Compile Swift Module 'NIOHTTP2' (16 sources)
Compile Swift Module 'NIOHTTP2Server' (1 sources)
Linking ./.build/x86_64-apple-macosx10.10/debug/NIOHTTP2Server
       14.34 real        28.08 user         6.60 sys
 159391744  maximum resident set size
         0  average shared memory size
         0  average unshared data size
         0  average unshared stack size
   1548258  page reclaims
      7027  page faults
         0  swaps
         0  block input operations
         0  block output operations
         0  messages sent
         0  messages received
         8  signals received
      1237  voluntary context switches
     30039  involuntary context switches

The code being compiled here is a static Huffman decoding table. It consists of a long array containing 255 groups of 16 tuples, each containing three items: a UInt8, an OptionSet with a RawValue of UInt8, and another UInt8. This corresponds to the 2-dimensional C array used by nghttp2 which can be seen here.

In C, this sort of static data would be pretty easy for the compiler to handle, but here it's anything but, which seems strange. I actually remedied the issue in my swift-nio-http2 fork by getting the raw bytes of the C implementation and encoding them as a large base64 string which I copied into the code and parsed on first use. Which seems rather backwards, to be honest.

[belkadan]

cc @rudkx, @xedin

[xedin]

Thank you for reporting, alanQuatermain (JIRA User)! Unfortunately this is a known problem in type-checker which we are trying to optimize, it comes from the fact that all of the entries in array are type-checked together at the moment because we need to make sure that the types are all the same.

[xedin]

@swift-ci create

[rudkx]

In this case I believe there is a combination of relatively high overhead in parts of the constraint solver and potentially some quadratic behavior as well, rather than the exponential behavior that we see in some reports of slow type checking.

This isn't the most palatable suggestion, but I noticed that putting `as HuffmanDecodeEntry` after each entry in the array cuts the type checking time in half, so you may consider doing that if you're finding that compiling this file is a bottleneck in your development.