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/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
@@ skipping 249 matching lines @@
   // It will be merged later.
   EntrySet::iterator it = entries_set_.find(entry_hash);
   if (it == entries_set_.end())
     // If not initialized, always return true, forcing it to go to the disk.
     return !initialized_;
   it->second.SetLastUsedTime(base::Time::Now());
   PostponeWritingToDisk();
   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_)
     return;
   // Take all live key hashes from the index and sort them by time.
   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;
+  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;
   }
 
   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_,
@@ skipping 168 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