嗨，habrozhiteli！ 当您需要创建真正快速的应用程序时，选择C ++语言。 高质量的竞争性处理将使它们变得更快。 C ++ 17的新功能使您可以利用多线程编程的全部功能轻松解决图形处理，机器学习等问题。竞争性处理专家Anthony Williams考虑了示例并描述了实际任务，并分享了对所有人有用的秘密包括最有经验的开发人员。
书中•C ++ 17功能的完整概述。 •启动和流量控制。 •竞争性运营的同步。 •制定竞争法规。 •调试多线程应用程序。 本书适合使用C和C ++的中级开发人员。 不需要竞争编程经验。
竞争代码开发
8.1。 在线程之间分配工作的方法
想象一下，您需要盖房子。 为此，您将必须挖一个基坑，填充地基本身，竖立墙壁，铺设管道和电线等。理论上，只要具备足够的技能，一切都可以独立完成，但是很可能会花费很多时间，并且您必须从一项工作切换到另一项工作。另一个。 但是您可以雇用助手。 然后，有必要选择要雇用多少助手，并确定他们应具备的能力。 例如，您可以雇用两个工人并与他们一起工作。 然后，您仍然必须从一种作品切换到另一种作品，但是现在情况会变得更快，因为会有更多的艺术家。
您可以选择另一个选项-雇用一个专家团队，例如瓦工，木匠，电工和水管工。 每个人都将按自己的专业工作，因此，在管道工有工作前，他将闲着。 然而，随着工人的增加，事情的发展将比以前更快，电工将在厨房进行布线，而水管工则可以去洗手间。 但是，当没有特定专家的工作时，将获得更多的停机时间。 但是，应该指出的是，即使考虑到停机时间，当专家上班而不是一组工人上班时，工作移动也会更快。 专家不需要经常更换工具，并且可以肯定的是，他们每个人都比劳动者更快地完成任务。 实际情况是否如此取决于具体情况：在实践中学到了一切。
即使您涉及专家，您仍然需要选择不同数量的各个专业的工人。 例如，也许雇用更多的泥瓦匠比电工有意义。 此外，如果您必须一次建造几所房屋，则团队的组成及其工作的整体效率可能会发生变化。 即使在一栋房子里水管工的工作量很少，那么当一次盖几栋房子时，就可以整日使用。 此外，即使您不必为停机而支付专家费用，您也可以招募更大的团队，即使同时工作的人数没有变化。
但是，别再谈论建筑了。 这与线程有什么关系？ 您可以将类似的注意事项应用于它们。 您必须决定要使用多少个线程以及应该执行哪些任务。 我们需要通用线程来完成特定时刻所需的工作，还是需要只适合一件事的专家线程？ 还是值得将两者结合起来？ 无论是否要并行执行程序，都必须做出这些决定，并且代码的性能和清晰度在很大程度上取决于它们的成功程度。 因此，在开发应用程序结构时，想出可以使用哪些选项来做出明智的决定至关重要。 在本节中，我们将考虑多种分配任务的方法，首先是在线程之间分配数据以执行任何其他工作。
8.1.1。 处理之前线程之间的数据分配
最容易并行化的是简单算法，例如std :: for_each，它们对数据集的每个元素执行操作。 要并行化此算法，可以将每个元素分配给一个处理线程。 将来，在考虑性能问题时，很明显，实现最佳性能的最佳分发选项取决于数据结构的特征。
分配数据时，最简单的情况是将前N个元素分配给一个流，将后N个元素分配给另一个流，依此类推（图8.1），但是可以使用其他方案。 无论采用哪种数据分发方法，每个线程仅处理分配给它的元素，而在完成处理之前不会与其他线程进行交互。
在Message Passing Interface（MPI，
www.mpi-forum.org ）或OpenMP（http://www.openmp.org/）环境中进行编程的任何人都应该熟悉该结构：该任务分为许多并行执行的任务，工作流彼此独立地运行，结果在信息的最后阶段收集。 该示例在示例中使用了2.4节中的累加功能：并行任务和简化阶段都是累加。 对于简单的for_each算法，由于没有什么可减少的，因此缺少最后一步。
混合被定义为最后阶段的本质这一事实起着非常重要的作用：类似于清单2.9所示的基本实现将把这种混合作为最后的连续阶段来执行。 但是通常这个阶段也是并行的：累积是一种归约运算，因此例如当线程数大于该线程处理的最小元素数时，可以更改清单2.9中的代码以递归调用同一代码。 您还可以强制工作流程在每个工作流程完成后立即执行汇总步骤，而不是每次都启动新线程。
尽管具有全部有效性，但该技术并不是通用的。 有时，由于每个部分的组成仅在处理期间才知道，因此无法预先精确地划分数据。 特别是在使用诸如Quicksort之类的递归算法时，这很明显，因此它们需要不同的方法。
8.1.2。 递归数据分发
Quicksort算法有两个主要阶段：将数据分为两部分-属于元素（引用）之一的所有内容，以及最后排序顺序中的所有内容，以及这两个半部分的递归排序。 通过初步分割数据来并行化它是不可能的，因为有可能仅在处理元素期间确定它们属于哪个“一半”。 如果打算并行化此算法，则需要使用递归的本质。 在每个递归级别上，都会执行对quick_sort函数的越来越多的调用，因为您必须对大于引用的引用和小于引用的引用进行排序。 这些递归调用彼此独立，因为它们引用了单独的元素集。 因此，它们是竞争力的首批候选人。 此递归分布如图2所示。 8.2。
在第4章中已经实现了该实现。我们没有对较大的和较小的一半进行两次递归调用，而是使用了std :: async（）函数，该函数在每个步骤中为较小的一半运行异步任务。 由于使用了std :: async（），C ++线程库必须决定何时在新线程中启动任务，以及何时-在同步模式下启动任务。
有一个重要情况：对大型数据集进行排序时，为每个递归启动一个新线程将导致线程数量迅速增加。 在检查性能问题时，将显示太多线程会降低应用程序的速度。 此外，拥有大量数据流可能根本不够。 在这种递归模式下拆分整个任务的想法非常成功，您只需要仔细监视线程数即可。 在简单的情况下，std :: async（）函数可以解决此问题，但是还有其他选项。
其中之一是使用std :: thread :: hardware_concurrency（）函数来选择线程数，如清单2.9中的accumulate（）函数的并行版本中那样。 然后，不必为每个递归调用启动新线程，您可以将要排序的片段放到线程安全的堆栈中，例如，如第6章和第7章中所述。如果线程不执行任何操作或已完成所有片段的处理或正在等待片段的排序，则可以从堆栈中取出一个片段并对其进行排序。
清单8.1展示了该技术的简单实现。 像在其他大多数示例中一样，它仅演示了意图，而不是可供实际使用的代码。 如果使用C ++ 17编译器且您的库支持该编译器，则应根据第10章中的描述使用标准库提供的并行算法。
清单8.1 一种并行Quicksort算法，该算法使用一堆等待排序的片段
在这里，parallel_quick_sort
（19）函数将大部分功能职责放在sorter
（1）类上，这提供了一种将未排序的片段
（2）和多个线程
（3）的堆栈进行分组的简便方法。 主要工作在do_sort组件函数
（9）中执行，该函数由常规数据分区
（10）占用。 这次，它没有为每个片段启动一个新线程，而是将该片段压入堆栈（11）并仅在有可用的处理器资源时才启动一个新线程（12）。 由于值小于参考值的片段可以由另一个流处理，因此我们应该等待其准备就绪
（13） 。 为了避免浪费时间（在我们只有一个线程或所有其他线程已被占用的情况下），尝试在此等待时间段内处理来自堆栈的片段
（14） 。 try_sort_chunk函数从堆栈中检索一个片段
（7） ，对其进行排序
（8），然后将结果保存在promise promise中，以便他们可以接收将该片段放入堆栈中的流
（15） 。
现在，刚启动的线程处于循环中，如果未设置end_of_data
（16）标志，则尝试从堆栈
（17）中排序片段。 在两次检查之间，它们将计算资源放弃给其他线程，以便它们可以将其他工作推送到堆栈上。 按照这些线程的顺序进行代码的工作取决于您的sorter
（4）类的析构函数。 对所有数据进行排序后，do_sort函数将返回控制权（即使同时保持工作线程的活动），主线程将从parallel_quick_sort
（20）返回并销毁排序器对象。 它将设置end_of_data标志
（5）并等待线程完成工作
（6）。设置该标志将停止线程功能（16）中的循环。
使用这种方法，启动新线程的spawn_task函数中固有的线程数量不受限制的问题将消失，并且对C ++线程库的依赖将消失，后者依赖于为您选择线程数的C ++线程库，就像使用std :: async（）时一样。 相反，为了防止任务切换过多，线程数受std :: thread :: hardware_concurrency（）函数返回的值限制。 但是又出现了另一个问题：管理这些流并在它们之间交换数据会极大地使代码复杂化。 此外，尽管线程处理单个数据元素，但所有线程都访问堆栈，向堆栈中添加新片段，并获取片段进行处理。 即使使用无锁（因此，无阻塞）堆栈，这种激烈的竞争也会降低性能，并且很快将考虑其原因。
这种方法是线程池的特殊版本-一组线程，每个线程从延迟的作业列表中接收工作，执行该工作，然后转向该列表以获取新的线程。 第9章讨论了线程池中固有的一些潜在问题（包括访问工作列表时的竞争）以及解决这些问题的方法。在扩展已创建的应用程序使其在多个处理器上运行时，我们将在稍后讨论本章（请参见参考资料）。第8.2.1节）。
当在处理之前和以递归模式分发数据时，假定它们是预先固定的，并且正在对其进行搜索。 但这并不总是会发生：如果数据是在动态模式下创建的或来自外部源，则此方法无效。 在这种情况下，根据任务的类型而不是根据数据本身来分配工作可能更为合理。
8.1.3。 按任务类型分配工作
在任何情况下，通过在线程之间分配每个数据（在数据处理过程中预先或递归）不同的数据块之间进行工作分配，是基于以下假设：线程将在每个数据块上执行相同的工作。 另一种工作分配是流程的专业化，因为水管工和电工在建造房屋时要执行不同的任务，因此每个流程都执行单独的任务。 流可以使用不同或相同的数据，但是在后一种情况下，它们可以出于不同的目的进行处理。
这种特殊的分工是在竞争的帮助下任务分离的结果：每个线程都有一个单独的任务，它独立于其他流程执行。 有时其他线程可以将数据传递到流或产生应响应的事件，但是通常，每个流都专注于单个任务的高质量性能。 这是一个很好的基础设计，其中每个代码段都应负责一件事情。
按任务类型分配工作以分担责任
当在一定时间内必须连续执行多个任务，或者应用程序必须及时处理传入事件的处理（例如，用户按下某个键或数据通过网络到达）时，单线程应用程序必须处理与单一职责原则相关的冲突。在其他未完成的任务中。 在单线程计算环境中，您必须独立创建运行任务A的一部分，任务B的一部分的代码，检查是否按下了键并且没有网络数据包，然后循环返回到任务A的下一部分。这使代码的执行复杂化由于需要维护任务A的状态并定期将控制权返回给主循环，因此需要执行任务A。 如果您在周期中添加了太多任务，则工作可能会大大减慢速度，并且用户可能会注意到对按键的反应很慢。 我敢肯定，每个人都观察到某些应用程序中类似情况的极端表现：您为应用程序设置了任务，并且接口在完成之前不会对任何内容做出反应。
流量到了舞台。 如果您在单独的线程中运行每个任务，则操作系统可以代替您执行此操作。 在任务A的代码中，您可以专注于完成任务，而不必担心维护状态和返回主循环，也不必担心会花费多少时间。 也就是说，操作系统将自动保存状态并在正确的时间切换到任务B或C，并且如果要运行该程序的系统具有多个内核或处理器，则可以同时执行任务A和B。用于处理击键或回执的代码现在可以及时执行网络数据包，每个人都将从中受益：用户将收到适当的程序响应，而作为开发人员，您将收到简化的代码，因为每个流都可以定向 进行与他的职责直接相关的操作，而无需将其与控制流和用户交互混合在一起。
一个理想的画面正在出现。 但这一切可以证明吗？ 与往常一样，这完全取决于特定的情况。 如果尊重完全独立性，并且流之间不需要相互交换数据，那么这将发生。 不幸的是，很少看到类似的情况。 通常，用户必需的操作具有方便的后台任务的形式，并且它们需要将任务通知用户，并以某种方式更新用户界面。 否则用户可能需要停止任务，因此用户界面将需要以某种方式将消息发送到后台任务，从而使其停止执行。 在这两种情况下，都必须仔细考虑设计和适当的同步，但是执行的任务仍然是零散的。 用户界面线程仍然控制此界面，但是可以应其他线程的请求将其分配为执行更新。 实现后台任务的线程仍然专注于完成该任务所需的操作；也有一个后台线程允许任务停止另一个线程。 在这两种情况下，流程都不在乎请求来自何处，它们只在乎请求是为他们设计的，并且与他们的职责直接相关。
在多个线程之间共享责任有两个严重的危险。 首先，可能会发现分配了不适当的责任。 这说明流共享了太多数据，或者不同流必须互相等待。
在这两种情况下，流之间的数据交换过多。我们需要处理这种交换的原因。如果是由相同原因引起的，那么这些线程所做的一切也许应该是一个线程的主要职责，并且应该释放以前占用的所有线程。在两个流之间以及其他流之间进行密集数据交换的情况下（压力要小得多），也许应该将这两个流合并为一个。根据任务的类型在线程之间划分工作时，不应只限于完全隔离的选项。如果几组输入数据需要相同的应用操作序列，则可以分配工作，以便每个线程从通用序列执行一个阶段。如果任务的实质是将相同的操作序列应用于许多独立的数据元素，则可以使用管道来使用系统中可用的竞争性工具。有一个类似于真实管道的类比：到达一端的数据经过一系列操作，然后离开另一端。通过这种工作分配，将为每个管道阶段创建一个单独的线程-该序列中的每个操作一个线程。操作完成后，数据项被放入队列中，下一个线程从该队列中拾取数据项。这允许执行序列中第一个操作的线程开始使用下一个数据元素，而第二个流水线流使用第一个元素。在流之间的数据分配的另一种变体（在第8.1.1节中讨论）适用于在操作开始时对输入数据一无所知的情况。例如，数据可能来自网络，或者序列的第一个操作可能是文件系统扫描，以识别正在处理的文件。, : , . , 20 , 3 . , . , , , , 12 , 24 — . . 20 . . . , , , , 12 . , 12 , . , : , , , , , . 3 12 .
整个数据包的总处理时间将增加，因为最后一个内核开始处理第一个元素之前必须花费9秒。但是在某些情况下，更平滑，更合理的处理可能是更可取的。考虑例如高分辨率数字视频观看系统。为了舒适地观看视频，您通常需要每秒至少演示25帧，理想情况下，还要演示更多。此外，对于用户来说，连续运动的错觉应该统一发生：每秒解码100帧的应用程序如果暂停1秒，将显示100帧，停止显示1秒钟，然后显示接下来的100帧，将无用。 。同时，观众很可能不会在观看视频之前停顿两秒钟。在这种情况下，当然优选使用以恒定速度生产框架的输送机进行平行化。考虑了在线程之间分配工作的各种方式之后，我们来讨论影响多线程系统性能的因素，以及在选择方法时如何将它们考虑在内。8.2。影响竞争代码性能的因素
如果在具有多个处理器的系统上使用竞争力来提高代码性能，则应注意可能影响性能的因素。即使使用多个线程来分担责任，您也需要确保这不会影响性能。如果您的应用程序在具有16核的宏伟计算机上运行的速度比在旧的单核计算机上运行的速度慢，则消费者不会感谢您。不久将显示，许多因素都会影响多线程代码的性能-即使是简单的诸如重新排列每个流处理的数据元素（而其他所有内容保持不变）的简单因素也可能导致性能显着下降。现在，不用冗长的序言，让我们考虑其中的一些因素，最明显的是：目标系统上有多少个处理器？8.2.1。我们有多少个处理器？
( ) , . , , , . , . , . , , ( ) . , , , .
大致来说，一个16核处理器类似于四个四核处理器或16个单核处理器：在任何情况下，系统中可以同时启动16个线程。如果需要使用此功能，则您的应用程序必须至少具有16个线程。当它们较少时，除非系统同时启动另一个应用程序（现在我们将忽略这种可能性），否则处理能力将保持无用。同时，如果有超过16个准备就绪的工作线程在等待事件发生时未被阻塞，则您的应用程序将浪费CPU时间在它们之间进行切换，如第1章所述。这种情况称为超额预订。为了使应用程序可以将活动线程数调整为可在现有设备上同时启动的线程数，标准线程库C ++ 11（标准线程库）提供了功能std :: thread :: hardware_concurrency（）。它已经展示了使用它扩展设备功能线程数的能力。直接使用std :: thread :: hardware_concurrency（）函数需要谨慎：在您显式共享此信息之前，系统上运行的任何其他线程都不会考虑您的代码。在最坏的情况下，如果多个线程使用std :: thread :: hardware_concurrency（）同时调用一个函数以进行缩放，则可能会重新评估计算能力。 std :: async（）函数设法避免此问题，因为该库知道所有调用并可以处理调度。您还可以通过正确使用线程池来解决此问题。但是，即使考虑到应用程序中运行的所有线程，仍将同时运行其他应用程序的影响。尽管在单用户系统上同时使用多个消耗大量CPU资源的情况很少见，但是在许多地区，这种情况比平常更频繁发生。为此场景设计的系统通常提供允许每个应用程序选择适当数量的线程的机制，尽管这种机制不适合C ++标准的范围。 std :: async（）之类的函数的一种选择是在选择线程数时考虑所有应用程序启动的异步任务的总数。另一个选择是限制核心数量特定应用程序可以使用的内容。可以预期，此限制将反映在std :: thread :: hardware_concurrency（）函数在此类平台上返回的值中，但不能保证这样的结果。如果您需要处理这种情况，请查阅系统文档以查看这些选项是否可用。这种情况的另一个细微差别是，与计算单元数量相比，用于解决此问题的理想算法可能取决于其规模。如果您拥有一个具有许多计算单元的强大并行系统，那么执行每个操作的算法通常比执行更少操作的算法更快地完成任务，因为每个处理器只能执行几个操作。随着处理器数量的增加，另一个问题会影响性能的可能性也随之增加，即多个处理器尝试访问同一数据。»这本书的更多详细信息可以在出版商的网站上找到» 目录» 摘录Khabrozhiteley优惠券-C ++ 可获得25％的折扣。当收到纸质版书籍的付款后，会通过电子邮件发送电子书。