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 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
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 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 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 void
merge(concurrent_unordered_map &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/
