[Container] small flat set ?

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
15 messages Options
Reply | Threaded
Open this post in threaded view
|

[Container] small flat set ?

Boost - Dev mailing list
Dear all,

boost::container::small_vector and boost::container::static_vector
are great.  boost::container::flat_set is great too.

But today I need a small_flat_set!  And I don't think it's
possible to compose flat_set and small_vector.  (flat_set
can use a custom allocator, but it can't take a custom
implementation type in the way that, for example,
std::priority_queue can.)

Having said that, maybe composing flat_set and small_vector
(or static_vector) isn't the optimum solution for the case
where I will store something like 0...4 ints; I suspect that
linear search in an unordered sequence will be quicker.  But
that gets complicated if you need iterators with the normal
behaviour.

Any thoughts?


Regards, Phil.





_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: [Container] small flat set ?

Boost - Dev mailing list
On 04/09/2017 17:12, Phil Endecott via Boost wrote:

> Dear all,
>
> boost::container::small_vector and boost::container::static_vector
> are great.  boost::container::flat_set is great too.
>
> But today I need a small_flat_set!  And I don't think it's
> possible to compose flat_set and small_vector.  (flat_set
> can use a custom allocator, but it can't take a custom
> implementation type in the way that, for example,
> std::priority_queue can.)
>
> Having said that, maybe composing flat_set and small_vector
> (or static_vector) isn't the optimum solution for the case
> where I will store something like 0...4 ints; I suspect that
> linear search in an unordered sequence will be quicker.  But
> that gets complicated if you need iterators with the normal
> behaviour.
>
> Any thoughts?

I recently committed to develop the initial implementation (not properly
tested!) to use a different container than boost::container::vector as
the underlying sequence. The idea is to pass a container instead of an
allocator:

flat_set<int, std::less<int>, small_vector<int> >

   and

flat_set<int, std::less<int>, static_vector<int> >

should work. Or better said, they'll work properly soon. Willing to try?

Best,

Ion



_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: [Container] small flat set ?

Boost - Dev mailing list
In reply to this post by Boost - Dev mailing list
On 4 September 2017 at 18:12, Phil Endecott via Boost <[hidden email]
> wrote:
>
> But that gets complicated if you need iterators with the normal behaviour.
>

 Wrap a std::vector or a std::array (if fixed size) and forward the begin()
and end() iterators of the container. This then will also give you range
based for loops (for free) on your type.

degski
--
"*Ihre sogenannte Religion wirkt bloß wie ein Opiat reizend, betäubend,
Schmerzen aus Schwäche stillend.*" - Novalis 1798

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: [Container] small flat set ?

Boost - Dev mailing list
In reply to this post by Boost - Dev mailing list
Den 04-09-2017 kl. 22:42 skrev Ion Gaztañaga via Boost:
> On 04/09/2017 17:12, Phil Endecott via Boost wrote:

>> Any thoughts?
>
> I recently committed to develop the initial implementation (not properly
> tested!) to use a different container than boost::container::vector as
> the underlying sequence. The idea is to pass a container instead of an
> allocator:

Awesome. Also for flat_map, I presume?

-T

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: [Container] small flat set ?

Boost - Dev mailing list
On 05/09/2017 9:07, Thorsten Ottosen via Boost wrote:

> Den 04-09-2017 kl. 22:42 skrev Ion Gaztañaga via Boost:
>> On 04/09/2017 17:12, Phil Endecott via Boost wrote:
>
>>> Any thoughts?
>>
>> I recently committed to develop the initial implementation (not
>> properly tested!) to use a different container than
>> boost::container::vector as the underlying sequence. The idea is to
>> pass a container instead of an allocator:
>
> Awesome. Also for flat_map, I presume?

Sure!

Ion

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: [Container] small flat set ?

