Linking error occur when i use cilk reducer with STL

[sejunho]

Hello,

I'm sorry for not exact sentence in english.

I troubled with cilk plus reducer when I had declared that.

This code is delared reducer.

--------------------------------------------------------------------------------

unordered_map< string, cilk::reducer_list_append > A;

--------------------------------------------------------------------------------

well, it completed compiling, but occured linking error with error output text.

--------------------------------------------------------------------------------

error LNK2019: unresolved external symbol "private: __thiscall cilk::reducer_list_append

--------------------------------------------------------------------------------

How can I use reducer in the STL container? Is it impossible?

Is it just my mistake?

[Pablo_H_Intel]

Hi Sejunho,

I need a little more information to understand what is going on.

Please post the entire error message. I don't know what symbol is missing, but I suspect that it is the copy constructor for the reducer.

You cannot put reducers into most STL containers at this time because STL containers (until C++11) require that element types be copy constructible. Reducers are not copy constructible because it is not clear what it would mean to copy a reducer. (Should both copies refer to the same view, or should they be independent? If independent, should the non-deterministic value of the reducer at the point of copy be copied, or the value of the initial view, or something else?) We have not yet updated reducers to C++11 movable types.

I suggest that you change your map to:

unordered_map* >

or

unordered_map> >

and allocate your reducers from the heap.

I hope this helps,
-Pablo

[sejunho]

Hi Pablo,

Thanks for anwer my question.

I reply what you need.

First, it is the entire linking error output.

-------------------------------------------------------------

error LNK2019: unresolved external symbol "private: __thiscall cilk::reducer_list_append >::reducer_list_append >(class cilk::reducer_list_append > const &)" (??0?$reducer_list_append@HV?$allocator@H@std@@@cilk@@AAE@ABV01@@Z) referenced in function "public: __thiscall std::_Pair_base,class std::allocator > const ,class cilk::reducer_list_append > >::_Pair_base,class std::allocator > const ,class cilk::reducer_list_append > >(class std::basic_string,class std::allocator > const &&,class cilk::reducer_list_append > &&)" (??0?$_Pair_base@$$CBV?$basic_string@DU?$char_traits@D@std@@V?$allocator@D@2@@std@@V?$reducer_list_append@HV?$allocator@H@std@@@cilk@@@std@@QAE@$$QBV?$basic_string@DU?$char_traits@D@std@@V?$allocator@D@2@@1@$$QAV?$reducer_list_append@HV?$allocator@H@std@@@cilk@@@Z)

--------------------------------------------------------------

maybe it is not for human, but computer(i love STL).

Second, i'm trying to understand and do what you was advise to me. I'll try to solve this problem and

post it how i could solve the problem. In fact, i feel concerned about parallel excution. Maybe some threads

operate STL hash map's methods and iterators concurrently. I think it must be problem, so i consider to

implement the hash map that designed for multithreadexcutable.

[Pablo_H_Intel · Accepted solution]

Your error message confirms my suspicion: the problem is that the unorderd_map is trying to use a copy constructor that does not exist.

You are correct that there are two levels of possible conflict in a map: building the map concurrently and modifying the elements concurrently. If you build the map in non-parallel code but modify the elements in parallel, then the solutions I mentioned (using pointers or unique_pointers in the map) will work. However, if you are actually inserting or removing elements from the unordered_map in parallel, then you need a data structure designed for concurrent access. Look at Intel Threading Building Blocks' tbb::concurrent_hash_map for such a parallel hash container. It should be compatible with Cilk parallelism. The two approaches can be combined, as well.

[sejunho]

Hi, I report the results how can i solved the problem(link error : But I think it is not perfect solution)

First, i used tbb::concurrent_hash_map for such a parallel hash container,

Because, My program modify the structure while some threads access some elements.

So, i declared tbb::concurrent_hash_map follows

----------------------------------------------------------

concurrent_hash_map, MyHashCompare> A;

----------------------------------------------------------

MyHashCompare is user-defined hash function, It is not has any problem. But, a linking error

occured looks like previous. The linking error output is follows

----------------------------------------------------------

error LNK2019: unresolved external symbol "private: __cdecl cilk::reducer_list_append >::reducer_list_append >(class cilk::reducer_list_append > const &)" (??0?$reducer_list_append@HV?$allocator@H@std@@@cilk@@AEAA@AEBV01@@Z) referenced in function "protected: bool __cdecl tbb::interface5::concurrent_hash_map,class std::allocator >,class cilk::reducer_list_append >,struct Partition::MyHashCompare,class tbb::tbb_allocator,class std::allocator >,class cilk::reducer_list_append > > > >::lookup(bool,class std::basic_string,class std::allocator > const &,class cilk::reducer_list_append > const *,class tbb::interface5::concurrent_hash_map,class std::allocator >,class cilk::reducer_list_append >,struct Partition::MyHashCompare,class tbb::tbb_allocator,class std::allocator >,class cilk::reducer_list_append > > > >::const_accessor *,bool)" (?lookup@?$concurrent_hash_map@V?$basic_string@DU?$char_traits@D@std@@V?$allocator@D@2@@std@@V?$reducer_list_append@HV?$allocator@H@std@@@cilk@@UMyHashCompare@Partition@@V?$tbb_allocator@U?$pair@V?$basic_string@DU?$char_traits@D@std@@V?$allocator@D@2@@std@@V?$reducer_list_append@HV?$allocator@H@std@@@cilk@@@std@@@tbb@@@interface5@tbb@@IEAA_N_NAEBV?$basic_string@DU?$char_traits@D@std@@V?$allocator@D@2@@std@@PEBV?$reducer_list_append@HV?$allocator@H@std@@@cilk@@PEAVconst_accessor@123@0@Z)

----------------------------------------------------------

I thought the codes "cilk::reducer_list_append" in the declared is maybe the problem.

So, I give up to use cilk reducer and change the container to vector.

----------------------------------------------------------

concurrent_hash_map, MyHashCompare> A;

----------------------------------------------------------

and as references of TBB, we can read-access by const_accessor andwrite-access by accessor.

But, as my best know, The write-accessor "accessor", locks the entire structure so that

other threads can't access to the structure. When I operate push_back method to one of

containers ofhash map, It's not need to lock the entire structure. But, because I use vector container,

It must use write-accessor to protect the structure while one thread call push_back method.(I only

need the write-accessor when I insert element to hash map, not vector container.)I think it reduces

the performance ofprogram.

Anyway, It has very good linear speed up even though some declines exists.

Thank you very much for much advices.

[Pablo_H_Intel]

Your solution sounds reasonable. I'm guessing that if you are getting linear speedup to a reasonable number of cores, that locks and lock contention are not your biggest issues. However, the order of elements in each vector will be non-deterministic. if you do want to give reducers another try, then what you should use is:

tbb::concurrent_hash_map*, MyHashCompare>

(Note that the second parameter is a pointer) or

tbb::concurrent_hash_mapstd::unique_ptr<cilk::reducer_list_append >, MyHashCompare>

This change will prevent you from running up against the missing copy constructor for reducers at the cost of having to allocate your reducers from the heap. One important benefit, however, is that the order of elements in each list will be identical to a serial run.

Regards,
-Pablo