스레드 결합의 성능 문제

Question

벡터 벡터의 모든 요소를 ​​검사하기 위해 다음과 같은 병렬 코드를 작성했습니다. 주어진 조건을 만족하는 vector<vector<int> >의 요소 만 저장합니다. 그러나, 내 문제는 vector<vector<int> > 내의 벡터 중 일부가 꽤 큰 반면 다른 것들은 꽤 작습니다. 이로 인해 내 코드가 thread.join()을 수행하는 데 오랜 시간이 걸립니다. 누군가 제 코드의 성능을 어떻게 향상시킬 수 있는지 제안 해주십시오.

void check_if_condition(vector<int>& a, vector<int>& satisfyingElements) 
{ 
    for(vector<int>::iterator i1=a.begin(), l1=a.end(); i1!=l1; ++i1) 
     if(some_check_condition(*i1)) 
      satisfyingElements.push_back(*i1); 

} 

void doWork(std::vector<vector<int> >& myVec, std::vector<vector<int> >& results, size_t current, size_t end) 
{ 
    end = std::min(end, myVec.size()); 
    int numPassed = 0; 
    for(; current < end; ++current) { 
     vector<int> satisfyingElements; 
     check_if_condition(myVec[current], satisfyingElements); 
     if(!satisfyingElements.empty()){ 
      results[current] = satisfyingElements;    
     } 
    }  
} 

int main() 
{ 
    std::vector<std::vector<int> > myVec(1000000); 
    std::vector<std::vector<int> > results(myVec.size()); 
    unsigned numparallelThreads = std::thread::hardware_concurrency(); 

    std::vector<std::thread> parallelThreads; 
    auto blockSize = myVec.size()/numparallelThreads; 
    for(size_t i = 0; i < numparallelThreads - 1; ++i) { 
     parallelThreads.emplace_back(doWork, std::ref(myVec), std::ref(results), i * blockSize, (i+1) * blockSize); 
    } 

    //also do work in this thread 
    doWork(myVec, results, (numparallelThreads-1) * blockSize, myVec.size()); 

    for(auto& thread : parallelThreads) 
     thread.join(); 

    std::vector<int> storage; 
    storage.reserve(numPassed.load()); 

    auto itRes = results.begin(); 
    auto itmyVec = myVec.begin(); 
    auto endRes = results.end(); 
    for(; itRes != endRes; ++itRes, ++itmyVec) { 
     if(!(*itRes).empty()) 
      storage.insert(storage.begin(),(*itRes).begin(), (*itRes).end()); 
    } 

    std::cout << "Done" << std::endl; 
} 

Answer 1

당신이 단지 문제가 얼마나 나쁜 볼 그 '큰'내부 - 벡터의 일부 규모를 줄 수 있는지 좋을 것이다. 이 비트가 있습니다

for(auto& thread : parallelThreads) 
    thread.join(); 

모든 스레드 순차적를 통해 진행하고 완료 될 때까지 기다린 다음에야 다음 하나에 보이는 : 나는 그러나 생각

, 당신의 문제가이 때문이다. 스레드 풀의 경우 모든 스레드가 완료 될 때까지 대기하려고합니다. 이는 각 스레드에 대해 condition_variable을 사용하여 마칠 수 있습니다. 그들이 끝내기 전에 그들은 당신이 기다릴 수있는 condition_variable을 알려야한다.

구현을 보면 큰 문제는 작업자 스레드의 소비가 균형을 이루지 않는다는 것입니다.

모든 스레드에보다 균형있는로드를 얻으려면 데이터 구조를 병합해야하므로 다른 작업자 스레드가 비교적 비슷한 크기의 데이터 청크를 처리 할 수 ​​있습니다. 나는 당신의 데이터가 어디서 왔는지는 모르겠지만 큰 데이터 세트를 다루는 애플리케이션에 벡터 벡터를 갖는 것은 좋은 생각처럼 들리지 않는다. 기존 벡터 벡터를 하나의 벡터로 처리하거나 가능한 경우 해당 데이터를 읽습니다. 처리를 위해 행 번호가 필요한 경우 행 번호를 찾을 수있는 시작 범위 범위의 벡터를 유지할 수 있습니다.

큰 벡터가 하나 있으면 동일한 크기의 청크로 나누어 작업자 스레드에 공급할 수 있습니다. 둘째, 스택에서 벡터를 생성하고 다른 벡터로 푸시하고 싶지는 않습니다. 스레드 작업 중에 메모리를 할당하는 문제가 발생하기 때문입니다. 메모리를 할당하는 것은 전역적인 상태 변경이므로 적절한 수준의 주소 파티셔닝을 통해 어느 수준의 잠금이 필요합니다. 일반적으로 성능을 추구 할 때마다 성능 중요한 부분에서 동적 할당을 제거해야합니다.

이 경우 만족스러운 elems의 벡터를 작성하는 것이 아니라 스레드가 오히려 '마킹'요소가 만족스러운 조건 일 것입니다. 그리고 일단 끝나면 아무 것도 밀거나 복사하지 않고 좋은 것들만 반복 할 수 있습니다. 이러한 솔루션은 낭비가 적습니다.

사실 내가 너라면 나는 위의 제안을 수행하여 단일 스레드에서이 문제를 먼저 해결하려고 노력할 것입니다. Vector-of-vectors 구조체를 제거하고 요소를 조건부로 반복한다면 (이것은 C++ 11 표준 라이브러리가 제공하는 xxxx_if 알고리즘을 사용하는 것만 큼 간단 할 수 있습니다.) 결국 충분한 성능을 얻을 수 있습니다. 그리고 그 시점에서이 작업의 덩어리를 작업자 스레드에 위임 할 때만 가치가 있습니다. 코딩 된이 시점에서 작업자 스레드를 사용하기위한 정당성은 거의 없습니다. 할 수있는대로 작문과 이동을 거의하지 마십시오. 많은 성과를 얻을 수 있습니다. 병렬화는 특정 환경에서만 잘 작동합니다.