What do people think about std::multimap?

[Daniel]

Would you use it? Or would you more likely use std::map with a sequence
mapped_type?

Thanks,
Daniel

[Mr Flibble]

On 19/10/2016 23:30, Daniel wrote:
> Would you use it? Or would you more likely use std::map with a sequence
> mapped_type?

Of course people use it: std::multimap is just as useful as std::map. I
have no idea what you mean by "sequence mapped_type".

/Flibble

[Daniel]

Thanks for your comment.

All associative containers with template parameters Key,T, have a member type
called mapped_type that is defined as T. I was referring to an instance of
std::map where the mapped_type was a sequence container (e.g. std::vector)

Daniel

[Alf P. Steinbach]

He probably means a `map<Key, vector<Value>>` as a way to to the same as
`multimap<Key, Value>`.

One reasonable way to compare them could be to look at some typical
concrete usage examples, implemented with both approaches.

Then one could compare complexity, efficiency, code size, whatever.


Cheers & hth.,

- Alf

[Daniel]

On Wednesday, October 19, 2016 at 8:06:33 PM UTC-4, Alf P. Steinbach wrote:
>
> One reasonable way to compare them could be to look at some typical
> concrete usage examples, implemented with both approaches.
>

Yes, those, but also aesthetics. I've never actually seen std::multimap
used outside of examples. Perhaps I've been too cloistered.

Daniel

[Öö Tiib]

Note that your question is too abstract ... sort of "solution searches
for problem". ;)

Clarity. The 'std::multimap<X,Y>' is IMHO simpler data structure than
'std::map<X,std::vector<Y>>'. For clarity I would take it.

Performance. If it is "one to sometimes more than one
relation" then multimap likely wins, if it is "one to really
many relation" then map of vectors likely wins.

So unless I know that it is going to be one-to-numerous that it
represents I would take multimap.

[Jens Kallup]

You can use it for cross products in e.g database applications

[Marcel Mueller]

On 20.10.16 00.30, Daniel wrote:
> Would you use it? Or would you more likely use std::map with a sequence
> mapped_type?

It depends on how many values you intend to store per key. Creating a
container for every map element could be rather expensive if duplicate
keys are rare.
On the other side, if most keys have many values sequence scans for one
key could be more effective with distinct maps.
In doubt multimap is in most cases a better choice than a nested container.

The reason why I almost never use std::multimap neither std::map is that
they are implemented as Red Black Tree which is quite ineffective for
small key-value pairs due to the excessive allocation overhead. B-Trees
are by far more efficient in most use cases.
Unfortunately there is no B-Tree container in the C++ standard. So I end
up with my own implementation in almost any project sooner or later.


Marcel

[Mr Flibble]

The performance of map and multimap can often be improved significantly
by using a pool allocator such as the one Boost provides. You should
try using that rather than eschewing such standard workhorse containers.

/Leigh

[Marcel Mueller]

You just mentioned that the standard allocator is often also not that
efficient when dealing with many objects. Even if the algorithms and
containers used for data processing and storage are suitable the overall
application performance may scale unexpectedly bad when the number of
allocated objects is large. So using a more efficient allocator for
std::(multi)map is just a work around for a not well chosen container
type and does not really solve the problem at all. Furthermore nested
allocators may significantly increase memory fragmentation in case the
container is held for a longer time with less than its maximum size.

The fact that there is no B-Tree in the standard makes no difference. RB
trees are only a good choice if invalidation of iterators on container
changes are undesirable. In most other cases they are outperformed by a
B-Tree by far. Think also of cache efficiency when small objects are
distributed over the entire memory.


Marcel

[Daniel]

On Thursday, October 20, 2016 at 1:39:46 PM UTC-4, Mr Flibble wrote:
>
> The performance of map and multimap can often be improved significantly
> by using a pool allocator such as the one Boost provides.
>

Which boost allocator? In my experiments I've found the stateless
boost::fast_pool_allocator to be slower than std::allocator. Also with
boost::fast_pool_allocator there doesn't appear to be a way to free the underlying
memory pool until the process ends.

Daniel

[Mr Flibble]

I've found quite the opposite. Your experiments are obviously flawed.

/Flibble

[Öö Tiib]

You have found what opposite? that std::allocator is slower and that there
is a way to free the pool 'under boost::fast_pool_allocator'?

[Mr Flibble]

I've found that performance improves using it.

/Flibble

[Daniel]

On Friday, October 21, 2016 at 10:55:19 AM UTC-4, Mr Flibble wrote:
>
> I've found that performance improves using it.
>

What did you specify as the template parameters for boost::fast_pool_allocator? Or did you take the defaults (apart from the first)?

boost::fast_pool_allocator uses a singleton pool, which requires
synchronization for thread safety, and the synchronization does affect
performance, especially if there really is contention. If you know your
application will never use more than the main thread, you can improve
performance by specifying a Mutex template parameter as null_mutex.

But I think I would prefer to use a stateful allocator.

Thanks,
Daniel

[Mr Flibble]

Defaults.

std::allocator will likely be calling std::malloc which also requires
(internally) synchronization for thread safety so we can ignore this
overhead when comparing std::allocator with boost::fast_pool_allocator.

/Flibble

[Daniel]

On Friday, October 21, 2016 at 10:12:11 PM UTC-4, Mr Flibble wrote:
>
> std::allocator ... also requires (internally) synchronization for thread safety

