evict larger entries first

net/disk_cache/simple/simple_index.cc

 // Copyright (c) 2013 The Chromium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include "net/disk_cache/simple/simple_index.h"
 
 #include <algorithm>
 #include <limits>
 #include <string>
 #include <utility>
 
 #include "base/bind.h"
 #include "base/bind_helpers.h"
+#include "base/bits.h"
 #include "base/files/file_enumerator.h"
 #include "base/files/file_util.h"
 #include "base/logging.h"
 #include "base/message_loop/message_loop.h"
 #include "base/metrics/field_trial.h"
 #include "base/numerics/safe_conversions.h"
 #include "base/pickle.h"
 #include "base/strings/string_number_conversions.h"
 #include "base/strings/string_tokenizer.h"
 #include "base/task_runner.h"
 #include "base/time/time.h"
 #include "base/trace_event/memory_usage_estimator.h"
 #include "net/base/net_errors.h"
 #include "net/disk_cache/simple/simple_entry_format.h"
+#include "net/disk_cache/simple/simple_experiment.h"
 #include "net/disk_cache/simple/simple_histogram_macros.h"
 #include "net/disk_cache/simple/simple_index_delegate.h"
 #include "net/disk_cache/simple/simple_index_file.h"
 #include "net/disk_cache/simple/simple_synchronous_entry.h"
 #include "net/disk_cache/simple/simple_util.h"
 
 #if defined(OS_POSIX)
 #include <sys/stat.h>
 #include <sys/time.h>
 #endif
 
 namespace {
 
 // How many milliseconds we delay writing the index to disk since the last cache
 // operation has happened.
 const int kWriteToDiskDelayMSecs = 20000;
 const int kWriteToDiskOnBackgroundDelayMSecs = 100;
 
 // Divides the cache space into this amount of parts to evict when only one part
 // is left.
 const uint32_t kEvictionMarginDivisor = 20;
 
 const uint32_t kBytesInKb = 1024;
 
+// Estimated bytes used above the size of the data itself.
+static const int kEstimatedEntryOverhead = 512;

[Maks Orlovich, 2017/06/22 16:30:51]

FWIW, GetEntrySize is the size of the file, not of payload (though it doesn't
include things like block overhead and FS costs of tracking it)

[hubbe, 2017/06/22 17:36:10]

Updated comment.

+
 }  // namespace
 
 namespace disk_cache {
 
 EntryMetadata::EntryMetadata()
   : last_used_time_seconds_since_epoch_(0),
     entry_size_(0) {
 }
 
 EntryMetadata::EntryMetadata(base::Time last_used_time,
@@ skipping 240 matching lines @@
   eviction_in_progress_ = true;
   eviction_start_time_ = base::TimeTicks::Now();
   SIMPLE_CACHE_UMA(
       MEMORY_KB, "Eviction.CacheSizeOnStart2", cache_type_,
       static_cast<base::HistogramBase::Sample>(cache_size_ / kBytesInKb));
   SIMPLE_CACHE_UMA(
       MEMORY_KB, "Eviction.MaxCacheSizeOnStart2", cache_type_,
       static_cast<base::HistogramBase::Sample>(max_size_ / kBytesInKb));
 
   // Flatten for sorting.
-  std::vector<const std::pair<const uint64_t, EntryMetadata>*> entries;
+  typedef std::pair<const uint64_t, EntryMetadata> Entry;
+  typedef std::pair<uint64_t, const Entry*> SortHelper;
+  std::vector<SortHelper> entries;
   entries.reserve(entries_set_.size());
+  uint32_t now = (base::Time::Now() - base::Time::UnixEpoch()).InSeconds();
+  bool use_size = base::FeatureList::IsEnabled(kSimpleCacheEvictionWithSize);
   for (EntrySet::const_iterator i = entries_set_.begin();
        i != entries_set_.end(); ++i) {
-    entries.push_back(&*i);
+    uint64_t sort_value = now - i->second.RawTimeForSorting();
+    if (use_size)
+      sort_value *= i->second.GetEntrySize() + kEstimatedEntryOverhead;
+    // Subtract so we don't need a custom comparitor.

[Maks Orlovich, 2017/06/22 16:30:51]

typo, s/comparitor/comparator/

[hubbe, 2017/06/22 17:36:10]

Done.

+    entries.emplace_back(std::numeric_limits<uint64_t>::max() - sort_value,
+                         &*i);
   }
 
-  std::sort(entries.begin(), entries.end(),
-            [](const std::pair<const uint64_t, EntryMetadata>* a,
-               const std::pair<const uint64_t, EntryMetadata>* b) -> bool {
-              return a->second.RawTimeForSorting() <
-                     b->second.RawTimeForSorting();
-            });
+  // introselect algorithm:
+  // Pick a pivot element, partition elements into elements
+  // smaller than the pivot and not smaller than pivot.
+  // Then sum all the sizes from the "smaller" bucket. If it
+  // is still too large, then iterate again, but only consider
+  // elements from the "smaller" bucket.  If not, add all elements
+  // in the "smaller" bucket to the evict list.
+  // Then iterate again, to partition the "not smaller" bucket.
+  // If we go over 2 * log2(|entries|) iterations, resort to calling
+  // std::sort() to avoid N-squared worst case scenario.
+  uint64_t evicted_so_far_size = 0;
+  const uint64_t amount_to_evict = cache_size_ - low_watermark_;
+  std::vector<uint64_t> entry_hashes;
+  int loops = 2 * base::bits::Log2Ceiling(entries.size());
+  auto begin = entries.begin();
+  auto end = entries.end();
+  while (loops > 0 && evicted_so_far_size < amount_to_evict &&
+         end - begin >= 3) {
+    loops--;
 
-  // Remove as many entries from the index to get below |low_watermark_|,
-  // collecting least recently used hashes into |entry_hashes|.
-  std::vector<uint64_t> entry_hashes;
-  std::vector<const std::pair<const uint64_t, EntryMetadata>*>::iterator it =
-      entries.begin();
-  uint64_t evicted_so_far_size = 0;
-  while (evicted_so_far_size < cache_size_ - low_watermark_) {
-    DCHECK(it != entries.end());
-    entry_hashes.push_back((*it)->first);
-    evicted_so_far_size += (*it)->second.GetEntrySize();
-    ++it;
+    // Select a pivot.
+    uint64_t tmp[3];
+    tmp[0] = begin->first;
+    tmp[1] = (end - 1)->first;
+    tmp[2] = (begin + (end - begin) / 2)->first;
+    std::sort(tmp, tmp + 3);
+    uint64_t pivot = tmp[1];
+
+    // Partition
+    auto middle = std::partition(begin, end, [pivot](const SortHelper& entry) {
+      return entry.first < pivot;
+    });
+    if (middle == end || middle == begin) {
+      // No progress will be made.
+      break;
+    }
+    uint64_t lt_sum = 0;
+    for (auto i = begin; i != middle; ++i)
+      lt_sum += i->second->second.GetEntrySize();
+
+    if (evicted_so_far_size + lt_sum > amount_to_evict) {
+      end = middle;
+    } else {
+      evicted_so_far_size += lt_sum;
+      for (auto i = begin; i != middle; ++i)
+        entry_hashes.push_back(i->second->first);
+
+      begin = middle;
+    }
+  }
+
+  if (end > begin && evicted_so_far_size < amount_to_evict) {
+    std::sort(begin, end);
+    for (auto i = begin; i < end; ++i) {
+      if (evicted_so_far_size > amount_to_evict)

[hubbe, 2017/06/22 17:36:10]

Done.

+        break;
+      evicted_so_far_size += i->second->second.GetEntrySize();
+      entry_hashes.push_back(i->second->first);
+    }
   }
 
   SIMPLE_CACHE_UMA(COUNTS,
                    "Eviction.EntryCount", cache_type_, entry_hashes.size());
   SIMPLE_CACHE_UMA(TIMES,
                    "Eviction.TimeToSelectEntries", cache_type_,
                    base::TimeTicks::Now() - eviction_start_time_);
   SIMPLE_CACHE_UMA(
       MEMORY_KB, "Eviction.SizeOfEvicted2", cache_type_,
       static_cast<base::HistogramBase::Sample>(
@@ skipping 167 matching lines @@
                        start - last_write_to_disk_);
     }
   }
   last_write_to_disk_ = start;
 
   index_file_->WriteToDisk(reason, entries_set_, cache_size_, start,
                            app_on_background_, base::Closure());
 }
 
 }  // namespace disk_cache