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

Subject: Re: [Boost-users] [MultiArray, Intrusive] Instantiating a multi_array of intrusive lists as a class member
From: Jeffrey Lee Hellrung, Jr. (jeffrey.hellrung_at_[hidden])
Date: 2012-12-10 01:40:00

On Sun, Dec 9, 2012 at 6:04 AM, Jiri Vyskocil <svzj_at_[hidden]> 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 <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
>

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