首页 > GCD > 【译】dispatch_once的秘密

【译】dispatch_once的秘密

本文译自:https://mikeash.com/pyblog/friday-qa-2014-06-06-secrets-of-dispatch_once.html,本人才疏学浅,译文难免有些纰漏,如有不对的地方,请指正。
读者Paul Kim在Michael Tsai写的文章(http://mjtsai.com/blog/2014/05/21/making-dispatch_once-fast)中指出一点关于如何让dispatch_once更快。然而dispatch_once源码的注释看起来不太令人难懂,它没有全面的揭示一些人们希望看到的细节。今天的这篇文章我将精确的讨论它如何工作和到底发生了什么。

dispatch_once

顾名思义,它就是做某些事情一次,仅仅一次。

它有两个参数,第一个参数是一个表达“一次”的术语,第二个参数是一个第一次调用执行的block。用下面的方法调用它:

static dispatch_once_t predicate;
dispatch_once(&predicate, ^{
    // some one-time task
});

不管是一个全局字典、一个单列、一个缓存或者任何需要第一次通过几个步骤的事情,对于懒加载共享模式来说这是一个很好的接口。
在单线程的世界中,这种调用是很糟糕的,应该用一个简单的if语句来代替。但是我们生活在多线程的世界中,dispatch_once是线程安全的。它能保证多个线程同时调用却只会执行块一次。在dispatch_once返回之前,所有线程将会等待直到执行完毕。即使这个对你来说也不是很难完成,但是dispatch_once超级快的执行速度是你很难实现。

单线程的实现

让我们首先看一个简单的单线程的方法实现。这个在实际中是无意义的,但是却能很好的表达出一个具体的意思。注意:这里的dispatch_once_t是一个long类型并初始化为0的变量,其他的值的作用保持不变。下面是实现方法:

void SimpleOnce(dispatch_once_t *predicate, dispatch_block_t block) {
    if(!*predicate) {
        block();
        *predicate = 1;
    }
}

这个实现相当的简单:如果predicate是0,就执行那个block并且把它置为1.随后的调用看见它是1就不再次的调用block。这个正是我们想要的,但是在多线程环境中是完全不安全的。有一种很不好的情况就是两个线程可能会同时执行到if语句,同时调用那个block。不幸的是,使这段代码线程安全将会花费大量的性能是常有的事。

性能

当谈到dispatch_once的性能时,有下列三个不同的场景需要考虑:
1.首次调用dispatch_once的时候,穿入一个给定的断言,并执行block。
2.第一次调用dispatch_once之后,但在这个block完成之前,调用着必须等待直到那个block执行结束。
3.第一次调用dispatch_once之后,但在这个block完成之后,调用者不需要任何的等待立即执行。
场景1的性能在很大程度上是无关紧要的,只要不是异常缓慢。毕竟,它只发生一次。
场景2的性能同样的不太重要。它可能发生几次,但都只发生在block执行的期间。在大多数情况下,它永远不会发生。如果是这样,它很可能就发生一次。甚至在测试中用大量的线程同时调用dispatch_once,并且Block需要很长时间来执行的时候,等待线程的数量仍在千的数量级上。这些调用都必须等待block,虽然这样做会烧一些不必要的CPU时间,但也没有什么大不了的。
场景3的性能是极其重要的。在一个程序执行中,这种性质的调用可能会发生数百万,甚至数十亿次。我们希望能够使用dispatch_once来保护执行一次并结果到处都是的计算。理想情况下,dispatch_once的计算成本不应超过明确做提前计算并从一些全局变量返回结果的成本。换句话说,一旦你达到场景3中,我们真正想要这两个代码块平等的执行:

id gObject;

void Compute(void) {
    gObject = ...;
}

id Fetch(void) {
    return gObject;
}

id DispatchFetch(void) {
    static id object;
    static dispatch_once_t predicate;
    dispatch_once(&predicate, ^{
        object = ...;
    });
    return object;
}

在内联和优化的情况下,我用SimpleOnce方法来做测试。在我的电脑上面,它花费了0.5ns的时间。这在以后将会作为线程安全的对比标准。

线程安全标的准做法是对共享数据加把锁。比较棘手的是,这里没有一个好的地方在需要保护的数据上面加锁,因为dispatch_once_t是一个long类型,没有地方来加锁。
我们可以修改API结构,让它包含一个锁和一个标记。但在保留和dispatch_once一样的方法签名,因为这仅仅是说明性的代码。我决定使用一个全局锁。代码使用一个静态的pthread_mutex_t来保护断言对所有访问。在有很多不同的断言实际项目中,这将是一个可怕的想法,因为没有关系的断言还要相互等待彼此。但对一个简短的例子来说,我只测试一个断言。除了加了一个锁,代码和之前是一样的:

void LockedOnce(dispatch_once_t *predicate, dispatch_block_t block) {
    static pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;
    
    pthread_mutex_lock(&mutex);
    if(!*predicate) {
        block();
        *predicate = 1;
    }
    pthread_mutex_unlock(&mutex);
}

这段代码是线程安全的,但不幸的是慢很多。在我的电脑,与上个版本0.5ns相比,每次调用大概需要30ns。锁是非常快,但是是纳秒级别。

自旋锁

自旋锁是一种实现把锁本身的开销降到最低的锁。这个名字来自这个锁在锁住的时候,反复轮询查看自己是否被释放。一个普通锁将配合操作系统睡眠等待的线程,并在锁释放的时候唤醒他们。这样可以节省CPU时间,但额外的开销可不是免费的。自旋锁可以解决这个怎么减少这些时间的问题。当多个线程试图同时尝试加锁的时候,这个锁并不被持有,当然会以低效率为代价。
OS X提供了一个方便的OSSpinLock的API来实现自旋锁的功能。下面是用OSSpinLock来实现LockedOnce,仅仅改变了很少的字:

void SpinlockOnce(dispatch_once_t *predicate, dispatch_block_t block) {
    static OSSpinLock lock = OS_SPINLOCK_INIT;
    
    OSSpinLockLock(&lock);
    if(!*predicate) {
        block();
        *predicate = 1;
    }
    OSSpinLockUnlock(&lock);
}

在我的电脑上面大约每次调用花费6.5ns,对于上个用pthread_mutex版本的花了30ns来说是一个很大的改进。然而,它仍然远高于花了0.5ns的不安全的版本。

原子操作

原子操作是低级的CPU操作始终是线程安全的并且还没有锁。(严格意义上说,他们使用锁在硬件层面,但这是一个实现细节。)他们是你想实现锁的时候第一个应该考虑的。当锁花费了太多的开销,直接使用原子操作是一个提高性能的方法。线程编程没有锁可能会非常棘手,所以使用原子操作不是一个好主意,除非你真的真的需要它。在这种情况下,我们讨论的是一个可以大量使用的操作系统库,所以这种场景还是比较适合。
这个原子性操作的block是比较和交换,这个是单线程操作,相当于下面代码:

BOOL CompareAndSwap(long *ptr, long testValue, long newValue) {
    if(*ptr == testValue) {
        *ptr = newValue;
        return YES;
    }
    return NO;
}

也就是说,它测试内存中的某个位置是否一直是一个值,如果是个新值的话,就交换。返回值是是否交换过。因为比较和交换被实现为一个原子CPU指令。不过得保证如果多个线程都试图访问这同一个内存位置时,只有一个会成功。
这个版本的函数的实现策略是将三个值分配给这个断言变量。0表示它永远不会被碰到。1表示这个block目前正在执行,任何调用者应该等待它。2表示block已经执行完成,所有的调用者都可以返回。
比较和交换将用于检查0和在那种情况下自动过渡到1。如果成功了,第一个线程就开始调用,然后将运行。在运行完成之后,它将断言变量置为2表明它已经完成。
如果比较和交换失败,那么它将进入一个循环,反复检查2,直到成功。这将导致它等待其他线程执行完那个block。
第一步是断言变量指针转换成一个一直变化的指针,为了告诉编译器这个值可以被其他线程在函数中改变:

void AtomicBuiltinsOnce(dispatch_once_t *predicate, dispatch_block_t block) {
    volatile dispatch_once_t *volatilePredicate = predicate;

接下来是比较和交换。GCC和clang编译器都提供了以__sync开头的内置函数来实现原子操作的。现在较新的一部分是以__atomic开头的,这个项目中我就用我所知道的函数。下面的函数的作用就是比较如果相等就swap,并且返回true,否则返回false。

if(__sync_bool_compare_and_swap(volatilePredicate, 0, 1)) {

如果上面的操作成功了,证明函数返回为true。在这种情况下,这意味着那个断言变量是0,而且是第一次访问。然后开始下一个任务就是调用block:

block();

当block完成之后,将断言变量置为2,来应对任何等待线程和任何未来的调用者。然而,在此之前,我们需要一个内存屏障,以确保每个人都看到适当的读和写的顺序。更稍微多说一点,用内置函数__sync_synchronize执行一个内存屏障:

__sync_synchronize();

然后这个断言变量可以安全的设置了。

*volatilePredicate = 2;
} else {

while(*volatilePredicate != 2)
;

如果断言变量不是0,然后进入循环等待它变成2。如果它已经2,这个循环就立即终止。如果它是1,那么它一直在循环中,不断重新测试断言变量的值,直到它变成2:

__sync_synchronize();
}
}

这样子的作品应该是安全的。(无锁线程编码相当的棘手以至于我不想直接的宣布没有人比我更投入的研究它。但这是一个相当简单的场景,在任何情况下我们并不试图应用于产品中。)
性能怎么样?原来也不太好。在我的电脑,每次调用大概需要20纳秒,有点高于自旋锁的那个版本。

早期补救

对于这段代码有一个明显的优化。常见的情况是当断言变量是2的时候,代码任然第一次判断是否是它0。首先测试2和在此时优化一下,常见的情况可以更快。代码很简单:也就是在顶部添加一个检查是否是2的功能,如果它是2的话,就在内存屏障之后返回:

void EarlyBailoutAtomicBuiltinsOnce(dispatch_once_t *predicate, dispatch_block_t block) {
    if(*predicate == 2) {
        __sync_synchronize();
        return;
    }
    volatile dispatch_once_t *volatilePredicate = predicate;
    if(__sync_bool_compare_and_swap(volatilePredicate, 0, 1)) {
        block();
        __sync_synchronize();
        *volatilePredicate = 2;
    } else {
        while(*volatilePredicate != 2)
            ;
        __sync_synchronize();
    }
}

这是在第一个版本的代码中一个不错的改进,每次调用约为11.5纳秒。然而,这仍然是比半纳秒的目标要慢得多,甚至还低于自旋锁的代码。
内存屏障并不是没有花销的,这就解释了为什么这段代码是低于我们的预期。至于为什么要慢于自旋锁,是因为不同类型的内存屏障。__sync_synchronize生成的mfence指令,在处理SSE4流读/写方面很可能是最偏执的一个,而OSSpinLock相对来说是很适合普通的代码。我们可以用更多的判断来优化这个代码以获得更好的性能,但很明显成本仍然要高于我们预期,所以我将会跳过。

不安全的早期补救

让我们来看另一个版本的代码。除了它的内存屏障外其他的都相同:

void UnsafeEarlyBailoutAtomicBuiltinsOnce(dispatch_once_t *predicate, dispatch_block_t block) {
    if(*predicate == 2)
        return;
    volatile dispatch_once_t *volatilePredicate = predicate;
    if(__sync_bool_compare_and_swap(volatilePredicate, 0, 1)) {
        block();
        *volatilePredicate = 2;
    } else {
        while(*volatilePredicate != 2)
            ;
    }
}

果然不出所料,这样执行和SimpleOnce一样的快,每次调用约0.5纳秒。由于*predicate == 2 对于最常见的情况,几乎每一个调用都执行检查并返回。在block已经被调用之后的情况下,这个工作量和SimpleOnce都是同样的。
然而,正如它的名字表明,缺乏内存屏障使它很不安全。为什么呢?

分支预测,乱序执行和你

我们假设cpu是简单的机器。我们告诉他们做一件事,他们这样做。然后我们告诉他们去做下一件事,然后他们就做。一直重复着直到我们感到无聊或者它没电了。
以前这是真实的存在的。旧的cpu确实很像简单的机器做这样的工作。他们获取一条指令,执行它。然后他们获取下一条指令,再执行它。
不幸的是,虽然这种方法很简单容易,但是并不是非常快。摩尔定律赐予我们不断增长的晶体管数量来堆到cpu。8086CPU中大约有29000个晶体管。一个英特尔Haswell架构的CPU包含超过十亿个晶体管。
市场——希望更好的电脑游戏(以及少数人想要更快地执行各种无聊的并不值得一提的业务任务)——要求CPU制造商使用这些进展获得更好的性能。现代化CPU是人们花数十年的工作将更多的晶体管变成更快的电脑的产品。
有很多技巧使cpu的速度更快。其中之一是流水线化(pipelining)。执行单个CPU指令的时候会分为很多小的步骤:
1。从内存加载指令。
2。解码指令。(也就是说找出指令里面的操作数)。
3。加载输入数据。
4。对输入数据执行操作。
5。保存输出。
早期CPU中的工作序列的类似于下面:
加载指令
解码指令
加载数据
执行操作
保存输出
加载指令
解码指令
加载数据
执行操作
保存输出

但只要你有足够的资源,你可以并行执行这些操作。有流水线化的CPU,并行序列的工作最终会看起来更像这样:

加载指令
解码指令 加载指令
加载数据 解码指令 加载指令
执行操作 加载数据 解码指令
保存输出 执行操作 加载数据
        保存输出  执行操作
                 保存输出

这样子快得多!但是足够多的晶体管同时并行执行许多指令使事情会变得更加复杂。
除此之外,如果有加快速度的话,指令被完全的乱序执行。不像上面的简化示例,现实世界的指令往往需要更多的步骤而且步骤里面有很多的差异。例如,读写内存可能需要大量的时间。通过在读出指令流之前执行其他工作,CPU可以从事很多的工作而不是闲置下来一直等待。正因为如此,CPU会发现这样做有利于乱序读写在指令流中出现相应的指令。
上述东西的最终结果是,你的代码并不总是看起来像它运行的顺序那样运行。如果你写:

x = 1;
y = 2;

您的CPU可以先执行写入y。在某些情况下编译器也可以重新排序,甚至你排除这些,CPU仍然可以这样做。如果你有多个CPU系统(正如我们这些天总是这样做)其他CPU就会乱序的写入。即使写入是按顺序执行,其他cpu也可以不按顺序的读取。总之,另一个线程在读取x和y的时候可以看到y = 2,但仍然看到x的旧值。
有时你需要这些值按照代码顺序读写,那得设置一个内存屏障。在上面的代码添加一个内存屏障确保x是先写的:

x = 1;
memory_barrier();
y = 2;

同样,一个内存屏障能确保下面代码以正确的顺序执行:

use(x);
memory_barrier();
use(y);

然而,由于内存屏障的整个人生的目标就是阻止CPU试图运行的更快,所以就有一个内在的性能损失。
因为有多个读写序列,并且它们的顺序是非常重要的,这一点与dispatch_once和懒加载一样。

static SomeClass *obj;
static dispatch_once_t predicate;
dispatch_once(&predicate, ^{ obj = [[SomeClass alloc] init]; });
[obj doStuff];

如果obj在predicate之前被读到,那么这段代码很可能在它为空的时候读到它,刚好在另一个线程写最后的值到变量和设置predicate之前。这段代码可以读谓词作为表明工作完成,从而继续使用未初始化零。这段代码可以读predicate表明工作完成,从而继续使用未初始化的nil。甚至可以想象,这个代码能读正确的值obj,但是读取的是未初始化的未为对象分配内存的值,当试图发送doStuff引发crash。
因此,dispatch_once需要内存屏障。但正如我们所看到的,内存屏障相对缓慢。在普通情况下如果我们能避免它,我们不想付这个代价。

分支预测和预测执行

流水线、无序模型非常适合一个线性序列的指令,但是在条件分支时候会出现麻烦。CPU不知道从哪里开始抓取更多的指令,直到分支条件可以评估,通常取决于指令的前面。CPU必须停止,等待前面的工作完成,然后评估分支条件和恢复执行。这叫做管道停止,将会造成很大的性能损失。
为了弥补这样的损失,CPU会进行预执行,cpu先猜测一个可能的分支,然后开始执行分支中的指令。现代CPU一般都能做到超过90%的猜测命中率,这可比NBA选手发球命中率高多了。然后当判定语句返回,假如cpu猜错分支,那么之前进行的执行都会被抛弃,然后从正确的分支重新开始执行。
在dispatch_once中,唯一一个判断分支就是predicate,dispatch_once会让CPU预执行条件成立的分支,这样可以大大提升函数执行速度。但是这样的预执行导致的结果是使用了未初始化的obj并将函数返回,这显然不是预期结果。

不平衡的屏障

写屏障通常都是需要对称的。一方面要确保按照正确的顺序写入,另一方面也要确保以正确的顺序读取。然而,在这种特定的情况下我们的性能需求完全不对称。我们可以容忍写入方面巨大的缓慢,但是我们想要在读取方面尽可能快。
关键是要解决引发难题的预测执行。当分支预测是不正确的,预测执行的结果将被丢弃,这意味着可能把未初始化值丢弃在内存中。如果dispatch_once可以强制一个分支在初始化值对所有cpu的可见之后预测失败,那么这个难题就解决啦。
在条件分支之后最早的可能预测内存读取断言变量与条件分支实际上被评估之间有一个关键的间隔。间隔的确切长度取决于特定的CPU设计,但它通常会比CPU周期低很多。
如果写的一边至少等待相当长的时间在初始化值和写入最后的值到断言变量之间,一切都好。但是所有的懒加载无序执行将难以保证再次发挥作用。
在Intel CPU中,dispatch_once用cpuid指令来达到目的。cpuid指令是用来获取身份标识信息和功能的,但它也强行序列化指令流并需要一定的时间执行,大约需要几百个CPU周期来完成这项工作。
如果你看dispatch_once的源码实现,你会看到在读取方面没有任何的屏障:

DISPATCH_INLINE DISPATCH_ALWAYS_INLINE DISPATCH_NONNULL_ALL DISPATCH_NOTHROW
void
_dispatch_once(dispatch_once_t *predicate, dispatch_block_t block)
{
    if (DISPATCH_EXPECT(*predicate, ~0l) != ~0l) {
        dispatch_once(predicate, block);
    }
}
#define dispatch_once _dispatch_once

这是在头文件声明,并且总是内联编译在调用者里面。DISPATCH_EXPECT是一个宏,它告诉编译器编译的代码要告诉CPU:*predicate更有可能等于~0L。这可以提高分支预测的成功率,从而提高性能。最终,这只是一个简单的没有任何障碍的if语句。性能测试也证明了这一点:调用真正的dispatch_once很符合0.5 ns的目标。
在写方面也可以找到实现。调用block之后,在做任何其他事情之前,dispatch_once使用这个宏:

dispatch_atomic_maximally_synchronizing_barrier();

在Intel上,这个宏生成一个cpuid指令,并针对其他CPU架构产生适当的组装。

结论

多线程是一个奇怪而复杂的世界,尤其是现代CPU设计的在你背后做更多的事情。当你真正需要按照一定的顺序来做事情时,内存屏障允许你通知硬件这样做,但是会付出了一定的代价。dispatch_once独特的需求允许它以非传统的方式解决问题。由于要在相关内存写入之间的等待足够长的时间,它确保读者总是看到一个一致的图像,而不需要在每个访问花费一个内存屏障的成本。
今天就到这儿。下次回来将带更多令人兴奋的东西,很可能讨论这些天关于Swift的问题。如果你有一个想在这里看到的话题,除了“谈论Swift”(这是一个很好的话题,但在这一点上有足够的要求),请发送!

  1. 还没有评论
评论提交中, 请稍候...

留言


可以使用的标签: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>
Trackbacks & Pingbacks ( 0 )
  1. 还没有 trackbacks