[MultiArray, Intrusive] Instantiating a multi_array of intrusive lists as a class member
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
On Sun, Dec 9, 2012 at 6:04 AM, Jiri Vyskocil <svzj@centrum.cz> 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
On Sun, 2012-12-09 at 22:40 -0800, Jeffrey Lee Hellrung, Jr. wrote: - See if a std::vector< boost::intrusive::list > works.
This construction compiles and works with gcc 4.7.2 in C++11 mode only. With wersion 4.7.2 in default mode and 4.6 in any mode, compilation fails with a similar error. - See if a boost::multi_array< boost::container::vector > works.
This compiles and works fine in both 4.6 and 4.7, even in non-C++11 mode 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).
GCC 4.7.2 won't compile the MultiArray of intrusive lists even in C++11 mode. It spews the same error as gcc 4.6 in C++0x mode: /usr/include/boost/intrusive/list.hpp:1488:4: error: ‘boost::intrusive::list<T, O1, O2, O3>::list(const boost::intrusive::list<T, O1, O2, O3>&) [with T = Particle, O1 = boost::intrusive::none, O2 = boost::intrusive::none, O3 = boost::intrusive::none, boost::intrusive::list<T, O1, O2, O3> = boost::intrusive::list<Particle>]’ is private It would be nice to have this working at least in the newer gcc, but I have no idea what to look for...
On Fri, Dec 14, 2012 at 5:02 AM, Jiri Vyskocil <svzj@centrum.cz> wrote:
On Sun, 2012-12-09 at 22:40 -0800, Jeffrey Lee Hellrung, Jr. wrote:
- See if a std::vector< boost::intrusive::list > works.
This construction compiles and works with gcc 4.7.2 in C++11 mode only. With wersion 4.7.2 in default mode and 4.6 in any mode, compilation fails with a similar error.
- See if a boost::multi_array< boost::container::vector > works.
This compiles and works fine in both 4.6 and 4.7, even in non-C++11 mode
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).
GCC 4.7.2 won't compile the MultiArray of intrusive lists even in C++11 mode. It spews the same error as gcc 4.6 in C++0x mode:
/usr/include/boost/intrusive/list.hpp:1488:4: error: ‘boost::intrusive::list<T, O1, O2, O3>::list(const boost::intrusive::list<T, O1, O2, O3>&) [with T = Particle, O1 = boost::intrusive::none, O2 = boost::intrusive::none, O3 = boost::intrusive::none, boost::intrusive::list<T, O1, O2, O3> = boost::intrusive::list<Particle>]’ is private
It would be nice to have this working at least in the newer gcc, but I have no idea what to look for...
Ah, evidently boost::multiarray expects its value_type to be copy-constructible (at least), which Boost.Intrusive data structures are not [1]: "Boost.Intrusive containers are non-copyable and non-assignable." Also explains the failure of std::vector< boost::intrusive::list >, too, in C++03 mode. In C++11 mode, I guess std::vector (and similar) are able to fall back to using the move constructors and assignment operators of the Boost.Intrusive data structures. - Jeff [1] http://www.boost.org/doc/libs/1_52_0/doc/html/intrusive/intrusive_vs_nontrus...
OK. It makes sense, that the multi_array expects its values to be copy-constructible. Still I would like to use the intrusive list since this part of algorithm is particularly sensitive to cache locality issues and I cannot lose the multi_array interface - stuff like views for example - because I already use it everywhere. I know, I'm not going to copy the lists contained in the multi_array. Any ideas how to get an intrusive list inside the multi_array? I can only think of implementing the intrusive list myself usin plain old pointer and reimplementing parts of STL-like interface. But it seems like a long path... What about inheriting a class from intrusive list, providing a false copy constructor (which would i.e. throw an error when called to be safe)? Would something like this be possible?
Ah, evidently boost::multiarray expects its value_type to be copy-constructible (at least), which Boost.Intrusive data structures are not [1]: "Boost.Intrusive containers are non-copyable and non-assignable." Also explains the failure of std::vector< boost::intrusive::list >, too, in C++03 mode. In C++11 mode, I guess std::vector (and similar) are able to fall back to using the move constructors and assignment operators of the Boost.Intrusive data structures.
- Jeff
[1] http://www.boost.org/doc/libs/1_52_0/doc/html/intrusive/intrusive_vs_nontrus...
_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
On Mon, Jan 7, 2013 at 2:11 PM, Jiri Vyskocil <svzj@centrum.cz> wrote:
Ah, evidently boost::multiarray expects its value_type to be copy-constructible (at least), which Boost.Intrusive data structures are not [1]: "Boost.Intrusive containers are non-copyable and non-assignable." Also explains the failure of std::vector< boost::intrusive::list >, too, in C++03 mode. In C++11 mode, I guess std::vector (and similar) are able to fall back to using the move constructors and assignment operators of the Boost.Intrusive data structures.
- Jeff
[1] http://www.boost.org/doc/libs/1_52_0/doc/html/intrusive/intrusive_vs_nontrus...
_______________________________________________ Boost-users mailing listBoost-users@lists.boost.orghttp://lists.boost.org/mailman/listinfo.cgi/boost-users
OK. It makes sense, that the multi_array expects its values to be copy-constructible. Still I would like to use the intrusive list since this part of algorithm is particularly sensitive to cache locality issues and I cannot lose the multi_array interface - stuff like views for example - because I already use it everywhere.
I know, I'm not going to copy the lists contained in the multi_array. Any ideas how to get an intrusive list inside the multi_array?
I can only think of implementing the intrusive list myself usin plain old pointer and reimplementing parts of STL-like interface. But it seems like a long path...
What about inheriting a class from intrusive list, providing a false copy constructor (which would i.e. throw an error when called to be safe)? Would something like this be possible?
I suppose it would be possible to either inherit (most hacky) or otherwise wrap an intrusive list and give it a "false", unconditionally throwing copy constructor, as you suggested. You can also wrap all your intrusive lists in shared_ptr (easiest) or use a multiarray of bare pointers to intrusive lists (as long as you manage their lifetime outside the multiarray). The best and correct solution, of course, is to update Boost.Multiarray for C++11, but that requires the most work :/ - Jeff
participants (2)
-
Jeffrey Lee Hellrung, Jr. -
Jiri Vyskocil