Re: [boost] [Container] Provide more guarantees for flat_multimap

Subject: Re: [boost] [Container] Provide more guarantees for flat_multimap
From: Niall Douglas (s_sourceforge_at_[hidden])
Date: 2014-08-15 14:22:23

On 15 Aug 2014 at 19:02, Ion Gaztañaga wrote:

> El 15/08/2014 18:30, Niall Douglas escribió:
> > On 15 Aug 2014 at 0:28, Vinícius dos Santos Oliveira wrote:
> >
> >> Currently, flat_multimap mirrors C++98's multimap concept.
> >>
> >> I'd like to propose an update to flat_multimap fulfil the C++11's multimap
> >> concept.
> >
> > Can I persuade you to also implement the N3645
> > (http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2013/n3645.pdf)
> > extensions?
> 
> Sure. Open a trac ticket so it's not forgotten. No promise for Boost 
> 1.57, though.

Let me finish my concurrent_unordered_map which implements that 
superset of N3645 first.

> > If you're interested, they have become enhanced since, and I can tell
> > you those enhancements on request. However, the essence of the
> > extensions remains the same - they make maps much faster and lower
> > latency by letting you do node allocation outside of any mutex locks.
> 
> In which sense they have become enhanced?

I stress the following is still in flux, but it's getting close to 
final. The following changes were mostly agreed with Howard and 
Jonathan, and none of the other authors of N3645 objected:

* node_ptr_type gains the get(), release() and reset() member 
functions so it now looks identical to a std::unique_ptr.

* The following three new node_ptr_type factory functions are added:

1. template<class... Args> node_ptr_type make_node_ptr(Args&&... 
args);

This allocates a node_ptr_type using the container allocator.

2. template<class U> node_ptr_type rebind_node_ptr(typename 
U::node_ptr_type &&p);

This rebinds, with potential reallocation, a foreign node_ptr_type to 
this container's allocator. If the allocators are identical and the 
type is an rvalue ref, a simple move rebind of the pointer occurs, if 
they are not the same allocator or the type is not a rvalue ref, a 
new allocation and forward is performed.

This lets one move node_ptr_type instances between maps as 
efficiently as possible without needing to hold any mutexs.

3. template<class InputIterator> std::vector<node_ptr_type> 
make_node_ptrs(InputIterator start, InputIterator finish, value_type 
**to_use=nullptr);

This is an interesting one. This manufactures many node_ptr_types 
from the input iterator range, optionally using an externally 
supplied list of already allocated storage. This optionally lets you 
use batch/burst allocation to very substantially reduce amortised 
memory allocation overheads.

* The proposed insert_return_t insert(node_ptr_type v) becomes 
std::pair<iterator, bool> insert(node_ptr_type &&v) instead. We 
dispense with the insert_return_t type and the input rvalue ref is 
the same as on entry if the operation fails.

* A new std::pair<iterator, bool> insert_ct(node_ptr_type &&v) 
inserts only if no new memory would be allocated. This is highly 
valuable for low latency use.

* merge() is now of two forms:

1. template<class U> void merge(U &o) where U is any map providing a 
node_ptr_type. This is surprisingly trivial to implement actually 
thanks to rebind_node_ptr() above e.g.

      template<class U> void merge(U &o)
      {
        for(typename U::iterator it=o.begin(); it!=o.end(); 
it=o.begin())
        {
          typename U::node_ptr_type e=o.extract(it);
          insert(rebind_node_ptr(e));
        }
      }

2. template<class _Hash, class _Pred, class _Alloc> void 
merge(concurrent_unordered_map<Key, T, _Hash, _Pred, _Alloc> &o) is 
an optional local map container specialisation. It may offer stronger 
guarantees and performance than the generic template<class U> void 
merge(U &o).

I think that is more or less it. Obviously this is for code not fully 
tested yet, so gotchas and surprises may yet present.

Comments are welcome. My extensions may be poorly thought through.

Niall

-- 
ned Productions Limited Consulting
http://www.nedproductions.biz/ 
http://ie.linkedin.com/in/nialldouglas/