c++ - 为什么 std::scoped_lock 的不同互斥顺序会影响性能？

Question

注意:这不是一个实际问题(我从来没有用 scoped_lock 锁定超过 2 个互斥量)，我主要好奇为什么 scoped_lock 的实现在以不同顺序锁定互斥量时显然有相对较大的性能损失。

下面的示例代码，godbolt link .

#include<mutex>
#include<thread>
#include<chrono>
#include<iostream>

std::mutex m1, m2, m3, m4, m5, m6;

int cnt =0;

void f(){
    for (int i=0; i< 500*1000; ++i){
        std::scoped_lock sl{m1, m2, m3, m4, m5, m6};
        cnt++;
    }
}

void f_unord(){
    for (int i=0; i< 500*1000; ++i){
        std::scoped_lock sl{m4, m5, m6, m1, m2, m3};
        cnt++;
    }
}


int main(){
for (int run = 0; run<4; ++run)
{
    {
        const auto start = std::chrono::steady_clock::now();
        std::thread t1(f), t2(f);
        t1.join();
        t2.join();
        const auto end = std::chrono::steady_clock::now();
        std::cout << "same lock order: " << std::chrono::duration_cast<std::chrono::milliseconds>(end-start).count() << std::endl; 
        std::cout << cnt << std::endl;
    }
    {
        const auto start = std::chrono::steady_clock::now();
        std::thread t1(f), t2(f_unord);
        t1.join();
        t2.join();
        const auto end = std::chrono::steady_clock::now();
        std::cout << "different lock order: " << std::chrono::duration_cast<std::chrono::milliseconds>(end-start).count() << std::endl; 
        std::cout << cnt << std::endl;
    }
}
}

请注意为什么这令人惊讶:我希望，由于互斥体对于实现而言是不可移​​动的，因此只能按地址对互斥体进行排序并使用该锁定顺序。

关于 godbolt 基准测试的注意事项:我知道 godbolt 不可靠，我在我的虚拟机机器上得到了类似的结果:

g++ --version; g++ -O2 -std=c++17 scoped_lock.cpp -pthread; ./a.out

g++ (Ubuntu 9.2.1-9ubuntu2) 9.2.1 20191008 Copyright (C) 2019 FreeSoftware Foundation, Inc. This is free software; see the source forcopying conditions. There is NO warranty; not even forMERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

different lock order: 1074

1000000

same lock order: 602

2000000

different lock order: 987

3000000

same lock order: 612

4000000

different lock order: 1012

5000000

same lock order: 585

6000000

different lock order: 1050

7000000

same lock order: 675

8000000

different lock order: 1107

9000000

same lock order: 609

10000000

Answer 1

正如其他人所说，它与实现相关。但是该实现可以比 gcc 的 持久性 一遍又一遍地尝试同一件事的实现做得更好。

Peristent

Lock the first lock and then try_lock the rest. If any of the try_locks fail, unlock everything and try again.

如果两个线程以相同的顺序列出它们的互斥量，则此算法效果最佳。

为了获得更高性能和更稳健的算法，实现应该使用什么 this paper调用智能和礼貌。

Smart & Polite

Lock the first lock and then try_lock the rest. If any of the try_locks fail, unlock everything, then yield, then retry except the first lock is done on the one that previously failed the try_lock.

The paper表明该算法的性能永远不会比其他算法差，而且通常性能要好得多。此分析包括更传统的算法，该算法将可锁定对象按全局顺序排序，然后按该顺序锁定它们(标记为Ordered)。

libc++和 Visual Studio两者都使用聪明和礼貌。 gcc's libstdc++使用持久性。

在非 Apple 平台上使用 clang 时，使用 -stdlib=libc++ 选择 libc++ 而不是 gcc 的 std::lib。

阅读Dining Philosophers Rebooted对 std::lock 的这些算法进行深入的性能分析。