在这里大声思考…不确定这有多有效,但是:

可以创建锁定某些索引的方法:

vector<int> mutexed_slots;
std::mutex mtx;

bool lock_element(int index) 
{
    std::lock_guard<std::mutex> lock(mtx);
    // Check if item is in the mutexed list
    if ( !std::find(mutexed_slots.begin(), mutexed_slots.end(), index) != vector.end() ) 
    {
       // If its not then add it - now that array value is safe from other threads
       mutexed_slots.emplace_back(index);
       return true;
    }
    return false;
}

void unlock_element(int index) 
{
    std::lock_guard<std::mutex> lock(mtx);
    // No need to check because you will only unlock the element that you accessed (unless you are a very naughty boy indeed)
    vec.erase(vec.begin() + index);
}

注: 这是一个想法的开始,所以现在不要太用力了!它也是未经测试的伪代码。这并不是最终的答案,而是一个起点。请添加评论以改进或建议这是/不合理的。

进一步要点:

• 可能会有一个更有效的STL来使用
• 您可以将所有这些与数据一起打包到一个类中。
• 你需要循环通过 lock_element() 直到它变回真的——又一次,现在不漂亮。这种机制可以改进。
• 每个线程都需要记住它们当前正在处理的索引,以便它们只解锁那个特定的索引——同样,这可以更集成到一个类中,以确保行为。

但作为一个概念——可行吗?我想如果你真的需要快速访问(也许你会这样做),这可能不是那么有效,思想?

更新

如果每个线程/工作线程在 mutexed_slots . 然后就不会从向量中推回/移除(除了开始/结束)。所以每个线程只设置它所锁定的索引——如果它没有被锁定,那么它只设置为-1(或者类似的)。我认为还有很多这样的效率改进要做。同样,一个完整的类来为您完成所有这些,这将是实现它的方法。

测试/结果

我为此实现了一个测试程序,只是因为我非常喜欢这种类型的东西。我的实现是 here

我认为这是一个公共的Github回购-所以欢迎你看看。但我将结果发布在顶级自述文件上(所以滚动一点查看它们)。我做了一些改进,比如:

• 运行时没有对保护阵列的插入/删除操作

• 不需要锁保护来执行“解锁”,因为我不依赖std::atomic索引。

  以下是我的摘要打印输出:

总结:

当工作负载为1毫秒(执行每个操作所需的时间)时,完成的工作量为:

• 9808用于受保护

• 8117为正常

  注释 这些值各不相同,有时正常值更高,似乎没有明显的赢家。

当工作负载为0毫秒(基本上增加几个计数器)时,完成的工作量为:

• 9791264用于受保护
• 29307829正常

在这里,你可以看到使用静音保护可以将工作速度降低大约三分之一(1/3)。这个比率在测试之间是一致的。

我也对1个工人进行了同样的测试,同样的比率大致保持不变。但是,当我使数组更小(~1000个元素)时,对于工作负载为1毫秒的情况,完成的工作量仍然大致相同。但是当工作负载非常轻时,我得到如下结果:

• 五百六十二万一千三百一十一

• 三千九百一十五万七千九百三十一

  速度慢了7倍。

结论

• 阵列越大,发生的碰撞就越少-性能越好。
• 工作负荷(每个项目)越长,使用保护机制的区别就越不明显。

锁似乎只是增加了一个开销,比增加几个计数器慢2-3倍。这可能是由于实际碰撞造成的偏差,因为(从结果来看)记录的最长锁定时间是40毫秒-但当时工作时间非常快,所以发生了许多碰撞(每次碰撞约8个成功锁定)。

这取决于访问模式,您是否有有效地划分工作的方法?基本上,您可以将数组划分为8个块(或尽可能多的块),并用互斥体覆盖每个部分,但是如果访问模式是随机的,那么仍然会有很多冲突。

您的系统上有TSX支持吗?这将是一个经典的例子,只有一个全局锁,并且让线程忽略它,除非发生实际的冲突。

您可以编写一个类,当某个特定的索引需要它时,它将动态地创建锁, std::optional 将有助于此(前面的C++ 17代码):

class IndexLocker {
  public:
    explicit IndexLocker(size_t size) : index_locks_(size) {}

    std::mutex& get_lock(size_t i) {
        if (std::lock_guard guard(instance_lock_); index_locks_[i] == std::nullopt) {
            index_locks_[i].emplace();
        }
        return *index_locks_[i];
    }

  private:
    std::vector<std::optional<std::mutex>> index_locks_;
    std::mutex instance_lock_;
};

你也可以用 std::unique_ptr 要最小化堆栈空间,但保持相同的语义:

class IndexLocker {
  public:
    explicit IndexLocker(size_t size) : index_locks_(size) {}

    std::mutex& get_lock(size_t i) {
        if (std::lock_guard guard(instance_lock_); index_locks_[i] == nullptr) {
            index_locks_[i] = std::make_unique<std::mutex>();
        }
        return *index_locks_[i];
    }

  private:
    std::vector<std::unique_ptr<std::mutex>> index_locks_;
    std::mutex instance_lock_;
};

使用这个类并不一定意味着您需要创建所有1000000个元素。您可以使用modulo操作将locker视为mutex的“哈希表”:

constexpr size_t kLockLimit = 8;
IndexLocker index_locker(kLockLimit);

auto thread_code = [&](size_t i) {
    std::lock_guard guard(index_locker.get_lock(i % kLockLimit));
    // Do work with lock.
};

值得一提的是,“哈希表”方法使得死锁非常容易( get_lock(0) 然后 get_lock(16) 例如)。但是,如果每个线程一次只能处理一个元素,那么这不应该是一个问题。

还有其他的折衷办法,比如细颗粒锁定。原子操作是昂贵的,因此锁定每个元素的并行算法可能比顺序版本花费更长的时间。

如何有效锁定取决于。数组元素是否依赖于数组中的其他元素?你主要是在看书吗?大部分是写作?

我不想把数组分成8个部分,因为这会导致 等待的可能性很高(访问是随机的)。的元素 数组是我将要编写的一个类,它将被多个golomb编码 价值观。

我不认为有8个互斥是这里的方法。如果一个给定的锁保护一个数组部分,那么在并行执行过程中,如果不引入争用条件(使互斥体无意义),就不能将其切换为保护另一个部分。

数组项是否小?如果可以将它们减少到8个字节,则可以用 alignas(8) 实例化 std::atomic<YourClass> 物体。(大小取决于架构。验证 is_lock_free() 返回true。)这可能会打开无锁算法的可能性。在这里,危险指针的变体似乎很有用。这很复杂,所以如果时间有限,最好研究其他并行方法。