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 c41c829bdefd808db4ea55dded03e54f4574b641..549b6ee3bb1167334f7049c8c0429760c4febe0b 100644
--- a/net/disk_cache/simple/simple_index.cc
+++ b/net/disk_cache/simple/simple_index.cc
@@ -25,6 +25,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"
@@ -294,6 +295,25 @@ bool SimpleIndex::UseIfExists(uint64_t entry_hash) {
   return true;
 }
 
+namespace {
+
+struct EvictionSortHelper {

[jkarlin, 2017/06/08 14:32:49]

Struct needs comment

[hubbe, 2017/06/08 17:45:03]

Done.

+  explicit EvictionSortHelper(
+      const std::pair<const uint64_t, EntryMetadata>* entry)
+      : entry(entry) {}
+  uint32_t SortValue1() const { return entry->second.RawTimeForSorting(); }
+  int64_t SortValue2() const { return sort_value_; }
+  void SetSortValue(uint64_t rank) {
+    sort_value_ = rank * (entry->second.GetEntrySize() +
+                          EntryMetadata::kEstimatedEntryOverhead);

[jkarlin, 2017/06/08 14:32:49]

The kEstimatedEntryOverhead bit is strange.

Each sort_value_ has (rank * kEstimatedEntryOverhead) added to it.

You could divide kEstimatedEntryOverhead out of each sort_value_ without
affecting the order, which means that this is effectively:

sort_value_ = rank + rank*entry->second.GetEntrySize();

[hubbe, 2017/06/08 17:45:03]

Eh? No?
sv = rank * (size + overhead) =>
sv = rank * size + rank * overhead =>
sv / overhead = rank * size / overhead + rank

[jkarlin, 2017/06/08 18:18:53]

Whoops :) Still, where does the size of overhead come from?

[hubbe, 2017/06/08 18:23:36]

The overhead comes from the block size of most devices.
However, it also serves a separate purpose: It moderates the effect of the size
for small files. The idea being that saving a 1-byte file twice as long as a
2-byte file makes no sense.

Maybe I should write a design doc for this change too?

+  }
+
+  const std::pair<const uint64_t, EntryMetadata>* entry;
+  uint64_t sort_value_;
+};
+
+}  // namespace
+
 void SimpleIndex::StartEvictionIfNeeded() {
   DCHECK(io_thread_checker_.CalledOnValidThread());
   if (eviction_in_progress_ || cache_size_ <= high_watermark_)
@@ -309,30 +329,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;
+  std::vector<EvictionSortHelper> entries;
   entries.reserve(entries_set_.size());
   for (EntrySet::const_iterator i = entries_set_.begin();
        i != entries_set_.end(); ++i) {
-    entries.push_back(&*i);
+    entries.emplace_back(&*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();
-            });
+  std::sort(
+      entries.begin(), entries.end(),
+      [](const EvictionSortHelper& a, const EvictionSortHelper& b) -> bool {
+        return a.SortValue1() < b.SortValue1();

[jkarlin, 2017/06/08 14:32:49]

If you use > here instead of < then you don't need the entries.sizes()-i bit
below, which is a bit clearer.

[hubbe, 2017/06/08 17:45:03]

That won't work when kSimpleCacheEvictionWithSize is not enabled though. But it
can be cleaned up later if we decide that kSimpleCacheEvictionWithSize should
always be on.

[jkarlin, 2017/06/08 18:18:53]

Acknowledged.

+      });
+
+  if (base::FeatureList::IsEnabled(kSimpleCacheEvictionWithSize)) {
+    for (size_t i = 0; i < entries.size(); i++) {
+      entries[i].SetSortValue(entries.size() - i);
+    }
+
+    std::sort(
+        entries.begin(), entries.end(),
+        [](const EvictionSortHelper& a, const EvictionSortHelper& b) -> bool {
+          return a.SortValue2() > b.SortValue2();
+        });
+  }
 
   // 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();
+  std::vector<EvictionSortHelper>::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();
+    entry_hashes.push_back(it->entry->first);
+    evicted_so_far_size += it->entry->second.GetEntrySize();
     ++it;
   }