Intel® oneAPI Threading Building Blocks
Ask questions and share information about adding parallelism to your applications when using this threading library.

concurrent_hash_map::erase() returns bool?

james_b1
Beginner
545 Views
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.
0 Kudos
10 Replies
jimdempseyatthecove
Honored Contributor III
545 Views
>>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
0 Kudos
SergeyKostrov
Valued Contributor II
545 Views
>>...
>>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
0 Kudos
RafSchietekat
Valued Contributor III
545 Views
"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).
0 Kudos
Anton_M_Intel
Employee
545 Views
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.
0 Kudos
SergeyKostrov
Valued Contributor II
545 Views
...
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.

0 Kudos
RafSchietekat
Valued Contributor III
545 Views
"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).
0 Kudos
Anton_M_Intel
Employee
545 Views
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.
0 Kudos
RafSchietekat
Valued Contributor III
545 Views
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.
0 Kudos
Anton_M_Intel
Employee
545 Views
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.
0 Kudos
RafSchietekat
Valued Contributor III
545 Views
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...
0 Kudos
Reply