Efficacement/insérer simultanément dans unordered_map <>

Question

je dois recueillir quelques statistiques pour mon projet avec l'algorithme suivant (en Python):

stats = defaultdict(list) 
for s in L: 
    current = [] 
    for q in L: 
     stats[s, q] = copy(current) 
     current = f(current, s, q) 

Parce que la liste L est grande et f() et la copie current prendre un certain temps et Le langage principal du projet est C++ J'ai décidé de choisir C++ et d'utiliser ses capacités de multithreading pour implémenter mon algorithme.

Je propose que partie:

  stats[s, q] = copy(current) 
     current = f(current, s, q) 

à un std::async séparé et verrouillé std::mutex lors de l'insertion de stats mais qui fait les choses plus lent. J'ai essayé d'utiliser tbb::concurrent_ordered_map mais cela a empiré les choses.

j'ai écrit de référence qui reproduit son comportement: https://gist.github.com/myaut/94ee59d9752f524d3da8

Résultats pour 2 x Xeon E5-2420 avec Debian 7 pour 800 entrées dans L:

single-threaded      8157ms 
async    mutex   10145ms 
async with chunks mutex   9618ms 
threads    mutex   9378ms 
async    tbb    10173ms 
async with chunks tbb    9560ms 
threads    tbb    9418ms 

Je ne comprends pas pourquoi TBB est plus lent (il semble tbb::concurrent_ordered_map alloue de plus grandes quantités de mémoire, mais pour quoi). Y a-t-il d'autres options qui peuvent m'aider?

EDIT: J'ai mis à jour mon benchmark avec des approches suggérées (et réduit N à 800). Il semble que problème est ailleurs ...

• morceaux - grâce à @ Dave - gère désormais chaque async paquet de 20 élément séquentiel de la liste
• threads - sorte de threadpool comme le suggère @Cameron - Je crée 20 threads et chacun d'entre eux prend chaque 20ème élément de la liste initiale.

EDIT2: Je trouve un des problèmes - l'application consomme grande quantité de mémoire, de sorte que Xen Hypervisor est devenu un goulot d'étranglement - redémarré en mode natif, maintenant les modes multithread, il est seulement plus lent que uni-thread

EDIT3: Il semble que le problème avec multithreading est énorme quantité d'allocations lors de la copie list:

mprotect() 
_int_malloc+0xcba/0x13f0 
__libc_malloc+0x70/0x260 
operator new(unsigned long)+0x1d/0x90 
__gnu_cxx::new_allocator<int>::allocate(unsigned long, void const*)+0x40/0x42 
std::_Vector_base<int, std::allocator<int> >::_M_allocate(unsigned long)+0x2f/0x38 
std::_Vector_base<int, std::allocator<int> >::_M_create_storage(unsigned long)+0x23/0x58 
std::_Vector_base<int, std::allocator<int> >::_Vector_base(unsigned long, std::allocator<int> const&)+0x3b/0x5e 
std::vector<int, std::allocator<int> >::vector(std::vector<int, std::allocator<int> > const&)+0x55/0xf0 
void threaded_process<concurrent_map_of_list_of_lists>(concurrent_map_of_list_of_lists&, std::vector<int, std::allocator<int> > const&)::{lambda(__gnu_cxx::__normal_iterator<int const*, std::vector<int, std::allocator<int> > >, __gnu_cxx::__normal_iterator<int const*, std::vector<int, std::allocator<int> > >, int)#1}::operator()(__gnu_cxx::__normal_iterator<int const*, std::vector<int, std::allocator<int> > >, __gnu_cxx::__normal_iterator<int const*, std::vector<int, std::allocator<int> > >, int) const+0x5f/0x1dc 
_ZNSt12_Bind_simpleIFZ16threaded_processI31concurrent_map_of_list_of_listsEvRT_RKSt6vectorIiSaIiEEEUlN9__gnu_cxx17__normal_iteratorIPKiS6_EESD_iE_SD_SD_iEE9_M_invokeIJLm0ELm1ELm2EEEEvSt12_Index_tupleIJXspT_EEE+0x7c/0x87 
std::_Bind_simple<void threaded_process<concurrent_map_of_list_of_lists>(concurrent_map_of_list_of_lists&, std::vector<int, std::allocator<int> > const&)::{lambda(__gnu_cxx::__normal_iterator<int const*, std::vector<int, std::allocator<int> > >, __gnu_cxx::__normal_iterator<int const*, std::vector<int, std::allocator<int> > >, int)#1} (__gnu_cxx::__normal_iterator<int const*, std::vector<int, std::allocator<int> > >, __gnu_cxx::__normal_iterator<int const*, std::vector<int, std::allocator<int> > >, int)>::operator()()+0x1b/0x28 
std::thread::_Impl<std::_Bind_simple<void threaded_process<concurrent_map_of_list_of_lists>(concurrent_map_of_list_of_lists&, std::vector<int, std::allocator<int> > const&)::{lambda(__gnu_cxx::__normal_iterator<int const*, std::vector<int, std::allocator<int> > >, __gnu_cxx::__normal_iterator<int const*, std::vector<int, std::allocator<int> > >, int)#1} (__gnu_cxx::__normal_iterator<int const*, std::vector<int, std::allocator<int> > >, __gnu_cxx::__normal_iterator<int const*, std::vector<int, std::allocator<int> > >, int)> >::_M_run()+0x1c/0x1e 
std::error_code::default_error_condition() const+0x40/0xc0 
start_thread+0xd0/0x300 
clone+0x6d/0x90 

la chose est lorsque l'espace de tas épuisé, libc c grow_heap(), qui ajoute généralement une seule page, mais il appelle mprotect() qui appelle validate_mm() dans le noyau. validate_mm() semblent verrouiller tout VMA en utilisant sémaphore. J'ai remplacé l'allocateur par défaut list avec tbb::scalable_allocator, il bascule! Maintenant tbb est 2 fois plus rapide que l'approche mono-processeur.

Merci pour votre aide, j'utiliserai @Dave approche avec des morceaux de travail dans std::async.

Answer 1

Si f(current, s, q) et la copie current sont trivialement bon marché, il va être difficile de faire grandir avec le multithreading vaut la surcharge.Cependant, je pense que j'utiliserais un hash sans verrou/carte non ordonnée (tbb::concurrent_hash_map? Je ne sais pas tbb) et lancer l'ensemble pour boucle interne avec std::async. L'idée est de lancer un morceau de travail de taille décente avec std::async, s'il est trop petit et que vous lancez un million de tâches triviales, l'utilisation de std::async va éclipser le travail que la tâche doit faire!

également à noter, lorsque vous utilisez std::async vous devez enregistrer le retour de future quelque part ou il finit par bloquer jusqu'à ce que la tâche se fait dans le destructor de future, vous l'achat d'multithreading frais généraux et aucun traitement parallèle du tout. Vous pouvez courir dans cela maintenant. C'est très désagréable et j'aurais aimé que ça ne marche pas comme ça.