multithreading - 对无锁与锁定数据结构进行基准测试的正确方法

Question

我的理解是，当争用很多时，无锁结构会更好，而如果争用较少，锁定数据结构会更好。
为了测试这一点，我编写了以下代码:

#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;
}

问题是我的无锁数据结构时间开始看起来像这样: .
我怀疑问题出在线程创建时间(有更多线程显然不是常数)，但减去线程创建时间得出了这个图:
这显然是错误的。
关于如何正确进行基准测试的任何想法？

Answer 1

我建议您实际上不要衡量时间，而是衡量操作次数。
所以我认为你可以启动所有线程，然后让主线程休眠一段时间(我认为 1 秒或更长时间是可以接受的)。
在测试中，每个线程都应该有一个该线程的私有(private)整数，该整数会随着您对数据结构所做的每个操作而递增。
(如果需要，您可以为每个操作设置不同的计数器)。

然后你可以像这样运行测试

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();
}

顺便说一句，这是我对我的数据结构和其他多线程基准进行的常用测试。