parallel_for an unordered_map

[CliveWongTohSoon]

Is it possible to use unordered_map in parallel_for? I have tried using the following:

tbb::parallel_for(my_map.begin(), my_map.end(), [&](std::pair<uint16_t, std::vector<src_weight>> x) {
    // My code here
});

but I got a compilation error saying

error: no matching conversion for static_cast from 'int' to     'std::__1::__hash_map_const_iterator<std::__1::__hash_const_iterator<std::__1::__hash_node<std::__1::__hash_value_type<unsigned short,
      std::__1::vector<src_weight, std::__1::allocator<src_weight> > >, void *> *> >'

I wonder is there any trick to use unordered_map with tbb::parallel_for?

[jjd06]

Since you presumably want safe concurrent access to (elements of) my_map, you should probably look into concurrent_unordered_map, which happens to have the range method I think you'll need for parallel_for.

[CliveWongTohSoon]

I tried changing the unordered_map type to using concurrent_unordered_map, and use the range method in the parallel_for.

// At the beginning of the code
typedef tbb::concurrent_unordered_map<uint16_t, std::vector<src_weight>> myUnorderedMap;

// In execute
tbb::parallel_for(dst_src_map.range(), [&](const myUnorderedMap::range_type &r) {
    for (myUnorderedMap::iterator x = r.begin(); x != r.end(); x++) {
        // My code here
    }
});

However, I still get errors:

error: no matching function for call to object of type 'const (lambda at
      src/layers/par_for_clustered.cpp:63:48)'
            my_body( r ); 
            ^~~~~~~
/usr/local/include/tbb/partitioner.h:439:19: note: in instantiation of member function
      'tbb::interface9::internal::start_for<tbb::interface5::internal::concurrent_unordered_base<tbb::interface5::concurrent_unordered_map_traits<unsigned
      short, std::__1::vector<src_weight, std::__1::allocator<src_weight> >, tbb::interface5::internal::hash_compare<unsigned short,
      tbb::tbb_hash<unsigned short>, std::__1::equal_to<unsigned short> >, tbb::tbb_allocator<std::__1::pair<const unsigned short,
      std::__1::vector<src_weight, std::__1::allocator<src_weight> > > >, false> >::const_range_type, (lambda at
      src/layers/par_for_clustered.cpp:63:48), const tbb::auto_partitioner>::run_body' requested here
            start.run_body( range ); // simple partitioner goes always here
                  ^
/usr/local/include/tbb/partitioner.h:257:16: note: in instantiation of function template specialization
      'tbb::interface9::internal::dynamic_grainsize_mode<tbb::interface9::internal::adaptive_mode<tbb::interface9::internal::auto_partition_type>
      >::work_balance<tbb::interface9::internal::start_for<tbb::interface5::internal::concurrent_unordered_base<tbb::interface5::concurrent_unordered_map_traits<unsigned
      short, std::__1::vector<src_weight, std::__1::allocator<src_weight> >, tbb::interface5::internal::hash_compare<unsigned short,
      tbb::tbb_hash<unsigned short>, std::__1::equal_to<unsigned short> >, tbb::tbb_allocator<std::__1::pair<const unsigned short,
      std::__1::vector<src_weight, std::__1::allocator<src_weight> > > >, false> >::const_range_type, (lambda at
      src/layers/par_for_clustered.cpp:63:48), const tbb::auto_partitioner>,
      tbb::interface5::internal::concurrent_unordered_base<tbb::interface5::concurrent_unordered_map_traits<unsigned short,
      std::__1::vector<src_weight, std::__1::allocator<src_weight> >, tbb::interface5::internal::hash_compare<unsigned short, tbb::tbb_hash<unsigned
      short>, std::__1::equal_to<unsigned short> >, tbb::tbb_allocator<std::__1::pair<const unsigned short, std::__1::vector<src_weight,
      std::__1::allocator<src_weight> > > >, false> >::const_range_type>' requested here
        self().work_balance(start, range);
               ^
/usr/local/include/tbb/parallel_for.h:143:22: note: in instantiation of function template specialization
      'tbb::interface9::internal::partition_type_base<tbb::interface9::internal::auto_partition_type>::execute<tbb::interface9::internal::start_for<tbb::interface5::internal::concurrent_unordered_base<tbb::interface5::concurrent_unordered_map_traits<unsigned
      short, std::__1::vector<src_weight, std::__1::allocator<src_weight> >, tbb::interface5::internal::hash_compare<unsigned short,
      tbb::tbb_hash<unsigned short>, std::__1::equal_to<unsigned short> >, tbb::tbb_allocator<std::__1::pair<const unsigned short,
      std::__1::vector<src_weight, std::__1::allocator<src_weight> > > >, false> >::const_range_type, (lambda at
      src/layers/par_for_clustered.cpp:63:48), const tbb::auto_partitioner>,
      tbb::interface5::internal::concurrent_unordered_base<tbb::interface5::concurrent_unordered_map_traits<unsigned short,
      std::__1::vector<src_weight, std::__1::allocator<src_weight> >, tbb::interface5::internal::hash_compare<unsigned short, tbb::tbb_hash<unsigned
      short>, std::__1::equal_to<unsigned short> >, tbb::tbb_allocator<std::__1::pair<const unsigned short, std::__1::vector<src_weight,
      std::__1::allocator<src_weight> > > >, false> >::const_range_type>' requested here
        my_partition.execute(*this, my_range);
                     ^
/usr/local/include/tbb/parallel_for.h:56:9: note: in instantiation of member function
      'tbb::interface9::internal::start_for<tbb::interface5::internal::concurrent_unordered_base<tbb::interface5::concurrent_unordered_map_traits<unsigned
      short, std::__1::vector<src_weight, std::__1::allocator<src_weight> >, tbb::interface5::internal::hash_compare<unsigned short,
      tbb::tbb_hash<unsigned short>, std::__1::equal_to<unsigned short> >, tbb::tbb_allocator<std::__1::pair<const unsigned short,
      std::__1::vector<src_weight, std::__1::allocator<src_weight> > > >, false> >::const_range_type, (lambda at
      src/layers/par_for_clustered.cpp:63:48), const tbb::auto_partitioner>::execute' requested here
        start_for( const Range& range, const Body& body, Partitioner& partitioner ) :
        ^
/usr/local/include/tbb/parallel_for.h:92:67: note: in instantiation of member function
      'tbb::interface9::internal::start_for<tbb::interface5::internal::concurrent_unordered_base<tbb::interface5::concurrent_unordered_map_traits<unsigned
      short, std::__1::vector<src_weight, std::__1::allocator<src_weight> >, tbb::interface5::internal::hash_compare<unsigned short,
      tbb::tbb_hash<unsigned short>, std::__1::equal_to<unsigned short> >, tbb::tbb_allocator<std::__1::pair<const unsigned short,
      std::__1::vector<src_weight, std::__1::allocator<src_weight> > > >, false> >::const_range_type, (lambda at
      src/layers/par_for_clustered.cpp:63:48), const tbb::auto_partitioner>::start_for' requested here
                start_for& a = *new(task::allocate_root(context)) start_for(range,body,partitioner);
                                                                  ^
/usr/local/include/tbb/parallel_for.h:202:70: note: in instantiation of member function
      'tbb::interface9::internal::start_for<tbb::interface5::internal::concurrent_unordered_base<tbb::interface5::concurrent_unordered_map_traits<unsigned
      short, std::__1::vector<src_weight, std::__1::allocator<src_weight> >, tbb::interface5::internal::hash_compare<unsigned short,
      tbb::tbb_hash<unsigned short>, std::__1::equal_to<unsigned short> >, tbb::tbb_allocator<std::__1::pair<const unsigned short,
      std::__1::vector<src_weight, std::__1::allocator<src_weight> > > >, false> >::const_range_type, (lambda at
      src/layers/par_for_clustered.cpp:63:48), const tbb::auto_partitioner>::run' requested here
    internal::start_for<Range,Body,const __TBB_DEFAULT_PARTITIONER>::run(range,body,__TBB_DEFAULT_PARTITIONER());
                                                                     ^
src/layers/par_for_clustered.cpp:63:14: note: in instantiation of function template specialization
      'tbb::parallel_for<tbb::interface5::internal::concurrent_unordered_base<tbb::interface5::concurrent_unordered_map_traits<unsigned short,
      std::__1::vector<src_weight, std::__1::allocator<src_weight> >, tbb::interface5::internal::hash_compare<unsigned short, tbb::tbb_hash<unsigned
      short>, std::__1::equal_to<unsigned short> >, tbb::tbb_allocator<std::__1::pair<const unsigned short, std::__1::vector<src_weight,
      std::__1::allocator<src_weight> > > >, false> >::const_range_type, (lambda at src/layers/par_for_clustered.cpp:63:48)>' requested here
        tbb::parallel_for(dst_src_map.range(), [&](const myUnorderedMap::range_type &r) {
             ^
src/layers/par_for_clustered.cpp:63:48: note: candidate function not viable: no known conversion from
      'tbb::interface5::internal::concurrent_unordered_base<tbb::interface5::concurrent_unordered_map_traits<unsigned short,
      std::__1::vector<src_weight, std::__1::allocator<src_weight> >, tbb::interface5::internal::hash_compare<unsigned short, tbb::tbb_hash<unsigned
      short>, std::__1::equal_to<unsigned short> >, tbb::tbb_allocator<std::__1::pair<const unsigned short, std::__1::vector<src_weight,
      std::__1::allocator<src_weight> > > >, false> >::const_range_type' to 'const myUnorderedMap::range_type' for 1st argument
        tbb::parallel_for(dst_src_map.range(), [&](const myUnorderedMap::range_type &r) {
                                               ^
1 error generated.
make: *** [bin/run_network] Error 1

It appears to be the incompatible type for my first arg dst_src_map.range() and second arg myUnorderedMap::range_type &r. I'm not so sure how to properly give them the right type, or do they need to be instantiated. Any hint?

[jjd06]

I couldn't find any examples in the docs of using concurrent_unordered_map with parallel_for, but I did find this with concurrent_hash_map instead, which should be very similar. Does that help?

[CliveWongTohSoon]

I still couldn't find a way to make concurrent_unordered_map work with parallel_for. A workaround I made was to copy the unordered_map to a vector, and use parallel_for to parallelise over the vector.

[ThunderMikey]

If all we are doing is mapping some synapse destination numbers, IMO, vector is more efficient than map because there is more overhead for allocating (key, value) pairs in mapping.