Switch StringRef::edit_distance over to using raw pointers, since both

std::vector and llvm::SmallVector have annoying performance
tradeoffs. No, I don't expect this to matter, and now it won't.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@92884 91177308-0d34-0410-b5e6-96231b3b80d8

diff --git a/lib/Support/StringRef.cpp b/lib/Support/StringRef.cpp
index e4a9984828f3edc74e88270c223395fd34f5cb35..e577b954c553a3fcda63ad3ad2efaf76684d14b4 100644 (file)
--- a/lib/Support/StringRef.cpp
+++ b/lib/Support/StringRef.cpp
@@ -8,7 +8,8 @@
 //===----------------------------------------------------------------------===//
 
 #include "llvm/ADT/StringRef.h"
 //===----------------------------------------------------------------------===//
 
 #include "llvm/ADT/StringRef.h"

-#include "llvm/ADT/SmallVector.h"
+#include <cstring>
+

 using namespace llvm;
 
 // MSVC emits references to this into the translation units which reference it.
 using namespace llvm;
 
 // MSVC emits references to this into the translation units which reference it.


@@ -51,13 +52,21 @@ unsigned StringRef::edit_distance(llvm::StringRef Other,
   size_type m = size();
   size_type n = Other.size();
 
   size_type m = size();
   size_type n = Other.size();
 

-  SmallVector<unsigned, 32> previous(n+1, 0);
-  for (SmallVector<unsigned, 32>::size_type i = 0; i <= n; ++i) 
+  unsigned SmallPrevious[32];
+  unsigned SmallCurrent[32];
+  
+  unsigned *previous = SmallPrevious;
+  unsigned *current = SmallCurrent;
+  if (n + 1 > 32) {
+    previous = new unsigned [n+1];
+    current = new unsigned [n+1];
+  }
+  
+  for (unsigned i = 0; i <= n; ++i) 

     previous[i] = i;
 
     previous[i] = i;
 

-  SmallVector<unsigned, 32> current(n+1, 0);

   for (size_type y = 1; y <= m; ++y) {
   for (size_type y = 1; y <= m; ++y) {

-    current.assign(n+1, 0);
+    std::memset(current, 0, (n + 1) * sizeof(unsigned));

     current[0] = y;
     for (size_type x = 1; x <= n; ++x) {
       if (AllowReplacements) {
     current[0] = y;
     for (size_type x = 1; x <= n; ++x) {
       if (AllowReplacements) {


@@ -69,10 +78,19 @@ unsigned StringRef::edit_distance(llvm::StringRef Other,
         else current[x] = min(current[x-1], previous[x]) + 1;
       }
     }
         else current[x] = min(current[x-1], previous[x]) + 1;
       }
     }

-    current.swap(previous);
+    
+    unsigned *tmp = current;
+    current = previous;
+    previous = tmp;

   }
 
   }
 

-  return previous[n];
+  unsigned Result = previous[n];
+  if (n + 1 > 32) {
+    delete [] previous;
+    delete [] current;
+  }
+  
+  return Result;

 }
 
 //===----------------------------------------------------------------------===//
 }
 
 //===----------------------------------------------------------------------===//