Replace uses of hash_map in //base

base/id_map.h

 // 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.
 
 #ifndef BASE_ID_MAP_H_
 #define BASE_ID_MAP_H_
 
 #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"
 
 // This object maintains a list of IDs that can be quickly converted to
 // pointers to objects. It is implemented as a hash table, optimized for
 // relatively small data sets (in the common case, there will be exactly one
 // item in the list).
 //
 // Items can be inserted into the container with arbitrary ID, but the caller
 // must ensure they are unique. Inserting IDs and relying on automatically
 // generated ones is not allowed because they can collide.
 
 // The map's value type (the V param) can be any dereferenceable type, such as a
 // raw pointer or smart pointer
 template <typename V, typename K = int32_t>
 class IDMap final {
  public:
   using KeyType = K;
 
  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) {
     // A number of consumers of IDMap create it on one thread but always
     // access it from a different, but consistent, thread (or sequence)
     // post-construction. The first call to CalledOnValidSequence() will re-bind
     // it.
     sequence_checker_.DetachFromSequence();
   }
 
@@ skipping 180 matching lines @@
     removed_ids_.clear();
   }
 
   // Keep track of how many iterators are currently iterating on us to safely
   // handle removing items during iteration.
   int iteration_depth_;
 
   // 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_;
 
   HashTable data_;
 
   // See description above setter.
   bool check_on_null_data_;
 
   base::SequenceChecker sequence_checker_;
 
   DISALLOW_COPY_AND_ASSIGN(IDMap);
 };
 
 #endif  // BASE_ID_MAP_H_