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/

On 15 Aug 2014 at 21:38, Ion Gaztañaga wrote:

...

...

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:

I think we should implement the minimal functions in order to improve the proposal and add it to the standard when possible. Even in the original proposal, "node_ptr extract(const key_type& x);" seems redundant.

Why?

...

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

So why not call it unique_ptr ;-) The deleter type can be something like allocator_deleter<A>, which calls a.destroy() + a.deallocate() via allocator_traits. There are issues with allocator_traits::propagate_xxxx but maybe solvable. A new type with nearly the same interface and semantics as unique_ptr is something that sounds avoidable.

Allocators :( I personally choose to have no opinion on this, or rather I defer to the opinion of others more expert in this, but I can see where you're coming from. I would say though that a full unique_ptr lets external code do stuff like reset(newptr) which may or may not be wise. I also think that if you do go down this route, I am no longer sure if node_ptr_type should be a member type of each map class. Perhaps now a std::map_node_ptr<> used by all map STL containers makes more sense.

node_ptr_type is also a bit confusing, because it holds also an allocator. node_ptr_type sounds a a pointer (raw or smart) to the internal node type used by the container. Maybe node_holder is a bit more accurate.

My original implementation which duplicated the essence of N3645 before I knew about N3645 used "value_type_ptr". I still think that the best name - after all, we're not pointing to a node, it's actually a smart pointer to an allocated value_type not currently owned nor managed by a map.

...

* 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.

Thanks for the explanations, still don't see the need for too many operations, but I will start with basic operations and start thinking about your proposed extensions.

Most of my extensions are driven by the needs of a reliable latency concurrent_unordered_map. They are probably slightly overkill for something not as latency sensitive, equally they also do no harm. I do quite like the way that in the future one can convert a std::map into a std::unordered_map with very little overhead. BTW I personally have found my extensions let you collapse a lot of implementation into single reusable routines. For example, insert/emplace are simply a make_node_ptr followed by insert, and insert is simply an insert_ct followed by a storage expanding insert if it fails. It probably isn't ideal for performance, but it sure makes debugging and maintenance much easier. Niall -- ned Productions Limited Consulting http://www.nedproductions.biz/ http://ie.linkedin.com/in/nialldouglas/

On 17 Aug 2014 at 9:47, Ion Gaztañaga wrote:

...

...

I think we should implement the minimal functions in order to improve the proposal and add it to the standard when possible. Even in the original proposal, "node_ptr extract(const key_type& x);" seems redundant.

Why?

Isn't just a slightly modified "extract(find(k))"? The only difference that extract(it) is undefined when passing the end node. I don't know if having the extra check is important or the programmer should check find() != end() before using extract()

For a concurrent_unordered_map, extract(key) is rehash safe while extract(iterator) is not. Indeed, anything which uses an iterator is rehash unsafe, for obvious reasons. Niall -- ned Productions Limited Consulting http://www.nedproductions.biz/ http://ie.linkedin.com/in/nialldouglas/

On Sun, Aug 17, 2014 at 02:08:52PM +0200, Bjorn Reese wrote:

On 08/15/2014 08:22 PM, Niall Douglas wrote:

...

* 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.

The _ct suffix is a bit obscure (as in "I have no idea what it means.") Alternatively you could use a tag argument on an overloaded insert() to specify the memory-allocation policy.

After thinking way too hard for a bit, I'd reckon it stands for "constant time". I would not have deciphered it without the "low latency" and "no allocation" hints. -- Lars Viklund | zao@acc.umu.se

On 18/08/2014 22:47, Niall Douglas wrote:

On 17 Aug 2014 at 17:06, Lars Viklund wrote:

...

...

...

* 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.

The _ct suffix is a bit obscure (as in "I have no idea what it means.") Alternatively you could use a tag argument on an overloaded insert() to specify the memory-allocation policy.

After thinking way too hard for a bit, I'd reckon it stands for "constant time". I would not have deciphered it without the "low latency" and "no allocation" hints.

It does.

I like the idea of a noalloc_t tag, so insert(noalloc_t, node_ptr_type &&v). Thoughts?

Shouldn't tags traditionally be the final argument?

On August 19, 2014 7:39:44 AM EDT, Niall Douglas wrote:

On 19 Aug 2014 at 14:33, Gavin Lambert wrote:

...

...

...

After thinking way too hard for a bit, I'd reckon it stands for "constant time". I would not have deciphered it without the "low latency" and "no allocation" hints.

It does.

I like the idea of a noalloc_t tag, so insert(noalloc_t, node_ptr_type &&v). Thoughts?

Shouldn't tags traditionally be the final argument?

Pre-C++11 I would agree. However availability of variadic args makes putting tags at the end harder than at the start. For me personally in my own code, I would prefer all tags to go at the front rather than some at the start and some at the end.

Ok, I'm being lazy, but it saves productivity in having to write Args&&... filters just to put tags at the end.

I put non-const reference parameters (for "out" arguments) first because of defaults, so it's the same idea. Putting the tag first is a bit jarring at first, but I like your argument. ___ Rob (Sent from my portable computation engine)

On 08/19/2014 01:39 PM, Niall Douglas wrote:

On 19 Aug 2014 at 14:33, Gavin Lambert wrote:

...

...

I like the idea of a noalloc_t tag, so insert(noalloc_t, node_ptr_type &&v). Thoughts?

Shouldn't tags traditionally be the final argument?

Pre-C++11 I would agree. However availability of variadic args makes putting tags at the end harder than at the start. For me personally in my own code, I would prefer all tags to go at the front rather than some at the start and some at the end.

Ok, I'm being lazy, but it saves productivity in having to write Args&&... filters just to put tags at the end.

Unless you know of a better way?

Specifying the policy as the first argument seems rather natural given that we go from method_policy(...) to method(policy_t, ...).