Reduce the memory usage of bookmarks storage

components/bookmarks/browser/titled_url_index.h

 // Copyright 2014 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.
 
 #ifndef COMPONENTS_BOOKMARKS_BROWSER_TITLED_URL_INDEX_H_
 #define COMPONENTS_BOOKMARKS_BROWSER_TITLED_URL_INDEX_H_
 
 #include <stddef.h>
 
 #include <map>
-#include <set>
 #include <string>
 #include <vector>
 
+#include "base/containers/flat_set.h"
 #include "base/macros.h"
 #include "base/strings/string16.h"
 #include "components/query_parser/query_parser.h"
 
 namespace bookmarks {
 
 class TitledUrlNode;
 class TitledUrlNodeSorter;
 struct TitledUrlMatch;
 
@@ skipping 18 matching lines @@
 
   // Returns up to |max_count| of matches containing each term from the text
   // |query| in either the title or the URL.
   void GetResultsMatching(const base::string16& query,
                           size_t max_count,
                           query_parser::MatchingAlgorithm matching_algorithm,
                           std::vector<TitledUrlMatch>* results);
 
  private:
   using TitledUrlNodes = std::vector<const TitledUrlNode*>;
-  using TitledUrlNodeSet = std::set<const TitledUrlNode*>;
+  using TitledUrlNodeSet = base::flat_set<const TitledUrlNode*>;

[sky, 2017/05/12 20:00:13]

I'm worried about using flat_set here as there is no guarantee that the set is
small. I think they generally are, but that isn't always the case. Do you have
data backing up they *always* are small enough?

[ssid, 2017/05/25 00:27:27]

The flat_set uses a std::vector as backing type. So, it must be always smaller
than using a tree data structure in the case of std::set. The tree uses a lot
more overhead in each node whereas vector directly stores only the pointers. In
the case I observe the memory overhead of std::set<void*> is 20% payload and 80%
overhead.
I checked the memory usage patterns with multiple insertion sizes from 10-100000
(random elements) and in all cases the flat_map allocates 4 times lesser memory
than std::set.
The performance of insertion regressed by 6ms for the case of 10000 insertions
and 500ms for the case of 100,000 insertions. The number of people with so many
bookmarks is <0.01%

[sky, 2017/05/25 02:54:02]

My question is that the data populating these sets comes from user data. How do
you know it is going to be small(ish)? flat_set is best used for small data
sets.

[ssid, 2017/05/26 01:45:40]

The uma for the number of bookmarks used:
https://uma.googleplex.com/p/chrome/histograms/?endDate=20170524&dayCount=1&h...

Shows that user at 99th percentile uses 1000 bookmarks and 0.01% of the
population uses more than 12K bookmarks. We do not regress the performance for
these users.
Median user uses 9 bookmarks.

   using Index = std::map<base::string16, TitledUrlNodeSet>;
 
   // Constructs |sorted_nodes| by copying the matches in |matches| and sorting
   // them.
   void SortMatches(const TitledUrlNodeSet& matches,
                    TitledUrlNodes* sorted_nodes) const;
 
   // Add |node| to |results| if the node matches the query.
   void AddMatchToResults(const TitledUrlNode* node,
                          query_parser::QueryParser* parser,
@@ skipping 21 matching lines @@
   Index index_;
 
   std::unique_ptr<TitledUrlNodeSorter> sorter_;
 
   DISALLOW_COPY_AND_ASSIGN(TitledUrlIndex);
 };
 
 }  // namespace bookmarks
 
 #endif  // COMPONENTS_BOOKMARKS_BROWSER_TITLED_URL_INDEX_H_