Evaluate reducing compiler file system reads by reducing search paths

[jerrymarino]

When looking at rules_ios, I noticed that there are a significant number of search paths passed into the compiler. It seems to be O(N) transitive dependencies.

If the compiler needs to hit these search paths for each job, there will be a O( M search paths X N imports ) performance hit on I/O: specifically it will do a lot more reads than it should. The classic fix for this, which PodToBUILD uses is to pass a single search path to a headermap which has O(1) lookups. This is just something I noticed when looking at rules_ios and haven't tested it out in depth.

[segiddins]

Most everything is a framework search path, which headermaps won't work for -- we'd need a vfs overlay, and either way, this is how Xcode handles search paths for framework headers, and we don't want to deviate in behavior

[jerrymarino]

Makes sense to me, I haven't tested using a VFS VS hmap recently but originally the hmap loaded a lot faster into memory and was faster for clang. This being aside, I noticed a few things when playing around with this locally:

A basic Xcode project with frameworks

Xcode puts built frameworks into single directory - tools would find the build frameworks at O(1) search cost if it gets the it the build directory in the search first - it seems to in my testing.

In practice, the tools like clang swift and ld would up finding a matching dep framework in the build directory and won't search further.

Specifically the command lines always will have the first search path

-F/Path/toDerivedData/*/Build/Products/Debug-iphonesimulator

Cocoapods default behavior with a framework

Cocoapods version I'm running locally seems to put frameworks in their own directory, so even if xcode were to have the path as above it won't find them. This would implicate the O(N) deps searching as above, unless of course it is using a top level VFS or other mechanism to mitigate the search in clang and swift.

-F/Path/toDerivedData/*/Build/Products/Debug-iphonesimulator/DepA
-F/Path/toDerivedData/*/Build/Products/Debug-iphonesimulator/DepB

Mitigation going forward

I'm interested to see flame graphs and --profiling output for any solution to this before and after 📈

Perhaps a VFS could be a path to get it to the state of O(1) framework locating: vs having to search all the transitive framework paths. I'm interested to see how this can impact the search algorithms in clang and swift, and also the cost of serializing in the json vfs. Where hmap is a binary hash table that's fast to map in.

Also, the module cache can help here. When not pulling from a populated module cache, it might still be expensive and may be worth worth profiling. The header search cost is probably paid down multiple times with per OS modules: #225