2 wątki wolniejsze niż 1?

Question

Grałem około z std::thread i coś dziwnego pojawiło się:

#include <thread> 

int k = 0; 

int main() { 
    std::thread t1([]() { while (k < 1000000000) { k = k + 1; }}); 
    std::thread t2([]() { while (k < 1000000000) { k = k + 1; }}); 

    t1.join(); 
    t2.join(); 

    return 0; 
} 

Kompilując powyższy kod bez optymalizacji za pomocą szczęk ++, mam następujące standardy:

real 0m2.377s 
user 0m4.688s 
sys 0m0.005s 

Potem zmieniłem kod do następujących czynności: (Teraz używa tylko 1 wątku)

#include <thread> 

int k = 0; 

int main() { 
    std::thread t1([]() { while (k < 1000000000) { k = k + 1; }}); 

    t1.join(); 

    return 0; 
} 

A to były nowe standardy:

real 0m2.304s 
user 0m2.298s 
sys 0m0.003s 

Dlaczego kod wykorzystujący 2 wątki wolniej niż kod z 1?

Answer 1

Masz dwie nitki walczące o tę samą zmienną, k. Więc spędzasz czas, w którym procesor mówi: "Procesor 1: Hej, czy wiesz, jaką wartość ma k? Procesor 2: Jasne, proszę bardzo!", Ping-pongowanie tam iz powrotem co kilka aktualizacji. Ponieważ k nie jest atomowe, nie ma również gwarancji, że thread2 nie zapisuje "starej" wartości k, tak że następnym razem wątek 1 odczytuje wartość, przeskakuje o 1, 2, 10 lub 100 kroków i ma do zrobienia to znowu - w teorii, co mogłoby doprowadzić do braku pętli po każdym zakończeniu, ale wymagałoby to sporo pecha.

Answer 2

To naprawdę powinien być komentarz w odpowiedzi na odpowiedź Matsa Peterssona, ale chciałem podać przykłady kodu.

Problem stanowi rywalizacja konkretnego zasobu, a także pamięci podręcznej.

Alternatywa 1:

#include <cstdint> 
#include <thread> 
#include <vector> 
#include <stdlib.h> 

static const uint64_t ITERATIONS = 10000000000ULL; 

int main(int argc, const char** argv) 
{ 
    size_t numThreads = 1; 
    if (argc > 1) { 
     numThreads = strtoul(argv[1], NULL, 10); 
     if (numThreads == 0) 
      return -1; 
    } 

    std::vector<std::thread> threads; 

    uint64_t k = 0; 
    for (size_t t = 0; t < numThreads; ++t) { 
     threads.emplace_back([&k]() { // capture k by reference so we all use the same k. 
      while (k < ITERATIONS) { 
       k++; 
      } 
     }); 
    } 

    for (size_t t = 0; t < numThreads; ++t) { 
     threads[t].join(); 
    } 
    return 0; 
} 

Tutaj gwinty utrzymują dla pojedynczej zmiennej, występując zarówno odczytu i zapisu, który zmusza go do ping-ponga, powodując rywalizacji i co jednolitym gwintowanych przypadku najbardziej efektywny.

#include <cstdint> 
#include <thread> 
#include <vector> 
#include <stdlib.h> 
#include <atomic> 

static const uint64_t ITERATIONS = 10000000000ULL; 

int main(int argc, const char** argv) 
{ 
    size_t numThreads = 1; 
    if (argc > 1) { 
     numThreads = strtoul(argv[1], NULL, 10); 
     if (numThreads == 0) 
      return -1; 
    } 

    std::vector<std::thread> threads; 

    std::atomic<uint64_t> k = 0; 
    for (size_t t = 0; t < numThreads; ++t) { 
     threads.emplace_back([&]() { 
      // Imperfect division of labor, we'll fall short in some cases. 
      for (size_t i = 0; i < ITERATIONS/numThreads; ++i) { 
       k++; 
      } 
     }); 
    } 

    for (size_t t = 0; t < numThreads; ++t) { 
     threads[t].join(); 
    } 
    return 0; 
} 

Tutaj dzielimy pracy deterministycznie (upadamy afoul przypadkach numThreads nie jest dzielnikiem liczby iteracji, ale jest to na tyle blisko tej demonstracji). Niestety wciąż napotykamy na rywalizację o dostęp do współużytkowanego elementu w pamięci.

#include <cstdint> 
#include <thread> 
#include <vector> 
#include <stdlib.h> 
#include <atomic> 

static const uint64_t ITERATIONS = 10000000000ULL; 

int main(int argc, const char** argv) 
{ 
    size_t numThreads = 1; 
    if (argc > 1) { 
     numThreads = strtoul(argv[1], NULL, 10); 
     if (numThreads == 0) 
      return -1; 
    } 

    std::vector<std::thread> threads; 
    std::vector<uint64_t> ks; 

    for (size_t t = 0; t < numThreads; ++t) { 
     threads.emplace_back([=, &ks]() { 
      auto& k = ks[t]; 
      // Imperfect division of labor, we'll fall short in some cases. 
      for (size_t i = 0; i < ITERATIONS/numThreads; ++i) { 
       k++; 
      } 
     }); 
    } 

    uint64_t k = 0; 
    for (size_t t = 0; t < numThreads; ++t) { 
     threads[t].join(); 
     k += ks[t]; 
    } 
    return 0; 
} 

