Reduce on hashmaps

[Sensei_S_]

Dear all, 

I am now trying to use a parallel_reduce on a concurrent_hash_map, always with lambdas. My hashmap is very basic, maps strings to integers, however, I am not able to compile:

    // Handy 
    typedef tbb::concurrent_hash_map<std::string, std::size_t> hashtype;
    typedef tbb::blocked_range<hashtype::iterator> rangetype;
    
    hashtype tmp;
    
    typename hashtype::accessor accessor;
    
    std::string k;
    
    k = "AAAA";
    tmp.insert(accessor, k);
    accessor->second = 10;

    k = "BBBB";
    tmp.insert(accessor, k);
    accessor->second = 4;

    k = "ABCD";
    tmp.insert(accessor, k);
    accessor->second = 7;

    
    // Compute the sum
    auto sum = tbb::parallel_reduce(rangetype(tmp.begin(), tmp.end()),
                                    0,
                                    [](rangetype &r, std::size_t init) -> std::size_t
                                    {
                                        
                                        std::size_t q = init;
                                        for (auto &p : r)
                                        {
                                            q += p.second;
                                        }
                                        return q;

// THE FOLLOWING WASN'T THE PROBLEM, I THINK
//                                        return std::accumulate(r.begin(), r.end(), init,
//                                                               [&r, &init](const hashtype::value_type &p) -> std::size_t
//                                                               {
//                                                                   return init + p.second;
//                                                               });
                                    },
                                    std::plus<std::size_t>());
    

The errors regard some problems with the empty() function, so I am doing something wrong here (obviously!).

/usr/local/include/tbb/blocked_range.h:82:42: error: invalid operands to binary expression ('const tbb::interface5::internal::hash_map_iterator<tbb::interface5::concurrent_hash_map<std::__1::basic_string<char>, unsigned long, tbb::tbb_hash_compare<std::__1::basic_string<char> >, tbb::tbb_allocator<std::__1::pair<std::__1::basic_string<char>, unsigned long> > >, std::__1::pair<const std::__1::basic_string<char>, unsigned long> >' and 'const tbb::interface5::internal::hash_map_iterator<tbb::interface5::concurrent_hash_map<std::__1::basic_string<char>, unsigned long, tbb::tbb_hash_compare<std::__1::basic_string<char> >, tbb::tbb_allocator<std::__1::pair<std::__1::basic_string<char>, unsigned long> > >, std::__1::pair<const std::__1::basic_string<char>, unsigned long> >')
    bool empty() const {return !(my_begin<my_end);}
                                 ~~~~~~~~^~~~~~~

As you can see, I've also tried to remove the call to std::accumulate, trying to exclude that as the culprit. I believe I can say that it isn't really the problem here.

Can you help me?

Thanks!

[Vladimir_P_1234567890]

I think that blocked_range uses operator<() which is not implemented for concurrent_hash_map.

--Vladimir

[Vladimir_P_1234567890 · Accepted solution]

concurrent_hash_map has own ranges implementation.

change lines 24-27 to

    // Compute the sum
    auto sum = tbb::parallel_reduce(tmp.range(),
        0,
        [] (hashtype::range_type &r, std::size_t init) -> std::size_t

More details https://www.threadingbuildingblocks.org/docs/help/hh_goto.htm#reference/containers_overview/concurrent_hash_map_cls/parallel_iteration_container.htm

--Vladimir

[Sensei_S_]

Thanks Vladimir, I think I'm still not there though...

    // Handy range type
    typedef tbb::concurrent_hash_map<std::string, std::size_t> hashtype;
    typedef tbb::blocked_range<hashtypeZ::iterator> rangetype;
    
    hashtype tmp;
    
    typename hashtype::accessor accessor;
    
    std::string k;
    
    k = "AAAA";
    tmp.insert(accessor, k);
    accessor->second = 10;
    
    k = "BBBB";
    tmp.insert(accessor, k);
    accessor->second = 4;
    
    k = "ABCD";
    tmp.insert(accessor, k);
    accessor->second = 7;

    
    // Serial code
    std::size_t sum = std::accumulate(tmp.begin(), tmp.end(), 0,
                                      [](std::size_t s, const hashtype::value_type &p)
                                      {
                                          return s + p.second;
                                      });
    
    // Compute the sum of all frequencies
    sum = tbb::parallel_reduce(tmp.range(),
                                    0,
                                    [](rangetype &r, std::size_t init) -> std::size_t
                                    {
                                        
                                        std::size_t q = init;
                                        for (const auto &p : r)
                                        {
                                            q += p.second;
                                        }
                                        return q;
                                        //                                        return std::accumulate(r.begin(), r.end(), init,
                                        //                                                               [&r, &init](const hashtype::value_type &p) -> std::size_t
                                        //                                                               {
                                        //                                                                   return init + p.second;
                                        //                                                               });
                                    },
                                    std::plus<std::size_t>());

But now I'm getting another error:

/usr/local/include/tbb/parallel_reduce.h:322:24: error: no matching function for call to object of type 'const (lambda at /Users/sensei/Documents/Projects/sequence/sequence/sequence/assembler/lmf_graph.cpp:70:37)'
            my_value = my_real_body(range, const_cast<const Value&>(my_value));
                       ^~~~~~~~~~~~
/usr/local/include/tbb/parallel_reduce.h:151:37: note: in instantiation of member function 'tbb::internal::lambda_reduce_body<tbb::interface5::internal::hash_map_range<tbb::interface5::internal::hash_map_iterator<tbb::interface5::concurrent_hash_map<std::__1::basic_string<char>, unsigned long, tbb::tbb_hash_compare<std::__1::basic_string<char> >, tbb::tbb_allocator<std::__1::pair<std::__1::basic_string<char>, unsigned long> > >, std::__1::pair<const std::__1::basic_string<char>, unsigned long> > >, int, (lambda at /Users/sensei/Documents/Projects/sequence/sequence/sequence/assembler/lmf_graph.cpp:70:37), std::__1::plus<unsigned long> >::operator()' requested here
        void run_body( Range &r ) { (*my_body)( r ); }
                                    ^

I've tried using [](const rangetype &r, std::size_t init) -> std::size_t, but it didn't help.

Thanks!

[Vladimir_P_1234567890]

you have not changed rangetype to hashtype::range_type on line 34. I've asked to copy 4 lines:)

--Vladimir

[Sensei_S_]

Aw man, I thought I copied that! My bad, sorry!

Thanks, it works wonderfully! ;)