Reduce the memory usage of bookmarks storage

components/bookmarks/browser/titled_url_index.h

Index: components/bookmarks/browser/titled_url_index.h
diff --git a/components/bookmarks/browser/titled_url_index.h b/components/bookmarks/browser/titled_url_index.h
index d6a0fbae8d33b6e3397103b6428422c9014d7b60..f6df5980d2e8a592f297c5bd71971f697f625d60 100644
--- a/components/bookmarks/browser/titled_url_index.h
+++ b/components/bookmarks/browser/titled_url_index.h
@@ -8,10 +8,10 @@
 #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"
@@ -50,7 +50,7 @@ class TitledUrlIndex {
 
  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