From 362a8f21a6438bb0b1901e0b7ae44b5c33fb48ca Mon Sep 17 00:00:00 2001
From: Douglas Gregor <dgregor@apple.com>
Date: Tue, 19 Oct 2010 19:39:10 +0000
Subject: [PATCH] Improve the performance of typo correction, by using a simple
computation to compute the lower bound of the edit distance, so that we can
avoid computing the edit distance for names that will clearly be rejected
later. Since edit distance is such an expensive algorithm (M x N), this leads
to a 7.5x speedup when correcting NSstring -> NSString in the presence of a
Cocoa PCH.
git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@116849 91177308-0d34-0410-b5e6-96231b3b80d8
---
lib/Sema/SemaLookup.cpp | 6 ++++++
1 file changed, 6 insertions(+)
diff --git a/lib/Sema/SemaLookup.cpp b/lib/Sema/SemaLookup.cpp
index 6cd0207c80..de581fc6c6 100644
--- a/lib/Sema/SemaLookup.cpp
+++ b/lib/Sema/SemaLookup.cpp
@@ -2730,6 +2730,12 @@ void TypoCorrectionConsumer::FoundDecl(NamedDecl *ND, NamedDecl *Hiding,
}
void TypoCorrectionConsumer::FoundName(llvm::StringRef Name) {
+ // Use a simple length-based heuristic to determine the minimum possible
+ // edit distance. If the minimum isn't good enough, bail out early.
+ unsigned MinED = abs((int)Name.size() - (int)Typo.size());
+ if (MinED > BestEditDistance || (MinED && Typo.size() / MinED < 3))
+ return;
+
// Compute the edit distance between the typo and the name of this
// entity. If this edit distance is not worse than the best edit
// distance we've seen so far, add it to the list of results.
--
2.40.0