在第8.1节中，我们看到了一些在线程之间划分工作的方法，在第8.2节中，我们看到了一些影响代码性能的因素。在为多线程性能设计数据结构时如何使用这些信息？这是第6章和第7章中处理的难题，关于设计可安全并行读取的数据结构。正如您在第8.2节中看到的，即使没有其他线程共享数据，单个线程使用的数据布局也会影响它。为多线程性能设计数据结构时要考虑的关键问题是竞争、错误共享和数据邻近性。这三个方面都会对性能产生很大影响，通常您可以通过更改数据布局或更改分配给线程的数据元素来提高性能。首先，让我们看一个在线程之间划分数组元素的简单示例。8.3.1为复杂运算划分数组元素假设您正在进行一些复杂的数学计算并且需要将两个大矩阵相乘。要执行矩阵乘法，您将第一个矩阵第一行的每个元素与第二个矩阵第一列对应的每个元素相乘，然后将结果相加得到第一个元素。然后，您继续将第二行乘以第一列以获得结果矩阵第一列的第二个元素，依此类推。如图8.3，高亮部分表示将第一个矩阵的第二行与第二个矩阵的第三列配对，得到结果矩阵的第三列第二行的值。图8.3矩阵乘法为了值得使用多线程来优化此乘法，现在让我们假设它们具有包含数千行和几列的大型矩阵。通常，非稀疏矩阵在内存中表示为一个大数组，第一行中的所有元素后跟第二行中的所有元素，依此类推。为了实现矩阵乘法，现在有3个大数组。为了获得更好的性能，需要注意数据访问部分，尤其是第三个数组。有许多方法可以在线程之间划分工作。假设你有比处理器更多的行实例，那么你可以让每个线程计算结果矩阵中某些列的值，或者让每个线程计算结果矩阵中某些行的值，甚至每个线程都有线程计算结果矩阵的一个规则矩形子集的值。回顾8.2.3和8.2.4小节，你会发现读取数组中的相邻元素比读取数组中各处的值要好，因为这样可以减少缓存使用和虚假共享。如果你让每个线程处理一些列，那么你需要读取第一个矩阵中的所有元素和第二个矩阵中对应的列元素，但你只会得到列元素的值。假设矩阵按行顺序存储，这意味着你从第一行读取N个元素，从第二行读取N个元素，依此类推（N的值是你正在处理的列数）。其他线程会读取每行中的其他元素，所以很明显应该读取相邻的列，所以每行的N个元素都是相邻的，假共享最小化。当然，如果这N个元素使用的空间等于cacheline的个数，就不会出现falsesharing，因为每个线程都会在一个独立的cacheline上工作。另一方面，如果每个线程处理一些行元素，那么它需要读取第二个矩阵中的所有元素，以及第一个矩阵中的关联行元素，但它只会获取行元素。由于矩阵是按行顺序存储的，因此您现在从第N行开始读取所有元素。如果您选择相邻的行，则意味着该线程是唯一写入这N行的线程；它拥有内存中的连续块，不会被其他线程访问。这比让每个线程处理一个元素列表要好，因为唯一可能发生错误共享的地方是块的最后一个元素和下一个块的开始元素之间。但值得花时间确认目标结构。第三个选项——分成矩形块呢？这可以认为是先分列，再分行。它遇到与按列元素分区相同的错误共享问题。如果您可以选择块中的列数来避免此问题，那么从读取端划分为矩形块的优点是您不需要读取任何完整的源矩阵。你只需要读取相关目标矩阵的行值和列值即可。具体来说，考虑两个1000行和1000列的矩阵相乘。那是一百万个元素。如果您有100个处理器，那么每个线程可以处理10行元素。然而，为了计算这10000个元素，需要读取第二个矩阵的所有元素（一百万个元素）加上第一个矩阵相关行的10000个元素，总共1010000个元素；另一方面，如果每个线程处理一个100行100列的矩阵块（共10000个元素），那么它们需要读取第一个矩阵的100行元素（100x1000=100000个元素）和100列元素第二个矩阵（否则为100000元素）。那只有200,000个元素，将读取的元素数量减少到五分之一。如果您读取的元素越少，缓存未命中的可能性就越小，并有可能获得更好的性能。因此，将生成的矩阵划分为小的正方形或类似正方形的矩阵比每个线程完全处理多行要好。当然，您可以在运行时调整每个块的大小，具体取决于矩阵的大小和处理器的数量。如果性能很重要，那么根据目标结构分析各种选项也很重要。也有可能你没有做矩阵乘法，那么它适用吗？当您在线程之间划分大块数据时，同样的原则也适用。仔细观察数据的读取方式并确定性能影响的潜在原因。可能存在与你遇到的问题类似的环境，即只改变工作的划分方式就可以在不改变底层算法的情况下提高性能。好的，我们已经了解了数组读取如何影响性能。其他数据结构类型呢？8.3.2其他数据结构中的数据访问模式从根本上说，这也适用于尝试优化其他数据结构中的数据访问模式。1.改变线程之间的数据分配，使相邻的数据由同一个线程应用。2.最小化任何给定线程所需的数据。3.确保独立线程访问的数据相隔足够远，避免虚假共享。当然，要应用到其他数据结构中并不容易。例如，二叉树本质上很难以任何方式进行细分，有用或无用取决于树的平衡程度以及需要将其分成多少部分。此外，树的性质意味着节点是动态分配的，并最终位于堆上的不同位置。现在，让数据最终位于堆上的不同位置本身并不是一个特别的问题，但这确实意味着处理器需要在缓存中保留更多内容。事实上，这可能非常有益。如果多个线程需要遍历树，它们都需要读取树节点，但是如果树节点包含指向该节点持有的数据的指针，那么处理器必须在需要时从内存中取出数据。加载数据。如果线程正在修改所需数据，这避免了节点数据和提供树结构的数据之间错误共享的性能损失。使用互斥锁保护数据时也会出现同样的问题。假设您有一个简单的类，其中包含一些数据项和一个互斥量以保护来自多个线程的读取。如果互斥量和数据项在内存中靠得很近，这对使用互斥量的线程是有好处的；它需要的数据已经在处理器缓存中，因为它已被移动以修改互斥量。加载。但它也有一个缺点：当第一个线程持有互斥量时，如果其他线程试图锁定互斥量，则需要读取内存。互斥锁通常作为对互斥锁内存储单元的读取-修改-写入原子操作来实现，该操作尝试获取互斥锁，如果互斥锁已被锁定，则随后调用操作系统内核。这种读取-修??改-写入操作可能会导致拥有互斥量的线程所持有的缓存中的数据变得无效。只要使用互斥锁，这就不是问题。但是，如果互斥锁和线程使用的数据共享同一个缓冲区行，则拥有互斥锁的线程的性能将受到影响，因为另一个线程试图锁定互斥锁。测试这种错误共享是否是一个问题的方法是在数据元素之间添加填充块，以便不同线程同时读取。例如，您可以使用:来测试互斥竞争问题或使用:来测试数组数据是否虚假共享。如果这样做提高了性能，您就知道错误共享确实是一个问题，您可以继续填充数据或通过重新安排数据读取来消除错误共享。当然，在并发设计的时候，需要考虑的不仅仅是数据读取模式，下面我们看看其他需要考虑的方面。8.4并发设计时的其他考虑在本章中，我们研究了在线程之间划分工作的一些方法、影响性能的因素，以及这些因素如何影响您选择的数据读取模式和数据结构。然而，设计并发代码需要更多的思考。您需要考虑的事情，例如异常安全性和可扩展性。如果性能（在减少执行时间或增加吞吐量方面）随着系统中处理核心的增加而增加，则代码是可扩展的。理论上，性能提升是线性的。因此，具有100个处理器的系统的性能将比只有一个处理器的系统好100倍。即使代码不可扩展，它也能工作。例如，单线程应用程序不可扩展，异常安全关乎正确性。如果您的代码不是异常安全的，您可能会以损坏的不变量或竞争条件而告终，或者您的应用程序可能会因为操作抛出异常而突然终止。考虑到这些，我们将首先考虑异常安全。8.4.1并行算法中的异常安全异常安全是良好C++代码的一个基本方面，使用并发的代码也不例外。事实上，并行算法通常需要你比普通的线性算法更多地考虑异常。如果线性算法中的操作抛出异常，该算法只关心确保它能很好地处理它以避免资源泄漏和破坏不变量。它可以允许调用者处理扩展异常。相反，在并行算法中，许多操作在不同的线程上运行。在这种情况下，扩展异常是不允许的，因为它在错误的调用堆栈中。如果一个函数生成异常结束的新线程，应用程序将终止。作为一个具体的例子，让我们回顾一下清单2.8中的parallel_accumulate函数，并在清单8.2中进行了一些修改。清单8.2sta::accumulate的并行版本（来自清单2.8）。现在我们检查并确定抛出异常的地方：基本上，任何调用函数或对用户定义类型执行操作的地方都可以抛出异常。首先，调用distance2，它对用户定义的迭代器类型进行操作。因为您还没有做任何工作，而且这是在调用线程上，所以这很好。接下来，分配结果迭代器3和线程迭代器4。同样，这是在调用线程上，您没有做任何工作或产生任何线程，所以这很好。当然，如果threads的构造函数抛出异常，那么分配给results的内存就必须清空，析构函数会帮你完成。跳过block_start的初始化5，因为它是安全的，并转到生成线程的循环中的操作6、7、8。7一旦创建了第一个线程，如果抛出异常就麻烦了，你新建的sta::thread对象的析构函数会调用std::terminate然后在程序中，调用accumulate_block9也可能抛出异常被抛出，你的线程对象将被销毁，std:terminate将被调用；另一方面，对std::accumulate10的最后一次调用也可能抛出异常并且不会造成任何困难，因为所有线程都将汇聚于此。这不是针对主线程，但也可能会抛出异常，在新线程上调用accumulate_block可能会抛出异常1。这里没有catch块，所以异常会在后面处理并导致库调用sta::terminate()中止程序。即使不明显，这段代码也不是异常安全的。1.增加异常的安全性好了，我们已经把所有可能抛出异常的地方以及异常带来的不良影响都识别出来了。那么如何处理呢？我们先解决新线程抛出异常的问题。执行此操作的工具在第4章中描述。如果您仔细考虑您希望在新线程中实现什么，很明显您正在尝试计算要返回的结果，同时允许代码抛出异常。std::packaged_task和std:future的组合设计恰到好处。如果重新设计代码以使用std::packaged_task，最终会得到清单8.3中的代码。清单8.3使用std::packaged_task的std::accumulate并行版本第一个变化是函数调用accumulate_block操作并直接返回结果，而不是返回对存储地址的引用1.你使用std::packaged_task和std::future用于异常安全，因此您也可以使用它来传输结果。这要求您调用std::accumulate2以显式使用默认构造函数T而不是重新使用提供的结果值，但这只是一个小的变化。下一个变化是，不是为每个生成的线程存储一个std:future和结果，而是存储一个futures3向量。在生成块的循环中，首先为accumulate_block创建任务4。std:packaged_task现在您已经使用了futures，不再有结果数组，所以最后一个块的结果必须存储在变量7而不是数组中的某个位置。此外，由于您将从future中获取值，因此使用基本的for循环比std:accumulate更简单，从提供的初始值8开始，并将每个future的结果相加到9。如果对应的任务抛出异常，以后会被捕获，调用get()时再次抛出异常。最后，在将总结果返回给调用者之前，将最后一个块的结果加10。因此，这消除了在工作线程中抛出的异常将在主线程中重新抛出的可能问题。如果多个工作线程抛出异常，则只会传播一个异常，但这也不是什么大问题。如果它真的相关，请使用类似std::nested_exception的东西来捕获所有异常并抛出它。如果在您生成第一个线程和加入它们之间抛出了异常，那么剩下的问题就是线程泄漏。最简单的方法是捕获所有异常，并将它们合并到调用joinable()的线程中，然后再次抛出异常。现在可以了。无论代码如何离开块，所有线程都将被加入。尽管如此，try-catch块还是很烦人，而且您有重复的代码。您将加入正常的控制流以及catch块的线程。重复代码并不是一件好事，因为这意味着需要更改更多的地方。我们在对象的析构函数中检查它，毕竟这是C++中清理资源的惯用方式。下面是你的课。这类似于清单2.3中的thread_guard类，只是它被扩展为适合所有线程。您可以简化代码，如清单8.4所示。清单8.4std::accumulate的异常安全并行版本创建线程容器后，您还创建了类1的新实例以连接所有退出的线程。只要您知道无论函数是否退出，线程都将合并，您就可以摆脱联合循环。请注意，调用futures[i].get()2将阻塞直到结果可用，因此此时无需显式与线程融合。这与清单8.2中的原型不同，在清单8.2中，您必须与线程结合以确保正确复制结果向量。您不仅获得异常安全代码，而且您的函数也更短，因为联合代码被提取到您的新（可重用）类中。2.STD::ASYNC()的异常安全性现在您知道了在处理线程时需要什么是异常安全的，让我们看一下在使用std::async()时需要做的同样的事情。您已经看到，在这种情况下，库会为您处理这些线程，并且当future准备就绪时，所有线程都已生成。需要注意的关键是异常安全，如果future没有等待就被销毁，析构函数将等待线程完成。这避免了泄漏仍在执行和持有数据引用的线程的问题。清单8.5显示了使用std::async()的异常安全实现。清单8.5使用std::async的异常安全并行版本的std::accumulate这个版本使用递归而不是重新计算将数据分成块，但它比以前的版本简单一点并且是异常安全的。和以前一样，您首先计算序列长度1，如果它小于最大块大小，则直接调用std::accumuate2。如果它的元素大于块大小，找到中点3并生成一个异步任务来处理前半部分！[订单号4。范围的第二部分通过对5.的直接递归调用处理，然后将这两个块的结果相加6。库确保std::async调用使用可用的硬件线程并且不不要创建很多线程。某些“异步”调用将在调用get()时异步执行6。这种方法的美妙之处在于它不仅可以利用硬件并发性，而且还是异常安全的。如果递归调用抛出异常5，则通过调用std::async4创建的未来将在异常传播时被销毁。它会轮流等待异步线程完成，从而避免挂起线程。另一方面，如果异步调用抛出异常，会被future捕获，调用get()6会再次抛出异常。设计并发代码时还需要考虑什么？让我们看看可扩展性。如果将代码移至更多处理器的系统，性能会提高多少？8.4.2可伸缩性和Amdahl定律可伸缩性是关于确保您的应用程序可以利用系统中添加的处理器的优势。在一个极端情况下，您有一个根本无法扩展的单线程应用程序，即使您向系统添加100个处理器而性能没有变化也是如此。在另一个极端，您有像SETI@Home[3]这样的项目，旨在利用数千个额外的处理器（以用户将PC添加到网络的形式）。对于任何给定的多线程程序，执行有用工作的线程数在程序运行时会发生变化。即使每个线程都在做有用的操作，应用程序初始化时也可能只有一个线程，然后一个任务产生其他线程。但即便如此，这种情况也不太可能发生。线程经常花时间等待彼此或等待I/O操作完成一种简单的方法是将程序分为“串行”部分和“并行”部分，其中只有一个线程在做有用的工作，而“并行”部分是所有可用的处理器都在做有用的工作。如果你在一个有更多处理器的系统上运行你的应用程序，“并行”部分理论上可以完成得更快，因为工作可以分摊到更多处理器上，但“串行”部分仍然是串行的。在这样一个简单的假设下，你可以估算出增加处理器数量可以获得的性能。如果“顺序”部分构成一个程序的一部分fs，那么使用N个处理器获得的性能P可以估计为这就是Amdahl定律，在谈到并发代码的性能时经常被引用。如果一切都可以并行化，那么串行部分是0，加速比是N，或者，如果串行部分是三分之一，即使有无限数量的处理器，你也不会得到超过3的加速比所以，这是一个理想的情况。因为任务很少能像等式所要求的那样被无限划分，而且几乎所有事情都达到它假定的CPU限制。如您所见，线程在执行时会等待很多事情。从Amdahl定律可以明确的一件事是，当您使用并发来提高性能时，值得考虑整体应用程序设计，以最大限度地提高并发的可能性，并确保处理器始终有有用的工作要做。如果可以减少“串行”部分或减少线程等待的可能性，则可以提高具有更多处理器的系统的性能。或者，如果您可以为系统提供更多数据并保持并行部分准备好工作，则可以减少串行部分并增加性能P的值。基本上，可伸缩性就是当您添加更多处理器时，可以减少所需的时间执行操作或增加一段时间内处理的数据量。有时这两点是相同的（如果每个元素可以处理得更快，就可以处理更多的数据），但并非总是如此。在选择在线程之间划分工作的方法之前，有必要确定可伸缩性的哪些方面对您很重要。我在本节开头提到，线程并不总是有有用的工作要做。有时他们必须等待其他线程，或等待I/O操作完成，或其他事情。如果在等待期间让系统做一些有用的事情，就可以有效地“隐藏等待”。8.4.3用多线程隐藏延迟在许多关于多线程代码性能的讨论中，我们假设当它们实际在处理器上运行时，线程“正在满负荷运行，并且总是有有用的工作要做。这当然不是真的，在应用程序代码中，线程在等待时经常被阻塞。例如，它们可能正在等待某些I/O操作完成、等待获取互斥量、等待另一个线程完成某些操作并通知条件变量，或者只是休眠一会儿。无论等待的原因是什么，如果您只有与系统中的物理处理单元一样多的线程，那么阻塞线程意味着您在浪费CPU时间。运行阻塞线程的处理器什么都不做。因此，如果您知道一个线程将在相当长的一段时间内等待，那么您可以通过运行一个或多个附加线程来使用空闲的CPU时间。考虑一个使用管道在线程之间分配工作的病毒扫描应用程序。第一个线程搜索文件系统以检查文件并将它们放入队列中。同时，另一个线程获取队列中的文件名、加载文件并扫描它们是否有病毒。您知道在文件系统中搜索文件的扫描线程必然会遇到I/O限制，因此您可以通过运行额外的扫描线程来使用“空闲”CPU时间。然后你有一个用于搜索文件的线程，以及与系统中物理内核或处理器一样多的扫描线程。由于扫描线程可能还必须从磁盘读取文件的重要部分来扫描它们，因此拥有更多扫描线程也是有意义的。但在某些时候，线程会过多，系统会再次变慢，因为它会花费更多时间切换程序，如第8.2.5节所述。不过，这是一个优化问题，因此在更改线程数之前和之后测量性能很重要；最佳线程数在很大程度上取决于工作的性质和线程等待的时间比例。根据应用程序的不同，它也可能会在不运行额外线程的情况下耗尽空闲CPU时间。例如，如果一个线程在等待I/O操作完成时被阻塞，那么使用可用的异步I/O操作是有意义的。然后线程可以在后台执行I/O操作的同时执行其他有用的工作。在其他情况下，如果一个线程正在等待另一个线程执行操作，等待线程可以自己执行该操作而不是被阻塞，就像第7章中的无锁队列一样。在极端情况下，如果一个线程正在等待为了完成一个任务并且该任务没有被其他线程执行，等待线程可以在其内部或另一个未完成的任务中执行该任务。你在清单8.1中看到了这个例子，其中排序程序一直对它需要的块进行排序，只要它们没有被排序。有时它会添加线程以确保及时处理外部事件以提高系统响应能力，而不是添加线程以确保使用所有可用的处理器。8.4.4使用并发提高响应能力许多现代图形用户界面框架都是事件驱动的。用户通过键盘输入或移动鼠标在用户界面上进行操作，会产生一系列的事件或消息，稍后由应用程序it进行处理。系统本身也会生成消息或事件。为确保正确处理所有事件和消息，应用程序通常具有如下所示的事件循环。显然，API的细节不同，但结构大体相同，等待一个事件，做需要的操作处理它，然后等待下一个事件。如果您有一个单线程应用程序，则很难编写长时间运行的任务，如第8.1.3节所述。为确保及时处理用户输入，无论应用程序在做什么，都必须以合理的频率调用get_event()和process()。这意味着要么任务必须定期暂停并将控制权交给事件循环，要么在方便的时候在代码中调用get_event()/process()代码。每个选项都会使任务的实施复杂化。通过将关注点与并发分离，您可以在新线程上执行长任务，并使用专用的GUI线程来处理事件。线程可以以一种简单的方式相互访问，而不必以某种方式将事件处理代码放入任务代码中。清单8.6给出了这种分离的简单概述。清单8.6将GUI线程与任务线程分离通过以这种方式分离屏障，用户线程可以及时响应事件，即使任务需要很长时间才能执行。这种响应性通常是使用应用程序时用户体验的关键。每当执行特定操作时（无论该操作是什么），应用程序都会被完全锁定，使用起来很不方便。通过提供专用的事件处理线程，GUI可以处理特定于GUI的消息（例如调整大小或重绘窗口）而不会中断耗时进程的执行，并在它们确实影响长任务时传递相关消息。在本章中，您了解了设计并发代码时需要考虑的问题。总的来说，这些问题都很棒，但是当你习惯了“多线程编程”之后，它们就会变得得心应手。如果这些注意事项对您来说是新的，希望当您看到它们如何影响多线程代码的具体示例时，它会变得更加清晰。
