Speed up SimpleCache eviction set computation

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>
@@ skipping 32 matching lines @@
 // 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;
 
-// Utility class used for timestamp comparisons in entry metadata while sorting.
-class CompareHashesForTimestamp {
-  typedef disk_cache::SimpleIndex SimpleIndex;
-  typedef disk_cache::SimpleIndex::EntrySet EntrySet;
- public:
-  explicit CompareHashesForTimestamp(const EntrySet& set);
-
-  bool operator()(uint64_t hash1, uint64_t hash2);
-
- private:
-  const EntrySet& entry_set_;
-};
-
-CompareHashesForTimestamp::CompareHashesForTimestamp(const EntrySet& set)
-  : entry_set_(set) {
-}
-
-bool CompareHashesForTimestamp::operator()(uint64_t hash1, uint64_t hash2) {
-  EntrySet::const_iterator it1 = entry_set_.find(hash1);
-  DCHECK(it1 != entry_set_.end());
-  EntrySet::const_iterator it2 = entry_set_.find(hash2);
-  DCHECK(it2 != entry_set_.end());
-  return it1->second.GetLastUsedTime() < it2->second.GetLastUsedTime();
-}
-
 }  // namespace
 
 namespace disk_cache {
 
 EntryMetadata::EntryMetadata()
   : last_used_time_seconds_since_epoch_(0),
     entry_size_(0) {
 }
 
 EntryMetadata::EntryMetadata(base::Time last_used_time,
@@ skipping 236 matching lines @@
     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;
+  entries.reserve(entries_set_.size());
+  for (EntrySet::const_iterator i = entries_set_.begin();
+       i != entries_set_.end(); ++i) {
+    entries.push_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();
+            });
+
+  // Remove as many entries from the index to get below |low_watermark_|,
+  // collecting relevant hashed into entry_hashes.

[pasko, 2017/04/03 09:39:08]

s/relevant/least recently used/ <- reduces guessing for the reader

s/entry_hashes/|entry_hashes|/

[Maks Orlovich, 2017/04/03 14:32:40]

Done.

   std::vector<uint64_t> entry_hashes;
-  entry_hashes.reserve(entries_set_.size());
-  for (EntrySet::const_iterator it = entries_set_.begin(),
-       end = entries_set_.end(); it != end; ++it) {
-    entry_hashes.push_back(it->first);
-  }
-  std::sort(entry_hashes.begin(), entry_hashes.end(),
-            CompareHashesForTimestamp(entries_set_));
-
-  // Remove as many entries from the index to get below |low_watermark_|.
-  std::vector<uint64_t>::iterator it = entry_hashes.begin();
+  entry_hashes.reserve(entries_set_.size() / 16);
+  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 != entry_hashes.end());
-    EntrySet::iterator found_meta = entries_set_.find(*it);
-    DCHECK(found_meta != entries_set_.end());
-    evicted_so_far_size += found_meta->second.GetEntrySize();
+    DCHECK(it != entries.end());
+    entry_hashes.push_back((*it)->first);
+    evicted_so_far_size += (*it)->second.GetEntrySize();
     ++it;
   }
 
-  // Take out the rest of hashes from the eviction list.
-  entry_hashes.erase(it, entry_hashes.end());
   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>(
           evicted_so_far_size / kBytesInKb));
 
@@ skipping 30 matching lines @@
 
 // static
 void SimpleIndex::InsertInEntrySet(
     uint64_t entry_hash,
     const disk_cache::EntryMetadata& entry_metadata,
     EntrySet* entry_set) {
   DCHECK(entry_set);
   entry_set->insert(std::make_pair(entry_hash, entry_metadata));
 }
 
+void SimpleIndex::InsertEntryForTesting(uint64_t entry_hash,
+                                        const EntryMetadata& entry_metadata) {
+  InsertInEntrySet(entry_hash, entry_metadata, &entries_set_);
+}
+
 void SimpleIndex::PostponeWritingToDisk() {
   if (!initialized_)
     return;
   const int delay = app_on_background_ ? kWriteToDiskOnBackgroundDelayMSecs
                                        : kWriteToDiskDelayMSecs;
   // If the timer is already active, Start() will just Reset it, postponing it.
   write_to_disk_timer_.Start(
       FROM_HERE, base::TimeDelta::FromMilliseconds(delay), write_to_disk_cb_);
 }
 
@@ skipping 108 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