Re: [boost] [Container] small flat set ?

Subject: Re: [boost] [Container] small flat set ?
From: Phil Endecott (spam_from_boost_dev_at_[hidden])
Date: 2017-09-16 17:46:58

>> Ion Gazta?aga <igaztanaga_at_[hidden]>
>>> 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.