Joaquín Mª López Muñoz ha scritto:
Hello Alberto,
Alberto Ganesh Barbati ha escrito:
That would make the interface inefficient, because the search would be performed twice. I would go with:
f.find(x); f.insert(h, x);
where h is the value returned by f.find(x). This would exploit the two-parameter insert() provided by std::set (and even tr1::unordered_set, for what matters).
The interface would have to be a little more complicated than that, as find() does not return a useful handle (iterator) when the search was unsuccesful, it merely returns end(). We'd need to use something like lower_bound() for ordered associative containers. For unordered associative containers the situation would be even worse: although these containers formally accept a hint parameter, actually this is useless in containers with unique keys when it is known that no equivalent element exists (which is the case here). Furthermore, the only memfun usable to get a hint operator would be equal_range (no lower_bound in unordered associative containers), and this introduces a irregularity with the ordered case.
That is indeed correct. I was too hasty in my proposal.
All in all, I think using a hint is a lot of hassle for the small potential benefit it could bring. However, the only way to know for sure, of course, is measuring it.
I agree and the benefit could greatly depend on the actual container used.
which would become (using promote() instead of the very risky unlock/lock):
readwrite_lock l(mutex); l.read_lock(); if(h=find(x))return h; else{ l.promote(); h=insert(h, x); }
[promote() would be unlock_upgradable_and_lock() under the terminology of the current C++0x proposal, http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2006/n2094.html , if I understand it right.]
Yes, promote() was the name used in Boost.Thread. The new name is more verbose and much clearer.
Why is unlock/lock risky? If I'm getting it right (although I admit to be no expert on threading issues), unlock_upgradable_and_lock() is equivalent to unlocking and then exclusively locking with some additional guarantees, namely that the thread will be the first to obtain exclusive access. The problem is that this can fail (if two threads request the privilege at the same time), hence unlock_upgradable_and_lock() may throw.
The fact is that if another thread gets write/exclusive access before "our" thread, the hint may become invalid and can no longer be used reliably.
I believe you should consider using the find/insert approach immediately and not wait for readwrite locks. If you do so, you may upgrade to readwrite locks later once they become available, while sticking to the insert-only approach will make the upgrade more difficult because a change in the concept framework might break existing code (for example think about uses of assoc_container_factory with a user-provided container).
One way to implement this could be:
typename LockingPolicy::lock_type l(mutex); if(h=find(x))return h; else{ LockingPolicy::promote(l); h=insert(h, x); }
requiring the locking policy functions to provide *at least* read lock after the lock construction and to ensure write lock after a call to promote(). For regular mutexes promote() can simply be a no-op, of course. If the users had their own non-boost (and hopefully not buggy) read write mutex classes they could plug them in easily.
I don't think making the upgrade later on would be so difficult: the plan is not to *redefine* the concepts, but rather to provide extensions of them, so that older code will conform to the primitive concepts and new code can benefit of read/write stuff merely by appropriate tagging (for instance, marking a factory as a lookupfactory rather than a plain old factory, etc.) Your approach (making all mutexes look like read/write with promote a no-op where appropriate) is IMHO a little more inelegant than just having a hierarchy of concepts (just like, for instance, C++ does with iterator categories: non-random access iterators are not required to provide, say, a no-op operator[] just for conformity reasons).
After reading your answer I realized that probably the best way to benefit from any complex locking strategy without compromising the general case is to leave both the decision and the actual algorithm to factory itself. Therefore I make a different proposal, much simpler, something in line with: static handle_type insert(const Value& x) { lock_type lock(mutex()); return handle_type(factory().insert(entry_type(x), lock)); } by passing the lock to the insert() function, the factory has the opportunity to ignore it, favoring a simple locking strategy, or to use it to perform some more complex strategy. By overloading insert() the factory could even provide different strategies according to the type of the lock. Of course that would create problems with "simple" factories like hashed_factory_class and set_factory that don't expect the extra lock argument. This could solved by giving to class handle_factory_adaptor the responsibility to drop the lock argument unless explicitly requested by the user. How to let the user request the extra lock parameter is yet to be determined, one way might be to declare a new tag class advanced_factory_marker that derives from factory_marker. Does it make sense? Ganesh