延迟初始化具有多线程读取器的数组:没有障碍或原子是否安全？

Question

我在一个实现讨论中提出了一个想法，即CPU可以选择完全重新排序内存的存储。

我用C初始化了一个静态数组，使用的代码类似于：

static int array[10];
static int array_initialized = 0;

void initialize () {

    array[0] = 1;
    array[1] = 2;
    ...
    array_initialized = -1;

}

之后，它的用法类似于：

int get_index(int index) {
    if (!array_initialized) initialize();
    if (index < 0 || index > 9) return -1;
    return array[index];
}

CPU有没有可能在多核英特尔架构(或其他架构)中对存储器访问进行重新排序，从而在initialize函数完成数组元素的设置之前设置array_initialized？或者，在整个数组在其内存视图中初始化之前，另一个执行线程可以将array_initialized视为非零？

Answer 1

TL:DR:如果在启动多个线程之前没有这样做，那么为了使lazy-init安全，需要一个_Atomic标志。

CPU是否可以在多核英特尔(x86)体系结构中重新排序内存访问

不能，这样的重新排序只能在编译时进行。对于正常的加载/存储，x86 asm有效地具有获取/释放语义。(seq_cst +具有存储转发的存储缓冲器)。

https://preshing.com/20120625/memory-ordering-at-compile-time/

(或其他架构)

是的，大多数其他ISA都有一个较弱的内存模型，它允许StoreStore重新排序和LoadLoad重新排序。(有效地memory_order_relaxed，或者类似于除Alpha AXP之外的ISA上的memory_order_consume，但是编译器不会尝试维护数据依赖关系。)

对于C语言来说，这些都无关紧要，因为C内存模型非常弱，允许在编译时重新排序，同时读/写或write+write任何对象都是数据竞争UB。

数据竞争UB允许编译器在编译“正常”ISA时将static变量保留在函数生命周期的寄存器中/在循环中。

如果在两个线程运行之前没有设置 array_initialized ，那么让两个线程运行此函数的就是C数据竞争UB。(例如，通过使主线程在启动任何更多线程之前运行它一次)。并且完全删除array_initialized标志，除非您在启动更多线程之前使用了lazy-init特性。

无论有多少其他线程正在运行，对于单个线程来说都是100%安全的:C编程模型保证了单个线程始终按照程序顺序看到自己的操作。(就像所有普通ISA的asm一样；除了像Itanium这样的ISA中的显式并行之外，您始终可以看到自己的操作按顺序进行。只有其他线程看到你的操作，事情才会变得奇怪)。

启动一个新线程(我认为)总是一个“完全的障碍”，或者用C语言来说就是“与”新线程“同步”。新线程中的内容不能先于父线程中的任何内容发生。因此，只需从主线程调用get_index一次，就可以安全地运行get_index，之后其他线程就不会再遇到任何障碍。

您可以使用_Atomic标志使惰性初始化线程安全

这类似于gcc对具有非常数初始化器的函数局部static 变量所做的操作。如果您很好奇，请查看代码生成:只读检查已初始化标志，然后调用init函数，确保只有一个线程运行初始化器。

这需要在已初始化状态的快速路径中加载acquire。这在x86和SPARC-TSO上是免费的(与正常加载相同)，但在较弱的ISA上则不是。AArch64有一个获取加载指令，其他ISA需要一些屏障指令。

将您的array_initialized标志转换为一个三态_Atomic变量：

• 初始化未启动(例如init == 0)。使用acquire load检查这一点。
• 初始化已启动但未完成(例如init == -1)
• init已完成(例如init == 1)

你可以通过将static int array[10];本身保留为非atomic，以确保只有一个线程“声称”负责执行初始化，使用atomic_compare_exchange_strong的 (这将只有一个线程成功)。然后让其他线程自旋等待INIT_FINISHED状态。

使用初始状态== 0可以让它位于BSS中，希望是在数据旁边。否则，我们可能更喜欢ISA的INIT_FINISHED=0，因为在来自内存的int上的分支为(非)0比其他数字稍微更有效一些。(例如AArch64 cbnz、MIPS bne $reg, $zero)。

我们可以两全其美(对于已经初始化的情况，这是最便宜的可能的快速路径)，同时仍然在BSS中使用标志:让主线程在启动其他线程之前用INIT_NOTSTARTED = -1写它。

将标志放在数组旁边对于小型数组很有帮助，其中标志可能与我们要索引的数据在同一缓存行中。或者至少是相同的4k页面。

#include <stdatomic.h>
#include <stdbool.h>
#ifdef __x86_64__
#include <immintrin.h>
#define SPINLOOP_BODY  _mm_pause()
#else
#define SPINLOOP_BODY  /**/
#endif

#ifdef __GNUC__
#define unlikely(expr) __builtin_expect(!!(expr), 0)
#define likely(expr) __builtin_expect(!!(expr), 1)
#define NOINLINE __attribute__((noinline))
#else 
#define unlikely(expr) (expr)
#define likely(expr) (expr)
#define NOINLINE /**/
#endif

enum init_states {
 INIT_NOTSTARTED = 0,
 INIT_STARTED = -1,
 INIT_FINISHED = 1   // optional: make this 0 to speed up the fast-path on some ISAs, and store an INIT_NOTSTARTED before the first call
};

static int array[10];
static _Atomic int array_initialized = INIT_NOTSTARTED;

// called either before or during init.
// One thread claims responsibility for doing the init, others spin-wait
NOINLINE    // this is rare, make sure it doesn't bloat the fast-path
void initialize(void) {
    bool winner = false;
    // check read-only if another thread has already claimed init
    if (array_initialized == INIT_NOTSTARTED) {
        int expected = INIT_NOTSTARTED;
        winner = atomic_compare_exchange_strong(&array_initialized, &expected, INIT_STARTED);
        // seq_cst memory order is fine.  Weaker might be ok but it only has to run once
    }

    if (winner) {
        array[0] = 1;
        // ...
        atomic_store_explicit(&array_initialized, INIT_FINISHED, memory_order_release);
    } else {
         // spin-wait for the winner in other threads
         // yield();  optional.
         // Or use some kind of mutex or condition var if init is really slow

         // otherwise just spin on a seq_cst load.  (Or acquire is fine.)
         while(array_initialized != INIT_FINISHED)
             SPINLOOP_BODY;   // x86 only

         // winner's release store syncs with our load:
         // array[] stores Happened Before this point so we can read it without UB
    }

}

int get_index(int index) {
    // atomic acquire load is fine, doesn't need seq_cst.  Cheaper than seq_cst on PowerPC
    if (unlikely(atomic_load_explicit(&array_initialized, memory_order_acquire) != INIT_FINISHED))
        initialize();
    if (unlikely(index < 0 || index > 9)) return -1;
    return array[index];
}

这确实可以编译成外观正确且高效的asm on Godbolt。在没有unlikely()宏的情况下，gcc/clang认为至少get_index的单机版有initialize()和/或return -1作为最有可能的捷径。

编译器想要内联init函数，这将是愚蠢的，因为它最多只能在每个线程运行一次。希望配置文件引导的优化可以纠正这一点。