Skip to content

Instantly share code, notes, and snippets.

@vsapsai

vsapsai/clang-performance.md

Created October 21, 2021 20:56
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save vsapsai/53f9fbec54a76ab4302095ce84cdaed1 to your computer and use it in GitHub Desktop.
Save vsapsai/53f9fbec54a76ab4302095ce84cdaed1 to your computer and use it in GitHub Desktop.
Download ZIP
Potential avenues for improving clang performance. Mostly when working with modules.
Raw
clang-performance.md

Inspired by Richard Howell's change https://reviews.llvm.org/D109632 we are calling Sema::addMethodToGlobalList too much when ASTReader::ReadMethodPool.

Some debugging indicates that comments and assumptions in Sema::addMethodToGlobalList might not be correct for a modular case and ObjCMethodList *List can be longer than it was originally expected. Iterating through a long list can be expensive and in the worst case it can add O(n) complexity (that might end up being multiplied by a length of another list). So it is worth checking the length of ObjCMethodList in this method, how it can grow, should we use a different data structure for this purpose.

Another issue that came up is that visiting multiple modules can be expensive. I have no evidence that iterating through all dependencies once is expensive. But I have bad feeling that we are doing O(<number of direct dependencies> * <number of method references in a file>) work. Which can be pretty bad in the worst case. Need to create a synthetic test case and verify if it is a problem.

Also earlier I've observed we are calling ASTReader::ReadASTCore O(<number of all dependencies>^2) times. Maybe it was fixed since then, so need to check again. Used https://reviews.llvm.org/D86896 for data generation.

See also

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment