optimization

1 files changed, 29 insertions, 15 deletions

diff --git a/lib/completion.js b/lib/completion.js
index f04eb356..b3e70516 100644
--- a/lib/completion.js
+++ b/lib/completion.js
@@ -7,18 +7,21 @@ var completion = (function() {
     var self = {};
 
     self.timeToClean = 0;
-    self.matcherCacheSize = 300;
+    self.cacheSize = 1000;
     self.regexNonWord = /[\W_]/ig;
 
     // cache generated regular expressions
     self.matcherCache = {};
     // cache filtered results from recent queries
     self.filterCache = {};
+    self.normalizationCache = {};
 
     /** Normalizes the string specified in :query. Strips any non-word characters and converts
      * to lower case. */
     self.normalize = function(query) {
-      return query.replace(self.regexNonWord, '').toLowerCase();
+      if (!(query in self.normalizationCache))
+        self.normalizationCache[query] = query.replace(self.regexNonWord, '').toLowerCase();
+      return self.normalizationCache[query];
     }
 
     /** Returns the non-matching and matching string parts, in alternating order (starting with a
@@ -80,12 +83,17 @@ var completion = (function() {
       return sum * sum * sum;
     }
 
-    /** Trims the size of the regex cache to the configured size using a FIFO algorithm. */
-    self.cleanMatcherCache = function() {
-      // remove old matchers
-      Object.keys(self.matcherCache).forEach(function(query) {
+    /** Trims the size of the caches to the configured size using a FIFO algorithm. */
+    self.cleanCache = function() {
+      console.log("cleaning cache");
+      // remove old cached regexes
+      Object.keys(self.matcherCache).slice(self.cacheSize).forEach(function(query) {
         delete self.matcherCache[query];
       });
+      // remove old cached normalization results
+      Object.keys(self.normalizationCache).slice(self.cacheSize).forEach(function(query) {
+        delete self.normalizationCache[query];
+      });
     }
 
     /** Returns a regex that matches a string using a fuzzy :query. Example: The :query "abc" would result
@@ -94,12 +102,18 @@ var completion = (function() {
     self.getMatcher = function(query) {
       query = self.normalize(query);
       if (!(query in self.matcherCache)) {
-        // build up a regex for fuzzy matching
-        // TODO use an array and .join here
-        var regex = '^';
-        for (var i = 0; i < query.length; ++i)
-          regex += '([^' + query[i] + ']*)(' + query[i] + ')';
-        self.matcherCache[query] = new RegExp(regex + '(.*)$', 'i');
+        // build up a regex for fuzzy matching. This is the fastest method I checked (faster than:
+        // string building, splice, concat, multi-level join)
+        var regex = ['^'];
+        for (var i = 0; i < query.length; ++i) {
+          regex.push('([^');
+          regex.push(query[i]);
+          regex.push(']*)(');
+          regex.push(query[i]);
+          regex.push(')');
+        }
+        regex.push('(.*)$');
+        self.matcherCache[query] = new RegExp(regex.join(''), 'i');
       }
       return self.matcherCache[query];
     }
@@ -142,10 +156,10 @@ var completion = (function() {
         }
       }
 
-      // don't clean up the cache every iteration
-      if (++self.timeToClean > 20) {
+      // don't clean up the caches every iteration
+      if (++self.timeToClean > 100) {
         self.timeToClean = 0;
-        self.cleanMatcherCache();
+        self.cleanCache();
       }
 
       var matcher = self.getMatcher(query);