Indeed

> so we can ignore this overhead when comparing std::allocator with
> boost::fast_pool_allocator.
>

Umm ... no :-)

[Jorgen Grahn]

On Thu, 2016-10-20, Daniel wrote:
> On Wednesday, October 19, 2016 at 8:06:33 PM UTC-4, Alf P. Steinbach wrote:
>>
>> One reasonable way to compare them could be to look at some typical
>> concrete usage examples, implemented with both approaches.
>>
> Yes, those, but also aesthetics.

It's in the concrete examples you find the aesthetics; that's where
you might see one of the approaches becoming awkward and the other one
elegant and straightforward.

> I've never actually seen std::multimap used outside of
> examples. Perhaps I've been too cloistered.

I don't think I've used it either. But I don't know why, so I think
your question is a good one.

/Jorgen

--
// Jorgen Grahn <grahn@ Oo o. . .
\X/ snipabacken.se> O o .

[Mr Flibble]

Umm ... yes.

boost::fast_pool_allocator can offer better performance over
std::allocator when it uses a mutex (default) and even better
performance when it doesn't and you are using it with just one thread.

/Flibble

[Daniel]

On Saturday, October 22, 2016 at 4:22:44 PM UTC-4, Mr Flibble wrote:
>
> Umm ... yes.
>
> boost::fast_pool_allocator can offer better performance over
> std::allocator when it uses a mutex (default)

I don't think so. I ran the test below (Windows 10, vc140), and the results
were

(std_allocator) 3356 milliseconds
(boost_allocator) 5949 milliseconds

As an aside, from the boost docs, "The underlying singleton_pool used by the
[boost::fast_pool_allocator] allocator constructs a pool instance that is never
freed."

#include <boost/pool/pool_alloc.h>
#include <map>
#include <chrono>

using std::chrono::high_resolution_clock;
using std::chrono::time_point;
using std::chrono::duration;

struct book
{
std::string author;
std::string title;
double price;
};

using boost_allocator = boost::fast_pool_allocator<std::pair<size_t,book>>;
using std_allocator = std::allocator<std::pair<size_t, book>>;
using map1 = std::map<size_t, book, std::less<size_t>, std_allocator>;
using map2 = std::map<size_t, book, std::less<size_t>, boost_allocator>;

int main()
{
book book1{ "Haruki Murakami", "Kafka on the Shore", 25.17 };
size_t count = 10000000;

{
map1 booklist;
auto start = high_resolution_clock::now();
for (size_t i = 0; i < count; ++i)
{
booklist.insert(std::make_pair(i, book1));
}
auto end = high_resolution_clock::now();
auto elapsed = std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count();
std::cout << "(std_allocator) " << elapsed << " milliseconds" << std::endl;

}

{
map2 booklist;
auto start = high_resolution_clock::now();
for (size_t i = 0; i < count; ++i)
{
booklist.insert(std::make_pair(i, book1));
}
auto end = high_resolution_clock::now();
auto elapsed = std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count();
std::cout << "(boost_allocator) " << elapsed << " milliseconds" << std::endl;
}

return 0;
}

[Mr Flibble]

Your result isn't surprising at all given that your testcase isn't a
usage scenario where one would typically deploy memory pools. Now for a
more realistic usage scenario:

int main()
{
book book1{ "Robocop", "ED209", 25.17 }; // small strings for SSO to
avoid separate dynamic allocations
size_t count = 10000000;

map1 booklist1; // to be fair we don't want to deallocate booklist1
possibly creating fragmentation before testing booklist2
map2 booklist2;

{

auto start = high_resolution_clock::now();
for (size_t i = 0; i < count; ++i)
{

booklist1.insert(std::make_pair(i, book1));
if (count % 1000 == 0)
while (!booklist1.empty())
booklist1.erase(booklist1.begin());

}
auto end = high_resolution_clock::now();
auto elapsed =
std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count();
std::cout << "(std_allocator) " << elapsed << " milliseconds" <<
std::endl;
}

{

auto start = high_resolution_clock::now();
for (size_t i = 0; i < count; ++i)
{

booklist2.insert(std::make_pair(i, book1));
if (count % 1000 == 0)
while (!booklist2.empty())
booklist2.erase(booklist2.begin());

}
auto end = high_resolution_clock::now();
auto elapsed =
std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count();
std::cout << "(boost_allocator) " << elapsed << " milliseconds" <<
std::endl;
}

return 0;
}

Results:

(std_allocator) 1515 milliseconds
(boost_allocator) 1186 milliseconds

/Flibble

[Daniel]

On Monday, October 24, 2016 at 2:11:30 PM UTC-4, Mr Flibble wrote:
>
> Your result isn't surprising at all given that your testcase isn't a
> usage scenario where one would typically deploy memory pools. Now for a
> more realistic usage scenario:
>
>

> Results:
>
> (std_allocator) 1515 milliseconds
> (boost_allocator) 1186 milliseconds
>

My results for that one are

(std_allocator) 1438 milliseconds
(boost_allocator) 983 milliseconds

which are similar to yours. But I would quarrel a little bit with the notion
that that is a more realistic usage scenario :-) That's a lot of erases.

Best regards,
Daniel

[Mr Flibble]

It is more realistic because a primary driver for using memory pools is
to avoid and/or not be affected by memory fragmentation and memory only
fragments after deallocations: your testcase was just allocations.

/Flibble