     # Don't try to complete Javascrip URLs.
     return callback [] if 0 < queryTerms.length and Utils.hasJavascriptPrefix queryTerms[0]
 
+    # Cache completions.  However, completions depend upon both the searchUrl and the query terms.  So we need
+    # to generate a key.  We mix in some nonsense generated by pwgen. There is the possibility of a key clash,
+    # but it's vanishingly small.
+    junk = "//Zi?ei5;o//"
+    completionCacheKey = searchUrl + junk + queryTerms.join junk
+    @completionCache ?= new SimpleCache 6 * 60 * 60 * 1000, 2000 # Six hours, 2000 entries.
+    if @completionCache.has completionCacheKey
+      return callback @completionCache.get completionCacheKey
+
     engine = @lookupEngine searchUrl
     url = engine.getUrl queryTerms
-    @get searchUrl, url, (xhr = null) ->
-      if xhr? then engine.parse xhr, callback else callback []
+    @get searchUrl, url, (xhr = null) =>
+      if xhr?
+        callback @completionCache.set completionCacheKey, engine.parse xhr
+      else
+        callback []
 
 root = exports ? window
 root.SearchEngines = SearchEngines

  match: -> true
  # We return a useless URL which we know will succeed, but which won't generate any network traffic.
  getUrl: -> chrome.runtime.getURL "content_scripts/vimium.css"
  parse: (_, callback) -> callback []

completionEngines = [ Google, DummySearchEngine ]


    @requests ?= {} # Maps searchUrls to any outstanding HTTP request for that search engine.
    @cancel searchUrl

    # We cache the results of the most-recent 1000 requests with a one-minute expiry.
    @requestCache ?= new SimpleCache 1 * 60 * 1000, 1000

    if @requestCache.has url
      callback @requestCache.get url
