[Boost-bugs] [Boost C++ Libraries] #9839: Improve flat_containers performance during insertion phases

Subject: [Boost-bugs] [Boost C++ Libraries] #9839: Improve flat_containers performance during insertion phases
From: Boost C++ Libraries (noreply_at_[hidden])
Date: 2014-04-05 18:08:52

#9839: Improve flat_containers performance during insertion phases
-------------------------------------+--------------------------
 Reporter:  gonzalobg88@…            |      Owner:  igaztanaga
     Type:  Feature Requests         |     Status:  new
Milestone:  To Be Determined         |  Component:  container
  Version:  Boost Development Trunk  |   Severity:  Optimization
 Keywords:                           |
-------------------------------------+--------------------------
 The problem:

 A lot of applications have "look-up" phases and "insertion" phases. In
 each phase, lots of lookups/insertions take place. However, inserting
 elements into a flat_ container is slow.

 The current way to do this is: copy data out, insert, sort, unique, copy
 data back in (using the constructor that takes a sorted_uniqued_range).
 This requires two times the memory necessary, and performs two unnecessary
 O(N) traversals (the two copies).

 In the mailing list this issue was discussed [0], but no action was taken.

 The solutions:

 Proposal 1) Allow push_back_unsorted + sort
 Proposal 2) Allow underlying vector to be moved
 out/push_back/sort/unique/move back in/assert its good in debug mode

 I prefer Proposal 2) since I think is safer, so I'll elaborate on it.

 I propose two expand the interface of flat_containers with the following
 two methods:
   - Data&& retrieve_data();
   - void adquire_data(Data&& d);

 retrieve_data moves the underlying vector container out of the
 flat_container, makes the flat_container an empty container (s.t. it
 remains valid, are invariants are fine).

 adquire_data copies/moves a vector container of the same type as the one
 used by flat_containers, it assert in debug mode only that the container
 is sorted (and uniqued if necessary), and sets all container invariants to
 match the new data.

 IMO the underlying vector type should be configurable, but that is a
 different topic.

 [0] google: Containers-Should-flat-expose-implementation-vector-td3722533,
 trac doesn't like links :(

-- 
Ticket URL: <https://svn.boost.org/trac/boost/ticket/9839>
Boost C++ Libraries <http://www.boost.org/>
Boost provides free peer-reviewed portable C++ source libraries.