C++17 STL Cook Book
  • Introduction
  • 前言
  • 关于本书
  • 各章梗概
  • 第1章 C++17的新特性
    • 使用结构化绑定来解包绑定的返回值
    • 将变量作用域限制在if和switch区域内
    • 新的括号初始化规则
    • 构造函数自动推导模板的类型
    • 使用constexpr-if简化编译
    • 只有头文件的库中启用内联变量
    • 使用折叠表达式实现辅助函数
  • 第2章 STL容器
    • 擦除/移除std::vector元素
    • 以O(1)的时间复杂度删除未排序std::vector中的元素
    • 快速或安全的访问std::vector实例的方法
    • 保持对std::vector实例的排序
    • 向std::map实例中高效并有条件的插入元素
    • 了解std::map::insert新的插入提示语义
    • 高效的修改std::map元素的键值
    • std::unordered_map中使用自定义类型
    • 过滤用户的重复输入,并以字母序将重复信息打印出——std::set
    • 实现简单的逆波兰表示法计算器——std::stack
    • 实现词频计数器——std::map
    • 实现写作风格助手用来查找文本中很长的句子——std::multimap
    • 实现个人待办事项列表——std::priority_queue
  • 第3章 迭代器
    • 建立可迭代区域
    • 让自己的迭代器与STL的迭代器兼容
    • 使用迭代适配器填充通用数据结构
    • 使用迭代器实现算法
    • 使用反向迭代适配器进行迭代
    • 使用哨兵终止迭代
    • 使用检查过的迭代器自动化检查迭代器代码
    • 构建zip迭代适配器
  • 第4章 Lambda表达式
    • 使用Lambda表达式定义函数
    • 使用Lambda为std::function添加多态性
    • 并置函数
    • 通过逻辑连接创建复杂谓词
    • 使用同一输入调用多个函数
    • 使用std::accumulate和Lambda函数实现transform_if
    • 编译时生成笛卡尔乘积
  • 第5章 STL基础算法
    • 容器间相互复制元素
    • 容器元素排序
    • 从容器中删除指定元素
    • 改变容器内容
    • 在有序和无序的vector中查找元素
    • 将vector中的值控制在特定数值范围内——std::clamp
    • 在字符串中定位模式并选择最佳实现——std::search
    • 对大vector进行采样
    • 生成输入序列的序列
    • 实现字典合并工具
  • 第6章 STL算法的高级使用方式
    • 使用STL算法实现单词查找树类
    • 使用树实现搜索输入建议生成器
    • 使用STL数值算法实现傅里叶变换
    • 计算两个vector的误差和
    • 使用ASCII字符曼德尔布罗特集合
    • 实现分割算法
    • 将标准算法进行组合
    • 删除词组间连续的空格
    • 压缩和解压缩字符串
  • 第7章 字符串, 流和正则表达
    • 创建、连接和转换字符串
    • 消除字符串开始和结束处的空格
    • 无需构造获取std::string
    • 从用户的输入读取数值
    • 计算文件中的单词数量
    • 格式化输出
    • 使用输入文件初始化复杂对象
    • 迭代器填充容器——std::istream
    • 迭代器进行打印——std::ostream
    • 使用特定代码段将输出重定向到文件
    • 通过集成std::char_traits创建自定义字符串类
    • 使用正则表达式库标记输入
    • 简单打印不同格式的数字
    • 从std::iostream错误中获取可读异常
  • 第8章 工具类
    • 转换不同的时间单位——std::ratio
    • 转换绝对时间和相对时间——std::chrono
    • 安全的标识失败——std::optional
    • 对元组使用函数
    • 使用元组快速构成数据结构
    • 将void*替换为更为安全的std::any
    • 存储不同的类型——std::variant
    • 自动化管理资源——std::unique_ptr
    • 处理共享堆内存——std::shared_ptr
    • 对共享对象使用弱指针
    • 使用智能指针简化处理遗留API
    • 共享同一对象的不同成员
    • 选择合适的引擎生成随机数
    • 让STL以指定分布方式产生随机数
  • 第9章 并行和并发
    • 标准算法的自动并行
    • 让程序在特定时间休眠
    • 启动和停止线程
    • 打造异常安全的共享锁——std::unique_lock和std::shared_lock
    • 避免死锁——std::scoped_lock
    • 同步并行中使用std::cout
    • 进行延迟初始化——std::call_once
    • 将执行的程序推到后台——std::async
    • 实现生产者/消费者模型——std::condition_variable
    • 实现多生产者/多消费者模型——std::condition_variable
    • 并行ASCII曼德尔布罗特渲染器——std::async
    • 实现一个小型自动化并行库——std::future
  • 第10章 文件系统
    • 实现标准化路径
    • 使用相对路径获取规范的文件路径
    • 列出目录下的所有文件
    • 实现一个类似grep的文本搜索工具
    • 实现一个自动文件重命名器
    • 实现一个磁盘使用统计器
    • 计算文件类型的统计信息
    • 实现一个工具:通过符号链接减少重复文件,从而控制文件夹大小
