nickdesaulniers created this revision. nickdesaulniers added a reviewer: kadircet. Herald added a project: clang. Herald added a subscriber: cfe-commits.
A recent Linux kernel commit exposed a performance cliff in Clang. Calls to SourceManager::getFileIDLocal() when there's a cache miss against LastFileIDLookup can be relatively expensive, as getFileIDLocal() tries a few linear probes, then falls back to binary search. The use of SourceManager::isOffsetInFileID() is also relatively expensive (both isOffsetInFileID and getFileIDLocal dominated a trace of the performance cliff case). As a FIXME notes (and as @kadircet helpfully noted in review of D80681 <https://reviews.llvm.org/D80681>), there's a few optimizations we can do here since we've already identified that an offset is local (as opposed to "loaded"). This patch was forked off of D80681 <https://reviews.llvm.org/D80681>, which additionally did this and modified some caching behavior, as we expect this change to be less controversial. In terms of optimizations, we've already determined that the SLocOffset parameter to SourceManager::getFileIDLocal() is local in the caller SourceManager::getFileIDSlow(). Also, there's an early continue in the binary search loop in getFileIDLocal() that are duplicated in isOffsetInFileID() as pointed out by @kadircet. Take advantage of these to optimize the binary search patch, and remove the FIXME. Repository: rG LLVM Github Monorepo https://reviews.llvm.org/D82497 Files: clang/lib/Basic/SourceManager.cpp Index: clang/lib/Basic/SourceManager.cpp =================================================================== --- clang/lib/Basic/SourceManager.cpp +++ clang/lib/Basic/SourceManager.cpp @@ -898,9 +898,8 @@ } // If the middle index contains the value, succeed and return. - // FIXME: This could be made faster by using a function that's aware of - // being in the local area. - if (isOffsetInFileID(FileID::get(MiddleIndex), SLocOffset)) { + if (MiddleIndex + 1 == LocalSLocEntryTable.size() || + SLocOffset < getLocalSLocEntry(MiddleIndex + 1).getOffset()) { FileID Res = FileID::get(MiddleIndex); // If this isn't a macro expansion, remember it. We have good locality
Index: clang/lib/Basic/SourceManager.cpp =================================================================== --- clang/lib/Basic/SourceManager.cpp +++ clang/lib/Basic/SourceManager.cpp @@ -898,9 +898,8 @@ } // If the middle index contains the value, succeed and return. - // FIXME: This could be made faster by using a function that's aware of - // being in the local area. - if (isOffsetInFileID(FileID::get(MiddleIndex), SLocOffset)) { + if (MiddleIndex + 1 == LocalSLocEntryTable.size() || + SLocOffset < getLocalSLocEntry(MiddleIndex + 1).getOffset()) { FileID Res = FileID::get(MiddleIndex); // If this isn't a macro expansion, remember it. We have good locality
_______________________________________________ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits