[Boost-users] [MultiArray, Intrusive] Instantiating a multi_array of intrusive lists as a class member

Subject: [Boost-users] [MultiArray, Intrusive] Instantiating a multi_array of intrusive lists as a class member
From: Jiri Vyskocil (svzj_at_[hidden])
Date: 2012-12-09 09:04:42

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 <boost/multi_array.hpp>
struct Particle {
unsigned number;
Particle(unsigned n){ number = n; }
};
typedef std::list<Particle> ParticleList;
typedef boost::multi_array<ParticleList, 3> 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 <boost/intrusive/list.hpp>
#include <boost/multi_array.hpp>
typedef boost::intrusive::list_base_hook<> BaseHook;
struct Particle : BaseHook {
unsigned number;
};
typedef boost::intrusive::list<Particle> ParticleList;
typedef boost::multi_array<ParticleList, 3> 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<T, NumDims, Allocator>::allocate_space() [with T =
boost::intrusive::list<Particle>, long unsigned int NumDims = 3ul,
Allocator = std::allocator<boost::intrusive::list<Particle> >]’
/usr/include/boost/multi_array.hpp:186:5: instantiated from
‘boost::multi_array<T, NumDims, Allocator>::multi_array(const
boost::detail::multi_array::extent_gen<NumDims>&) [with T =
boost::intrusive::list<Particle>, long unsigned int NumDims = 3ul,
Allocator = std::allocator<boost::intrusive::list<Particle> >]’
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<T, O1, O2, O3>::operator
boost::rv<boost::intrusive::list<T, O1, O2, O3> >&() [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<ParticleList*, 3> 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