Powered by GitBook
On this page
  • How to do it...
  • How it works...

Was this helpful?

  1. 第9章 并行和并发

标准算法的自动并行

C++17对并行化的一个重要的扩展,就是对标准函数的执行策略进行了修改。69个标准算法都能并行到不同的核上运行,甚至是向量化。

对于使用者来说,如果经常使用STL中的算法,那么就能很轻易的进行并行。可以通过基于现存的STL算法一个执行策略,然后就能享受并行带来的好处。

本节中,我们将实现一个简单的程序(通过一个不太严谨的使用场景),其中使用了多个STL算法。使用这些算法时,我们将看到如何在C++17中,使用执行策略让这些算法并行化。本节最后一个子节中,我们会了解不同执行策略的区别。

How to do it...

本节,将使用标准算法来完成一个程序。这个程序本身就是在模拟我们实际工作中的场景。当使用这些标准算法时,我们为了得到更快的性能,将执行策略嵌入其中:

  1. 包含必要的头文件,并声明所使用的命名空间。其中execution头文件是C++17之后加入的:

    #include <iostream>
    #include <vector>
    #include <random>
    #include <algorithm>
    #include <execution>
    
    using namespace std;
  2. 这里声明一个谓词函数,其用来判断给定数值的奇偶:

    static bool odd(int n) { return n % 2; }
  3. 主函数中先来定义一个很大的vector。我们将对其进行填充,并对其中数值进行计算。这个代码的执行速度是非常非常慢的。对于不同配置的电脑来说,这个vector的尺寸可能会有变化:

    int main()
    {
        vector<int> d (50000000);
  4. 为了向vector中塞入随机值,我们对随机数生成器进行了实例化,并选择了一种分布进行生成,并且将其打包成为一个可调用的对象。如果你对随机数生成器不太熟,那么你可以回看一下本书的第8章:

        mt19937 gen;
    
        uniform_int_distribution<int> dis(0, 100000);
        auto rand_num ([=] () mutable { return dis(gen); });
  5. 现在,std::generate算法会用随机值将vector填满。这个算法是C++17新加入的算法,其能接受一种新的参数——执行策略。我们在这个位置上填入std::execution::par,其能让代码进行自动化并行。通过这个参数的传入,可以使用多线程的方式对vector进行填充,如果我们的电脑有多核CPU,那么就可以大大节约我们的时间:

        generate(execution::par, begin(d), end(d), rand_num);
  6. std::sort想必大家都是非常熟悉了。C++17对其也提供了执行策略的参数:

        sort(execution::par, begin(d), end(d));
  7. 还有std::reverse:

        reverse(execution::par, begin(d), end(d));
  8. 然后,我们使用std::count_if来计算vector中奇数的个数。并且也可以通过添加执行策略参数对该算法进行加速:

        auto odds (count_if(execution::par, begin(d), end(d), odd));
  9. 最后,将结果进行打印:

        cout << (100.0 * odds / d.size())
            << "% of the numbers are odd.\n";
    }
  10. 编译并运行程序,就能得到下面的输出。整个程序中我们就使用了一种执行策略,我们对不同执行策略之间的差异也是非常感兴趣。这个就留给读者当做作业。去了解一下不同的执行策略,比如seq,par和par_vec。 不过,对于不同的执行策略,我们肯定会得到不同的执行时间:

    $ ./auto_parallel
    50.4% of the numbers are odd.

How it works...

本节并没有设计特别复杂的使用场景,这样就能让我们集中精力与标准库函数的调用上。并行版本的算法和标准串行的算法并没有什么区别。其差别就是多了一个参数,也就是执行策略。

让我们结合以下代码,来看三个核心问题:

generate(execution::par, begin(d), end(d), rand_num);
sort( execution::par, begin(d), end(d));
reverse( execution::par, begin(d), end(d));

