My understanding is that tbb::concurrent_unordered_multimap
should behave like std::unordered_multimap
if I am using only one thread. However, in this example, it does not:
#include "tbb/concurrent_unordered_map.h"
#include <iostream>
#include <unordered_map>
struct myhash {
size_t operator()(const int& a) const {
return 1;
}
};
int main() {
tbb::concurrent_unordered_multimap<int, int, myhash> tbbidx;
std::unordered_multimap<int, int, myhash> stdidx;
for(int i = 0; i < 100; ++i) {
tbbidx.insert(std::make_pair(i % 10, i));
stdidx.insert(std::make_pair(i % 10, i));
}
std::cout << "tbb size " << tbbidx.size() << std::endl;
std::cout << "tbb count " << tbbidx.count(0) << std::endl;
std::cout << "std size " << stdidx.size() << std::endl;
std::cout << "std count " << stdidx.count(0) << std::endl;
}
The result is this:
tbb size 100
tbb count 1
std size 100
std count 10
If I remove myhash
, I get the correct result. The way I understand hashmaps, however, is that a horrible hash function should only affect the performance, not the correctness as long as the function returns the same value if x==y
.
mdsl,
The problem is in internal_insert()
. The reason i / 10
worked where i % 10
did not was the order the items were inserted into the multimap, which is a symptom of the bug. internal_insert
did not do a key-equality comparison, so every insertion was at the end of the list (all the hashes were equal, so the method just walked to the end.) When i / 10
was used, all the 0 keys were inserted, then all the 1 keys, and so on. internal_equal_range
does check the equality of the keys, and would correctly find then end of the range.
Thank you very much for finding the bug. I am adding a "degenerate hash" unit test, and I still have to figure why our validators didn't catch the out-of-order list.
Regards, Chris
(Sorry I got the key equation wrong...)
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With