I having trouble understanding the documentation of Boost.Intrusive. I'm referring to this section in particular: http://www.boost.org/doc/libs/1_65_0/doc/html/intrusive/intrusive_vs_nontrus... "The main difference between intrusive containers and non-intrusive containers is that in C++ non-intrusive containers store *copies* of values passed by the user." This is confusing, as that might not be true in case of C++11 and up. Does (or rather, can) move-construction invalidate the use case for Intrusive containers? "On the other hand, an intrusive container does not store copies of passed objects, but it stores the objects themselves. The additional data needed to insert the object in the container must be provided by the object itself." But then in the example for slist, it seems from the example code that (a) pointer(s) to the original object are stored (and makes it look like the object), but that's not what I read from the quoted text. class MyClass{ MyClass *next; MyClass *previous; //Other members...}; int main(){ acme_intrusive_list<MyClass> list; MyClass myclass; list.push_back(myclass); //"myclass" object is stored in the list assert(&myclass == &list.front()); return 0;} I would like to ask for somebody to confirm I'm right, or explain to me in language (palatable to a thick user) what is actually stored (in terms of implementation). Thanks in advance, degski -- "*Ihre sogenannte Religion wirkt bloß wie ein Opiat reizend, betäubend, Schmerzen aus Schwäche stillend.*" - Novalis 1798
On 23 August 2017 at 10:18, degski <degski@gmail.com> wrote:
But then in the example for slist, it seems from the example code that (a) pointer(s) to the original object are stored (and makes it look like the object), but that's not what I read from the quoted text.
<snip>
I would like to ask for somebody to confirm I'm right, or explain to me in language (palatable to a thick user) what is actually stored (in terms of implementation).
Maybe I got it now, the intrusive container is more like a view over the data, using the hook(s) in the object to do it's business (like chaining the objects to form an slist f.e.). degski -- "*Ihre sogenannte Religion wirkt bloß wie ein Opiat reizend, betäubend, Schmerzen aus Schwäche stillend.*" - Novalis 1798
On 08/23/17 10:18, degski via Boost wrote:
I having trouble understanding the documentation of Boost.Intrusive. I'm referring to this section in particular: http://www.boost.org/doc/libs/1_65_0/doc/html/intrusive/intrusive_vs_nontrus...
"The main difference between intrusive containers and non-intrusive containers is that in C++ non-intrusive containers store *copies* of values passed by the user."
This is confusing, as that might not be true in case of C++11 and up.
"On the other hand, an intrusive container does not store copies of passed objects, but it stores the objects themselves. The additional data needed to insert the object in the container must be provided by the object itself."
I think the important point here is that the conventional containers wrap user's objects in the auxiliary structures and therefore store a *different* object than the one passed by the user. In C++03 this is achieved by copying the object, in C++11 and later this can also be done by moving (ignoring emplacement as in this case the object doesn't exist until it is created by the container). Boost.Intrusive, on the other hand, links the exact same object that you passed into the container without copying and moving.
Does (or rather, can) move-construction invalidate the use case for Intrusive containers?
I guess, if your object's move is cheap and copy is expensive, and you were considering Boost.Intrusive as a way to avoid copying the object then you could use a conventional container with move-construction instead. But I wouldn't consider this a main use case of Boost.Intrusive. For me, there are two main use cases for Boost.Intrusive. First is when your object is not copyable or movable, which is often the case when the object is referenced by another API. The only alternative to Boost.Intrusive is keeping a pointer to the object in a separate container, which is way too cumbersome. Second is when you want your object to be a member of multiple containers and you don't want or cannot copy it. In a way, this is similar to Boost.MultiIndex, but you are not constrained to have the object present either in all indexes or none.
But then in the example for slist, it seems from the example code that (a) pointer(s) to the original object are stored (and makes it look like the object), but that's not what I read from the quoted text.
class MyClass{ MyClass *next; MyClass *previous; //Other members...}; int main(){ acme_intrusive_list<MyClass> list;
MyClass myclass; list.push_back(myclass);
//"myclass" object is stored in the list assert(&myclass == &list.front()); return 0;}
Yes, the assert is correct.
I would like to ask for somebody to confirm I'm right, or explain to me in language (palatable to a thick user) what is actually stored (in terms of implementation).
Internally, Boost.Intrusive containers mostly deal with linking. All the necessary data needed for container is stored in the hook that has to be injected somehow into the object. They do not allocate or free memory, they do not copy, move or construct user's objects. They can be *asked* to destroy the user's object upon removing it from the container but by default do not do that either. This makes the containers completely agnostic to the storage they operate on. In the hindsight, they are data structures with no cruft.
On 23 August 2017 at 12:03, Andrey Semashev via Boost <boost@lists.boost.org
wrote:
<snip> Andrey, I thank you very much for your extensive write-up. Everything is clear now, very handy indeed. degski -- "*Ihre sogenannte Religion wirkt bloß wie ein Opiat reizend, betäubend, Schmerzen aus Schwäche stillend.*" - Novalis 1798
object is referenced by another API. The only alternative to Boost.Intrusive is keeping a pointer to the object in a separate container, which is way too cumbersome. Second is when you want your object to be a member of multiple containers and you don't want or cannot copy it.
Storing a vector of pointers is not only less cumbersome than injecting structures into the original objects, it's less expensive. According to the Doom3 BFG technical note (fabiensanglard.net/doom3_documentation/DOOM-3-BFG-Technical-Note.pdf) a vector of indexes to a separate vector(s) of objects is significantly faster than an intrusive list. The same would be true for a vector of pointers (but less so). This approach is also amenable to multiple containers sharing objects. M
On Wed, Aug 23, 2017 at 3:18 PM, Soul Studios via Boost <boost@lists.boost.org> wrote:
Storing a vector of pointers is not only less cumbersome than injecting structures into the original objects, it's less expensive.
Intrusive doesn't model vectors, that would be pointless. It models lists (single and double), and sets (ordered and unordered). Beast uses intrusive for the header fields container: <https://github.com/boostorg/beast/blob/develop/include/boost/beast/http/fields.hpp#L164> Boost.Intrusive is one of my favorite Boost libraries, it is incredibly well written and well maintained on more platforms than I can count. It is very handy. Thanks
On 08/24/17 01:18, Soul Studios via Boost wrote:
object is referenced by another API. The only alternative to Boost.Intrusive is keeping a pointer to the object in a separate container, which is way too cumbersome. Second is when you want your object to be a member of multiple containers and you don't want or cannot copy it.
Storing a vector of pointers is not only less cumbersome than injecting structures into the original objects,
Having tried both, I will just have to disagree.
it's less expensive. According to the Doom3 BFG technical note (fabiensanglard.net/doom3_documentation/DOOM-3-BFG-Technical-Note.pdf) a vector of indexes to a separate vector(s) of objects is significantly faster than an intrusive list. The same would be true for a vector of pointers (but less so). This approach is also amenable to multiple containers sharing objects.
Whether that is faster or not depends on many factors, primarilly the use scenarios at hand. One can't make a general statement like that without specifics. One factor that could make a vector more efficient than a list is cache friendliness, but an intrusive list could exploit it as well if you manage the storage appropriately.
Whether that is faster or not depends on many factors, primarilly the use scenarios at hand. One can't make a general statement like that without specifics. One factor that could make a vector more efficient than a list is cache friendliness, but an intrusive list could exploit it as well if you manage the storage appropriately.
Examples please.
On 08/24/17 03:45, Soul Studios via Boost wrote:
Whether that is faster or not depends on many factors, primarilly the use scenarios at hand. One can't make a general statement like that without specifics. One factor that could make a vector more efficient than a list is cache friendliness, but an intrusive list could exploit it as well if you manage the storage appropriately.
Examples please.
Examples of what, exactly?
Whether that is faster or not depends on many factors, primarilly the use scenarios at hand. One can't make a general statement like that without specifics. One factor that could make a vector more efficient than a list is cache friendliness, but an intrusive list could exploit it as well if you manage the storage appropriately.
Examples please.
Examples of what, exactly?
Of scenarios where what you're saying is true. My benchmarks indicate that a list which allocates in chunks rather than individually only outperforms a vector of indexes to a vector of elements in the case where ordered insertion is very frequent (plf::list is the list in question: see http://www.plflib.org/benchmarks_haswell_gcc.htm#orderedlowmodification and http://www.plflib.org/benchmarks_haswell_gcc.htm#orderedhighmodification and http://www.plflib.org/benchmarks_haswell_gcc.htm#highmodification)
On Sun, Aug 27, 2017 at 3:33 AM, Soul Studios via Boost <boost@lists.boost.org> wrote:
Whether that is faster or not depends on many factors, primarilly the use scenarios at hand. One can't make a general statement like that without specifics. One factor that could make a vector more efficient than a list is cache friendliness, but an intrusive list could exploit it as well if you manage the storage appropriately.
Examples please.
Examples of what, exactly?
Of scenarios where what you're saying is true. My benchmarks indicate that a list which allocates in chunks rather than individually only outperforms a vector of indexes to a vector of elements in the case where ordered insertion is very frequent (plf::list is the list in question: see http://www.plflib.org/benchmarks_haswell_gcc.htm#orderedlowmodification and http://www.plflib.org/benchmarks_haswell_gcc.htm#orderedhighmodification and http://www.plflib.org/benchmarks_haswell_gcc.htm#highmodification)
Then you already have an example - a list over elements in a deque/vector, which is what I was referring to as a way to improve cache friendliness. But my main point was not about that. I was saying you have to consider many factors such as your use cases, object size and typical count, access patterns and what not before choosing one data structure or the other. Depending on those factors you will have a different preference in terms of performance, too. Take flat_map vs. std::map for example - both are good in some uses and not so good in other. Saying that flat_map is faster would be false.
Whether that is faster or not depends on many factors, primarilly the use scenarios at hand. One can't make a general statement like that without specifics. One factor that could make a vector more efficient than a list is cache friendliness, but an intrusive list could exploit it as well if you manage the storage appropriately.
Examples please.
Examples of what, exactly?
ps. This is largely due to the cost of iteration between either technique. An intrusive list has the same iteration cost.
Just posting my own experience with intrusive slists. I've (re-)implemented a Rooted Directed Graph (Adjacency-lists, in- and out-arcs, using the same arcs in both in and out slists). Underlying memory is provided by 2 memory pools (nodes-, arcs-value-types), the nodes and arcs are themselves intrusive as well, as the data is carried directly in the nodes and arcs. Eventually, I'll also need a map, to cater for Transpositions, which will also be intrusive, just need to add that to the nodes. Once I got my head around how to use Boost.Intrusive, its use simplified the design (so less error-prone) a lot. The previous implementation was, what is best described as a flat-graph, linked lists over vector(s), using indexes for linking up the various components. Depending on the fan-out, the new implementation is 40% (low fan-out) to 10% (high fan-out) faster than the old one. In testing, I've made sure no re-allocation of the vectors (in the flat-graph) is ever done, while the memory pools allocate sufficiently large chuncks not to make any difference as well. In my use case fan-out will (normally) decrease as the RDG gets deeper, this is not reflected in the testing, so the speed-up is under-estimated. So, all-in-all, I'm very happy with Boost.Intrusive (no need for multi-indexing, or duplication of data) and it also gives good performance. In the old design, iterators had to be implemented (to deal with the internal logic of the graph). In the new design, I just forward the standard ones provided by the linked intrusive lists, how easy is that. degski -- "*Ihre sogenannte Religion wirkt bloß wie ein Opiat reizend, betäubend, Schmerzen aus Schwäche stillend.*" - Novalis 1798
The previous implementation was, what is best described as a flat-graph, linked lists over vector(s), using indexes for linking up the various components.
Okay, that's not actually the same as what we're talking about here- I'm talking about comparing a vector of pointers/indexes where you directly iterate over the pointers, vs an intrusive list. You're talking about, as far as I can tell, using a vector of nodes with pointers to the elements to iterate. That's always going to be slower compared to an intrusive list because you're wastin space and creating an additional indirection. By contrast a vector of pointers/indexes will be faster to iterate due to the CPU being able to cache the jump locations/offsets, whereas it can't with a linked list of any type. That's what my graphs show.
On 28 August 2017 at 01:15, Soul Studios via Boost <boost@lists.boost.org> wrote:
By contrast a vector of pointers/indexes will be faster to iterate due to the CPU being able to cache the jump locations/offsets, whereas it can't with a linked list of any type. That's what my graphs show.
So, I implemented that. The design now as simple as it gets. A RootedDiGraph with Adjacency vectors (and pointers obtained from the memory-pool to nodes and arcs). Instead of std::vector, I use the pt::pector from https://github.com/aguinet/pector, which has (can have) a smaller footprint, allows for std::uint32_t's as indices and has a growth-policy option (possibly with the use of realloc). Results: fan-out 32: RootedDiGraphAdjIntrLists: 1810 milliseconds. RootedDiGraphAdjVectors: 1302 milliseconds. RootedDiGraphFlat: 2486 milliseconds. fan-out 512: RootedDiGraphAdjIntrLists: 28841 milliseconds. RootedDiGraphAdjVectors: 14698 milliseconds. RootedDiGraphFlat: 33168 milliseconds. That's a significant improvement. degski -- "*Ihre sogenannte Religion wirkt bloß wie ein Opiat reizend, betäubend, Schmerzen aus Schwäche stillend.*" - Novalis 1798
By contrast a vector of pointers/indexes will be faster to iterate due to the CPU being able to cache the jump locations/offsets, whereas it can't with a linked list of any type. That's what my graphs show.
So, I implemented that. The design now as simple as it gets. A RootedDiGraph with Adjacency vectors (and pointers obtained from the memory-pool to nodes and arcs). Instead of std::vector, I use the pt::pector from https://github.com/aguinet/pector, which has (can have) a smaller footprint, allows for std::uint32_t's as indices and has a growth-policy option (possibly with the use of realloc).
Results:
fan-out 32:
RootedDiGraphAdjIntrLists: 1810 milliseconds. RootedDiGraphAdjVectors: 1302 milliseconds. RootedDiGraphFlat: 2486 milliseconds.
fan-out 512:
RootedDiGraphAdjIntrLists: 28841 milliseconds. RootedDiGraphAdjVectors: 14698 milliseconds. RootedDiGraphFlat: 33168 milliseconds.
That's a significant improvement.
Thanks degski - that more-or-less reflects what I thought. Good to know I could make a difference!
On 23-08-17 09:18, degski via Boost wrote:
This is confusing, as that might not be true in case of C++11 and up. Does (or rather, can) move-construction invalidate the use case for Intrusive containers?
It's still the same. Even when moving into c++11 containers, the container owns the object instances. Intrusive containers do not.
On 23 August 2017 at 12:53, Seth via Boost <boost@lists.boost.org> wrote:
It's still the same. Even when moving into c++11 containers, the container owns the object instances. Intrusive containers do not.
Seth, thank you, it's all clear now. degski -- "*Ihre sogenannte Religion wirkt bloß wie ein Opiat reizend, betäubend, Schmerzen aus Schwäche stillend.*" - Novalis 1798
participants (5)
-
Andrey Semashev -
degski -
Seth -
Soul Studios -
Vinnie Falco