Thorsten Ottosen said: (by the date of Tue, 21 Nov 2006 00:03:21 +0100)

Janek Kozicki wrote:

...

Using Boost.MultiIndex with Boost.PtrContainer would be great.

It's certainly something I have considered, though I'm not sure what the best approach is. It would take some investigation, and I'm not able to invest that time in the foreseeable future.

OTOH, I would be happy to help out with feedback if someone took on the task.

Thanks for your reply :) I'm still thinking how to best refactor my current containers. They are in bad need for refactoring and I'm still not sure where to go. MultiIndex + PtrContainer are one of alternatives. If it turns out that this is the way to go, I will want to try this task. Also I'm sure that my new container will have to support threading. I was thinking about something like accessor methods that will lock for reading and lock for writing: template <T> class my_superb_container { // only one can write to item 'item_index', no reading allowed T& lock_write(int item_index); // multiple reads of item 'item_index' are allowed, no writing const T& lock_read(int item_index); } Lock will be released when leaving current block, in the destructor. (destructor of what? - still thinking about that). The operator[] will not be provided. Only lock_write() and lock_read(). This my_superb_container will need to store mutexes in another container - one mutex per each item. Has anoyone thought about that? (the thread-capable containers) -- Janek Kozicki |

Thorsten Ottosen said: (by the date of Tue, 21 Nov 2006 13:16:29 +0100)

...

Also I'm sure that my new container will have to support threading. I was thinking about something like accessor methods that will lock for reading and lock for writing:

template <T> class my_superb_container {

// only one can write to item 'item_index', no reading allowed T& lock_write(int item_index);

// multiple reads of item 'item_index' are allowed, no writing const T& lock_read(int item_index); }

Lock will be released when leaving current block, in the destructor. (destructor of what? - still thinking about that).

It seems like a bad idea to mix threading into the container itself. Threading should be an orthogonal issue; once you have the container design worked out, threading can be added by your-self on top of that.

In my problem I don't need this container to me <algorithms> -capable. It is only to store data on which numerous threads will work on. Rarely adding or removing elements, mostly changing their content, and reading it. Therefore I don't want a single mutex for whole container. I want one thread to be able to write to one element, while other threads can work with other elements. Single mutex would block whole container just because one thread is working on a single element. I see no other option than to have another container of mutexes: one mutex per element. Is there anything else I can do? With this solution the threading cannot be orthogonal. Or I'm missing something? -- Janek Kozicki |

Thorsten Ottosen wrote:

It seems like a bad idea to mix threading into the container itself.

Unless you're designing lock-free data structures.

If it were desirable to mix the locking with the container, use a locking policy. This would allow no locking, mutexed locking, and perhaps atomic operations when available. Iterators tend to be a pain. How do you propose the iterator would work when another thread is trying to change the container? -----Original Message----- From: Thorsten Ottosen [mailto:thorsten.ottosen@dezide.com] Sent: Tuesday, November 21, 2006 7:16 AM To: boost@lists.boost.org Subject: Re: [boost] [ptr_container] and [multi_index] and [thread] -capable containers ? Janek Kozicki wrote:

Thorsten Ottosen said: (by the date of Tue, 21 Nov 2006 00:03:21 +0100)

I'm still thinking how to best refactor my current containers. They are in bad need for refactoring and I'm still not sure where to go. MultiIndex + PtrContainer are one of alternatives. If it turns out that this is the way to go, I will want to try this task.

Also I'm sure that my new container will have to support threading. I was thinking about something like accessor methods that will lock for reading and lock for writing:

template <T> class my_superb_container {

// only one can write to item 'item_index', no reading allowed T& lock_write(int item_index);

// multiple reads of item 'item_index' are allowed, no writing const T& lock_read(int item_index); }

Lock will be released when leaving current block, in the destructor. (destructor of what? - still thinking about that).

It seems like a bad idea to mix threading into the container itself. Threading should be an orthogonal issue; once you have the container design worked out, threading can be added by your-self on top of that. -Thorsten

Since I can't stop thinking about that, I'll try to describe the most difficult data structure that I have here. Maybe you will have some suggestions. And maybe it will help me to sort the thing out. In my program I am calculating bodies collisions and other kind of interactions. This is a physical simualtion stuff. I have a container (an easier one) with bodies where each body has an integer ID number. And the bodies can interact together, there are various kinds of interaction. And I need to store those interactions in a container. The keys are: - interaction type: each polymorphic interaction type stored in this container is a different kind of interaction. Sometimes I need to interate over all interactions of selected type, thus it becomes one of the keys. This is an integer. - a set of interacting bodies: any number of bodies can interact. Two or more bodies, but very rarely as much as four. - Sometimes I need to iterate over all interactions which involve a selected body or, - check if an interaction of given type between bodies 1, 2 and 3 already exists, then get it, or add it, if it didn't exist. This is a list of integer values (IDs of bodies). If I had only two-body interaction of single type then this could ba a (sparse) two dimensional symmetric matrix. Boost.Graph library treats two-body interaction as a graph edge, and the container used is std::vector<std::set<T> > > which works well for that. An example content of this container could be: interaction Type IDs of bodies involved +---------------------+-------------------------------------- | | (2,3) (2,3,4) (8,11,12,15) (13,14) +---------------------+-------------------------------------- | ElasticContact | X X X +---------------------+-------------------------------------- | MagneticInteraction | X X X +---------------------+-------------------------------------- | . | . | . The 'X' means that there is an instance present. One solution (a bit of pseudocode) could be: multi_index_container< interaction*, indexed_by< ordered_non_unique<member<interaction*,int,&interaction::type> > ordered_unique <member<interaction*,std::set<int>,&interaction::bodies> > // non_unique in fact. But uniqe with respect to &interaction::type. // That's why it's pseudocode

;

But how to make this and get a reasonable performance? And how to make that std::set<int> working? :) (or maybe tr1::hash_set<int>, if there is one) How to iterate over all interactions involving a body with ID 3 of type 1 ? For example I could use lazy deletion (only sets the field as unused), with cleaning invoked from time to time. Performance priorities (from most important, to least important): A)iterating over all elements with the same &interaction::type must be constant access time. B)finding if there is an interaction between (1,2,3) - great if it was constant time (N-dimensional matrix gives that), I guess that log(O) is the best we can have. C)deleting and adding an interaction, again I guess that constant time is not possible. D)iterating over all interactions involving a body with given ID is used less often so can be a bit slower. If you have any insights I'd appreciate that :) -- Janek Kozicki |

Hello Janek, Janek Kozicki <janek_listy <at> wp.pl> writes:

Since I can't stop thinking about that, I'll try to describe the most difficult data structure that I have here. Maybe you will have some suggestions. And maybe it will help me to sort the thing out.

In my program I am calculating bodies collisions and other kind of interactions. This is a physical simualtion stuff.

I have a container (an easier one) with bodies where each body has an integer ID number. And the bodies can interact together, there are various kinds of interaction. And I need to store those interactions in a container. The keys are:

- interaction type: each polymorphic interaction type stored in this container is a different kind of interaction. Sometimes I need to interate over all interactions of selected type, thus it becomes one of the keys. This is an integer.

- a set of interacting bodies: any number of bodies can interact. Two or more bodies, but very rarely as much as four. - Sometimes I need to iterate over all interactions which involve a selected body or, - check if an interaction of given type between bodies 1, 2 and 3 already exists, then get it, or add it, if it didn't exist. This is a list of integer values (IDs of bodies). [...] One solution (a bit of pseudocode) could be:

multi_index_container< interaction*, indexed_by< ordered_non_unique<member<interaction*,int,&interaction::type> >

ordered_unique <member<interaction*,std::set<int>,&interaction::bodies> > // non_unique in fact. But uniqe with respect to &interaction::type. // That's why it's pseudocode

...

;

But how to make this and get a reasonable performance?

Well, your proposed structure has reasonable performance and complies with all your requirements except the ability to iterate on interactions involving a given body. In order to get this extra feature, you might need to set up an extra container like std::[unordered_]multimap<int /* body ID */, interaction*> which is kept in sync with the multi-index container: when an interaction is inserted, the multimap must be fed as many entries as bodies the given interaction involves. I can't think of a more elegant solution than this, which is a pity since one of the key goals of B.MI is to elminate the need to manually maintain this kind of composite structures :( [...]