auto odds (count_if(execution::par, begin(d), end(d), odd));

哪些STL可以使用这种方式进行并行?

69种存在的STL算法在C++17标准中,都可以使用这种方式进行并行,还有7种新算法也支持并行。虽然这种升级对于很多实现来说很伤,但是也只是在接口上增加了一个参数——执行策略参数。这也不是意味着我们总要提供一个执行策略参数。并且执行策略参数放在了第一个参数的位置上。

这里有69个升级了的算法。并且有7个新算法在一开始就支持了并发:

adjacent difference, adjacent find.
all_of, any_of, none_of
copy
count
equal
fill
find
generate
includes
inner product
in place merge, merge
is heap, is partitioned, is sorted
lexicographical_compare
min element, minmax element
mismatch
move
n-th element
partial sort, sort copy
partition
remove + variations
replace + variations
reverse / rotate
search
set difference / intersection / union /symmetric difference
sort
stable partition
swap ranges
transform
unique

这些算法的升级是一件令人振奋的事!如果我们之前的程序使用了很多的STL算法,那么就很容易的将这些算法进行并行。这里需要注意的是,这样的的改变并不意味着每个程序自动化运行N次都会很快,因为多核编程更为复杂,所要注意的事情更多。

不过,在这之前我们现在都会用std::thread,std::async或是第三方库进行复杂的并行算法设计,而现在我们可以以更加优雅、与操作系统不相关的方式进行算法的并行化。

执行策略是如何工作的?

执行策略会告诉我们的标准函数,以何种方式进行自动化并行。

std::execution命名空间下面,有三种策略类型:

策略

含义

算法使用串行的方式执行,这与原始执行方式没有什么区别。全局可用的实例命名为std::execution::seq。

算法使用多线程的方式进行执行。全局可用的实例命名为std::execution::par。

算法使用多线程的方式进行执行。并允许对代码进行向量化。在这个例子中,线程间可以对内存进行交叉访问,向量化的内容可以在同一个线程中执行。全局可用的实例命名为std::execution::par_unseq。

执行策略意味着我们需要进行严格限制。严格的约定,让我们有更多并行策略可以使用:

  • 并行算法对所有元素的访问,必须不能导致死锁或数据竞争。

  • 向量化和并行化中,所有可访问的函数不能使用任何一种阻塞式同步。

我们需要遵守这些规则,这样才不会将错误引入到程序中。

Note:

STL的自动并行化,并总能保证有加速。因为具体的情况都不一样,所以可能在很多情况下并行化并没有加速。多核编程还是很有难度的。

向量化是什么意思?

向量化的特性需要编译器和CPU都支持,让我们先来简单的了解一下向量化是如何工作的。假设我们有一个非常大的vector。简单的实现可以写成如下的方式:

std::vector<int> v {1, 2, 3, 4, 5, 6, 7 /*...*/};

int sum {std::accumulate(v.begin(), v.end(), 0)};

编译器将会生成一个对accumulate调用的循环,其可能与下面代码类似:

int sum {0};

for (size_t i {0}; i < v.size(); ++i) {
    sum += v[i];
}

从这点说起,当编译器开启向量化时,就会生成类似如下的代码。每次循环会进行4次累加,这样循环次数就要比之前减少4倍。为了简单说明问题,我们这里没有考虑不为4倍数个元素的情况:

int sum {0};
for (size_t i {0}; i < v.size() / 4; i += 4) {
    sum += v[i] + v[i+1] + v[i + 2] + v[i + 3];
}
// if v.size() / 4 has a remainder,
// real code has to deal with that also.

为什么要这样做呢?很多CPU指令都能支持这种操作sum += v[i] + v[i+1] + v[i+2] + v[i+3];,只需要一个指令就能完成。使用尽可能少的指令完成尽可能多的操作,这样就能加速程序的运行。

自动向量化非常困难,因为编译器需非常了解我们的程序,这样才能进行加速的情况下,不让程序的结果出错。目前,至少可以通过使用标准算法来帮助编译器。因为这样能让编译器更加了解哪些数据流能够并行,而不是从复杂的循环中对数据流的依赖进行分析。

Previous第9章 并行和并发Next让程序在特定时间休眠

Last updated 6 years ago

Was this helpful?

详细的内容可以查看。()

C++ Reference
参考页面
sequenced_policy
parallel_policy
parallel_unsequenced_policy