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..e3d3e7adaa0847e0c42a1c0f84205a37c6829a0c 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"
 
@@ -306,3 +308,33 @@ TEST_F(DiskCachePerfTest, BlockFilesPerformance) {
 }
 
 }  // namespace
+
+namespace disk_cache {
+
+// Measures how quickly SimpleIndex can compute which entries to evict.
+TEST(SimpleIndexPerfTest, EvictionPerformance) {
+  class NoOpDelegate : public disk_cache::SimpleIndexDelegate {
+    void DoomEntries(std::vector<uint64_t>* entry_hashes,
+                     const net::CompletionCallback& callback) override {}
+  };
+
+  NoOpDelegate delegate;
+  disk_cache::SimpleIndex index(nullptr, &delegate, net::DISK_CACHE, nullptr);
+
+  base::ElapsedTimer timer;
+  const int kEntries = 25000;
+  base::Time now(base::Time::Now());
+  index.SetMaxSize(kEntries);
+
+  for (int i = 0; i < kEntries; ++i) {
+    disk_cache::SimpleIndex::InsertInEntrySet(
+        i, disk_cache::EntryMetadata(now + base::TimeDelta::FromSeconds(i), 0u),
+        &index.entries_set_);
+    // Will trigger eviction once we are nearly full.
+    index.UpdateEntrySize(i, 1u);
+  }
+
+  LOG(ERROR) << "Took:" << timer.Elapsed().InMillisecondsF() << "ms";

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

How stable are the numbers produced?

I think it is easy to create a significantly better benchmark that would avoid
disadvantages of:

1. timing insertions together with evictions

2. being susceptible to noise from brief background activities on the machine
running the benchmark

The usual recommendation in such cases is to repeat the workload in a tight loop
to run for 10-20 seconds and then divide by the amount of operations (the amount
of iterations is constant in code chosen for some random powerful machine).

So I'm imagining an iteration to be like:
1. insert a bunch
2. start timer
3. make series of evicts by gradually shrinking with SetMaxSize+UpdateEntrySize
4. stop timer

we may not need numerous iterations if the number of entries is sufficiently
large, but I guess the number would be more realistic id we get 'typical' order
of magnitude amount of entries, and repeat evictions on those if one such shrink
is too short.

WDYT?

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

Less stable now that you've asked about it :) (usually was in about 0.1-0.2ms
range, but sometimes spiked)... and at any rate your suggestion produced numbers
that vary in single digit amount of microseconds or so.
That turned out a bigger deal than I thought, looks like insertions actually
dominated post-this-CL.

Bottom-line numbers after revised benchmark (and with smaller # of entries than
before):
4.82ms -> 0.33ms on a my Linux workstation. (Will get the test Windows laptop
numbers as follow up, need to upload the change first)
Anyway, did something similar. Any reason for constant iterations rather than
constant time?
Hmm, didn't think of shrinking the size, that's a nice way of avoiding mixed
timing. Why multiple evicts, though?
Yeah, don't want to increase the # of entries too much since the algorithm is
super-linear. Actually with these changes, I think I'll go to 10K since it's
more realistic.

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

Reasons I can see:
1. with const iterations there is less code
2. checking for time between iterations may be slow on some systems (Android/ARM
is one of them)
3. may affect CPU caches

The disadvantage of const iterations is that hypothetically at some point you
get a fast machine and in the world of standardized benchmarks this presents a
problem, but we can "re-standardize" this benchmark at almost no time.
I thought it's nice because it reduces the amount of preparation work to be done
before the timed part of the benchmark, hence the overall testing will take less
time. Also covers eviction of different sizes in some way (but this latter may
also confuse the interpretation of the number - less sure).

+}
+
+}  // namespace disk_cache