Speed up SimpleCache eviction set computation

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 57f9603a391e44c99c99192b7e28a54f5878ba8c..d84c491d1894f116af9ac2e940b42df8e24552c6 100644
--- a/net/disk_cache/simple/simple_index.cc
+++ b/net/disk_cache/simple/simple_index.cc
@@ -50,31 +50,6 @@ 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 {
@@ -331,28 +306,36 @@ void SimpleIndex::StartEvictionIfNeeded() {
   SIMPLE_CACHE_UMA(
       MEMORY_KB, "Eviction.MaxCacheSizeOnStart2", cache_type_,
       static_cast<base::HistogramBase::Sample>(max_size_ / kBytesInKb));
-  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);
+
+  // 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(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();
+  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() / 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,
@@ -403,6 +386,11 @@ void SimpleIndex::InsertInEntrySet(
   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;