Boost - Dev mailing list
In reply to this post by Boost - Dev mailing list
On 5/09/2017 16:25, degski wrote:
> On 4 September 2017 at 18:12, Phil Endecott wrote:
>>
>> But that gets complicated if you need iterators with the normal behaviour.
>
>   Wrap a std::vector or a std::array (if fixed size) and forward the begin()
> and end() iterators of the container. This then will also give you range
> based for loops (for free) on your type.

That produces iterators with vector behaviour (invalidated on any
modification) rather than set behaviour (invalidated only if that
element is deleted), which can be a significant behavioural change.


_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: [Container] small flat set ?

Boost - Dev mailing list
In reply to this post by Boost - Dev mailing list
Den 04-09-2017 kl. 17:12 skrev Phil Endecott via Boost:
> Dear all,
>

> Having said that, maybe composing flat_set and small_vector
> (or static_vector) isn't the optimum solution for the case
> where I will store something like 0...4 ints; I suspect that
> linear search in an unordered sequence will be quicker.  But
> that gets complicated if you need iterators with the normal
> behaviour.

What normal behavior is it exactly that you need?

kind regards

Thorsten

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: [Container] small flat set ?

Boost - Dev mailing list
In reply to this post by Boost - Dev mailing list
Hi degski,

degski <[hidden email]> wrote:
> On 4 September 2017 at 18:12, Phil Endecott via Boost <[hidden email]
>> wrote:
>>
>> But that gets complicated if you need iterators with the normal behaviour.
>>
>
>  Wrap a std::vector or a std::array (if fixed size) and forward the begin()
> and end() iterators of the container. This then will also give you range
> based for loops (for free) on your type.

Of course that works for a sorted vector.

But in the part of my message that you didn't quote, I mentioned
storing the values in an unsorted vector and doing linear search.
In this case, you can usefully iterate over the entire container
as long as you don't care about the order, but you can't iterate
over, for example, the range between two elements that you get
from find().


Regards, Phil.





_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: [Container] small flat set ?

Boost - Dev mailing list
In reply to this post by Boost - Dev mailing list
Ion Gazta?aga wrote:

> I recently committed to develop the initial implementation (not properly
> tested!) to use a different container than boost::container::vector as
> the underlying sequence. The idea is to pass a container instead of an
> allocator:
>
> flat_set<int, std::less<int>, small_vector<int> >
>
>    and
>
> flat_set<int, std::less<int>, static_vector<int> >
>
> should work. Or better said, they'll work properly soon. Willing to try?

Thanks Ion, I'll have a look at that.

I'm now using a crude implementation with linear insert and erase
on top of a static_vector.  This function has dropped from ~5% of
total runtime to not measurable.

It would be interesting to compare sorted vs. unsorted implementations.
But it will have to be with a synthetic benchmark.


Regards, Phil.





_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: [Container] small flat set ?

Boost - Dev mailing list
In reply to this post by Boost - Dev mailing list
Ion Gazta?aga <[hidden email]>

> I recently committed to develop the initial implementation (not properly
> tested!) to use a different container than boost::container::vector as
> the underlying sequence. The idea is to pass a container instead of an
> allocator:
>
> flat_set<int, std::less<int>, small_vector<int> >
>
>    and
>
> flat_set<int, std::less<int>, static_vector<int> >
>
> should work. Or better said, they'll work properly soon. Willing to try?

detail/flat_tree.hpp line 459 tries to use a macro BOOST_INTRUSIVE_HAS_TYPE
which doesn't seem to be defined anywhere.


Regards, Phil.





_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: [Container] small flat set ?

Boost - Dev mailing list
On 09/09/2017 23:49, Phil Endecott via Boost wrote:

