                         break
             # Apply each of the patches we need to get from
             # value (the last snapshot) to time.
-            for i in [start...@_patches.length]
-                x = @_patches[i]
+            cache_time = 0
+            cache_start = start
+            for x in @_patches.slice(start, @_patches.length)
                 if time? and x.time > time
                     # Done -- no more patches need to be applied
                     break
                 # Apply a patch to move us forward.
                 #console.log("applying patch #{i}")
                 value = apply_patch(x.patch, value)[0]
-                if not time?
-                    # We will save the results of applying
-                    # all these patches in our local cache.
-                    cache_time = x.time
-
-        if cache_time
-            # update the cache with our new known value
-            @_cache = {time:cache_time, value:value, start:@_patches.length}
+                cache_time = x.time
+                cache_start += 1
+            if not time? or cache_time and cache_start - start >= 10
+                # Newest -- or at least 10 patches needed to be applied -- so
+                # update the cache with our new known value
+                @_cache.include(cache_time, value, cache_start)
+                @_cache.prune(Math.max(3, Math.min(Math.ceil(30000000/value.length), MAX_PATCHLIST_CACHE_SIZE)))
 
         #console.log("value: time=#{new Date() - start_time}")
+        # Use the following only for testing/debugging, since it will make everything VERY slow.
+        #if @_value_no_cache(time) != value
+        #    console.warn("value for time #{time-0} is wrong!")
+        return value
+
+    # Slow -- only for consistency checking purposes
+    _value_no_cache: (time) =>
+        value = '' # default in case no snapshots
+        start = 0
+        if @_patches.length > 0  # otherwise the [..] notation below has surprising behavior
+            for i in [@_patches.length-1 .. 0]
+                if (not time? or @_patches[i].time - time <= 0) and @_patches[i].snapshot?
+                    # Found a patch with known snapshot that is as old as the time.
+                    # This is the base on which we will apply other patches to move forward
+                    # to the requested time.
+                    value = @_patches[i].snapshot
+                    start = i + 1
+                    break
+        # Apply each of the patches we need to get from
+        # value (the last snapshot) to time.
+        for x in @_patches.slice(start, @_patches.length)
+            if time? and x.time > time
+                # Done -- no more patches need to be applied
+                break
+            value = apply_patch(x.patch, value)[0]
         return value
 
     # integer index of user who made the edit at given point in time (or undefined)

time_cmp = (a,b) ->
    return a - b   # sorting Date objects doesn't work perfectly!

# Sorted list of patches applied to a string
class SortedPatchList
    constructor: () ->
        @_patches = []
        @_times = {}
        @_snapshot_times = {}

    add: (patches) =>

            # nothing to do
            return
        v = []
        oldest = undefined
        for x in patches
            if x? and (not @_times[x.time - 0] or (x.snapshot? and not @_snapshot_times[x.time - 0]))
                v.push(x)
                @_times[x.time - 0] = true
                if not oldest? or oldest > x.time
                    oldest = x.time
                if x.snapshot?
                    @_snapshot_times[x.time - 0] = true
                    # WARNING: again, assuming patch times are unique here.
                    @_patches = (y for y in @_patches when y.time - 0 != x.time - 0)
        if oldest?
            @_cache.invalidate(oldest)

        # this is O(n*log(n)) where n is the length of @_patches and patches;
        # better would be an insertion sort which would be O(m*log(n)) where m=patches.length...
        if v.length > 0
