记一次优化函数的经过

SixRC

不久前头疼想写一下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
不过玄学报错
疯了



此帖留念

664145107

是大佬
tql，awsl

myownroc

图像处理能查表就查表

SixRC

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

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

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

fux2

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