Speed up SimpleCache eviction set computation

net/disk_cache/disk_cache_perftest.cc

Index: net/disk_cache/disk_cache_perftest.cc
diff --git a/net/disk_cache/disk_cache_perftest.cc b/net/disk_cache/disk_cache_perftest.cc
index eeef3b71d7363016b6e582d05b0e544cb22c6607..f28c85eb293bee4e852e3ac3167a20c48f1b0028 100644
--- a/net/disk_cache/disk_cache_perftest.cc
+++ b/net/disk_cache/disk_cache_perftest.cc
@@ -27,6 +27,8 @@
 #include "net/disk_cache/disk_cache_test_base.h"
 #include "net/disk_cache/disk_cache_test_util.h"
 #include "net/disk_cache/simple/simple_backend_impl.h"
+#include "net/disk_cache/simple/simple_index.h"
+#include "net/disk_cache/simple/simple_index_file.h"
 #include "testing/gtest/include/gtest/gtest.h"
 #include "testing/platform_test.h"
 
@@ -305,4 +307,43 @@ TEST_F(DiskCachePerfTest, BlockFilesPerformance) {
   base::RunLoop().RunUntilIdle();
 }
 
+// Measures how quickly SimpleIndex can compute which entries to evict.
+TEST(SimpleIndexPerfTest, EvictionPerformance) {
+  const int kEntries = 10000;
+
+  class NoOpDelegate : public disk_cache::SimpleIndexDelegate {
+    void DoomEntries(std::vector<uint64_t>* entry_hashes,
+                     const net::CompletionCallback& callback) override {}
+  };
+
+  NoOpDelegate delegate;
+  base::Time start(base::Time::Now());
+
+  double evict_elapsed_ms = 0;
+  int iterations = 0;
+  while (iterations < 61000) {
+    ++iterations;
+    disk_cache::SimpleIndex index(nullptr, &delegate, net::DISK_CACHE, nullptr);
+
+    // Make sure large enough to not evict on insertion.
+    index.SetMaxSize(kEntries * 2);
+
+    for (int i = 0; i < kEntries; ++i) {
+      index.InsertEntryForTesting(
+          i, disk_cache::EntryMetadata(start + base::TimeDelta::FromSeconds(i),

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

nit: maybe do a sha1(i) to make the keys look more realistic? the hashmap has
its own hashing, which may play differently performance-wise with sequential
numbers than with seemingly random hashes we have.

Does not seem like worth complication though, fyi and up to you.

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

Yeah, I think I'll pass, since I trust unordered_map more than I trust myself
not to forget to indirect via keys[] somewhere....

+                                       0u));
+      index.UpdateEntrySize(i, 1u);

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

I think it would be less error prone to make InsertEntryForTesting to update
index.cache_size_ from the size of the entry.

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

Done. Also added a DCHECK to require entry to not be there, since the behavior
is weird otherwise, and making it right seems more code than this is worth.

+    }
+
+    // Trigger an eviction.
+    base::ElapsedTimer timer;
+    index.SetMaxSize(kEntries);
+    index.UpdateEntrySize(0, 1u);
+    evict_elapsed_ms += timer.Elapsed().InMillisecondsF();
+  }
+
+  LOG(ERROR) << "Average time to evict:" << (evict_elapsed_ms / iterations)
+             << "ms";
+}
+
 }  // namespace