当为多线程性能设计你的数据结构时需要考虑的关键问题是竞争、假共享以及数据接近。这三个方面都会对性能产生很大影响,并且通常你可以通过改变数据布局或者改变分配给某线程的数据元素来提高性能。首先,我们来看一个简单的例子,在线程间划分数组元素。
假设你正在做一些复杂的数学计算,你需要将两个大矩阵想乘。为了实现矩阵相乘,你将第一个矩阵的第一行每个元素与第二个矩阵的第一列相对应的每个元素相乘,并将结果相加得到结果矩阵左上角第一个元素。然后你继续将第二行与第一列相乘得到结果矩阵第一列的第二个元素,以此类推。正如图8.3所示,突出显示的部分表明了第一个矩阵的第二行与第二个矩阵的第三列配对,得到结果矩阵的第三列第二行的值。
图8.3 矩阵相乘
有很多在线程间划分工作的方法。假设你有比处理器更多的行例,那么你就可以让每个线程计算结果矩阵中某些列的值,或者让每个线程计算结果矩阵中某些行的值,或者甚至让每个线程计算结果矩阵中规则矩形子集的值。
另一方面,如果每个线程处理一些行元素,那么就需要读取第二个矩阵中的所有元素,以及第一个矩阵中相关的行元素,但是它只会得到行元素。因为矩阵是用行顺序存储的,因此你现在读取从N行开始的所有元素。如果你选择相邻的行,那么就意味着此线程是现在唯一对这N行写入的线程;它拥有内存中连续的块并且不会被别的线程访问。这就比让每个线程处理一些列元素更好,因为唯一可能产生假共享的地方就是一块的最后一些元素与下一个块的开始一些元素。但是值得花时间确认目标结构。
因此将结果矩阵划分为小的方块或者类似方块的矩阵比每个线程完全处理好几行更好。当然,你可以调整运行时每个块的大小,取决于矩阵的大小以及处理器的数量。如果性能很重要,基于目标结构分析各种选择是很重要的。
好了,我们已经看到数组读取方式是如何影响性能的。其他数据结构类型呢?
从根本上说,当试图优化别的数据结构的数据访问模式时也是适用的。
2、最小化任何给定线程需要的数据。
当然,运用到别的数据结构上是不容易的。例如,二叉树本来就很难用任何方式来再分,有用还是没用,取决于树是如何平衡的以及你需要将它划分为多少个部分。同样,树的本质意味着结点是动态分配的,并且最后在堆上不同地方。
使用互斥元保护数据的时候也有同样的问题。假设你有一个简单的类,它包含一些数据项和一个互斥元来保护多线程读取。如果互斥元和数据项在内存中离得很近,对于使用此互斥元的线程来说就很好;它需要的数据已经在处理器缓存中了,因为为了修改互斥元已经将它载入了。但是它也有一个缺点:当第一个线程持有豆斥元的时候,如果别的线程试图锁住互斥元,它们就需要读取内存。互斥元的锁通常作为一个在互斥元内的存储单元上试图获取互斥元的读一修改一写原子操作来实现的,如果互斥元已经被锁的话,就接着调用操作系统内核。这个读一修改一写操作可能导致拥有互斥元的线程持有的缓存中的数据变得无效。只要使用互斥元,这就不是问题。尽管如此,如果互斥元和线程使用的数据共享同一个缓冲线,那么拥有此互斥元的线程的性能就会因为另一个线程试图锁住该互斥元而受到影响。
来测试互斥元竞争问题或者使用：
当然,当设计并发性的时候,不仅需要考虑数据读取模式,因此让我们来看看别的需要考虑的方面。
本章我们看了一些在线程间划分工作的方法,影响性能的因素,以及这些因素是如何影响你选择哪种数据读取模式和数据结构的。但是,设计并发代码需要考虑更多。你需要考虑的事情例如异常安全以及可扩展性。如果当系统中处理核心增加时性能(无论是从减少执行时间还是从增加吞吐量方面来说)也增加的话,那么代码就是可扩展的。从理论上说,性能增加是线性的。因此一个有100个处理器的系统的性能比只有一个处理器的系统好100倍。
8.4.1 并行算法中的异常安全
作为一个具体的例子,我们来回顾清单2.8中的 parallel_accumulate函数,清单8.2中会做一些修改
现在我们检查并且确定抛出异常的位置:总的说来,任何调用函数的地方或者在用户定义的类型上执行操作的地方都可能抛出异常。
跳过block_start 的初始化5因为这是安全的,就到了产生线程的循环中的操作6、7、8。一旦在7中创造了第一个线程,如果抛出异常的话就会很麻烦,你的新sta::thread 对象的析构函数会调用
调用accumulate_block 9也可能会抛出异常,你的线程对象将被销毁并且调用std:terminate ;另一方面,最后调用std::accumulate 10的时候也可能抛出异常并且不导致任何困难,因为所有线程将在此处汇合。
即使不是显而易见的,这段代码也不是异常安全的。
好了,我们识别出了所有可能抛出异常的地方以及异常所造成的不好影响。那么如何处理它呢?我们先来解决在新线程上抛出异常的问题。
清单8.3使用std::packaged_task的std::accumulate的并行版本
下一个改变就是你用futures 向量3,而不是用结果为每个生成的线程存储一个 std:future<T> 。在生成戈程的循环中,你首先为 accumulate_block 创造一个任务4。std:packaged_task<T(Iterator,Iterator)>声明了有两个 Iterator并且返回一个T 的任务,这就是你的函数所做的。然后你将得到任务的future 5,并且在一个新的线程上运行这个任务,输入要处理的块的起点和终点6。当运行任务的时候,将在future中捕捉结果,也会捕捉任何抛出的异常。
因此,这就去除了一个可能的问题,工作线程中抛出的异常会在主线程中再次被抛出。如果多于一个工作线程抛出异常,只有一个异常会被传播,但是这也不是一个大问题。如果确实有关的话,可以使用类似
如果在你产生第一个线程和你加入它们之间抛出异常的话,那么剩下的问题就是线程泄漏。最简单的方法就是捕获所有异常,并且将它们融合到调用joinable()的线程中,然后再次抛出异常。
这与清单2.3中的thread_guard类是相似的，除了它扩展为适合所有线程。你可以如清单8.4所示简化代码。
一旦你创建了你的线程容器,也就创建了一个新类的实例1来加入所有在退出的线程。你可以去除你的联合循环,只要你知道无论函数是否退出,这些线程都将被联合起来。注意调用 futures[i].get() 2将被阻塞直到结果出来,因此在这一点并不需要明确地与线程融合起来。这与清单8.2中的原型不一样,在清单8.2中你必须与线程联合起来确保正确复制了结果向量。你不仅得到了异常安全代码,而且你的函数也更短了,因为将联合代码提取到你的新(可再用的)类中了。
你已经知道了当处理线程时需要什么来实现异常安全,我们来看看使用std::async() 时需要做的同样的事情。你已经看到了,在这种情况下库为你处理这些线程,并且当future是就绪的时候,产生的任何线程都完成了。需要注意到关键事情就是异常安全,如果销毁future的时候没有等待它,析构函数将等待线程完成。这就避免了仍然在执行以及持有数据引用的泄漏线程的问题。清单8.5所示就是使用std::async ()的异常安全实现。
这个版本使用递归将数据划分为块而不是重新计算将数据划分为块,但是它比之前的版本要简单一些,并且是异常安全的。如以前一样,你以计算序列长度开始1,如果它比最大的块尺寸小的话,就直接调用
这种做法的好处在于它不仅可以利用硬件并发,而且它也是异常安全的。如果递归调用抛出异常5,当异常传播时,调用std::async 4创造的future就会被销毁。它会轮流等待异步线程结束,因此避免了悬挂线程。另一方面,如果异步调用抛出异常,就会被future捕捉,并且调用get() 6将再次抛出异常。
8.4.2可扩展性和阿姆达尔定律
对于任何给定的多线程程序,当程序运行时,执行有用工作的线程的数量会发生变化。即使每个线程都在做有用的操作,初始化应用的时候可能只有一个线程,然后就有一个任务生成其他的线程。但是即使那样也是一个不太可能发生的方案。线程经常花时间等待彼此或者等待I/O操作完成
一种简单的方法就是将程序划分为只有一个线程在做有用的工作"串行的"部分和所有可以获得的处理器都在做有用工作的"并行的"部分。如果你在有更多处理器的系统上运行你的应用,理论上就可以更快地完成"并行"部分,因为可以在更多的处理器间划分工作,但是"串行的"部分仍然是串行的。在这样一种简单假设下,你可以通过增加处理器数量来估计可以获得的性能。如果“连续的"部分组成程序的一个部分fs,那么使用N个处理器获得的性能P就可以估计为
尽管如此,这是一种很理想的情况。因为任务很少可以像方程式所需要的那样被无穷划分,并且所有事情都达到它所假设的CPU界限是很少出现的。正如你看到的,线程执行的时候会等待很多事情。
从根本上说,可扩展性就是当增加更多的处理器的时候,可以减少它执行操作的时间或者增加在一段时间内处理的数据数量。有时这两点是相同的(如果每个元素可以处理得更快,那么你就可以处理更多数据) ,但是并不总是一样的。在选择在线程间划分工作的方法之前,识别出可扩展性的哪些方面对你很重要是很必要的。
8.4.3用多线程隐藏迟
无论等待的原因是什么,如果你只有和系统中物理处理单元一样多的线程,那么有阻塞的线程就意味着你在浪费CPU时间。运行一个被阻塞的线程的处理器不做任何事情。因此,如果你知道一个线程将会有相当一部分时间在等待,那么你就可以通过运行一个或多个附加线程来使用那个空闲的CPU时间。
仍然,这是一个最优化问题,因此测量线程数量改变前后的性能时很重要的;最有的线程数量将很大程度上取决于工作的性质和线程等待的时间所占的比例。
有时它增加线程来确保外部事件及时被处理来增加系统响应性,而不是增加线程来确保所有可得到的处理器都被应用了。
很多现代图形用户接口框架是事件驱动的,使用者通过键盘输入或者移动鼠标在用户接口上执行操作,这会产生一系列的事件或者消息,稍后应用就会处理它。系统自己也会产生消息或者事件。为了确保所有事件和消息都能被正确处理,通常应用都有下面所示的一个事件循环。
process()代码。每一种选择都将任务的实现变得复杂了。
清单8.6从任务线程中分离GUI线程
本章你看到了设计并发代码的时候需要考虑的问题。就整体而言,这些问题是很大的,但是当你习惯了"多线程编程",它们就会变得得心应手了。如果这些考虑对你来说很新,那么希望当你看到它们是如何影响多线程代码的具体例子的时候,可以变得更清晰。
本书介绍如何编写或者设计、调试、维护、研究多线程C++程序，并提供了技术模式和工具，可以用来分析并发编程以及降低封装并发交互的复杂性。书中还提供了大量的实例、练习、可重用的代码以及用于网络通信程序的简化库。
