Number of collisions in concurrent_hash_map?

[alexandre_hamez]

Hello everybody,

I currently use the concurrent_hash_map, and, seeing the poor performances of my app, I profiled a little my code and see that 30% of the time is spent if the lookup. So, I was wondering if there is a way to know the number of collisions in the hash map? There is nothing about this in the documentation. I also made some grep into the tbb sources, but I found nothing.

[Anton_M_Intel]

There is no such tool in concurrent_hash_map. You could estimate collisions number by counting the same hash values masked by a 2^x-1 which is just enough to fit your size() items.

[RafSchietekat]

You seem like someone I could persuade to test the alternative implementation for concurrent_hash_map in downloads/contributions (a patch for tbb20_20080408oss_src)...

[Alexey-Kukanov · Accepted solution]

An addition to what Anton said: there is a so-called "performance warning" written by TBB 2.1 concurrent_hash_queue to stderr. The warning is enabled by defining TBB_DO_ASSERT or TBB_PERFORMANCE_WARNINGS macro to a non-zero value. The distribution of items across the hash map is (post-)evaluated when the map is cleared or destroyed, and if it seems bad the warning is issued. The map should have at least 3072 elements; otherwise it is considered too small to judge. Note that absence of the warning does not mean the distribution is good; it just might be not bad enough to deserve a warning. We decided to not make it too zealous because some irregularity in hash value distributionwill always exist.

[alexandre_hamez]

Indeed, defining TBB_PERFORMANCE_WARNINGS shows me that I have a big problem with my hash function :-) Now I know what is my top priority! Thank you! Raf -> What are the main contributions of your patch?

[Alexey-Kukanov]

A good hash function for tbb::concurrent_hash_map should provide uniform distribution in the lowest bits of the hash value. See little more details in this thread. E.g. if an address is directly used as a hash value, the distribution will likely be bad because objects are usually aligned in memory and their lowest bits almost always repeat.

[RafSchietekat]

The patch adds absolute unblockability (if used with well-behaved user-provided hash code and threads that remain available, where TBB's concurrent_hash_map may theoretically also block in weird and mysterious ways), which may or may not be significant for performance (note that unblockability applies to the internal workings of the map, not to the element accessors, of course), while bringing back the assurance, bought for a reduction in the performance of erase, that an accessor provides access to an element of the map and not to what I would call a possible "zombie" while the map already contains a new element with the same key (which may or may not be significant in the real world, so that's for you to judge). Another aspect, concurrent segment growth, is an orthogonal addition.

I'm curious about both laboratory and real-world comparative benchmark results for this version (after the hash code gets fixed, because both implementations rely on a decent hash function to be able to use a power-of-two array size).

(Added) Actually the patch may well provide even significantly better behaviour with a bad hash function (it will not block even if the hash function evaluates to a constant), but that's rather irrelevant, I would say, if you can still intervene.

[Nicolae_P_Intel]

Quoting - Alexey Kukanov (Intel)

An addition to what Anton said: there is a so-called "performance warning" written by TBB 2.1 concurrent_hash_queue to stderr. The warning is enabled by defining TBB_DO_ASSERT or TBB_PERFORMANCE_WARNINGS macro to a non-zero value. The distribution of items across the hash map is (post-)evaluated when the map is cleared or destroyed, and if it seems bad the warning is issued. The map should have at least 3072 elements; otherwise it is considered too small to judge. Note that absence of the warning does not mean the distribution is good; it just might be not bad enough to deserve a warning. We decided to not make it too zealous because some irregularity in hash value distributionwill always exist.

I think it would be useful togive the posibility to the user to reduce/increase the 3072 threshold. What do you think?

[Anton_M_Intel]

Quoting - Nicolae Popovici (Intel)

Quoting - Alexey Kukanov (Intel)

The map should have at least 3072 elements; otherwise it is considered too small to judge.

I think it would be useful togive the posibility to the user to reduce/increase the 3072 threshold. What do you think?

I don't think any preprocessor macro makes sense here. concurrent_hash_map wins a serial container with a lock around it only while holding a couple of thousand elements inside (in simple benchmarks).
We are looking for better algorithms anyway.

[Alexey-Kukanov]

Quoting - Nicolae Popovici (Intel)

I think it would be useful togive the posibility to the user to reduce/increase the 3072 threshold. What do you think?

What for? Making this value much lower does not make much sense, because of significantly reduced accuracy of the statistics; I feel that even this value is rather low. Making it higher does not make much sense either, all keys in the map will be taken into account for distribution estimation. The only reason would be to shut up the warning by increasing the threshold beyond the actual amount of keys, but the TBB_PERFORMANCE_WARNING macro is much more logical way to achieve the same. So what user value such a knob would add?