C++ 无锁线程问题 - 多个线程遍历连续数组但从不访问相同的成员数据？

Question

在我的 C++ 游戏引擎中，我有一个作业系统，它利用工作线程来执行各种任务。线程关联到每个可用的核心。最近，我一直在尝试通过最大化 CPU 利用率来优化我的一些系统管道。这是一些示例伪代码。它不是精确的复制品，但情况相似。

struct entityState {
  uint8 * byteBuffer; // Serialized binary data for the Entity
  uint8 * compressedData; // Compressed version of Entity data
  uint64  guid; // Unique ID
  gameTimeMS lastUpdated; // last time buffer was updated in milliseconds
  uint32 numUpdates; // Count of the number of updates
  uint32 numTimesAckedOverNetwork; // How many times client acked the data
  const char * typeData; // Type data in place of RTT
  bool markedForDelete; // Whether this object should be deleted next frame
  const char * debugData; // In debug configs, store meta data 
  // More member data but the point is made
};

// For examples sake, I have a contiguous array of entityState data
List< entityState * > entityStateList;
PopulateListWithEntityStateData(); // ~20,000 entityState ptrs on average
SortEntityStateList();
// Fire off 5 jobs each with their own worker thread
StartEntityStateJobs();

然后我有 5 个作业同时在这个列表上运行，没有 Mutexes 或 Critical Sections。每个作业函数都通过基于标准的二进制搜索访问数组，例如 guid，或者只是线性搜索。这是陷阱。 None个工作函数修改entityStateList中entityState指针的相同成员数据。但是，由于二分搜索与线性搜索存在冲突，它们可以引用相同的 entityState ptr。但是，我再说一遍，他们从不同时修改相同的成员数据。没有成员数据指针在每个线程上同时取消引用。

我运行通过单元测试进行了此模拟，没有遇到任何问题。但是，我有一些程序员朋友说，在取消引用同一个 entityStatePtr 时，这会导致线程暂停和恢复的未定义行为的可能性非常小。

我听说的另一点是此设置起作用的原因是 entityState 结构大小不适合缓存行并最终划分数据获取，这本身充当数据保护本身由于结构数据被分离到不同的缓存行。为了澄清，假设上半部分适合一个缓存行，下半部分适合另一个缓存行，并且作业函数仅对 entityState ptr 的一个数据成员进行操作，并且大多数时候它恰好在不同的缓存行中。我没有对成员数据使用任何原子修饰符或操作，因为没有作业会触及相同的成员数据。

最后，我也有一些程序员朋友说这是完美的线程安全。

尽管如此，我有三种不同的说法，而且我对多线程的低级知识缺乏足够的知识来确定哪种说法是正确的。

问题是...是否有可能发生 'x' 次中有 1 次在野外发生的超低碰撞？ 1/100万也不行。这是一种安全的、无锁线程机制，可以在列表上并行执行多个操作吗？尽量忽略示例数据的琐碎性。在我的引擎示例中要复杂得多。此代码可以运行在多个 OS 上，例如 PC、Linux 和控制台。它尚未崩溃，但曝光和测试是有限的。我承认我不是低级专家，但这节省了宝贵的表演时间。那么，我是在等待运行进入地雷还是这样安全？编译器是 gcc 版本 C++11。另外，请避免局部性的性能主题，除非它与线程和/或线程安全相关。我知道缓存未命中很糟糕。

问题 - 线程安全吗？如果是或否，请尽可能详细解释原因。我想加强我的低水平知识。

Answer 1

@walnut 已经详细解释了 "accessing different elements of an array is guaranteed to not cause data races".

但是，您提到您有多个作业函数更新 entityState，并且这些函数由某个作业链对象排序。您没有详细说明这个工作链是如何实现的，但是您必须确保它在不同的工作职能之间建立适当的 happens-before 关系，否则您在 entiyState 成员.

上进行数据竞赛

而且我也同意@rustyx - 运行你的代码使用了 ThreadSanitizer。它有助于揭示许多线程问题，包括数据竞争。

C++ 无锁线程问题 - 多个线程遍历连续数组但从不访问相同的成员数据？

C++ Lockless Threading Question - Multiple threads iterating over a contiguous array but never accessing same member data?

c++

multithreading

c++11

jobs

lockless