Znowu jest deterministyczny o podziale obciążeń, i spędzamy niewielką ilość wysiłku w końcu do sortowania wyników. Jednak nie zrobiliśmy nic, aby zapewnić dystrybucję liczników faworyzujących zdrową dystrybucję procesorów. W tym celu:

#include <cstdint> 
#include <thread> 
#include <vector> 
#include <stdlib.h> 

static const uint64_t ITERATIONS = 10000000000ULL; 
#define CACHE_LINE_SIZE 128 

int main(int argc, const char** argv) 
{ 
    size_t numThreads = 1; 
    if (argc > 1) { 
     numThreads = strtoul(argv[1], NULL, 10); 
     if (numThreads == 0) 
      return -1; 
    } 

    std::vector<std::thread> threads; 
    std::mutex kMutex; 
    uint64_t k = 0; 

    for (size_t t = 0; t < numThreads; ++t) { 
     threads.emplace_back([=, &k]() { 
      alignas(CACHE_LINE_SIZE) uint64_t myK = 0; 
      // Imperfect division of labor, we'll fall short in some cases. 
      for (uint64_t i = 0; i < ITERATIONS/numThreads; ++i) { 
       myK++; 
      } 
      kMutex.lock(); 
      k += myK; 
      kMutex.unlock(); 
     }); 
    } 

    for (size_t t = 0; t < numThreads; ++t) { 
     threads[t].join(); 
    } 
    return 0; 
} 

Tu uniknąć rywalizacji pomiędzy nićmi w dół do poziomu linii pamięci podręcznej, z wyjątkiem jednego przypadku na końcu, gdzie używamy mutex kontrolować synchronizację. W przypadku tego trywialnego obciążenia muteks będzie miał jeden względny koszt. Alternatywnie możesz użyć alignas, aby zapewnić każdemu wątkowi własną pamięć w zewnętrznym zasięgu i podsumować wyniki po złączeniach, eliminując potrzebę stosowania muteksu. Zostawiam to jako ćwiczenie dla czytelnika.

Answer 3

Wydaje mi się, że ważniejsze jest pytanie niż "dlaczego to nie zadziałało?" jest "Jak mogę to uruchomić?"Dla danego zadania, myślę std::async (mimo significant shortcomings) jest naprawdę lepszym narzędziem niż przy użyciu std::thread bezpośrednio.

#include <future> 
#include <iostream> 

int k = 0; 
unsigned tasks = std::thread::hardware_concurrency(); 
unsigned reps = 1000000000/tasks; 

int main() { 
    std::vector<std::future<int>> f; 

    for (int i=0; i<tasks; i++) 
     f.emplace_back(std::async(std::launch::async, 
            [](){int j; for (j=0; j<reps; j++); return j;}) 
        ); 

    for (int i=0; i<tasks; i++) { 
     f[i].wait(); 
     k += f[i].get(); 
    } 

    std::cout << k << "\n"; 
    return 0; 
} 

Answer 4

biegnę do tego problemu. Moja opinia jest taka, że ​​dla określonego rodzaju pracy kosztów zarządzania gwint może być więcej niż korzyści można uzyskać z systemem w wątkach. Oto mój przykładowy kod, jakiejś prawdziwej pracy w pętli dużej liczbie iteracji, więc mam bardzo spójny numer z poleceniem czasu.

pair<int,int> result{0,0}; 
#ifdef USETHREAD 
     thread thread_l(&Myclass::trimLeft, this, std::ref(fsq), std::ref(oriencnt), std::ref(result.first)); 
     thread thread_r(&Myclass::trimRight, this, std::ref(fsq), std::ref(oriencnt), std::ref(result.second)); 
     thread_l.join(); 
     thread_r.join(); 
#else 
     // non threaded version faster 
     trimLeft(fsq, oriencnt, result.first); 
     trimRight(fsq, oriencnt, result.second); 
#endif 

    return result; 

Wyniki czasowe

Thead   No_thread 
===========================  
Real 4m28s   2m49s 
usr 0m55s   2m49s 
sys 0m6.2s   0m0.012s 

Ignoruję dziesiętny dla sekund dla dużych. Mój kod aktualizuje tylko jedną wspólną zmienną oriencnt. Nie zezwalam na aktualizowanie jeszcze tej wersji: fsq. Wygląda na to, że w wersji z gwintem system wykonuje więcej pracy, co skutkuje dłuższym czasem zegarowym (w czasie rzeczywistym). Flaga mojego kompilatora jest domyślna -g -O2, nie jestem pewien, czy to jest główny problem, czy nie. W przypadku kompilacji z -O3 różnica jest minimalna. Istnieje również pewna operacja IO z kontrolowanym muteksem. Mój eksperyment pokazuje, że to nie przyczynia się do różnicy. Używam gcc 5.4 z C++ 11. Jedną z możliwości jest to, że biblioteka nie jest zoptymalizowana.

Tutaj jest skompilowany z O3

 Thead No_thread 
========================= 
real 4m24  2m44s 
usr 0m54s  2m44s 
sys 0m6.2s  0m0.016s