Boost logo

Boost :

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:

Regards, Phil.

Boost list run by bdawes at, gregod at, cpdaniel at, john at