Subject: Re: [boost] [flat_map] Any interest in a flat_map variant that is much faster on insertion/erase at the price of a slower lookup?
From: Ion Gaztañaga (igaztanaga_at_[hidden])
Date: 2015-03-13 12:39:50
El 13/03/2015 a las 16:04, Peter Dimov escribió:
> It doesn't have to have an interface, at least in principle. flat_map
> can just append the new elements to the end, keeping them sorted, until
> it hits a threshold, then merge. Lookups will first look at the new
> element range (because those are likely to be in cache), if not found,
> at the old element range.
That would complicate the container, and break some invariants, like
"equal_range". flat_map is designed to cover an scenario for more
searches than insertions, maybe another container could be designed for
a different scenario.
> Actually, the new element range doesn't even need to be kept sorted, if
> the merge threshold is low, although on the other hand this runs into
> op< vs op== issues, so maybe not.
You've touched an interesting point. Sort+Merging could improve flat_map
performance in some other scenarios. The option to do a merge can be
added to a range insertion, current implementation has not very good
performance due to excessive data movement. In this scenario we could
back-insert, sort and merge. The problem is:
-> It requires additional memory (stable_sort is needed for
flat_multimap) to achieve O(N·log(N)). inplace_merge requires additional
memory to obtain O(N). A user might not want to pay for this (you might
need 2x temporary memory). One option is to use the remaining capacity
as additional memory by default and optionally add an insertion option
that allocates temporary storage to achieve maximum performance.
-> we need to reimplement std::sort/std::stable_sort/std::inplace_merge
in a Boost.Move-compatible way (using boost::adl_move_swap). It should
allow customizing the temporary storage source. Maybe sorting experts
would like to implement it in Boost.Move.
> Of course, when the underlying vector runs out of capacity, a
> non-inplace merge will be performed after reallocation.
> Upon closer look on the subject line, did I just reinvent a wheel? :-)
Maybe, but everyone should reinvent the wheel at least once in life.
It's an great pleasure!
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk