使用向量操作

使用向量操作现代微处理器具有向量指令，使得可以同时对向量的所有元素进行操作，也称为单指令多数据操作（SIMD）每个向量的总大小可以是64位（MMX），128（XMM），256（YMM）和512（ZMM）； 大型数据集中，对多个数据元素执行相同的操作并且程序逻辑允许并行计算时，向量操作非常有用。 而本质上是串行的算法，比如大多数排序操作，以及严重依赖于查找表涉及大量数据变换的算法(例如许多加密算法)

optimizing software in C++

多线程

多线程在CPU时钟频率优先的情况下，提高CPU密集型程序吞吐量的方法是同时做多个事情，有以下三种方法： 使用多个CPU或者多核CPU 使用现代CPU的乱序执行能力 使用现代CPU的向量操作 为了利用CPU的多个核心，需要将任务划分到不同的线程，有两个主要的方法：功能分解和数据分解。 在考虑并行处理时，区分粗粒度并行和细粒度并行非常重要，细粒度并行是指任务被划分为许多的小任务，同时任务间存在协调

optimizing software in C++

优化内存访问

优化内存访问代码和数据缓存高速缓存是计算机贮存的代理，代理更小，更接近CPU，访问速度快很多，可能有二级或者三级缓存 CPU的速度比RMA内存的速度增长要快，因此高效的缓存变得很重要 缓存结构在程序中为了防止缓存竞争，了解缓存的组织结构将对于优化程序性能有很大作用 由于内存取数据到缓存的映射规则，当两个地址之间的间隔正好是关键步长的倍数（类似于同余）的情况下，会被取道相同的缓存组中，容易引起缓

optimizing software in C++

编译器中的优化

编译器中的优化8.1 编译器是如何优化的现代编译器为了提高性能会对代码做大量的修改，知道其做了啥，对程序员很有帮助 函数内联编译器默认内联小函数 节约调用、返回和传参开销 代码连续，代码缓存效率更高 缺点是，如果对内联函数有多个调用而且函数体很大，每个地方都会展开，代码会膨胀 常量折叠和常数传播只包含常量的表达式或者子表达式将被计算结果替换，例如： 1234double a, ba = b

optimizing software in C++

结构体和类

结构体和类面向对象编程使得软件具有模块化和更加清晰的特点，所谓对象就指结构和类的实例这种编程方法对程序性能有两面影响：** 正面影响：** 如果一起使用的变量是相同结构或者类的成员，那么他们会被存储到一起，这使得数据缓存效率更高 不需要将类成员和变量作为参数传递给成员函数，避免了参数传递的开销 ** 负面影响: ** 非静态成员函数有一个this指针，会作为隐形参数传递个函数，this的

optimizing software in C++

函数

函数函数调用可能减慢程序运行速度，原因如下： 函数调用涉及到代码地址跳转与返回，可能需要约4个时间周期 函数可能会导致代码分散在内存中，降低代码缓存的效率 32位系统中，函数参数存储在堆栈中，传参慢 需要额外时间设置栈帧，保存和恢复寄存器，还可能要保存异常处理信息 函数调用需要在分支目标缓冲器占（BTB）用空间，若程序关键部分包含许多调用和分支，BTB中的竞争可能会导致分支预测错误 因此针

optimizing software in C++

CF构造2022-03-24

概述2022-03-24 493D - Vasya and Chess简述给一个n x n的棋盘，左上角白色皇后，右上角黑色皇后，剩余地方绿色小兵，皇后可以水平、竖直以及斜角方向吃敌人，当被对方吃掉或者无小兵可吃时失败，问谁会赢。 思路显然应该分为奇偶来看待 当n为奇数时，白色必输，因为黑色棋永远可以和白色棋保持沿中心线对称的行动，从而白色棋不得不先去吃中心线上的小兵而导致其可以被黑色皇后吃掉

CodeForces 构造