evict larger entries first

net/disk_cache/simple/simple_index.cc

Index: net/disk_cache/simple/simple_index.cc
diff --git a/net/disk_cache/simple/simple_index.cc b/net/disk_cache/simple/simple_index.cc
index 3513b59856580adf8c157831ad264b0c28dc31ff..690d981d8b262bf0b8d2665a09fbf1d1ad6d5468 100644
--- a/net/disk_cache/simple/simple_index.cc
+++ b/net/disk_cache/simple/simple_index.cc
@@ -11,6 +11,7 @@
 
 #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"
@@ -25,6 +26,7 @@
 #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"
@@ -49,6 +51,13 @@ const uint32_t kEvictionMarginDivisor = 20;
 
 const uint32_t kBytesInKb = 1024;
 
+// This is added to the size of each entry before using the size
+// to determine which entries to evict first. It's basically an
+// estimate of the filesystem overhead, but it also serves to flatten
+// the curve so that 1-byte entries and 2-byte entries are basically
+// treated the same.
+static const int kEstimatedEntryOverhead = 512;
+
 }  // namespace
 
 namespace disk_cache {
@@ -309,31 +318,40 @@ void SimpleIndex::StartEvictionIfNeeded() {
       static_cast<base::HistogramBase::Sample>(max_size_ / kBytesInKb));
 
   // Flatten for sorting.
-  std::vector<const std::pair<const uint64_t, EntryMetadata>*> entries;
+  typedef std::pair<uint64_t, const EntrySet::value_type*> SortHelper;

[jkarlin, 2017/07/12 15:51:41]

using SortHelper = std::pair<uint64_t, const EntrySet::value_type*>;

[hubbe, 2017/07/12 18:22:50]

Done.

+  std::vector<SortHelper> entries;
   entries.reserve(entries_set_.size());
+  uint32_t now = (base::Time::Now() - base::Time::UnixEpoch()).InSeconds();

[jkarlin, 2017/07/12 15:51:41]

Hmm, can we instead use base::Time here instead of uint32_t? In fact, we should
be using base::Time and TimeDelta throughout.

[hubbe, 2017/07/12 18:22:50]

We can, but it slows things down, so I would prefer not to.

[jkarlin, 2017/07/13 13:24:26]

I'd like to see some sort of benchmark to show that the slowdown is significant.
We should be using base::Time where feasible.

+  bool use_size = false;
+  SimpleExperiment experiment = GetSimpleExperiment(cache_type_);
+  if (experiment.type == SimpleExperimentType::EVICT_WITH_SIZE &&
+      experiment.param) {
+    use_size = true;
+  }
   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();

[jkarlin, 2017/07/12 15:51:41]

The new eviction strategy needs tests in simple_index_unittest.cc

[hubbe, 2017/07/12 18:22:50]

Done.

+    if (use_size) {
+      // Will not overflow since we're multiplying two 32-bit values and storing
+      // them in a 64-bit variable.
+      sort_value *= i->second.GetEntrySize() + kEstimatedEntryOverhead;
+    }
+    // Subtract so we don't need a custom comparator.
+    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();
-            });
-
-  // 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;
+  const uint64_t amount_to_evict = cache_size_ - low_watermark_;
+  std::vector<uint64_t> entry_hashes;
+  auto begin = entries.begin();
+  auto end = entries.end();
+  std::sort(begin, end);
+  for (auto i = begin; i < end; ++i) {
+    if (evicted_so_far_size >= amount_to_evict)
+      break;
+    evicted_so_far_size += i->second->second.GetEntrySize();
+    entry_hashes.push_back(i->second->first);
   }
 
   SIMPLE_CACHE_UMA(COUNTS_1M,