手撸一款简单高效的线程池（二）
在上一章中，我们给大家简单介绍了传统 C++的线程池实现方案中存在的一些问题，并且立下 flag 要做一款简单好用、高性能的线程池。接下来，我们就用几章的内容，把曾经吹过的牛 B，编程实现。
大家好，我是不会写代码的纯序员——Chunel Feng[1]。这篇文章是线程池优化系列连载的第二篇。主要跟大家介绍几种线程池优化思路，包括：local-thread 机制、lock-free 机制、work-stealing 机制。
还是要提前说明一下，多线程并发的知识博大精深，且涉及内容极其广泛。以下介绍的内容也仅局限在我个人的认知范围。如果大家有什么意见和建议，请多多指教。
首先，还是照例，先上源码链接：CGraph 源码链接[2] 其中，线程池的实现在 /src/UtilsCtrl/ThreadPool/ 文件夹中。
local-thread 机制
上一章，我们分析传统的线程池的一个瓶颈，在于多个 thread 去【争抢】pool 中任务队列中的第一个 task，这里是有锁操作，会有一定的性能开销。而引入 local-thread 技术就是为了在一定程度上减少这种开销。
C++11 版本开始，已经引入了thread_local关键字，但是很少见有人用。具体到做工程的童鞋，其实更喜欢的方式，应该是自己封装一个属于自己的 thread 类，那这里的东东不就都是local了么。
为此，CGraph 中封装了 UThreadPrimary 类，其中就包含了一个 UWorkStealingQueue 类的对象。这是一个类似 std::deque 结构的双向队列，可以从头部弹出节点，也可以从尾部弹出节点。
把原先 pool 中 queue 中的任务，放到不同的 n 个线程的私有的 n 个 queue（UWorkStealingQueue 类型）中，线程执行任务的时候就不需要再从 pool 的 queue 中获取去【争抢】了。从而是不是就达到了“增加扇出”的效果。
再往前想一步，最初的线程池模型中，外部写入的时候也是写入 pool 中的 queue，会存在一个【争抢】写入，也会在 queue 被读的时候，无法抢到锁。那写入 thread 中的 queue 的话，是不是也一定程度上提升了“增加扇入”的效果。毕竟，跟你竞争的只有本线程的读操作了啊。
local-thread 还有一点内容，就是本线程执行过程中，产生的 task（尽可能的）放在本线程的 queue 中执行。这样也是local的一种体现，而且也会在一定程度上增加线程的亲和性——这个跟线程内部资源的缓存有关。
lock-free 机制
lock-free 是无锁编程的技术，也叫做 lockless 技术。lock-free 也分好几种维度，比如：基于 atomic 的、基于内部封装 mutex 的、基于 cas 机制的。当然可能还有一些我不知道的，欢迎补充。
无锁，乍一听像是并发编程的时候不用上锁了。但在你不加锁的时候，别人在暗中默默的帮你加了锁。举个例子，C++11 中的std::atomic<int>类型，就是一种无锁类型。但其实在这种类型的变量，做多线程并发的i++的时候，在变量内部维护了一个 spin-lock（自旋锁，确保当前线程不被切换）和一个 cas（乐观锁，确保最终数值正确）。说是无锁，实际上看进去之后会发现，还不止有一个锁——只是外部程序不感知罢了。
CGraph 中的 UAtomicQueue 类，采用的也是类似的技术。不过并不是 cas，而是内部加入 std::mutex 和 std::condition_variable 来进行控制。还有，刚才聊到的 UWorkStealingQueue 类，也属于无锁类型——仅是外部看上去无锁罢了。在内部封装的过程中，我们也在一些特定的情况下使用了 yield()方法让出线程的执行权限，实测效果是有明显提升的。
这里后期可以考虑尝试使用 cas 的方式实现一下，理论上 cas 是比直接内部上锁快一些的。
work-stealing 机制
任务偷窃机制——这种技术常被用于线程之间相互 backup 的场景中，Java 版本的线程池中也有这项技术。
通俗解释一下，比如当前线程池里有 3 个线程，分别为 thd1，thd2 和 thd3 吧。每个线程中的 local queue 中都包含了 100 个任务——已经很负载均衡了吧。我们设想极端一些哈，比如 thd3 的 task 都是sleep 1s，而 thd1 和 thd2 中的 task 都是sleep 1ms。如果每个 thd 仅执行自己 local queue 中的内容，那这个任务总体的耗时应该是max(100ms, 100ms, 100s) = 100s。
但是在所有任务开始执行的 100ms 后，thd1 和 thd2 就已经无工可做了（像极了 35 岁后的纯序员本员），但是 thd3 还是在苦苦支撑着，一直到 100s 结束。这显然是不太合理的。
一种比较合理的做法是，在 thd1 和 thd2 在执行 local 任务结束之后，可以去 thd3 的队列中去 stealing 一些任务（就是sleep 1s的那种）执行——这就是所谓的 work-stealing 机制。这种机制的优势也是很明显的，针对刚才描述的情况，原先 100s 才能执行完的任务，整体耗时瞬间就被降低到 30+s 左右。
需要说明的是，work-stealing 机制并不是一个万金油。比如，上面提到的头部/尾部弹出，明显会打乱任务执行顺序，所以这种机制更适合那种“可执行任务一把梭哈”的情况——对，我指的就是CGraph这种图执行框架。因为需要被放入线程池中的任务，都是可以无序并发执行的，有依赖的任务也不会被放入 pool 中啊。
还有一个问题哈，当 thread 本地没有 task 的时候，从哪个 thread 去 stealing 呢？一般的做法，是在初始化的 pool 时候给每个线程设定编号：比如 0~7，用 index 表示。thread5 进行 stealing 的时候，一般是从 thread6 的 queue 中开始，然后 thread7、thread0... 依次递推到 thread4。这样做的好处，是避免了大家都从某一个 thread 开始 stealing 而导致的不均衡。每个线程在 local 执行任务的时候，从 UWorkStealingQueue 的头部弹出 task，在偷/被偷的时候从 UWorkStealingQueue 尾部弹出 task。
有些时候，work-stealing 机制甚至可能成为“累赘”。举个例子，pool 中一共有 100 个线程吧，那当 thread0 中 queue 无任务的时候，thread0 会去遍历其他的 99 个 thread——就为了盗取一个任务。这个遍历有阻塞耗时不说，也会影响到 thread0 去执行新来的 local task——像极了天天帮同事排查 bug，但是自己一大堆 bug 却来不及修复的纯序员本员。
我们之前提过 local 的内容亲和性是最高的，理应优先执行，对吧。针对这种情况，一种可行的解决办法是设定“盗取范围”（对应 CGraph 中的CGRAPH_MAX_TASK_STEAL_RANGE参数）。比如，thread0 仅可以从相邻的 3 个线程（也就是 thread1、thread2 和 thread3）中盗取任务，如果在这 3 个 thread 中都盗取不到，那就重新尝试看 local 的 queue。其他线程亦是如此。也就是说，大家仅关系自己本地的 task 和自己若干个邻居的 task，离得远的就不用问了。这种“事不关己高高挂起”（低情商说法）行为，在很多情况下却是好事，因为它还有一种高情商说法，就是“专注于自己的工作”，嘿嘿。
随便放几句相关的代码哈，更多代码大家去 github 上面看哈。
/*** 从其他线程窃取一个任务* @param task* @return*/bool stealTask(UTaskWrapperRef task) {if (unlikely(pool_threads_->size() < CGRAPH_DEFAULT_THREAD_SIZE)) {/*** 线程池还未初始化完毕的时候，无法进行steal。* 确保程序安全运行。*/return false;}/*** 窃取的时候，仅从相邻的primary线程中窃取* 待窃取相邻的数量，不能超过默认primary线程数*/int range = CGRAPH_MAX_TASK_STEAL_RANGE % CGRAPH_DEFAULT_THREAD_SIZE;for (int i = 0; i < range; i++) {/*** 从线程中周围的thread中，窃取任务。* 如果成功，则返回true，并且执行任务。*/int curIndex = (index_ + i + 1) % CGRAPH_DEFAULT_THREAD_SIZE;if (nullptr != (*pool_threads_)[curIndex]&& (((*pool_threads_)[curIndex]))->work_stealing_queue_.trySteal(task)) {return true;}}return false;}
我实测的一个结果，在开 16 个 thread 运行 48 路大批量空跑 task（就是所有的 task 都是return 0，这样可以一定程度体现出来 pool 的调度能力）情况下，如果不设定 steal 范围，大概是 194s 的样子，已经退化到跟普通线程池基本持平的水平了。而把 steal 范围设置为 4 之后，直接降低到了 163s 左右。不要问我怎么发现这个问题，火焰图会教你做人的。
本章小结
本章主要是介绍了一些线程池在设计过程中，有哪些优化点。总结一下就是下图中画红框的地方，主要的目的就是可以增加扇入扇出。今天分享的这几点偏硬核，都是我在自测过程中，的的确确可以增加调度性能的方案。我们也会在接下来的文章中，继续介绍 CGraph 中线程池的相关优化内容和思路。
如果你对这方面的内容也感兴趣，请加我微信以便随时联系。有什么实用的功能，我们可以尝试去一起实现。有什么好的指教和意见，也欢迎随时提出来，以便我们改进和提高。
接下来一章，我们将会跟大家介绍一下其他的一些线程池优化机制，比如主辅线程、自动扩缩容等。欢迎大家继续关注。
推荐阅读
•纯序员给你介绍图化框架的简单实现——执行逻辑[3]•纯序员给你介绍图化框架的简单实现——循环逻辑[4]•纯序员给你介绍图化框架的简单实现——参数传递[5]•纯序员给你介绍图化框架的简单实现——条件判断[6]•纯序员给你介绍图化框架的简单实现——线程池优化（一）[7]
引用链接
[1] Chunel Feng: http://www.chunel.cn[2] CGraph 源码链接: https://github.com/ChunelFeng/CGraph[3] 纯序员给你介绍图化框架的简单实现——执行逻辑: http://www.chunel.cn/archives/cgraph-run-introduce[4] 纯序员给你介绍图化框架的简单实现——循环逻辑: http://www.chunel.cn/archives/cgraph-loop-introduce[5] 纯序员给你介绍图化框架的简单实现——参数传递: http://www.chunel.cn/archives/cgraph-param-introduce[6] 纯序员给你介绍图化框架的简单实现——条件判断: http://www.chunel.cn/archives/cgraph-condition-introduce[7] 纯序员给你介绍图化框架的简单实现——线程池优化（一）: http://www.chunel.cn/archives/cgraph-threadpool-1-introduce