美文网首页
软件性能工程

软件性能工程

作者: 谭英智 | 来源:发表于2021-10-06 16:44 被阅读0次

矩阵相乘例子学习

pe-matrix

使用python编写:

pe-py
计算时间需要6小时

语言优化

  • 使用Java编写需要46分钟
  • 使用c编写需要19分钟

解析

  • python是解析性语言,运行指令需要经过解析、执行,需要的时间也会越多
  • Java是介于解析语言与编译语言之间,经过优化,Java会比python跑得更快
  • C是之间运行字节码,因此速度最快

For Loop优化

原来的循环如下:

pe-for

修改顺序为:

pe-for-opt

性能表现如下:

pe-for-perf

可见for的顺序不同,性能会有非常大的差异

分析:

  • CPU访问cache非常快

  • CPU访问内存非常慢

  • 如果访问数据都在cache中,则缓存命中,否则不命中

  • CPU访问数据具有局部性,因此局部性的数据更容易放进cache中

  • 下面分析下不同for的内存表现:

pe-for-an
pe-for-an-opt

从上图可见,在内存访问的连续性来说,ikj会更优

可以通过命令查看程序的缓存命中率:

valgrind --tool=cachegrind ./mm

编译优化

pe-matrix-compiler

并行优化

pe-matrix-pall

运行时间为3s

缓存使用优化

  • register: 1 cycle
  • L1-cache: 4 cycles,
  • L2-cache: 10 cycles,
  • L3-cache: 50 cycles,
  • DRAM: 150 cycles
pe-matrix-multi

如果内循环计算一行C

  • 4096个数据吸入C
  • 4096个数据从A读入
  • 4096 * 4096 = 16, 777, 216 从B读入

而遗憾的是CPU L1缓存只有32k

这会导致在计算一个内循环,数据会不断的从内存读入,cache的缓存会不断的被刷走,导致运算低效

解决思路

通过减少内循环的计算量,从而减少数据被刷走的机率

pe-matrix-multi-2

如上图,如果内循环只计算C 64 * 64

  • 64 * 64 = 4096会写入C
  • 64 * 4096 = 262, 144会从A读入
  • 64 * 4096 = 262, 144会从C读入
  • 总共需要访存 528, 384

可见通过减少计算C的维度,可以大大减少访存的数量

pe-matrix-multi-3
pe-matrix-s-size

递归优化

还没看懂,先贴出来

pe-matrix-split
pe-matrix-split-time

SIMD编译优化

现代CPU不仅仅提供SISD,还会提供SIMD的指令操作

通过clang和llvm的编译优化 -march=native -ffast-math可以把某些指令并行化

优化后的时间为0.7s

下面看看例子总的优化对比

pe-matrix-perf

代码简单优化技巧

数据结构

  • 通过增加数据结构的字段,来加快访问速度
pe-link

例如通过增加链表的尾指针,来加快访问链表结尾的速度

  • 预计算
pe-bomin

例如计算伯努利分布,可以通过先把结果在程序运行之前算出来,构造出一个数据表,那么在程序运行的时候就可以直接拿到结果了

  • 缓存

    通过把结果缓存起来,可以加快程序运行的速度,例如使用LRU算法或者redis之类的中间件

  • 稀疏表示

pe-sparsit

例如一个稀疏矩阵,大部分数据都是零,而零乘以任何数都是零,是没用的计算,通过构造稀疏数据结构,既可以节省计算时间,也可以节省存储空间

例如CSR技术

pe-csr

逻辑优化

  • 常量计算

    例如const double area = pi * 3

    可以通过编译器,直接计算出结果,来减少运行时的开销

  • 公共表达式共用

pe-exp

例如表达式a - b已经计算过一次了,那么d就可以直接取结果,来减少多一次的计算

  • 使用更廉价的计算符

    例如计算两个圆是否相交

pe-cycle

计算开根号是复杂的

那么可以两边平方来优化

pe-square
  • 更快的返回
pe-fast-path

例如计算x和y的距离,来加快运算的返回

  • if条件优化
pe-if

例如' '是更常见的一个符号,则可以提前判断,来减少if的运算

循环优化

  • 表达式运算外提
pe-hoisting
  • 循环平铺
pe-for-unroll

减少了循环判断和++操作

  • 局部平铺
pe-for-part-unroll
  • 循环融合
pe-for-confus

函数优化

  • inline

  • 减少尾递归

pe-tail-recur
  • 减少递归
pe-coarsening

二进制操作优化

pe-x
pe-neg
  • 设置k位

    y = x | (1 << k)
    
  • 清除k位

    y = x & ~(1 << k)
    
  • 反转k位

    y = x ^ (1 << k)
    
  • 取头字节

    (x & mask) >> shift
    
  • 交换两个整数

    x = x ^ y;
    y = x ^ y;
    x = x ^ y;
    
  • 取两数最小的一个

    min = y ^ ((x ^ y) & -(x < y));
    

计算机体系结构

流水线增加吞吐量

pe-pipe-line

乱序执行,解决流水线的冲突和冒险

pe-issue

分支预测

pe-predit-if

CPU遇到跳转指令的时候,由于会出现两个分支的代码,而CPU不想等待判断结果出来,为了效率,而执行下一个指令,因此,CPU会预判一条路径执行下去,如果判断对了,则提高了效率,否则,CPU会把执行的中间结果清理,并执行对的分支

并行优化

pe-quick-sort
  • 快排的总工作量是 O(n log n)
  • 最大的串行工作量 n + lg n = n
  • 并行度 = n log n / n = log n

可见如果要再优化快排的并行度,需要把partition并行化

题外话:使用堆来实现栈的功能

  • 当程序进入一个函数,会把部分寄存器的信息保存
  • 把参数入栈
  • 栈的指针下移
  • 函数返回时,会恢复寄存器
  • 栈指针上移

假设我要用堆连存储某个函数的栈的信息

  • 可以new出一片足够大的区域
  • 指针不下移,而是移动到堆的地址
  • 函数返回时,不上移栈指针,而是从堆的地址切回到栈的地址

归并排序优化

pe-merge-sort
  • 总工作量:n log n
  • 串行最大工作 n + log n
  • 并行化:log n

问题出在merge的时间复杂度为n

通过二分并行处理merge:

pe-merge-bin
pe-merge-bin-code

可得:

串行时间:log n ^2

编译器优化

TBD

性能测量

pe-sort

这式一个排序算法的测量时间分布图

发现图像会出现非常奇怪的抖动。

他的原因是CPU随着计算的时间,会呈现出发热,此时计算机为了降温,所以把CPU的始终频率调低,导致排序出现上面的图形

问题的调整

pe-question

一般来说,要解决问题,必先发现问题

稳定的重现后,才可以比较容易的调整

最后把问题解决

测量时的问题

计算机的状态是不稳定的

  • 无可预知的后台进程
  • 中断
  • 代码和数据的对齐
  • CPU运行时的调度
  • 超频
  • 竞争
  • 网络状态
  • 磁盘访问和内存访问的错误和重试

测量工具

  • gettimeofday
  • gdb
  • gprof
  • perf
  • cachegrind

测量结果

取最小值

访存优化

  • 申请和释放都是O(1)

  • 会引起内部碎片和外部碎片
  • 大小不固定
  • 多线程竞争
  • 不同内存片位于不同的页表
pe-memory

管理

pe-single-heap
pe-multi-heap
pe-multi-heap-2
pe-heap

GC

  • 通过智能指针
  • 通过构造内存引用图,后台进程不断扫描,并清理没有引用的内存

相关文章

  • 软件性能工程

    矩阵相乘例子学习 使用python编写: 语言优化 使用Java编写需要46分钟 使用c编写需要19分钟 解析 p...

  • 软件性能测试目录

    软件性能测试Ⅰ 软件性能测试Ⅱ 软件性能测试Ⅲ 软件性能测试Ⅳ 软件性能测试Ⅴ 软件性能测试Ⅵ 软件性能测试Ⅶ 软...

  • 第1章 初识软件工程

    第1章 初识软件工程 1.5 软件质量实现 1.5.1 软件质量 功能质量(用户)软件符合要求且极少缺陷,性能正常...

  • 软件系统测试方案

    引言 1.1 编写目的 为软件开发项目管理者、软件工程师、系统维护工程师、测试工程提供关于项目系统整体功能和性能的...

  • 2018读书规划

    2018.8.11 init 高性能MySQL 软件工程 算法导论 数据结构 设计模式:可复用面向对象软件的基...

  • 软件测试读书笔记(佟伟光著)

    一、软件测试概述 1.1 软件、软件危机和软件工程 程序是指按特定的功能和性能要求而设计的能够执行的指令序列;数据...

  • 人们常说的前端工程化到底是什么?

    前端工程本质上是软件工程的一种。软件工程化关注的是性能、稳定性、可用性、可维护性等方面,注重基本的开发效率、运行效...

  • 阿里大规模数据中心性能分析

    郭健美,阿里巴巴高级技术专家,目前主要从事数据中心的性能分析和软硬件结合的性能优化。CCF 系统软件专委和软件工程...

  • 一个软件测试主管的10年工作心得与经验分享

    “从事11年软件测试工作,由软件测试助理(实习)开始,经历过测试经理助理,实习测试工程师、性能测试工程师再到测试高...

  • 性能调优那些事儿

    性能调优那些事儿 问题 性能优化是软件开发中最重要的活动,也是软件工程中的深水区,可以说也是衡量一个程序员能力高低...

网友评论

      本文标题:软件性能工程

      本文链接:https://www.haomeiwen.com/subject/fijonltx.html