GCD源码分析（四）——dispatch_once(下)

发表于 | 分类于 |

一、引言

上篇文章中讲到，dispatch_once使用无锁方式实现线程安全和优异的性能。本篇文章我们来分析一下dispatch_once的性能。

从dispatch_once的源码可以看出，其本质就是一个if-else语句。我们使用非线程安全的纯if-else语句作为空白对照。

纯if-else:

1
2
3
4
5
6
7
8
9
10
- (void)benchmark {
    TestObject *obj = nil;
    mach_timebase_info(&_timebaseInfo);
    uint64_t start = mach_absolute_time();
    if (!obj) {
        uint64_t end = mach_absolute_time();
        uint64_t duration = (end - start) * _timebaseInfo.numer / _timebaseInfo.denom;
        NSLog(@"=== benchmark: %llu", duration);
    }
}

接下来是用pthread_mutex_lock实现的线程安全的if-else：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
- (void)mutexLock {
    TestObject *obj = nil;
    mach_timebase_info_data_t timebaseInfo;
    mach_timebase_info(&timebaseInfo);
    pthread_mutex_t lock = PTHREAD_MUTEX_INITIALIZER;
    uint64_t start = mach_absolute_time();
    pthread_mutex_lock(&lock);
    if (!obj) {
        //obj = [TestObject new];
    }
    pthread_mutex_unlock(&lock);
    uint64_t end = mach_absolute_time();
    uint64_t duration = (end - start) * _timebaseInfo.numer / _timebaseInfo.denom;
    NSLog(@"=== mutex_lock: %llu", duration);
}

最后是dispatch_once：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
- (void)dispatchOnce {
    __block TestObject *obj = nil;
    mach_timebase_info_data_t timebaseInfo;
    mach_timebase_info(&timebaseInfo);
    
    for (int i = 0; i < 5; i++) {
        uint64_t start = mach_absolute_time();
        static dispatch_once_t onceToken;
        dispatch_once(&onceToken, ^{
            //obj = [TestObject new];
        });
        uint64_t end = mach_absolute_time();
        uint64_t duration = (end - start) * _timebaseInfo.numer / _timebaseInfo.denom;
        NSLog(@"=== dispatch_once %llu", duration);
    }
}

在我的macbook pro上测试三种方式的耗时（单位：纳秒）分别为：

  1. 纯if-else：41
  2. pthread_mutex_lock: 13429
  3. dispatch_once: 5次输出分别为：3457、328、298、293、194

可以看出纯if-else语句耗时最少，而效率相对较高的pthread_mutex_lock锁比之dispatch_once的性能有最高40多倍的差距！（dispatch_once首次执行耗时较多）。
回顾下上篇中讲到的dispatch_once的三个场景：

  1. 第一次执行，执行block，执行完成后置predicate标记
  2. 非第一次执行，而步骤1尚未执行完毕，此时线程需要等待步骤1完成，步骤1完成后依次唤醒等待的线程
  3. 非第一次执行，且步骤1已经执行完成，线程跳过block继续执行后续任务

思考一下，在程序的实际运行中，场景1最多发生一次，场景2发生的次数很少甚至可能一次也不会发生，而场景3是程序执行中最常见的，可能成千上万次地执行。场景3的效率直接影响到整个程序的运行效率。

从上述的简单测试中发现：针对场景3，dispatch_once只比纯if-else语句慢不到10倍，但是它有着比pthread_mutex_lock高40多倍的性能表现，而且这是在保证线程安全的前提下的性能，确实不可思议，dispatch_once究竟是怎么做到的呢？

二、CPU指令流水与dispatch_once

回顾《计算机组成原理》的知识，CPU的指令执行一般包括：取指、译码、执行、回写三个步骤。

在最古老的CPU上，指令是严格按照顺序执行的：

而现代CPU为了提升运行速度，加入了指令流水线、分支预测和乱序执行等特性，此时CPU的执行顺序如下（图片出自Wikipedia）：

2.1 CPU分支预测

