[PATCH] D82497: [Clang][SourceManager] optimize getFileIDLocal()

[Kadir Cetinkaya via Phabricator via cfe-commits]

kadircet added a comment.

For the record: 
http://llvm-compile-time-tracker.com/compare.php?from=ed8184b7814df4310dbad065a9a1c3bb8f3bfa86=408efffbe4a52bae05f1677a47eb3ccfd5cdc1d3=instructions

https://photos.app.goo.gl/fJUS5jrMaJjvvmo1A


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D82497/new/

https://reviews.llvm.org/D82497



___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D82497: [Clang][SourceManager] optimize getFileIDLocal()

[Nick Desaulniers via Phabricator via cfe-commits]

This revision was automatically updated to reflect the committed changes.
Closed by commit rG408efffbe4a5: [Clang][SourceManager] optimize 
getFileIDLocal() (authored by nickdesaulniers).

Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D82497/new/

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

[PATCH] D82497: [Clang][SourceManager] optimize getFileIDLocal()

[Kadir Cetinkaya via Phabricator via cfe-commits]

kadircet accepted this revision.
kadircet added a comment.
This revision is now accepted and ready to land.

LGTM, thanks!

Btw, I've recently learned about http://llvm-compile-time-tracker.com/ so you 
might want to check the effect afterwards.


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D82497/new/

https://reviews.llvm.org/D82497



___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D82497: [Clang][SourceManager] optimize getFileIDLocal()

[Nick Desaulniers via Phabricator via cfe-commits]

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 
),
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 , 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