Replace uses of hash_map in //base

base/id_map.h

Index: base/id_map.h
diff --git a/base/id_map.h b/base/id_map.h
index d171fb14c102cefc5b5ec332315e8a7303f86b9c..e6622c82737121cd30cc351870fe34e306fec001 100644
--- a/base/id_map.h
+++ b/base/id_map.h
@@ -7,12 +7,14 @@
 
 #include <stddef.h>
 #include <stdint.h>
+#include <map>
 #include <memory>
 #include <set>
 #include <type_traits>
+#include <unordered_map>
 #include <utility>
 
-#include "base/containers/hash_tables.h"
+#include "base/containers/flat_set.h"
 #include "base/logging.h"
 #include "base/macros.h"
 #include "base/sequence_checker.h"
@@ -35,7 +37,10 @@ class IDMap final {
 
  private:
   using T = typename std::remove_reference<decltype(*V())>::type;
-  using HashTable = base::hash_map<KeyType, V>;
+
+  // Requires stable iterators so flat_map and small_map can't be used.
+  // unordered_map is not used due to high memory overhead for small containers.
+  using HashTable = std::unordered_map<KeyType, V>;

[Łukasz Anforowicz, 2017/04/24 18:46:10]

The declaration on previous line (using |std::unordered_map|) seems in conflict
with the preceding comment (saying |unordered_map is not used|).  Did you mean
to say |std::map| in the comment?

Also - once the above is straightened out, it seems weird that we need to add an
#include for both <map> and <unordered_map>, when we only add a reference to
*one* of these types.


Actually, could you please help me understand the requirement for "stable
iterators"?  AFAICT base::IdMap won't mutate |data_| while there are still some
iterators out there, so I don't understand why HashTable = base::small_map
couldn't be used here.  (and if the explanation/example are small, then maybe
they can be put into a comment above for the benefit of future
readers/maintainers?)

[brettw, 2017/04/25 23:32:36]

I misunderstood the implementation and stable iterators aren't required. I
removed the comment, thanks for noticing.

[Łukasz Anforowicz, 2017/04/25 23:49:01]

Thanks.  I see that the CL switches |removed_ids_| from being a |set::set| to
being a |base::flat_set|.  I wonder if a similar change (into
|base::small_map|?) might be beneficial also for |data_| (since a comment for
IDMap says that it is "optimized for relatively small data sets").

This is totally optional - I understand that it is probably safest to just
replace base::hash_map with std::unordered_map (the change should be a no-op
since base::hash_map is a typedef for std::unordered_map).  OTOH, if the CL
already modifies |removed_ids_|, then maybe it is also worth it to look into
modifying |data_|.

Hmmm.... thinking about it a bit more, I think we should just land the CL under
review as-is (and maybe consider what I wrote above in a separate CL).  Smaller
CLs = better (e.g. easier to attribute a perf regression [if any] to a smaller
CL).

[brettw, 2017/04/26 20:51:57]

IDMap is a template used in a bunch of places for things like IPC message
routing. I didn't want to mess with the performance of that, and I was also
concerned about code bloat from small_map. For the removed_ids, it's much easier
to understand the impact since it's used only for removals while iterating
through the map.

 
  public:
   IDMap() : iteration_depth_(0), next_id_(1), check_on_null_data_(false) {
@@ -236,7 +241,7 @@ class IDMap final {
   // Keep set of IDs that should be removed after the outermost iteration has
   // finished. This way we manage to not invalidate the iterator when an element
   // is removed.
-  std::set<KeyType> removed_ids_;
+  base::flat_set<KeyType> removed_ids_;

[Łukasz Anforowicz, 2017/04/24 18:46:10]

nit: I wonder if you could please expand the CL description and spell out what
"more appropriate types are" - this would have helped me more quickly understand
the change above.  For example:

"""
Some uses were replaced with more appropriate variants (e.g. base::flat_map or
base::small_map rather than std::unordered_map).
"""

 
   // The next ID that we will return from Add()
   KeyType next_id_;