4.1 达人的关注点
第3章，研究了如何检查耗时的部分，之后需要着眼于何处实现高效编程。这里，从系统构造来看，遇到问题要先解决什么问题。
硬件篇
程序中不稳定的部分是程序的瓶颈。以下因素可能成为程序瓶颈：
- 程序是否侧重于处理字符串；
- 是否侧重于处理数值运算；
- 是否侧重于访问底层硬件；
- 程序是否与其他程序紧密关联。
无论怎样的程序，都有计算机系统中各部件协调运作执行。因此计算机各部件的运行速度和不协调构成了程序执行过程中的“人行横道”。
尽量不使用低效率资源
高效编程的一个重要宗旨是：不停检查程序，操作中尽量采取高效率的操作和快速的存取对象。
存取对象时间，一般越远离CPU，存取越耗时，存取时间对比如下： 络存储器 > 直连辅助存储器 > 主存储器 > 缓存 > 寄存器。
高效利用CPU：SIMD与多核的应用
如今，CPU主频已经接近极限，提升空间有限，可通过其他方式提高CPU性能：
- 装载多个计算的核；
- 并行处理多个数据的SIMD。
想有效利用多核，代码需要支持多线程，与其他核同时运行。这需要再OpenMP和TBB(Threading Building Blocks)环境中进行。
另外，SIMD可使用SSE指令来计算大量的数据。
SSE指令
Intel和AMD的x86系列CPU都具有用于SIMD计算的SSE指令，且具备了在各CPU核内使用SSE指令的128位宽的寄存器。
结构为8位x16、16位x8、32位x4的寄存器能搜集分散数据，通过SSE指令同时执行多个数据的计算。
编译器/中间件篇
操作系统和编译器的基础软件、数据库软件、 络协议栈、扩充文件系统这些软件叫做中间件。
随着编译器技术的发展，将生成更合理的代码，删除多余的操作使编程更高效。如果能掌握编译器的运作，就能删除多余运作从而实现高效编程。
中间件的性能优化依赖于安装环境。
下面，讨论使用频率高和处理速度慢的函数。
输入输出操作
- 输入输出操作十分耗时，若多次输入输出操作集中做一次归并处理，速度会快很多。
- C语言的处理系统中，功能相近的输入输出函数有若干种。例如输入行：fread/fgets/getline。从使用缓冲区（I/O缓冲区）读取数据直到完成读取，整个过程因函数而异。
- 字符串输出函数printf/fprintf，执行标准化字符串扫描和调整时，非常耗时。若不需要复杂的调整造作，尽量使函数简单且少量。
字符串操作
字符串的复制、比较和替换操作比较频繁。为此，C语言处理系统中具备了相似却不相同的函数，使用时选用用途相同、速度较快函数。例如，将strcpy替换为memcpy。
算法篇
数据结构和程序算法是决定程序性能的两大要素。
但是，即使选择了通用算法，想写出更合理的代码，需要了解编译器如何生成代码，以及CPU如何执行程序。
了解CPU和编译器的运作
- 删除程序中无用的循环和条件判断；
- 修改代码，减少因内存读取和条件判断指令引起的等待时间；
- 了解CPU合适产生等待时间，采取相应措施；
- 采用SSE指令。
结合数据来调整算法
众所周知，将算法放入程序内会提高性能，如果将算法与实际数据的特性结合调整，性能会进一步提高。
4.2 【硬件篇】数组和缓存的有效利用
若存取的数据在内存中是连续的，缓存的作用会得到很好发挥。但如果数据在内存中不连续，会发生缓存未命中，从而增加存取的时间。
常用的矩阵乘积，是否能实现高效编程，关键在于能否通过数据操作使缓存得到有效利用。
矩阵的乘法运算
矩阵的乘法运算用以下算式定义
调整数组操作的顺序
由于变量间不存在联系，可以更换循环内的顺序。程序4-2为替换后的代码。
展开循环的方式
程序4-3为展开最内侧循环的结果。所谓”展开循环“，是将循环主体排列几次，减少循环次数。
矩阵的分块
想更大程度减少缓存未命中的情况，可采取分块手法，即将全体矩阵分割成相同的子矩阵，然后求被分割后各个子矩阵的乘积，最后将结果汇总秋整体的乘积。
优化的陷阱
图4-6为测试执行时间的结果，其中分别对长度为10byte、20byte、50byte、100byte的字符串进行对比。
- 使用pcmpeqb指令对方如寄存器的16字节字符串逐一进行对比（结果一致的字符串标识位0xFF，不一致的则为0x00）。
- 通过pmovmskb指令将各字符串的最高位同时放入整数寄存器中。此时，对寄存器中的值进行取反（通过与0xFFFF进行XOR操作获得），结果不为0则表示字符串不相同。
- 2的结果不为0时，用bsf指令来确认字符串中不相同字符的位置。
图4-8为改良memcmp函数执行时间的测试结果。
- fputs函数
- fwrite函数
- 自定义块大小的行输出函数
- 将归并程序用7个管道连接起来；
- 500万行的文件（每行157字节）作为输入数据归并到一个文件输出；
- 操作时使用8核CPU。
- 将输入的数据一边分类一边放入数组中，将分类后的数组按相同key数据进行输出。
- 输入后的数据按顺序放入数组中，使用指针链接生成二分查找树。然后按设定的规则对二分查找树进行查找，将分类后的数据取出，将持相同key的数据输出。
- （若有左边树杈）向左边部分树杈前进
- 若从左边返回则输出数据
- （若有右边树杈）向右边部分树杈前进
- 如从后面回来，则回到树根
输出方法
同样，对比以下三个输出方法。
fputs函数
fputs是与fgets相对的库函数，被调用时将接收到的数据复制到stdio缓冲区。缓冲区容量不足时，fputs将使用write系统调用来写入文件。
管道输入输出的特殊案例
在Unix/Linux中，无论输入输出对象是存储设备上的文件，还是标准输入的管道，程序都进行相同处理。Linux 2.6.11以上的内核内部管道的缓冲区大小是64KB，若缓冲区大于64KB，速度会降低。因此，当输入输出对象为管道是，块输入输出的缓冲区长度控制在64KB会是性能有所提高。
实际上，可以通过变换stdio的缓冲区大小来测试管道输入输出的性能。进行以下性能测试，如图4-15：
管道输入输出与文件输入输出
图4-17，需将程序的输出结果在文件输出后在传递给后面的程序，所以后段的程序需等前段的处理全部结束后再开始，因此总执行时间变长。
4.6 【算法篇】二分法查找与平衡二叉树
这里以搜索算法的选择为例，介绍在选择算法时需要考虑什么，如何选择以及效果等。
海量数据的分类
假定需要将各地连锁店的数据按商品或地区进行分类，并将结果分别放入文件中。可采取方法： 由于没有将输入数据进行分类，所以首先将数据按类别关键字的顺序来分类，然后将持有相同key的数据汇总放入文件中。
分类操作中，若处理数据不大，使用哪个算法时间都大致相同。但是若采用相同方法，将1亿数量的4GB大小的输入数据分类到十万个文件中，耗时可能时几天甚至数十天。因此需要进行改良。
截图4-1为输入数据的案例，空格将商品编 、地区、销售额等字段隔开。
采用二分法查找对数组上的数据进行排序
将输入数据按key值顺序插入数组，如图4-19。
声明：本站部分文章及图片源自用户投稿，如本站任何资料有侵权请您尽早请联系jinwei@zod.com.cn进行处理,非常感谢！