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

[pasko, 2017/03/31 17:41:56]

nit: period at the end of the sentence

[Maks Orlovich, 2017/03/31 19:01:29]

Done.

+  std::vector<const std::pair<const uint64_t, EntryMetadata>*> entries;
+  entries.reserve(entries_set_.size());
+  for (EntrySet::const_iterator i = entries_set_.begin();

[pasko, 2017/03/31 17:41:56]

how about:

for (auto& entry : entries_set_) { ... ?

[Maks Orlovich, 2017/03/31 19:01:29]

Hmm, I think it'll work (with a const... might not w/o it), but it's really hard
to be confident that it'd actually take pointers into the structure with one
more layer of abstraction here hiding the iterators. That's the trick here,
really --- EntryMetadata is biggish, but a pointer into the table is <= 8 bytes.
(The iterator isn't. I tried)

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

After looking at it 2nd time I think the explicit iterator is the right call,
since it might look confusing to have the 'auto' to map to std::pair. Maybe not
so confusing in 2020, but 2017 for pasko@ it would :)
sizeof(EntryMetadata) == 8, see:
https://codesearch.chromium.org/chromium/src/net/disk_cache/simple/simple_ind...

But then you are right about one target: sizeof(EntryMetadata*) == 4 on
Android/ARM (i.e. what we currently ship), so it's a win. By the way, please
update the description to mention that it saves one aspect of memory consumption
on android/arm32.

+       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.GetLastUsedTime() < b->second.GetLastUsedTime();

[Maks Orlovich, 2017/03/30 18:51:29]

Can get it further down to 2.9-3ms range by adding an inline accessor for
last_used_time_seconds_since_epoch_ to EntryMetadata and comparing that,
avoiding needing the external call and conversion to time::Base, etc.

Should I?

[pasko, 2017/03/31 17:41:56]

yeah, comparing the seconds directly sounds worth this small change, even if
only to avoid thinking of GetLastUsedTime() being more expensive on Windows
(though I am not sure whether the perf difference is actually noticeable).

Whether to inline it or not - maybe let the compiler decide for now? I think at
least GCC would do a good job of inlining simple 32bit getters, even when we
optimize for size. Anyway, it is not such a big deal, so just avoid clutter with
manual inline.

[Maks Orlovich, 2017/03/31 19:01:29]

Done. By inline I just meant int Accessor() const { return field_; } above.

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

Acknowledged.

+            });
+
+  // Remove as many entries from the index to get below |low_watermark_|,
+  // collecting relevant hashed into entry_hashes.
   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);

[pasko, 2017/03/31 17:41:56]

why 16? The low_watermark_ is based on kEvictionMarginDivisor, using it would be
good in assumptions that all entries are equally sized and probably OK otherwise
as well.

[Maks Orlovich, 2017/03/31 19:01:29]

Mostly just going with a nearest power of 2. Probably a pointless
overoptimization --- I don't suppose a proper divide would be an issue even on a
lowest-end phone? (Though GCC/clang can probably turn it into multiply, too)

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

Hm, I did not think of the division overhead here, thanks for insight :) It
would be hard to spot the cost of it on the benchmark we have, which is already
a microbenchmark, so on the real world scenarios the effect is even smaller.

I think the absence of .reserve() will also be not noticeable. Let's remove it
for simplicity? Looks like premature optimization.

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