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;
 
+// 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 {
 
 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;

[pasko, 2017/06/29 15:27:25]

Entry is an overloaded term. Maybe HashAndEntryPair?

[hubbe, 2017/06/29 18:55:27]

I think I'll just replace it with EntrySet::value_type

+  typedef std::pair<uint64_t, const Entry*> SortHelper;
+  std::vector<SortHelper> entries;

[pasko, 2017/06/29 15:27:25]

const SortHelper?

[hubbe, 2017/06/29 18:55:27]

Creates a long list of errors when I try to compile.
Not sure why.

   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;

[pasko, 2017/06/29 15:27:25]

nit: maybe worth a comment to say that it would not overflow because entry size
is topped at 2GiB and the time is in seconds? okay, maybe that's obvious..

[hubbe, 2017/06/29 18:55:27]

Might reduce reader friction slightly, so I'll put it in.

+    // 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();
-            });
+  // 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.

[pasko, 2017/06/29 15:27:25]

If it is only marginally faster than std::sort, I would prefer the latter.

[hubbe, 2017/06/29 18:55:27]

Depends on what you mean by marginal.
The introselect algorithm is linear on average, so the more entries that are in
the cache, the more we gain from it. Since evicting by size will keep more
entries in the cache, I felt that this might be important.

[pasko, 2017/07/06 12:30:17]

I'd say a custom introselect is worth if it provides more than 2ms improvement
over std::sort on M53 core for 99th %-ile of cache sizes (16K entries). Welcome
to my world of arbitrary numbers :)

+  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)
+        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