sammccall added a subscriber: klimek. sammccall added a comment. Wow, yeah, this seems pretty bad! I'm not very familiar with this code. I'm curious, for "it tooks more than 1 second" - what OS is this on?
My guess is that way back when, the performance of looking up a CDB entry that didn't exist wasn't a big deal, or windows support wasn't a big thing, or this was just an oversight. My reading of the code is that any TrieNode is a set of candidates that match a suffix of the path equally well, and we're trying to walk down the tree making the suffix longer and the candidate set more restrictive. When we reach the node whether the path stops matching, we scan all the candidates to see if they're symlink-equivalent. This is expensive if the set is too large, which is trivially the case if the filename is unique in the project (so we never get past the root node, and stat every file in the project). I think it would be slightly cleaner to fix this in the trie itself, either: - don't scan for equivalences if the set of candidates exceeds some size threshold (10 or so) - don't scan for equivalences if the node we'd scan under is the root @klimek In case you have context or thoughts here. Always fun to find a 9 year old bug :-) Repository: rG LLVM Github Monorepo CHANGES SINCE LAST ACTION https://reviews.llvm.org/D83621/new/ https://reviews.llvm.org/D83621 _______________________________________________ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
