concurrent_ordered_map OR iterating concurrent_hash_map in order

[Yumo_J_]

Hi, why there is no such thing as ordered map in TBB?

Is it something which can be achieved by existing maps? As far as I know, concurrent_hash_map iteration is not in the insertion order. For one of the implementation, we would like to remove old object without iterating through millions of object. Queue is definitely not the answer as we are looking for map with find functionalities. 

Thanks for any help.

[RafSchietekat]

I have "no idea" about your first question...

But even with an ordered map, you still wouldn't be able to iterate based on age (unless if that is the order of the map, and even then there are concurrency concerns).

Any objections to using 2 containers in tandem (a map and a queue)?

[Yumo_J_]

Thanks Raf, I should have used word 'idle' instead of 'old'.

In our current implementation, we maintain a hash table and a linked-list and every time an object is updated, object is moved to the back of the list. We then periodically check for 'not in use' objects from the front of the list and remove if requires. 

As you suggested, we thought of using concurrent_queue but it doesn't allow moving the object from middle of the queue to front or back like linked list and hence we can't use queue. 

[jimdempseyatthecove]

Why not use only the hash table and add to your object a "when last updated" member variable. This will remove the necessity of lock list or CAS/DCAS operations used to maintain the linked list. Your periodic stale data remover task can traverse the hash table removing stale entries.

Jim Dempsey

[RafSchietekat]

So, concurrent garbage collection: wrong language! :-)

To get something quick, although not necessarily the most efficient solution, you could of course put timestamps in both the map and the queue. Whenever the element value is updated, also update the timestamp (like Jim suggested). However, because you cannot concurrently iterate through a TBB map that knows how to delete entries, you would use the queue to poll the entries in the map least recently checked, and then you either delete both entries or recycle the element in the queue (with the timestamp indicating when the check happened, or the minimum of the timestamp in the map and a global queue timestamp that is updated as appropriate). You can pause the polling when the frontmost element is not old enough to be removed. As the allowed "age" grows, the fraction of checks that result in deletions grows, and the strategy becomes more efficient, so you'll have to tune that. Note that you wouldn't be doing anything to the queue for an update, so as the number of updates before an element is retired grows you also cross the level of efficiency of that linked list you were using.

Just an idea, let us know what you think...

(Added) Obviously, both the "As" and "Note" sentences above are about larger maximum age leading to increased efficiency, with as the opposing force a larger map and queue, so that's the compromise you have to make, assuming that the update rate is fixed.

[jimdempseyatthecove]

>> because you cannot concurrently iterate through a TBB map that knows how to delete entries,

The iteration is only performed by the single task that deletes the old entries (and deletes are only performed by this single task). It should be thread safe to concurrently perform this operation. While there may not be a formal member function to do this, it does not preclude the user from adding this function. Then if others find this useful, they can petition for the function to become included in the distribution.

Jim Dempsey

[RafSchietekat]

jimdempseyatthecove wrote:

The iteration is only performed by the single task that deletes the old entries (and deletes are only performed by this single task).

Even with this imposed limitation on deleting, other threads may still concurrently add elements to the map, so that wouldn't work.

[jimdempseyatthecove]

>>Even with this imposed limitation on deleting, other threads may still concurrently add elements to the map, so that wouldn't work.

There is nothing wrong with that.

Assume you have a TBB map... that has a delete function.
Assume you timestamp the add/modify entries.
Your single task that periodically searches the map for old entries using a back door (I suppose you could implement operator[] until formal method is implemented), obtains the timestamp, if stale, obtains the key, then performs the formal delete operation using the key. Next continues.

Jim Dempsey

[RafSchietekat]

Let's keep it real.