Index initialization improvements for Simple Cache.

The Simple Cache index initialization path was making far too
many allocations, which caused an unneeded early peak in the
heap during index initialization. By reserving memory for
table resizes and making merges from small sets into big sets,
this peak is cut significantly.

R=pliard,ttuttle
BUG=None

Review URL: https://chromiumcodereview.appspot.com/22406005

git-svn-id: svn://svn.chromium.org/chrome/trunk/src@216941 0039d316-1c4b-4281-b951-d872f2087c98

4 files changed, 37 insertions, 17 deletions

diff --git a/net/disk_cache/simple/simple_index.cc b/net/disk_cache/simple/simple_index.cc
index caec19f60..78ce87e 100644
--- a/net/disk_cache/simple/simple_index.cc
+++ b/net/disk_cache/simple/simple_index.cc
@@ -359,18 +359,24 @@ void SimpleIndex::MergeInitializingSet(
     index_file_entries->erase(*it);
   }
 
-  // Recalculate the cache size while merging the two sets.
-  for (EntrySet::const_iterator it = index_file_entries->begin();
+  for (EntrySet::const_iterator it = entries_set_.begin();
+       it != entries_set_.end(); ++it) {
+    const uint64 entry_hash = it->first;
+    std::pair<EntrySet::iterator, bool> insert_result =
+        index_file_entries->insert(EntrySet::value_type(entry_hash,
+                                                        EntryMetadata()));
+    EntrySet::iterator& possibly_inserted_entry = insert_result.first;
+    possibly_inserted_entry->second = it->second;
+  }
+
+  uint64 merged_cache_size = 0;
+  for (EntrySet::iterator it = index_file_entries->begin();
        it != index_file_entries->end(); ++it) {
-    // If there is already an entry in the current entries_set_, we need to
-    // merge the new data there with the data loaded in the initialization.
-    EntrySet::iterator current_entry = entries_set_.find(it->first);
-    // When Merging, existing data in the |current_entry| will prevail.
-    if (current_entry == entries_set_.end()) {
-      InsertInEntrySet(it->first, it->second, &entries_set_);
-      cache_size_ += it->second.GetEntrySize();
-    }
+    merged_cache_size += it->second.GetEntrySize();
   }
+
+  entries_set_.swap(*index_file_entries);
+  cache_size_ = merged_cache_size;
   initialized_ = true;
   removed_entries_.clear();
 
diff --git a/net/disk_cache/simple/simple_index_file.cc b/net/disk_cache/simple/simple_index_file.cc
index 596b816..7bcea7c 100644
--- a/net/disk_cache/simple/simple_index_file.cc
+++ b/net/disk_cache/simple/simple_index_file.cc
@@ -8,6 +8,7 @@
 
 #include "base/file_util.h"
 #include "base/files/file_enumerator.h"
+#include "base/files/memory_mapped_file.h"
 #include "base/hash.h"
 #include "base/logging.h"
 #include "base/metrics/histogram.h"
@@ -254,14 +255,16 @@ void SimpleIndexFile::SyncLoadFromDisk(const base::FilePath& index_filename,
                                        SimpleIndexLoadResult* out_result) {
   out_result->Reset();
 
-  std::string contents;
-  if (!file_util::ReadFileToString(index_filename, &contents)) {
-    LOG(WARNING) << "Could not read Simple Index file.";
+  base::MemoryMappedFile index_file_map;
+  if (!index_file_map.Initialize(index_filename)) {
+    LOG(WARNING) << "Could not map Simple Index file.";
     base::DeleteFile(index_filename, false);
     return;
   }
 
-  SimpleIndexFile::Deserialize(contents.data(), contents.size(), out_result);
+  SimpleIndexFile::Deserialize(
+      reinterpret_cast<const char*>(index_file_map.data()),
+      index_file_map.length(), out_result);
 
   if (!out_result->did_load)
     base::DeleteFile(index_filename, false);
@@ -322,6 +325,10 @@ void SimpleIndexFile::Deserialize(const char* data, int data_len,
     return;
   }
 
+#if !defined(OS_WIN)
+  // TODO(gavinp): Consider using std::unordered_map.
+  entries->resize(index_metadata.GetNumberOfEntries() + kExtraSizeForMerge);
+#endif
   while (entries->size() < index_metadata.GetNumberOfEntries()) {
     uint64 hash_key;
     EntryMetadata entry_metadata;
diff --git a/net/disk_cache/simple/simple_index_file.h b/net/disk_cache/simple/simple_index_file.h
index 8a96a72..b536df9 100644
--- a/net/disk_cache/simple/simple_index_file.h
+++ b/net/disk_cache/simple/simple_index_file.h
@@ -97,6 +97,10 @@ class NET_EXPORT_PRIVATE SimpleIndexFile {
  private:
   friend class WrappedSimpleIndexFile;
 
+  // When loading the entries from disk, add this many extra hash buckets to
+  // prevent reallocation on the IO thread when merging in new live entries.
+  static const int kExtraSizeForMerge = 512;
+
   // Synchronous (IO performing) implementation of LoadIndexEntries.
   static void SyncLoadIndexEntries(base::Time cache_last_modified,
                                    const base::FilePath& cache_directory,
diff --git a/net/disk_cache/simple/simple_index_unittest.cc b/net/disk_cache/simple/simple_index_unittest.cc
index cfc83b3..0c845b2 100644
--- a/net/disk_cache/simple/simple_index_unittest.cc
+++ b/net/disk_cache/simple/simple_index_unittest.cc
@@ -197,12 +197,15 @@ TEST_F(SimpleIndexTest, IndexSizeCorrectOnMerge) {
   {
     scoped_ptr<SimpleIndexLoadResult> result(new SimpleIndexLoadResult());
     result->did_load = true;
-    const uint64 hash_key = simple_util::GetEntryHashKey("eleven");
+    const uint64 new_hash_key = simple_util::GetEntryHashKey("eleven");
     result->entries.insert(
-        std::make_pair(hash_key, EntryMetadata(base::Time::Now(), 11)));
+        std::make_pair(new_hash_key, EntryMetadata(base::Time::Now(), 11)));
+    const uint64 redundant_hash_key = simple_util::GetEntryHashKey("seven");
+    result->entries.insert(std::make_pair(redundant_hash_key,
+                                          EntryMetadata(base::Time::Now(), 7)));
     index()->MergeInitializingSet(result.Pass());
   }
-  EXPECT_EQ(25U, index()->cache_size_);
+  EXPECT_EQ(2U + 5U + 7U + 11U, index()->cache_size_);
 }
 
 // State of index changes as expected with an insert and a remove.