Speed up SimpleCache eviction set computation

net/disk_cache/disk_cache_perftest.cc

 // Copyright (c) 2011 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 <limits>
 #include <string>
 
 #include "base/bind.h"
 #include "base/bind_helpers.h"
 #include "base/files/file_enumerator.h"
 #include "base/files/file_path.h"
 #include "base/hash.h"
 #include "base/process/process_metrics.h"
 #include "base/rand_util.h"
 #include "base/run_loop.h"
 #include "base/strings/string_util.h"
 #include "base/test/perf_time_logger.h"
 #include "base/test/test_file_util.h"
 #include "base/threading/thread.h"
 #include "net/base/cache_type.h"
 #include "net/base/io_buffer.h"
 #include "net/base/net_errors.h"
 #include "net/base/test_completion_callback.h"
 #include "net/disk_cache/blockfile/backend_impl.h"
 #include "net/disk_cache/blockfile/block_files.h"
 #include "net/disk_cache/disk_cache.h"
 #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"
 
 using base::Time;
 
 namespace {
 
 size_t MaybeGetMaxFds() {
 #if defined(OS_POSIX)
   return base::GetMaxFds();
@@ skipping 258 matching lines @@
 
     files.DeleteBlock(address[entry], false);
     EXPECT_TRUE(
         files.CreateBlock(disk_cache::RANKINGS, block_size, &address[entry]));
   }
 
   timer2.Done();
   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