Performance priorities (from most important, to least important): A)iterating over all elements with the same &interaction::type must be constant access time.

B)finding if there is an interaction between (1,2,3) - great if it was constant time (N-dimensional matrix gives that), I guess that log(O) is the best we can have. C)deleting and adding an interaction, again I guess that constant time is not possible. D)iterating over all interactions involving a body with given ID is used less often so can be a bit slower.

If you use hashed indices instead of ordered ones and also use an unordered_multimap for the additional data structure, you can get the performance you aim for, constant time for A), B), C) and D). HTH, Joaquín M López Muñoz Telefónica, Investigación y Desarrollo

----- Mensaje original ----- De: Janek Kozicki <janek_listy@wp.pl> Fecha: Miércoles, Noviembre 29, 2006 8:36 pm Asunto: Re: [boost] [ptr_container] and [multi_index] ? Para: boost@lists.boost.org [...]

Many thanks, it helps me a lot. The additional data structure maybe will be used later if the performace of D becomes more important. Already a constant time for A,B and C is a really good news.

You assured me that going multi_index is the way to go. Therefore I should work my way through using PtrContainer and MultiIndex together. I guess that it will result in a new kind of container (mosty due to fact that PtrContainer is so different from ''typical'' containers), probably PtrMultiIndex ?

To be honest, I don't think there's any sensible way to merge these two from the outside, i.e. without internal changes to the libraries. One critical problem is that both containers (as most other containers do) reclaim element ownership. A humble substitute for PtrContainer would be to store shared_ptr<Base>s in a multi_index_container. Note that B.MI predefined key extractors allow you to handle (smart) pointers with minimal hassle: typedef multi_index_container< boost::shared_ptr<Base>, indexed_by< // note the key extractor does not mention any shared_ptr; // const_mem_fun automatically dereferences the pointers // to get to the Base& needed ordered_unique<const_mem_fun<Base,int,&Base::get_x> >, ... Of course, you lose many advantages Boost.PtrContainer is designed to provide you with, for instance: * Null pointer handling overhead as compared to shared_ptr, * Indirected interface (http://tinyurl.com/y6t7ja ).

Accessing keys through pointers will require the base class of everything that is stored in the container to contain all the necessary keys.

Not necessarily so: you can resort to const_mem_fun<> to use a virtual function as the key provider: class Base { virtual int get_x()const = 0; ... };

Currently I'm working on something else, so I will not start right now. It waits in my 'queue' :) I guess that the real coding will happen not earlier than in one/two months from now. But in the meantimeif you have some useful thoughts about merging MutliIndex and PtrContainer they are welcome. Maybe with your guidance (the authors of those two libraries) we will make it.

Nevertheless, when I will start this task I'll let you know by asking more specific questions about merging those two.

Good luck with your projects, don't hesitate to come back here for further discussion. Joaquín M López Muñoz Telefónica, Investigación y Desarrollo

Mathias Gaunard wrote:

Janek Kozicki wrote:

...

Is it possible to use those two together? I'm considering storing my polymorphic stuff into ptr_container but vector (or other standard containers) are not enough for my needs.

Using Boost.MultiIndex with Boost.PtrContainer would be great.

As far as I understand it, pointer containers are more efficient than containers of smart pointers because standard containers rely on copy semantics instead of move semantics (currently).

That is to some extend true, though we have seen some cloning smart-pointers posted here on the list that had pretty good efficiency (the one I'm thinking of was a copy-on-write pointer). But the differences are more than that. For example, wirh a move_ptr it's not possible to have containers (that guarantees to be) without nulls; the pointer containers can keep that invariant because they move the object and subsequently remove the pointer from the container. Moving from a standard like container would leave a null sitting there in the middle of the container.

But since we're inside of boost, couldn't multi index be smart enough to not do copying with smart pointers?

I guess it could. I use a move_ptr by Jonthan Turkanis internally in Boost.PtrContainer. -Thorsten