Can/should 非无锁原子可以用 SeqLock 实现吗？
Can/should non-lock-free atomics be implemented with a SeqLock?
在 MSVC STL 和 LLVM libc++ 实现中 std::atomic 非原子大小是使用自旋锁实现的。
libc++ (Github):
_LIBCPP_INLINE_VISIBILITY void __lock() const volatile {
while(1 == __cxx_atomic_exchange(&__a_lock, _LIBCPP_ATOMIC_FLAG_TYPE(true), memory_order_acquire))
/*spin*/;
}
_LIBCPP_INLINE_VISIBILITY void __lock() const {
while(1 == __cxx_atomic_exchange(&__a_lock, _LIBCPP_ATOMIC_FLAG_TYPE(true), memory_order_acquire))
/*spin*/;
}
MSVC (Github) (recently discussed in this Q&A):
inline void _Atomic_lock_acquire(long& _Spinlock) noexcept {
#if defined(_M_IX86) || (defined(_M_X64) && !defined(_M_ARM64EC))
// Algorithm from Intel(R) 64 and IA-32 Architectures Optimization Reference Manual, May 2020
// Example 2-4. Contended Locks with Increasing Back-off Example - Improved Version, page 2-22
// The code in mentioned manual is covered by the 0BSD license.
int _Current_backoff = 1;
const int _Max_backoff = 64;
while (_InterlockedExchange(&_Spinlock, 1) != 0) {
while (__iso_volatile_load32(&reinterpret_cast<int&>(_Spinlock)) != 0) {
for (int _Count_down = _Current_backoff; _Count_down != 0; --_Count_down) {
_mm_pause();
}
_Current_backoff = _Current_backoff < _Max_backoff ? _Current_backoff << 1 : _Max_backoff;
}
}
#elif
/* ... */
#endif
}
在思考更好的实现方式时，不知是否可以将其替换为SeqLock？如果读取不与写入竞争，优势将是廉价读取。
我想问的另一件事是，是否可以改进 SeqLock 以使用 OS 等待。在我看来，如果 reader 观察到一个奇数计数，它可以等待原子等待底层机制（Linux futex/Windows WaitOnAddress），从而避免自旋锁的饥饿问题。
对我来说这似乎是可能的。虽然 C++ 内存模型目前不涵盖 Seqlock，但 std::atomic 中的类型必须是可平凡复制的，因此 seqlock 中的 memcpy reads/writes 将起作用，并且如果使用足够的障碍来获取，将处理竞争一个 volatile-equivalent 而不会严重破坏优化。这将是 特定 C++ 实现的头文件的一部分，因此它不必是可移植的。
关于在 C++ 中实现 SeqLock 的现有 SO 问答（可能 使用 其他 std::atomic 操作）
- how to implement a seqlock lock using c++11 atomic library
是的，如果您提供编写器之间的互斥，您可以使用 SeqLock 作为 readers/writers 锁。您仍然可以获得读取端的可扩展性，而写入和 RMW 将保持大致相同。
这不是个坏主意，尽管如果您的写入非常频繁，它对 readers 有潜在的公平性问题。对于主流标准库来说可能不是一个好主意，至少如果没有在一系列硬件上对一些不同的工作负载/用例进行一些测试就不是这样，因为在某些机器上工作得很好但在其他机器上进行面部移植并不是你想要的标准库东西. （不幸的是，希望在其特殊情况下获得出色性能的代码通常必须使用为其调整的实现，而不是标准实现。）
可以使用单独的自旋锁实现互斥，或者只使用序列号的低位。事实上，我已经看到了其他关于 SeqLock 的描述，这些描述假定您将与多个编写器一起使用它，甚至没有提到允许对序列号进行纯加载和纯存储以避免原子 RMW 的成本。
如何使用序列号作为自旋锁
作者或 RMWer 尝试自动 CAS 序列号以增加（如果它不是奇数）。如果序列号已经是奇数，编写者只需旋转直到他们看到偶数。
这意味着作者必须在尝试写入之前先读取序列号，这可能会导致 （MESI 共享请求，然后是 RFO）。在硬件上实际上有 fetch_or 的机器上，您可以使用它自动使计数变为奇数，看看您是否赢得了将它从偶数变为奇数的竞赛。
在 x86-64 上，你可以使用 lock bts 设置低位并找出旧的低位是什么，如果之前是偶数则加载整个序列号（因为你赢了比赛，没有其他作者会修改它）。所以你可以做一个加 1 的发布存储来“解锁”而不是需要 lock add.
让其他作者更快地回收锁实际上可能是一件坏事，尽管如此：您想要 window 等待 reader 完成。也许只是在写端自旋循环中使用多个 pause 指令（或非 x86 上的等效指令），而不是在读端自旋中。如果竞争很低，readers 可能有时间在作者到达之前看到它，否则作者会经常看到它被锁定并进入较慢的自旋循环。也许对作家的回退也更快。
LL/SC 机器（至少在 asm 中）可以像 CAS 或 TAS 一样轻松地进行测试和增量。我不知道如何编写可以编译成那样的纯 C++。 fetch_or 可以为 LL/SC 高效地编译，但即使它已经很奇怪了，它仍然可以存储。 （如果非要LL和SC分开，还不如好好利用，用不着就干脆不存，希望硬件设计能物尽其用。）
(不要无条件递增是很关键的；你不能解锁另一个作者对锁的所有权。但是保持值不变的atomic-RMW总是正确的，如果不是性能。）
默认情况下这可能不是一个好主意，因为大量写入 activity 的结果很糟糕，这使得 reader 可能很难成功读取。正如维基百科指出的那样：
The reader never blocks, but it may have to retry if a write is in progress; this speeds up the readers in the case where the data was not modified, since they do not have to acquire the lock as they would with a traditional read–write lock. Also, writers do not wait for readers, whereas with traditional read–write locks they do, leading to potential resource starvation in a situation where there are a number of readers (because the writer must wait for there to be no readers). Because of these two factors, seqlocks are more efficient than traditional read–write locks for the situation where there are many readers and few writers. The drawback is that if there is too much write activity or the reader is too slow, they might livelock (and the readers may starve).
“太慢reader”的问题不太可能，只是一个小的memcpy。对于非常大的 T，代码不应期待 std::atomic<T> 的良好结果；一般的假设是，对于在某些实现上可以无锁的 T，您只会为 std::atomic 烦恼。 （通常不包括事务内存，因为主流实现不这样做。）
但是“写入过多”的问题可能仍然存在：SeqLock 最适合读取为主的数据。读者可能会在重写混合中度过一段糟糕的时光，重试次数甚至超过简单的自旋锁或 readers-writers 锁。
如果有办法使它成为实现的 选项 就好了，比如 std::atomic<T, true> 之类的可选模板参数，或者 #pragma，或 #define，然后再包含 <atomic>。或者一个命令行选项。
可选的模板参数会影响类型的每次使用，但可能比单独的 class 名称（如 gnu::atomic_seqlock<T>）略显笨拙。可选的模板参数仍然会使 std::atomic 类型成为 class 名称，例如std::atomic 的其他事物的匹配专业化。但可能会破坏其他东西，IDK。
破解一些东西进行实验可能会很有趣。
在 MSVC STL 和 LLVM libc++ 实现中 std::atomic 非原子大小是使用自旋锁实现的。
libc++ (Github):
_LIBCPP_INLINE_VISIBILITY void __lock() const volatile {
while(1 == __cxx_atomic_exchange(&__a_lock, _LIBCPP_ATOMIC_FLAG_TYPE(true), memory_order_acquire))
/*spin*/;
}
_LIBCPP_INLINE_VISIBILITY void __lock() const {
while(1 == __cxx_atomic_exchange(&__a_lock, _LIBCPP_ATOMIC_FLAG_TYPE(true), memory_order_acquire))
/*spin*/;
}
MSVC (Github) (recently discussed in this Q&A):
inline void _Atomic_lock_acquire(long& _Spinlock) noexcept {
#if defined(_M_IX86) || (defined(_M_X64) && !defined(_M_ARM64EC))
// Algorithm from Intel(R) 64 and IA-32 Architectures Optimization Reference Manual, May 2020
// Example 2-4. Contended Locks with Increasing Back-off Example - Improved Version, page 2-22
// The code in mentioned manual is covered by the 0BSD license.
int _Current_backoff = 1;
const int _Max_backoff = 64;
while (_InterlockedExchange(&_Spinlock, 1) != 0) {
while (__iso_volatile_load32(&reinterpret_cast<int&>(_Spinlock)) != 0) {
for (int _Count_down = _Current_backoff; _Count_down != 0; --_Count_down) {
_mm_pause();
}
_Current_backoff = _Current_backoff < _Max_backoff ? _Current_backoff << 1 : _Max_backoff;
}
}
#elif
/* ... */
#endif
}
在思考更好的实现方式时，不知是否可以将其替换为SeqLock？如果读取不与写入竞争，优势将是廉价读取。
我想问的另一件事是，是否可以改进 SeqLock 以使用 OS 等待。在我看来，如果 reader 观察到一个奇数计数，它可以等待原子等待底层机制（Linux futex/Windows WaitOnAddress），从而避免自旋锁的饥饿问题。
对我来说这似乎是可能的。虽然 C++ 内存模型目前不涵盖 Seqlock，但 std::atomic 中的类型必须是可平凡复制的，因此 seqlock 中的 memcpy reads/writes 将起作用，并且如果使用足够的障碍来获取，将处理竞争一个 volatile-equivalent 而不会严重破坏优化。这将是 特定 C++ 实现的头文件的一部分，因此它不必是可移植的。
关于在 C++ 中实现 SeqLock 的现有 SO 问答（可能 使用 其他 std::atomic 操作）
- how to implement a seqlock lock using c++11 atomic library
是的，如果您提供编写器之间的互斥，您可以使用 SeqLock 作为 readers/writers 锁。您仍然可以获得读取端的可扩展性，而写入和 RMW 将保持大致相同。
这不是个坏主意，尽管如果您的写入非常频繁，它对 readers 有潜在的公平性问题。对于主流标准库来说可能不是一个好主意，至少如果没有在一系列硬件上对一些不同的工作负载/用例进行一些测试就不是这样，因为在某些机器上工作得很好但在其他机器上进行面部移植并不是你想要的标准库东西. （不幸的是，希望在其特殊情况下获得出色性能的代码通常必须使用为其调整的实现，而不是标准实现。）
可以使用单独的自旋锁实现互斥，或者只使用序列号的低位。事实上，我已经看到了其他关于 SeqLock 的描述，这些描述假定您将与多个编写器一起使用它，甚至没有提到允许对序列号进行纯加载和纯存储以避免原子 RMW 的成本。
如何使用序列号作为自旋锁
作者或 RMWer 尝试自动 CAS 序列号以增加（如果它不是奇数）。如果序列号已经是奇数，编写者只需旋转直到他们看到偶数。
这意味着作者必须在尝试写入之前先读取序列号，这可能会导致 fetch_or 的机器上，您可以使用它自动使计数变为奇数，看看您是否赢得了将它从偶数变为奇数的竞赛。
在 x86-64 上，你可以使用 lock bts 设置低位并找出旧的低位是什么，如果之前是偶数则加载整个序列号（因为你赢了比赛，没有其他作者会修改它）。所以你可以做一个加 1 的发布存储来“解锁”而不是需要 lock add.
让其他作者更快地回收锁实际上可能是一件坏事，尽管如此：您想要 window 等待 reader 完成。也许只是在写端自旋循环中使用多个 pause 指令（或非 x86 上的等效指令），而不是在读端自旋中。如果竞争很低，readers 可能有时间在作者到达之前看到它，否则作者会经常看到它被锁定并进入较慢的自旋循环。也许对作家的回退也更快。
LL/SC 机器（至少在 asm 中）可以像 CAS 或 TAS 一样轻松地进行测试和增量。我不知道如何编写可以编译成那样的纯 C++。 fetch_or 可以为 LL/SC 高效地编译，但即使它已经很奇怪了，它仍然可以存储。 （如果非要LL和SC分开，还不如好好利用，用不着就干脆不存，希望硬件设计能物尽其用。）
(不要无条件递增是很关键的；你不能解锁另一个作者对锁的所有权。但是保持值不变的atomic-RMW总是正确的，如果不是性能。）
默认情况下这可能不是一个好主意，因为大量写入 activity 的结果很糟糕，这使得 reader 可能很难成功读取。正如维基百科指出的那样：
The reader never blocks, but it may have to retry if a write is in progress; this speeds up the readers in the case where the data was not modified, since they do not have to acquire the lock as they would with a traditional read–write lock. Also, writers do not wait for readers, whereas with traditional read–write locks they do, leading to potential resource starvation in a situation where there are a number of readers (because the writer must wait for there to be no readers). Because of these two factors, seqlocks are more efficient than traditional read–write locks for the situation where there are many readers and few writers. The drawback is that if there is too much write activity or the reader is too slow, they might livelock (and the readers may starve).
“太慢reader”的问题不太可能，只是一个小的memcpy。对于非常大的 T，代码不应期待 std::atomic<T> 的良好结果；一般的假设是，对于在某些实现上可以无锁的 T，您只会为 std::atomic 烦恼。 （通常不包括事务内存，因为主流实现不这样做。）
但是“写入过多”的问题可能仍然存在：SeqLock 最适合读取为主的数据。读者可能会在重写混合中度过一段糟糕的时光，重试次数甚至超过简单的自旋锁或 readers-writers 锁。
如果有办法使它成为实现的 选项 就好了，比如 std::atomic<T, true> 之类的可选模板参数，或者 #pragma，或 #define，然后再包含 <atomic>。或者一个命令行选项。
可选的模板参数会影响类型的每次使用，但可能比单独的 class 名称（如 gnu::atomic_seqlock<T>）略显笨拙。可选的模板参数仍然会使 std::atomic 类型成为 class 名称，例如std::atomic 的其他事物的匹配专业化。但可能会破坏其他东西，IDK。
破解一些东西进行实验可能会很有趣。