lockfree와 locked 데이터 구조를 벤치 마크하는 올바른 방법

Question

많은 논쟁이있을 때 lock free 구조가 더 좋으며, 경합이 낮 으면 잠긴 데이터 구조가 더 잘된다는 것을 이해합니다.

#include<thread> 
#include<chrono> 
#include<iostream> 
#include<vector> 
#include<stack> 
#include<mutex> 
#include<fstream> 
#include <boost/lockfree/stack.hpp> 
using namespace std; 
mutex mut; 

const static int totalNumberOfWorkItems = 100000; 
const static int maxNumberOfThreads = 2000; 
const static int threadIncrement = 5; 

chrono::milliseconds calcRawSpawnTime(int n) { 
    auto start = chrono::high_resolution_clock::now(); 
    vector<thread> ts; 
    int j = 0; 
    for (int i = 0; i < n; i++) 
     ts.push_back(thread([&](){j += i; })); 
    for (auto&& t : ts) 
     t.join(); 
    auto end = chrono::high_resolution_clock::now(); 
    return chrono::duration_cast<chrono::milliseconds>(end - start); 
} 


chrono::milliseconds timeNThreadsLock(int n, int worksize){ 
    stack<int> data; 
    vector<thread> ts; 
    auto startSpawn = chrono::high_resolution_clock::now(); 
    for (int i = 0; i < n; i++) 
     ts.push_back(thread([&]() { 
     for (int j = 0; j < worksize; j++){ 
      mut.lock(); 
      data.push(7); 
      mut.unlock(); 
     } 
    })); 
    auto startWait = chrono::high_resolution_clock::now(); 
    for (auto&& t : ts) 
     t.join(); 
    auto endWait = chrono::high_resolution_clock::now(); 
    return chrono::duration_cast<chrono::milliseconds>(endWait - startSpawn); 
} 

chrono::milliseconds timeNThreadsLockFree(int n, int worksize) 
{ 
    boost::lockfree::stack<int> data; 
    vector<thread> ts; 
    auto startSpawn = chrono::high_resolution_clock::now(); 
    for (int i = 0; i < n; i++) 
     ts.push_back(thread([&](){ 
     for (int j = 0; j < worksize; j++) 
      data.push(7); 
    })); 
    auto startWait = chrono::high_resolution_clock::now(); 
    for (auto&& t : ts) 
     t.join(); 
    auto endWait = chrono::high_resolution_clock::now(); 
    return chrono::duration_cast<chrono::milliseconds>(endWait - startSpawn); 
} 
int main(int argc, char* argv []) 
{ 
    ofstream lockFile("locklog.log"); 
    ofstream lockFreeFile("lockfreelog.log"); 
    ofstream spawnTimes("spawnTimes.log"); 
    for (int i = 1; i < maxNumberOfThreads; i += threadIncrement){ 
     cout << i << endl; 
     spawnTimes << i << ",\t" << calcRawSpawnTime(i).count() << endl; 
     lockFreeFile << i << ",\t" << timeNThreadsLockFree(i, totalNumberOfWorkItems/i).count() << endl; 
     lockFile << i << ",\t" << timeNThreadsLock(i, totalNumberOfWorkItems/i).count() << endl; 
    } 
    return 0; 
} 

문제는 내 lockfree 데이터 구조 시간은 다음과 같이 시작이다 :

이를 테스트하려면

, 나는 다음과 같은 코드를 썼습니다.

가 나는 문제가 (분명히 일정하지 더 스레드) 스레드 생성 시간이었다 의심하지만, 스레드 생성 시간을 뺀 것은이 플롯했다 : 분명히 잘못

합니다.

이것을 올바르게 벤치마킹하는 방법에 대한 아이디어가 있습니까?

Answer 1

실제로 시간은 측정하지 말고 작업 수를 측정하는 것이 좋습니다. 그래서 나는 모든 스레드를 시작할 수 있다고 생각하고 잠시 동안 주 스레드가 잠들게 할 것입니다 (1 초 또는 그 이상은 받아 들일 만합니다). 테스트에서 각 스레드는 해당 스레드에 대한 개인 정수가 있어야합니다.이 정수는 데이터 구조에서 수행 한 각 작업에 따라 증가합니다. (원하는 경우 각 작업마다 다른 카운터가있을 수 있습니다).

그런 다음이 내 데이터 구조 및 기타 멀티 스레드 벤치 마크에 내가 만드는 일반적인 테스트입니다 BTW,

int x = random() % 1000; //just some granularity 
if(x > 500) { 
    some_test_on_the_data_structure(); 
} else { //you can adjust the limits to perform different number of each operation. 
    other_test_on_the_data_structure(); 
} 

같은 것을에서 테스트를 실행할 수 있습니다.

Answer 2

속도 향상 벤치 마크가 아니라 처리량 벤치 마크로이 테스트를 구성 해 보셨습니까?

각 스레드 수에 대해 가능한 한 자주 해당 기간 동안 작업을 반복하고 처리량을 "작업/기간"으로 계산하십시오. 이것은 실험 시간 (검사 할 스레드 수 * 기간 ~ 실험 시간)에 따라 쉽게 조정할 수있는 이점이 있습니다. 모든 준비가 완료 될 때까지 장벽을 사용하여 생성 된 스레드를 보관할 수 있습니다.

---

이 벤치 마크에는 경합을 제어 할 수있는 내용이 없습니다. 네가 좋아할만한 것일 수도있어.

이 작업을 수행하는 것은 유스 케이스가 어떤 것이라고 생각하는지, 그리고 테스트중인 데이터 구조에 따라 조금씩 다릅니다.

이 경우에는 테스트 할 데이터 구조의 배열을 만드는 것이 좋습니다. 삽입 작업을 수행 할 때이 배열 사이에서 임의로 스레드를 변경하십시오. 배열이 길수록 경쟁이 줄어 듭니다. 이것은 최종 값을 얻기 위해 '감소'연산이 필요한 데이터 구조를 모델링합니다. 특히 일부 작업의 경우 완벽하게 충분할 수 있습니다. 특히 일관성에 대한 약한 요구 사항을 충족해야합니다.

단순한 스택/벡터 외부의 많은 다른 데이터 구조에서 경쟁은 결국 입력의 함수가됩니다. HashMap의 경우 키 범위와 확률 분포를 벤치 마커로 제어 할 수 있습니다.