Bug in tbb::concurrent_unordered_multimap? Entries get lost even if single-threaded

Question

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.

League

Also, if you do an ordered insert (i / 10, i instead of i % 10, i), everything is fine. – League

What happens if you declare volatile size_t one = 1; and return one instead of return 1? I'm curious if something is being optimized away because all hashes are equal. – Interrelate

Doesn't change anything. Also, I compiled with -O0. – League

Update: After looking into the TBB code, I am quite sure that this is a bug with internal_equal_range and multimapping. Waiting for Intel to confirm. – League

Answer 1

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...)

Centralize