Project1

标题: 记一次优化函数的经过 [打印本页]

作者: SixRC 时间: 2019-5-25 01:19
标题: 记一次优化函数的经过
本帖最后由 SixRC 于 2019-5-25 12:31 编辑

不久前头疼想写一下RGSS的位图处理函数看看能不能提高效率
然后打开帮助手册定位Bitmap 从上面看下来 dispose dispose? width height rect 都没啥好写的
然后看到 blt 嗯！就决定是你了！
然后就一步步写
开始的过程没啥好讲的
就是判断传入的参数是不是超出位图界限了小于 0 大于宽高相应做处理
处理完这些开始好好开始写代码了
现在我们有源位图目标位图到目标的坐标源区域以及透明度

已知目标颜色 c1 源颜色 c2 目标透明 a1 源透明 a2 源透明=src点值的透明度*传入的透明度/255
查资料可以得到混合后的颜色

除法耗时间而且这样很乱化一化

这时候我没想太多
就单纯分别复制粘贴对每个颜色分量都处理了一下以及混合透明度 = 1-(1-a1)(1-a2)
然后套了一个多线程

我那时候觉得一直说RGSS效率不高感觉套个多线程应该可以跑赢原版吧不是不可能跑不赢啊
RGSS只有单线程而我毕竟四核
然后测试循环 10000次 200*200 的blt
结果是原版 1.05 s
而我这版本得大概 1.1 s

结果还是挺意外的真的
已经四核心在跑了还没人家单线程快...
这时候唯一打赢原版的就是在目标/源透明度为0或255的时候因为我写了判断直接复制/跳过而原版没有作这处理

不过没有绝望毕竟才刚开始
回到刚刚的玩意
发现可以提取一下算式的部件
处理每一像素的时候
源和目标的透明度值是固定的这部分就不需要重复计算
只要带入RGB三色计算
由 a1 a2 可以得到三个部件

可以简化到
混合色 = (目标色×Part2 + 源色×Part3) / Part1
这样一写一运行老样子
诶意料之中编译器优化不是白给的
不过又想到其实可以查表的
因为透明度值配对顶多 255×255 种储存每种情况的三部件运行的时候拿来用就好啦
然后开始写
写完一运行  0.99-1.01 完全没有性能提升的感觉..

心情糟糕的继续想
这期间我试了SSE指令但是SSE指令集没有packed除法
我就试了乘法把表格作成了 part2/part1 part3/part1 的浮点数
但是效率更糟糕了估计是类型转换的时候耗时太多了
我不甘心
肯定有更好的方法原版blt实现了我不能放弃

然后想啊想啊想想到编译器优化的时候除法会成为加法和位移
我表都预先算好了除数也都知道了除法还不能换成位移吗？
这想法太振奋我了
原来是 part2/part1
现在是 x >> n
随便选定 n 为 20
x预先算好为 (part2 << 20) / part1  到时候可以直接拿来用
这样一优化
耗时直接降到了 ~0.55 s
但这还不够
因为这是四核的成绩
换成单线程耗时升到了 ~1.4s 删掉对特殊情况的判断耗时比原版略多大概是多线程的开销 (毕竟我写的代码是多线程的测试的时候只是在任务管理器调了处理器相关性)

时间上的对比可以确定出RGSS的做法也是预先算好表拿位移优化掉除法
具体怎样不太清楚
这函数效率真不能算低了
没有自己实现一遍真不能人云亦云

不过也可能是我不是专业写这玩意的
很多优化思路都是现想的没什么经验
真的觉得想到这份上已经很蛋疼了

不过还没结束我得超过它不然初衷没完成很烦
现在对每个颜色分量只剩下两个乘法和一个位移有三个分量
可以用SSE优化了
因为以前没写过SSE 没接触过 intrinsic
开始在读 8 位整数上踩了很多坑
开始是依次复制到16位内存区然后load 取数据也是类似
这样效率很低
不做优化的时候一个分量两个乘法一个位移两次读取一个加法存  三个分量汇编大概可以考虑成 (5*2+1+1+1+1+1)*3 = 45 个指令周期
而上面那样读取数据到XMM寄存器光读取存入就得耗费 ~20 周期坑的是编译器还不是按我的想法做的效率还更低然后莫名其妙更慢了
后来发现正确的做法是8位读入 unpack 存的时候再pack
亦即
源->XMM0  RGBA  (A没用但是读入不影响)(实际顺序是BGRA 也不影响)
目标->XMM1 RGBA
unpack XMM0,XMM1 -> XMM2 RRGGBBAA
unpack XMM2,zero -> XMM3 R0R0G0G0B0B0A0A0
乘数 ->XMM3 12121200
然后 madd (multiply and add) --> R G B 0
再位移再pack两次回8位直接存入就好
这样只耗 13 周期
然后把判断透明度是否属于特殊情况的代码删了
因为这时候计算一个像素已经非常快了在内循环不需要特别优化个别情况判断反而费时快就够了
然后根据汇编代码调整了循环的判断又减了一指令周期
于是有了最后的测算
耗时4核心  ~0.375s 单线程 ~0.8s
针对传入的alpha值当其为 255 时有更快的处理(这个判断是很外的循环)
因为不需要再查表获取实际的源透明度了源像素的透明度就是 (不然是 alpha*源透明/255)
四核心 ~0.32s 单线程 ~0.666s
最内循环的周期数分别是 28 和 25
似乎还能再减两周期/一周期因为寄存器没用全
不过在编译期间改不现实
可以后期动态改新建内存放代码跳过去跳回来
确实成功了
28-->26  0.336s  0.7s
25-->24  0.306s  0.637s
不能再快了
真不行了

感觉
在优化的初期是各种想法
在后期完全是死抠指令周期因为少一周期就是百分之好几的提升

最后最后最后的优化
把 shl 5 和 add 表偏移
优化成了 lea *8 + x/4
后续寻址只要×4就行
就又减少一指令
不过估计是因为代码长度反而长了时间减少的没那么多了
不过 25 个周期现在是 23 多线程的耗时终于降到 0.3s以下啦！ 0.295s 0.59s
不过玄学报错
疯了

此帖留念

作者: fux2 时间: 2019-5-25 03:22

亲自做，比什么都强，受益匪浅吧。
墨菲定理生效~

作者: SixRC 时间: 2019-5-25 09:40

fux2 发表于 2019-5-25 03:22
亲自做，比什么都强，受益匪浅吧。
墨菲定理生效~

确实学到超多
现在我能写SSE啦
看见最终代码紧凑的样子真的是感觉没白写
开始反汇编出来一团糊
最后就那么几句了
发现核心循环的代码真的是越少越好
后期减少%4%5的核心指令减少的时间居然更多
可能指令越少在最核心预读越方便和快吧

好像又想到了能优化的地方..

作者: myownroc 时间: 2019-5-28 12:47
图像处理能查表就查表

作者: 664145107 时间: 2019-6-7 11:03
是大佬
tql，awsl

欢迎光临 Project1 (https://rpg.blue/)