Add range insertion for base::flat_tree

base/containers/flat_tree.h

 // Copyright 2017 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_CONTAINERS_FLAT_TREE_H_
 #define BASE_CONTAINERS_FLAT_TREE_H_
 
 #include <algorithm>
+#include <iterator>
 #include <vector>
 
 namespace base {
 
 enum FlatContainerDupes {
   KEEP_FIRST_OF_DUPES,
   KEEP_LAST_OF_DUPES,
 };
 
 namespace internal {
@@ skipping 161 matching lines @@
   const_reverse_iterator crbegin() const;
 
   reverse_iterator rend();
   const_reverse_iterator rend() const;
   const_reverse_iterator crend() const;
 
   // --------------------------------------------------------------------------
   // Insert operations.
   //
   // Assume that every operation invalidates iterators and references.
-  // Insertion of one element can take O(size). See the Notes section in the
-  // class comments on why we do not currently implement range insertion.
-  // Capacity of flat_tree grows in an implementation-defined manner.
+  // Insertion of one element can take O(size). Capacity of flat_tree grows in
+  // an implementation-defined manner.
   //
   // NOTE: Prefer to build a new flat_tree from a std::vector (or similar)
   // instead of calling insert() repeatedly.
 
   std::pair<iterator, bool> insert(const value_type& val);
   std::pair<iterator, bool> insert(value_type&& val);
 
   iterator insert(const_iterator position_hint, const value_type& x);
   iterator insert(const_iterator position_hint, value_type&& x);
 
+  template <class InputIterator>
+  void insert(InputIterator first,

[brettw, 2017/05/10 16:52:06]

Can you add a comment here about FlatContainerDupes applying to both the
existing and inserted items (i.e. it overwrites on "LAST").

[jdoerrie, 2017/05/11 06:34:57]

Done.

+              InputIterator last,
+              FlatContainerDupes dupes);
+
   template <class... Args>
   std::pair<iterator, bool> emplace(Args&&... args);
 
   template <class... Args>
   iterator emplace_hint(const_iterator position_hint, Args&&... args);
 
   // --------------------------------------------------------------------------
   // Erase operations.
   //
   // Assume that every operation invalidates iterators and references.
@@ skipping 96 matching lines @@
     const key_compare& key_comp_;
   };
 
   const flat_tree& as_const() { return *this; }
 
   iterator const_cast_it(const_iterator c_it) {
     auto distance = std::distance(cbegin(), c_it);
     return std::next(begin(), distance);
   }
 
-  void sort_and_unique(FlatContainerDupes dupes) {
+  void sort_and_unique(iterator first,
+                       iterator last,
+                       FlatContainerDupes dupes) {
     // Preserve stability for the unique code below.
-    std::stable_sort(begin(), end(), impl_.get_value_comp());
+    std::stable_sort(first, last, impl_.get_value_comp());
 
     auto comparator = [this](const value_type& lhs, const value_type& rhs) {
       // lhs is already <= rhs due to sort, therefore
       // !(lhs < rhs) <=> lhs == rhs.
       return !impl_.get_value_comp()(lhs, rhs);
     };
 
     iterator erase_after;
     switch (dupes) {
       case KEEP_FIRST_OF_DUPES:
-        erase_after = std::unique(begin(), end(), comparator);
+        erase_after = std::unique(first, last, comparator);
         break;
       case KEEP_LAST_OF_DUPES:
-        erase_after = LastUnique(begin(), end(), comparator);
+        erase_after = LastUnique(first, last, comparator);
         break;
     }
-    erase(erase_after, end());
+    erase(erase_after, last);
   }
 
   // To support comparators that may not be possible to default-construct, we
   // have to store an instance of Compare. Using this to store all internal
   // state of flat_tree and using private inheritance to store compare lets us
   // take advantage of an empty base class optimization to avoid extra space in
   // the common case when Compare has no state.
   struct Impl : private value_compare {
     Impl() = default;
 
@@ skipping 21 matching lines @@
     : impl_(comp) {}
 
 template <class Key, class Value, class GetKeyFromValue, class KeyCompare>
 template <class InputIterator>
 flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::flat_tree(
     InputIterator first,
     InputIterator last,
     FlatContainerDupes dupe_handling,
     const KeyCompare& comp)
     : impl_(comp, first, last) {
-  sort_and_unique(dupe_handling);
+  sort_and_unique(begin(), end(), dupe_handling);
 }
 
 template <class Key, class Value, class GetKeyFromValue, class KeyCompare>
 flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::flat_tree(
     const flat_tree&) = default;
 
 template <class Key, class Value, class GetKeyFromValue, class KeyCompare>
 flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::flat_tree(flat_tree&&) =
     default;
 
 template <class Key, class Value, class GetKeyFromValue, class KeyCompare>
 flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::flat_tree(
     std::vector<value_type> items,
     FlatContainerDupes dupe_handling,
     const KeyCompare& comp)
     : impl_(comp, std::move(items)) {
-  sort_and_unique(dupe_handling);
+  sort_and_unique(begin(), end(), dupe_handling);
 }
 
 template <class Key, class Value, class GetKeyFromValue, class KeyCompare>
 flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::flat_tree(
     std::initializer_list<value_type> ilist,
     FlatContainerDupes dupe_handling,
     const KeyCompare& comp)
     : flat_tree(std::begin(ilist), std::end(ilist), dupe_handling, comp) {}
 
 template <class Key, class Value, class GetKeyFromValue, class KeyCompare>
 flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::~flat_tree() = default;
 
 // ----------------------------------------------------------------------------
 // Assignments.
 
 template <class Key, class Value, class GetKeyFromValue, class KeyCompare>
 auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::operator=(
     const flat_tree&) -> flat_tree& = default;
 
 template <class Key, class Value, class GetKeyFromValue, class KeyCompare>
 auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::operator=(flat_tree &&)
     -> flat_tree& = default;
 
 template <class Key, class Value, class GetKeyFromValue, class KeyCompare>
 auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::operator=(
     std::initializer_list<value_type> ilist) -> flat_tree& {
   impl_.body_ = ilist;
-  sort_and_unique(KEEP_FIRST_OF_DUPES);
+  sort_and_unique(begin(), end(), KEEP_FIRST_OF_DUPES);
   return *this;
 }
 
 // ----------------------------------------------------------------------------
 // Memory management.
 
 template <class Key, class Value, class GetKeyFromValue, class KeyCompare>
 void flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::reserve(
     size_type new_capacity) {
   impl_.body_.reserve(new_capacity);
@@ skipping 160 matching lines @@
   if (position_hint == end() || impl_.get_value_comp()(val, *position_hint)) {
     if (position_hint == begin() ||
         impl_.get_value_comp()(*(position_hint - 1), val))
       // We have to cast away const because of crbug.com/677044.
       return impl_.body_.insert(const_cast_it(position_hint), std::move(val));
   }
   return insert(std::move(val)).first;
 }
 
 template <class Key, class Value, class GetKeyFromValue, class KeyCompare>
+template <class InputIterator>
+auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::insert(
+    InputIterator first,
+    InputIterator last,
+    FlatContainerDupes dupes) -> void {
+  // Initialize the first insertion point and provide a convenience lambda to
+  // obtain an iterator pointing past the old element. This needs to be dymanic
+  // due to possible re-allocations.
+  difference_type pos_first_new = std::distance(begin(), end());

[dyaroshev, 2017/05/10 17:12:09]

Nit:
Just say size()? Or are there problems with difference_type/size_type
conversions?
I would use two different variables for pos_first_new and original_size, it's
slightly confusing this way.

(Do not insist).

[jdoerrie, 2017/05/11 06:34:57]

Done both now. There usually is a difference, difference_type is commonly
ptrdiff_t, while size_type is size_t. However, I don't think there should be
issues initializing one with the other.

+  auto middle = [this, pos_first_new]() {
+    return std::next(begin(), pos_first_new);
+  };

[dyaroshev, 2017/05/10 17:12:09]

How do you feel about reserve if we can compute distance?
Folly does it.

You can do it with an if, by the way, if you want to:
if (std::is_same<typename
std::iterator_traits<InputIterator>::iterator_category,
                 std::random_access_iterator_tag>::value)
  reserve(std::distance(first, last));

[jdoerrie, 2017/05/11 06:34:57]

I don't like using reserve, because it can lead to very bad performance when
this method is called in a loop. Commonly reserve(n) only allocates space for
exactly n elements, causing a reallocation every single time. This leads to
quadratic performance as the benchmark shows:

Number of Items: 16384      Method: With Reserve= 163415 us
Number of Items: 16384      Method: Without Reserve= 2556 us

Number of Items: 32768      Method: With Reserve= 654739 us
Number of Items: 32768      Method: Without Reserve= 4798 us

Number of Items: 65536      Method: With Reserve= 2017561 us
Number of Items: 65536      Method: Without Reserve= 9691 us

Number of Items: 131072     Method: With Reserve= 8027410 us
Number of Items: 131072     Method: Without Reserve= 18062 us

Number of Items: 262144     Method: With Reserve= 32167225 us
Number of Items: 262144     Method: Without Reserve= 32479 us

We could fix this by doing reserve(std::max(size() + last - first, growth_factor
* size()), but I don't like the idea of defining a growth factor ourself and
messing with what standard library implementations intended.

However, I do like your idea of checking for multipass iterators in order to
optimize for insertions of one element. With the introduction of dupes we cannot
simply dispatch to insert(val) anymore, but we can provide a simplified
implementation for this case. Here are the benchmarks for it:

Number of Items: 1048576    Method: One By One      =  43246 us
Number of Items: 1048576    Method: Special Case    =  38016 us
Number of Items: 1048576    Method: No Special Case = 159393 us

Number of Items: 2097152    Method: One By One      =  95512 us
Number of Items: 2097152    Method: Special Case    =  80637 us
Number of Items: 2097152    Method: No Special Case = 306446 us

Number of Items: 4194304    Method: One By One      = 204112 us
Number of Items: 4194304    Method: Special Case    = 167022 us
Number of Items: 4194304    Method: No Special Case = 488665 us

Number of Items: 8388608    Method: One By One      = 309807 us
Number of Items: 8388608    Method: Special Case    = 265266 us
Number of Items: 8388608    Method: No Special Case = 990554 us

Number of Items: 16777216   Method: One By One      = 645032 us
Number of Items: 16777216   Method: Special Case    = 570092 us
Number of Items: 16777216   Method: No Special Case = 2005552 us

Number of Items: 33554432   Method: One By One      = 1355454 us
Number of Items: 33554432   Method: Special Case    = 1177451 us
Number of Items: 33554432   Method: No Special Case = 4051799 us

Doing the special case is 3 - 4x faster and can even out perform one-by-one,
therefore I added this now in this patch set.

[dyaroshev, 2017/05/11 09:46:43]

That's a good point.

+
+  for (; first != last; ++first) {
+    iterator lower = std::lower_bound(begin(), middle(), *first, value_comp());
+    if (lower == middle() || value_comp()(*first, *lower)) {
+      // Insert completely new elements at the back.
+      pos_first_new = std::min(pos_first_new, std::distance(begin(), lower));
+      impl_.body_.push_back(*first);
+    } else if (lower != middle() && dupes == KEEP_LAST_OF_DUPES) {

[dyaroshev, 2017/05/10 17:12:09]

1 - The check for (dupes == KEEP_LAST_OF_DUPES) should not be inside a loop.
2 - Maybe factor this piece out (I do not insist)

[jdoerrie, 2017/05/11 06:34:57]

Done.

+      // Only overwrite existing elements in case of KEEP_LAST_OF_DUPES.
+      *lower = *first;
+    }
+  }
+
+  // The new elements might be unordered and contain duplicates, so post-process
+  // the just inserted elements and merge them with the rest, inserting them at
+  // the previously found spot.
+  sort_and_unique(middle(), end(), dupes);
+  std::inplace_merge(std::next(begin(), pos_first_new), middle(), end(),
+                     value_comp());

[dyaroshev, 2017/05/10 17:12:09]

Have you measured? Are you closer now to inserting by one element?

[jdoerrie, 2017/05/11 06:34:57]

See above.

+}
+
+template <class Key, class Value, class GetKeyFromValue, class KeyCompare>
 template <class... Args>
 auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::emplace(Args&&... args)
     -> std::pair<iterator, bool> {
   return insert(value_type(std::forward<Args>(args)...));
 }
 
 template <class Key, class Value, class GetKeyFromValue, class KeyCompare>
 template <class... Args>
 auto flat_tree<Key, Value, GetKeyFromValue, KeyCompare>::emplace_hint(
     const_iterator position_hint,
@@ skipping 152 matching lines @@
 void EraseIf(base::internal::flat_tree<Key, Value, GetKeyFromValue, KeyCompare>&
                  container,
              Predicate pred) {
   container.erase(std::remove_if(container.begin(), container.end(), pred),
                   container.end());
 }
 
 }  // namespace base
 
 #endif  // BASE_CONTAINERS_FLAT_TREE_H_