> Ion Gazta?aga <[hidden email]>
>> I recently committed to develop the initial implementation (not
>> properly tested!) to use a different container than
>> boost::container::vector as the underlying sequence. The idea is to
>> pass a container instead of an allocator:
>>
>> flat_set<int, std::less<int>, small_vector<int> >
>>
>>    and
>>
>> flat_set<int, std::less<int>, static_vector<int> >
>>
>> should work. Or better said, they'll work properly soon. Willing to try?
>
> detail/flat_tree.hpp line 459 tries to use a macro BOOST_INTRUSIVE_HAS_TYPE
> which doesn't seem to be defined anywhere.

You should update Boost.Intrusive also to the latest version, sorry for
not saying that before.

Best,

Ion

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: [Container] small flat set ?

Boost - Dev mailing list
>> Ion Gazta?aga <[hidden email]>
>>> I recently committed to develop the initial implementation (not
>>> properly tested!) to use a different container than
>>> boost::container::vector as the underlying sequence. The idea is to
>>> pass a container instead of an allocator:
>>>
>>> flat_set<int, std::less<int>, small_vector<int> >
>>>
>>> ?? and
>>>
>>> flat_set<int, std::less<int>, static_vector<int> >

Hi Ion,

This now works for me.  I've done some quick benchmarks; I have a test
harness that applies a sequence of operations - insert, erase by value,
assign, empty(), equality comparison, enumeration - extracted from a
run of my application to various implementations of small sets.  The
value type in each case is uint64_t and for the static and small vectors
the size is 8.  Benchmark run times are:

  2.2 no-op - test harness only
 65.2 std::set
 38.3 std::set with move assignment (*)
 20.2 boost::container::flat_set using std::vector
 15.8 boost::container::flat_set (defaults)
 17.6 boost::container::flat_set using boost::container::small_vector
 15.6 boost::container::flat_set using boost::container::static_vector
 16.7 my linear flat_set using boost::container::small_vector
 15.3 my linear flat_set using boost::container::static_vector

(*) std::set with move assignment doesn't have the same semantics as the
other tests so it isn't directly comparable, as some assignments in my
application need the assigned-from value afterwards and others don't.

This is on an ARM64 system (Cavium ThunderX) using:

$ g++ --version
g++ (Debian 6.3.0-18) 6.3.0 20170516

So it appears that my linear flat set has just a tiny benefit over binary
search for this set size.  The theory is that when N is small, the
O(log N) vs. O(N) difference is less important than the simpler algorithms
and better branch prediction of linear methods.

Benchmark code is here:  http://chezphil.org/tmp/set_bm.tgz


Regards, Phil.



_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: [Container] small flat set ?

Boost - Dev mailing list
On 16/09/2017 19:46, Phil Endecott via Boost wrote:

> This now works for me.  I've done some quick benchmarks; I have a test
> harness that applies a sequence of operations - insert, erase by value,
> assign, empty(), equality comparison, enumeration - extracted from a
> run of my application to various implementations of small sets.  The
> value type in each case is uint64_t and for the static and small vectors
> the size is 8.  Benchmark run times are:

Many thanks. I need to see why flat_set segfaults.

Best,

Ion

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: [Container] small flat set ?

Boost - Dev mailing list
Hi Ion,

Ion Gazta?aga <[hidden email]> wrote:
> Many thanks. I need to see why flat_set segfaults.

Errr.....

Are you looking at the line where I wrote "15.8
boost::container::flat_set (defaults)" and reading it
as "segfaults" ?

I just mean flat_set<uint64_t>, with its other template
parameters as their default values.

Nothing segfaults.


Regards, Phil.








_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: [Container] small flat set ?

Boost - Dev mailing list
On 18/09/2017 15:55, Phil Endecott via Boost wrote:

> Hi Ion,
>
> Ion Gazta?aga <[hidden email]> wrote:
>> Many thanks. I need to see why flat_set segfaults.
>
> Errr.....
>
> Are you looking at the line where I wrote "15.8
> boost::container::flat_set (defaults)" and reading it
> as "segfaults" ?

Exactly. Thanks for the forward error correction. Need to check my
glasses ;-)

Best,

Ion

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost