Take the 2-minute tour ×

I'm looking for a concurrent cache structure. I'm using the PPL from Microsoft so I have the concurrent_unordered_map class, but it doesn't quite seem to be what I need. I've got a hash value and I need to associate it with a pointer type, or return that pointer if it was already in the cache. I'm not using LRU or MRU cache strategy and values wil never be removed, so it's more like a concurrent memoize.

Would it be simpler to just lock an existing std::unordered_map?

share|improve this question
What exactly is wrong with using concurrent_unordered_map? The unordered map is a hash structure and you say you have a hash value, so... –  Zan Lynx Jul 8 '11 at 18:10
@Zan Lynx: Because the interface does not offer insertion only if not present in a single atomic operation. It would not be thread-safe to guarantee only one insertion based on the existing interface. –  Puppy Jul 10 '11 at 20:46
That is a very important piece of information that should be part of your question and probably the title. –  Zan Lynx Jul 11 '11 at 1:23
I suppose it is in the question if read carefully, but it didn't jump out at me. –  Zan Lynx Jul 11 '11 at 1:24

1 Answer 1

up vote 1 down vote accepted

I don't know about the Microsoft PPL. I just looked at the Intel Thread Building Blocks header files for Intel's concurrent_unordered_map and its insert function returns false as the second part of the returned pair when the key is already in the map.

This seems to be exactly what you need. Do the insert and if it returns true then it was a new insert. If it returns false then it was already in the map.

Edit: There seems to be some confusion here. I didn't mean that you should always run the insert. I meant that you should look for the value and if it is missing then attempt the insert. Two or more threads may occasionally race on the insert and so work will be duplicated, but this should be a rare event.

share|improve this answer
No, that's not what I need, because by the time I get a duplicate insert, it's too late to get the behaviour I need. –  Puppy Jul 11 '11 at 11:59
@DeadMG: Then I guess you have to explain what you need much more carefully. –  Zan Lynx Jul 11 '11 at 14:46
It's a concurrent memoize. Memoizing is defined as only running the function once. Inserting twice would be running the function twice. –  Puppy Jul 13 '11 at 18:23
@DeadMG: Unless your function has side effects, which it probably shouldn't, then who cares if you occasionally run it twice? –  Zan Lynx Jul 13 '11 at 20:24
@DeadMG: Also, it seems to me there's a simple solution to the problem. Insert the memoized key with a place-holder value that indicates "computation in progress". Threads that pull that value then pile up on a condition variable/semaphore until the result is ready. More complicated but probably the only way to get what you want. –  Zan Lynx Jul 14 '11 at 19:13

Your Answer