流水线特性使得CPU能够更快速地执行线性指令序列，但是对于if-else语句，在条件判断结果出来之前，CPU不知道应该执行哪个分支，如果此时让CPU停下来等待判断结果显然不是最优的做法。

所以现代CPU加入了分支预测的特性，分析程序以往运行记录猜测本次要执行的分支并进行预执行，这样就会产生两个结果：

  1. 猜测正确，CPU无需等待判断结果了，继续往下执行。这样效率是最高的。
  2. 猜测错误，CPU要抛弃所有预执行的结果，重置寄存器等，回滚到正确的分支，重新热启动。由于现代编译器的高度复杂性，程序运行时往往有着很长的piplines，回滚状态和热启动都是很耗时的。

幸运的是，大多数的程序都有着状态良好的（well-behaved）分支，比如：dispatch_once_f的if-else语句。所以现代CPU的分支预测一般能达到90%的准确率，但是面对无法预测的分支（比如，判断的条件依赖网络返回值等），分支预测就无用武之地了。

想了解更详细的分支预测，请戳这里：Wikipedia_Brach_predictor。

2.2 barrier

现代CPU为了尽可能快的运行速度，加入了分支预测和预执行技术。想象一下如下场景：

1
2
3
4
5
6
static TestObject *obj;
static dispatch_once_t predicate;
dispatch_once(&predicate, ^{
    obj = [TestObject new];
});
[obj description];

线程A第一次执行dispatch_once，此时线程B、C、D执行dispatch_once，CPU根据以往的经验预执行了“dispatch_once已执行完毕”的分支，但是此时线程A的block尚未执行完毕，obj是nil，此时程序往下执行必然会导致异常行为，严重时甚至会引起crash。

这种问题要如何避免呢？

这时，dispatch_once需要一种类似于Memory_barrier的机制，防止CPU跑的太快导致程序的异常。当然由于memory_barrier的开销比较大，在对性能很敏感dispatch_once中尽量不要使用。

我们在_dispatch_once函数中发现了这样一行代码：

1
dispatch_compiler_barrier();

它是一个宏：

1
2
3
4
5
6
7
#if __GNUC__
#define DISPATCH_EXPECT(x, v) __builtin_expect((x), (v))
#define dispatch_compiler_barrier()  __asm__ __volatile__("" ::: "memory")
#else
#define DISPATCH_EXPECT(x, v) (x)
#define dispatch_compiler_barrier()  do { } while (0)
#endif

在GCC编译器下，dispatch_compiler_barrier使用__asm__ __volatile__("" ::: "memory")语句创建了一个memory_barrier。

扩展：Xcode编译器的历史

由于GCC是一个开源组织维护的编译器，GCC的开发组很傲娇，经常无视或者拖延Apple对GCC提出的各种需求，同时GCC对Objecttive-C的许多新特性的支持并不友好。因此，苹果从Xcode3开始就着手使用自家的LLVM编译器代替GCC了，到Xcode5版本时，GCC已被完全废弃，使用LLVM代替。现在Xcode中使用的编译器普遍是Clang-LLVM了，这个编译器的作者是大名鼎鼎的Swift之父Chris Lattner。

Clang-LLVM比GCC优秀在哪些方面
据说新的Clang编译器编译Objective-C代码速度比GCC快3倍，并且提供了更友好的代码提示。

对比下新老版本的dispatch_once是如何解决由于CPU预执行了错误的分支而导致的程序异常的问题。

2.2.1 libdispatch-187.9

看下相关代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
void
dispatch_once(dispatch_once_t *val, dispatch_block_t block)
{
	struct Block_basic *bb = (void *)block;

	dispatch_once_f(val, block, (void *)bb->Block_invoke);
}

void
_dispatch_once_f(dispatch_once_t *predicate, void *context,
		dispatch_function_t function)
{
	if (DISPATCH_EXPECT(*predicate, ~0l) != ~0l) {
		dispatch_once_f(predicate, context, function);
	}
}

void
dispatch_once_f(dispatch_once_t *val, void *ctxt, dispatch_function_t func)
{
	struct _dispatch_once_waiter_s * volatile *vval =
			(struct _dispatch_once_waiter_s**)val;
	struct _dispatch_once_waiter_s dow = { NULL, 0 };
	struct _dispatch_once_waiter_s *tail, *tmp;
	_dispatch_thread_semaphore_t sema;

	if (dispatch_atomic_cmpxchg(vval, NULL, &dow)) {
		dispatch_atomic_acquire_barrier();
		_dispatch_client_callout(ctxt, func);

		dispatch_atomic_maximally_synchronizing_barrier();
		//dispatch_atomic_release_barrier(); // assumed contained in above
		tmp = dispatch_atomic_xchg(vval, DISPATCH_ONCE_DONE);
		tail = &dow;
		while (tail != tmp) {
			while (!tmp->dow_next) {
				_dispatch_hardware_pause();
			}
			sema = tmp->dow_sema;
			tmp = (struct _dispatch_once_waiter_s*)tmp->dow_next;
			_dispatch_thread_semaphore_signal(sema);
		}
	} else {
		dow.dow_sema = _dispatch_get_thread_semaphore();
		for (;;) {
			tmp = *vval;
			if (tmp == DISPATCH_ONCE_DONE) {
				break;
			}
			dispatch_atomic_store_barrier();
			if (dispatch_atomic_cmpxchg(vval, tmp, &dow)) {
				dow.dow_next = tmp;
				_dispatch_thread_semaphore_wait(dow.dow_sema);
			}
		}
		_dispatch_put_thread_semaphore(dow.dow_sema);
	}
}

老版本的libdispatch在写入端的执行block和设置predicate值为DISPATCH_ONCE_DONE中间加入了dispatch_atomic_maximally_synchronizing_barrier();这样一行语句，使得dispatch_once在置predicate的值为done之前，让CPU等待足够长的时间，防止CPU由于预执行到错误的分支而却认为自己执行对了，而继续执行从而导致程序行为异常。

另一个线程B（耗时为Ta）在预执行读取了未初始化的obj值之后，回过头来确认猜测正确性时，predicate可能被执行block的线程A置为了“done”，这就导致线程B误认为自己的预执行有效（实际上它读取了未初始化的值）

dispatch_atomic_maximally_synchronizing_barrier()实际上是调用GCC的__sync_synchronize(...)函数发出一个full_barrier，它其实生成了一个的memory_barrier，效率比较低。

2.2.2 libdispatch-913.1.6

由于苹果在最新版的Xcode摒弃了GCC，因此新版本的libdispatch中也放弃使用了一些GCC中的操作，比如__sync_synchronize。

回顾下代码：

1
2
3
4
5
6
7
8
9
10
void _dispatch_once_f(dispatch_once_t *predicate, void *_Nullable context,
		dispatch_function_t function)
{
	if (DISPATCH_EXPECT(*predicate, ~0l) != ~0l) {
		dispatch_once_f(predicate, context, function);
	} else {
		dispatch_compiler_barrier();
	}
	DISPATCH_COMPILER_CAN_ASSUME(*predicate == ~0l);
}

与老版本不同的是，新版本增加了else分支和DISPATCH_COMPILER_CAN_ASSUME语句。

dispatch_compiler_barrier()在GCC编译器下使用__asm__ __volatile__ ("" ::: "memory")制造一个memory_barrier，但是在Clang-LLVM编译器下，它转换成如下语句：

1
do { } while (0);

可以看到，无论CPU预测的分支正确与否，预执行的语句始终被局限在_dispatch_once_f函数中，即使第一次执行dispatch_once时，CPU分支预测错误，预执行了else分支，但是由于else分支中实际上是一句没实际作用的do-while代码，执行它不会对的程序行为产生异常影响。

这样一来，在dispatch_once_f_slow写入端就可以抛弃效率低下的memory_barrier了，进一步提高了dispatch_once的性能。这种做法相当于使用编译器给程序加了一层barrier，这也许就是dispatch_compiler_barrier命名的由来吧。

三、总结&参考文献