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.