From 08037045f85bb6875a15b6db9a80b3c3476278a4 Mon Sep 17 00:00:00 2001 From: Ted Kremenek Date: Wed, 27 Feb 2013 00:00:26 +0000 Subject: Refine SourceManager's isBeforeInTranslationUnit() cache to have more entries. isBeforeInTranslationUnit() uses a cache to reduce the expensive work to compute a common ancestor for two FileIDs. This work is very expensive, so even caching the latest used FileIDs was a big win. A closer analysis of the cache before, however, shows that the cache access pattern would oscillate between a working set of FileIDs, and thus caching more pairs would be profitable. This patch adds a side table for extending caching. This side table is bounded in size (experimentally determined in this case from a simple Objective-C project), and when the table gets too large we fall back to the single entry caching before as before. On Sketch (a small example Objective-C project), this optimization reduces -fsyntax-only time on SKTGraphicView.m by 5%. This is for a project that is already using PCH. Fixes llvm-svn: 176142 --- clang/lib/Basic/SourceManager.cpp | 32 +++++++++++++++++++++++++++++++- 1 file changed, 31 insertions(+), 1 deletion(-) (limited to 'clang/lib/Basic/SourceManager.cpp') diff --git a/clang/lib/Basic/SourceManager.cpp b/clang/lib/Basic/SourceManager.cpp index c5d275a..ea95650 100644 --- a/clang/lib/Basic/SourceManager.cpp +++ b/clang/lib/Basic/SourceManager.cpp @@ -1855,7 +1855,32 @@ static bool MoveUpIncludeHierarchy(std::pair &Loc, Loc = SM.getDecomposedLoc(UpperLoc); return false; } - + +/// Return the cache entry for comparing the given file IDs +/// for isBeforeInTranslationUnit. +InBeforeInTUCacheEntry &SourceManager::getInBeforeInTUCache(FileID LFID, + FileID RFID) const { + // This is a magic number for limiting the cache size. It was experimentally + // derived from a small Objective-C project (where the cache filled + // out to ~250 items). We can make it larger if necessary. + enum { MagicCacheSize = 300 }; + IsBeforeInTUCacheKey Key(LFID, RFID); + + // If the cache size isn't too large, do a lookup and if necessary default + // construct an entry. We can then return it to the caller for direct + // use. When they update the value, the cache will get automatically + // updated as well. + if (IBTUCache.size() < MagicCacheSize) + return IBTUCache[Key]; + + // Otherwise, do a lookup that will not construct a new value. + InBeforeInTUCache::iterator I = IBTUCache.find(Key); + if (I != IBTUCache.end()) + return I->second; + + // Fall back to the overflow value. + return IBTUCacheOverflow; +} /// \brief Determines the order of 2 source locations in the translation unit. /// @@ -1875,6 +1900,11 @@ bool SourceManager::isBeforeInTranslationUnit(SourceLocation LHS, // If we are comparing a source location with multiple locations in the same // file, we get a big win by caching the result. + InBeforeInTUCacheEntry &IsBeforeInTUCache = + getInBeforeInTUCache(LOffs.first, ROffs.first); + + // If we are comparing a source location with multiple locations in the same + // file, we get a big win by caching the result. if (IsBeforeInTUCache.isCacheValid(LOffs.first, ROffs.first)) return IsBeforeInTUCache.getCachedResult(LOffs.second, ROffs.second); -- cgit v1.1