RecursiveASTVisitor slow to compile

[nikic]

Compiling SourceCodeTest.cpp currently takes >50s (with clang 18 as host compiler). The reason is that it has 12 different subclasses of RecursiveASTVisitor. I believe this is also the root cause for a few other clang files with long compile times.

The basic problem is that RecursiveASTVisitor is a CRTP construction, which means that every subclass requires a completely separate instantiation of the visitor implementation -- which is huge. LLVM takes a long time to chew through that.

I'm not entirely sure how this can be fixed -- I'd expect that using virtual methods would make it too slow. Maybe there is some kind of middle ground.

[nikic]

cc @AaronBallman @Endilll in case you have any ideas.

[llvmbot]

@llvm/issue-subscribers-clang-frontend

Author: Nikita Popov (nikic)

Compiling SourceCodeTest.cpp currently takes >50s (with clang 18 as host compiler). The reason is that it has 12 different subclasses of RecursiveASTVisitor. I believe this is also the root cause for a new other clang files with long compile times.

The basic problem is that RecursiveASTVisitor is a CRTP construction, which means that every subclass requires a completely separate instantiation of the visitor implementation -- which is huge. LLVM takes a long time to chew through that.

I'm not entirely sure how this can be fixed -- I'd expect that using virtual methods would make it too slow. Maybe there is some kind of middle ground.

[Sirraide]

I'd expect that using virtual methods would make it too slow

Imo it might be worth exploring this since it is the more or less ‘obvious’ solution; I can look into refactoring the AST visitor to use virtual functions instead to see how much of a difference it would make, if that would help.

@nikic Also, iirc, you’re the one who maintains the compile-time tracker, so I’d appreciate it if you could help w/ the benchmarking in that case because I’m candidly not entirely sure how to do that ‘properly’...

[nikic]

I'd expect that using virtual methods would make it too slow

Imo it might be worth exploring this since it is the more or less ‘obvious’ solution; I can look into refactoring the AST visitor to use virtual functions instead to see how much of a difference it would make, if that would help.

@nikic Also, iirc, you’re the one who maintains the compile-time tracker, so I’d appreciate it if you could help w/ the benchmarking in that case because I’m candidly not entirely sure how to do that ‘properly’...

Sure! I added your fork to the server, so you can now run experiments by pushing a branch that starts with perf/.

[Sirraide]

Sure! I added your fork to the server, so you can now run experiments by pushing a branch that starts with perf/.

Thanks!

[Sirraide]

Ok, I’ve been making some progress, but I’ve run into a few issues that I’m not 100% sure how to solve:

1. TRAVERSE_STMT_BASE from what I can tell checks whether a derived class’s function accepts a DataRecursionQueue and passes it along if it does. The thing that confuses me a bit about this is that I couldn’t find a single function in any derived class that does anything with this queue whatsoever. It’s only the RecursiveASTVisitor itself that seems to be using it. Seeing as this isn’t really possible with virtual functions, can we get away with just storing the current queue in the visitor and pushing/popping a new one in some places (e.g. in TraverseStmt)?
2. Somewhat relatedly, PostVisitStmt uses isSameMethod to check if a derived class overrides a method... which doesn’t work at all with this approach. I’m honestly not sure what the best solution to this would be. That said, postorder traversal seems to be relatively uncommon (I could only find about 5 visitors that use it, as opposed to the 100+ visitors using preorder traversal), so maybe imposing additional constraints on postorder traversal would be an option if need be.

[Sirraide]

CC @AaronBallman

[Sirraide]

PostVisitStmt uses isSameMethod

(which simply just checks if two member function pointers are equal)

[Endilll]

I think that RecursiveASTVisitor is one of the interfaces we offer users. While we don't promise stability, the conservative assumption is that everything there is used by someone even if it's not used in our repository. So if you're going to remove anything, we should offer a transition path.

Post-order traversal will have to stay, I guess. I don't think it can be replaced with anything else.

[Sirraide]

Post-order traversal will have to stay, I guess. I don't think it can be replaced with anything else.

Yeah, I’m not really planning on removing it; it’s just that I’m not entierly sure how to refactor that particular part of it.