Hello Alberto, Alberto Ganesh Barbati ha escrito:
JoaquÃn Mª López Muñoz ha scritto:
[...]
This idea is very interesting and I will definitely pursue it. A complication of using read/write locks is that these do not fit well in the current concept framework: a factory f is expected to have the following interface:
f.insert(x); f.erase(h);
where both expressions are *externally* guarded by a regular lock. The problem is that f.insert(x) does lookup and optional insertion in one fell swoop, and thus does not provide the necessary granularity to use a read/write lock. Instead, we'd need something like:
f.find(x); f.insert(x);
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. 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.
so that we can follow this protocol:
readwrite_lock l(mutex); l.read_lock(); if(h=find(x))return h; else{ l.unlock(); l.write_lock(); h=insert(x); }
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.] 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. Given that we don't require the kind of guarantees provided by unlock_upgradable_and_lock(), and since dealing with a throwing operation is always a mess, I'd rather go with simple unlock/lock. But then again I'm no threading expert, if there's some problem in my analysis I'd be glad to be told.
An approach to convering both simple and read/write locks would be to extend the concepts "Locking Policy" (http://tinyurl.com/ypvy4l ) and "Factory" (http://tinyurl.com/2er6dl ) to "ReadWrite Locking Policy" and "Lookup Factory", respectively, and only when the components specified both conform to the extension concepts would we internally follow the readwrite protocol instead of the simple one. I think I can work this out, but I'd prefer to put this in the "Future work" section rather than trying to implement it immediately, so as to gain some more feedback and wait for read/write locks to be brought back into Boost (they were removed due to an implementation bug, see http://tinyurl.com/2clcr9 ).
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).
Just my two eurocent,
Ganesh
Thank you for your elaborate comments. I'd be glad if you could submit a full review! Best, Joaquín M López Muñoz Telefónica, Investigación y Desarrollo