concurrent_hash_map::erase() returns bool?

concurrent_hash_map::erase() returns bool?

Bild des Benutzers james_b

Hiya,

I see that erase() returns true or false, depending on whether the item was erase by 'particularly this call'.

Does anyone know why this might return false? Perhaps the item might already have been removed?

I'm just need to find out whether I can call erase() and ignore the return, or whether I need to loop until it returns true to make sure the item really is erased.

Any advice appreciated!

Cheers.

11 Beiträge / 0 neu
Letzter Beitrag
Nähere Informationen zur Compiler-Optimierung finden Sie in unserem Optimierungshinweis.
Bild des Benutzers jimdempseyatthecove

>>I'm just need to find out whether I can call erase() and ignore the return, or whether I need to loop until it returns true to make sure the item really is erased.

This depends on your program's requirements.

If multiple threads could (potentially) erase the same entry, and if upon (successfully) erasing an entry you were to perform an ancillary operation relating to that entry, then you would (may) only want to perform that ancillary operation once. Having the bool return true for only one thread in multiple threads concurrent erase operations to the same entry resolves this issue. When you have no such dependency (ancillary operation) you can ignore the return value.

Jim Dempsey

www.quickthreadprogramming.com
Bild des Benutzers Sergey Kostrov

>>...
>>Does anyone know why this might return false? Perhaps the item might already have been removed?
>>...

It returns false when a key is not found and amask not changed. Please take a look at theheader file
'concurrent_hash_map.h' for more details.

This is how it looks like:

...
if( !n ) { // not found, but mask could be changed
if( check_mask_race( h, m ) )
goto restart;
return false;
}
...

Best regards,
Sergey

Bild des Benutzers Raf Schietekat

"It returns false when a key is not found and amask not changed."
That's purely an implementation issue. The takeaway is that erase() will not spuriously return false (in the sense that the element is there but somehow not removed by the current thread), so there is no need to loop until true in that sense (unless you're expecting another thread to add it and you just want to waste some CPU time or worse by busy-waiting for that to happen). There are/were some tricky issues about the timing of logical removal of an element (unless my memory fails me, an element could be erased by one thread while another thread was still holding an accessor to it, and even more complicated scenarios), but those may have changed since I last had a close look (I don't remember what version that was), and there are no guarantees about the timing of executing the element's destructor (unless that too has changed). You may want to compare with concurrent_unordered_map.

(Added after #5) This was only in addition to Jim's essential answer of course, and #5 clarifies that the accessor still does not lock the element into the map (apparently I had repressed the non-acceptance of a proposal of mine that would have changed this).

Bild des Benutzers Anton Malakhov (Intel)

Jim's answer is on the target (thanks!). I'd add that I know no use cases where the said loop is necessary because erase() does not provide a global state, it just removes a key/value pair at the given moment of time after which anything can happen in concurrent environment.
Sergey, your answer can confuse by both parts because'mask' isunrelated implementation detail and "not found" is internal comment. The letter is fine for erase(by_key) but might look strange for erase(by_accessor). Let me clarify it: there is a difference between lifetime of an instance of akey/value pair and its visibility for the container. The accessors protect a pair from concurrent destruction&deallocation but can do nothing to prevent concurrent exclusion from container's bucket. Thus even when a thread owns an element, i.e.has a valid pointer through an accessor, another thread can concurrently exclude it from the container, and erase(by_accessor) called from the first thread will return false despite of having the pointer.

Bild des Benutzers Sergey Kostrov
Quoting Anton Malakhov (Intel) ...
Sergey, your answer can confuse by both parts because'mask' isunrelated implementation detail and "not found" is internal comment. The letter is fine for erase(by_key) but might look strange for erase(by_accessor). Let me clarify it: there is a difference between lifetime of an instance of akey/value pair and its visibility for the container. The accessors protect a pair from concurrent destruction&deallocation but can do nothing to prevent concurrent exclusion from container's bucket. Thus even when a thread owns an element, i.e.has a valid pointer through an accessor, another thread can concurrently exclude it from the container, and erase(by_accessor) called from the first thread will return false despite of having the pointer.

Thank you for the explanations.

Bild des Benutzers Raf Schietekat

"The accessors protect a pair from concurrent
destruction&deallocation but can do nothing to prevent concurrent
exclusion from container's bucket."
This is documented (Open Source Documentation/Reference Manual revision 1.28 as just downloaded) for erase(const Key&), but it should also be documented for erase(const_accessor&); erase(accessor&) might mention for clarity that this does not apply here because there are no other current accessors to the same pair. Furthermore, "Concurrent insertion of the same key creates a new pair in the table." (for 2 overloads) is misleading because this is about insertion during the lifetime of the (const_)accessor, not necessarily concurrently with the erase() call (it even applies when the insertion happens in the same thread after the erase).

Bild des Benutzers Anton Malakhov (Intel)

Thanks Raf for the clarification suggestion, I sent it for the documentation update. Your perception of the second part seems not right. Will the following addition fix it: "Concurrent insertion of the same key creates a
new pair in the table which can temporarily co-exist with being destroyed one." ? Here, "concurrent" applies exactly to erase call (not to accessor lifetime) because destructor is executed out of the bucket lock which forms a window where another pair can be created and inserted into the table. Before the call to erase, a new pair cannot be inserted because of the nature of the map container. Of course, it can legally be executed after the erase - nothing wrong in the original wording then.

Bild des Benutzers Raf Schietekat

You couldn't really tell whether the new pair was inserted during or right after the call to erase(), so "concurrent" seems irrelevant at best. The surprise is that the new pair can be inserted before the old accessor is destroyed.

Bild des Benutzers Anton Malakhov (Intel)

Hm.. Isn't it clear that accessor passed to erase() becomes empty, i.e. pointing to nothing? Or did you mean "old pair" instead? Regarding definition of "concurrent", what do you propose instead? IMO, it is fine that concurrent is so vague. The idea of the proposed note is to say that there is a possibility for pairs with the same key temporarly existing at the same time. We don't actually need more precision here.

Bild des Benutzers Raf Schietekat

Regarding what's "clear" or not, my assumption would be that the accessor locks the pair inside the map, and that's not true, so... Now erase() takes the pair out of the map, and that's all. You can still use it to store and retrieve values in the almost-dead pair, until the (last?) accessor goes away. Even then I don't know anymore if destruction is synchronous? The thing is that a new pair with the same key can be entered into the map while the/an accessor to the old pair is still alive, and nobody can tell whether that's during the erase() or right after it, so "concurrently" is misleading, because you can even do erase() and insert() in succession in the same thread. It's alright if you already know that, but then you don't need the documentation...

Melden Sie sich an, um einen Kommentar zu hinterlassen.