On Sun, Dec 9, 2012 at 6:04 AM, Jiri Vyskocil wrote:

Hello,

I want to try Boost Intrusive list instead of std::list in a performance and memory critical part of code. I have a Domain object, which contains a boost::multi_array of cells. each cell contains a list of particles std::list<Particle>.

This sample code works as expected (std::list):

#include <list> #include <iostream> #include struct Particle { unsigned number; Particle(unsigned n){ number = n; } }; typedef std::list<Particle> ParticleList; typedef boost::multi_array ParticleArray; class Domain { public: ParticleArray particles; Domain(int x, int y, int z) : particles(boost::extents[x][y][z]) { } }; int main(){ Domain* dom = new Domain(10,10,10); dom->particles[5][5][5].push_back(Particle(1)); std::cout << dom->particles[5][5][5].front().number << std::endl; return 0; }

When I try to swap the std::list for an intrusive list, I get a compile error on Domain instantiation. Minimal code leading to the error:

#include #include typedef boost::intrusive::list_base_hook<> BaseHook; struct Particle : BaseHook { unsigned number; }; typedef boost::intrusive::list<Particle> ParticleList; typedef boost::multi_array ParticleArray; class Domain { public: ParticleArray particles; Domain(int x, int y, int z) : particles(boost::extents[x][y][z]) { } }; int main(){ Domain* dom = new Domain(10,10,10); return 0; }

When I try to compile the above code, gcc tells me:

In file included from

/usr/lib/gcc/x86_64-pc-linux-gnu/4.6.3/include/g++-v4/bits/stl_tempbuf.h:61:0, from /usr/lib/gcc/x86_64-pc-linux-gnu/4.6.3/include/g++-v4/bits/stl_algo.h:64, from /usr/lib/gcc/x86_64-pc-linux-gnu/4.6.3/include/g++-v4/algorithm:63, from /usr/include/boost/move/move.hpp:37, from

/usr/include/boost/intrusive/detail/has_member_function_callable_with.hpp:22, from /usr/include/boost/intrusive/detail/memory_util.hpp:112, from /usr/include/boost/intrusive/pointer_traits.hpp:26, from /usr/include/boost/intrusive/detail/utilities.hpp:17, from /usr/include/boost/intrusive/list_hook.hpp:19, from /usr/include/boost/intrusive/list.hpp:20, from intrusive.cc:1: /usr/lib/gcc/x86_64-pc-linux-gnu/4.6.3/include/g++-v4/bits/stl_construct.h: In function ‘void std::_Construct(_T1*, const _T2&) [with _T1 = boost::intrusive::list<Particle>, _T2 = boost::intrusive::list<Particle>]’:

/usr/lib/gcc/x86_64-pc-linux-gnu/4.6.3/include/g++-v4/bits/stl_uninitialized.h:189:3: instantiated from ‘static void

std::__uninitialized_fill_n<_TrivialValueType>::__uninit_fill_n(_ForwardIterator, _Size, const _Tp&) [with _ForwardIterator = boost::intrusive::list<Particle>*, _Size = long unsigned int, _Tp = boost::intrusive::list<Particle>, bool _TrivialValueType = false]’

/usr/lib/gcc/x86_64-pc-linux-gnu/4.6.3/include/g++-v4/bits/stl_uninitialized.h:225:7: instantiated from ‘void std::uninitialized_fill_n(_ForwardIterator, _Size, const _Tp&) [with _ForwardIterator = boost::intrusive::list<Particle>*, _Size = long unsigned int, _Tp = boost::intrusive::list<Particle>]’ /usr/include/boost/multi_array.hpp:477:5: instantiated from ‘void boost::multi_array::allocate_space() [with T = boost::intrusive::list<Particle>, long unsigned int NumDims = 3ul, Allocator = std::allocator]’ /usr/include/boost/multi_array.hpp:186:5: instantiated from ‘boost::multi_array::multi_array(const boost::detail::multi_array::extent_gen<NumDims>&) [with T = boost::intrusive::list<Particle>, long unsigned int NumDims = 3ul, Allocator = std::allocator]’ intrusive.cc:18:49: instantiated from here

/usr/lib/gcc/x86_64-pc-linux-gnu/4.6.3/include/g++-v4/bits/stl_construct.h:84:7: error: passing ‘const boost::intrusive::list<Particle>’ as ‘this’ argument of ‘boost::intrusive::list::operator boost::rv >&() [with T = Particle, O1 = boost::intrusive::none, O2 = boost::intrusive::none, O3 = boost::intrusive::none]’ discards qualifiers [-fpermissive]

This is just a minimal sample code to trigger an error. In the actual code, both Domain and Particle objects are more complicated. The last line of error output is sligtly different:

/usr/lib/gcc/x86_64-pc-linux-gnu/4.6.3/include/g++-v4/bits/stl_construct.h:84:7: error: no matching function for call to ‘boost::intrusive::list<Particle>::list(const boost::intrusive::list<Particle>&)’

followed by a note with a list of candidate functions.

If I define the multi_array so that it contains pointers to ParticleArray, i.e.: typedef boost::multi_array ParticleArray; there seems to be no benefit over the std::list approach, since I have to hold the additional pointer. In a test simulation, this variant eats about 10% more RAM, which is of concern in our situation.

Any ideas how to replace std::list with boost::intrusive::list in a multi_array in a way which wouldn't consume more memory than the std::list approach? (I would want to see if it also brings the much needed performance benefit)

Jiri Vyskocil

Offhand, it *looks* like boost::intrusive::list uses Boost.Move-style emulation which may not be compatible with boost::multi_array. I'd try 2 things: - See if a std::vector< boost::intrusive::list > works. - See if a boost::multi_array< boost::container::vector > works. If the above nesting of data structures gives similar errors as the original combination (something about unavailability of a copy constructor and/or stuff involving boost::rv<>), then that would seem to confirm it's a Boost.Move + Boost.MultiArray incompatibility. At that point, the best options are either to patch Boost.MultiArray to be Boost.Move-aware (not sure how much work that would be...) or try gcc 4.7.x, where maybe Boost.Move would no longer have adverse effects (if rvalue references are enabled by default; I don't know actually if that's the case). HTH, - Jeff