本文主要是介绍冷热字段分离提升程序局部性,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
突然想起了上学期课堂上的一个提升程序局部性的案例,我觉得非常有意思,写篇博客记录一下。
1 场景
案例场景非常简单,就是遍历访问大结构体数组的某一字段。对应到下图,funcA
要访问a[N]的fld3字段,funcB
中要访问b[N]的fld5字段。
在这个场景中,程序要访问的结构体数组很大(单个结构体要占用600B内存),然而,要访问的字段却很小,大约1B-4B。总结来说,就是,大结构体数组,按行存储,按列访问。
这段程序的问题是,超过90%进入cache的数据不会被利用。在当前主流架构下,cache line的大小是64B,一次加载的粒度自然也是64B。那么,在这种场景下,缓存到cache的绝大部分数据是无效数据。一方面,这会对程序没有发挥出最好的性能;另一方面,无效的数据移动会带来很大的能量消耗,在嵌入式场景下,application对能耗还是很敏感的。
2 改进
其实,要解决这个问题,思路很简单,就是要把结构体数组中的热字段放在一块,冷字段放在一块。这样的话,cache命中率自然就提升上去了。
2.1 手工调整数据结构
这种方法简单粗暴,理论上没啥问题,就是有点费程序猿。具体来讲,有两种方法。
2.1.1 方法1
这种方法是在结构体内存调整字段顺序,将热字段靠拢放置。就比如,下图struct A
中的fld3和fld5是热字段,把两者放在一块就好了。这样一次cache line加载就可以将两个字段同时放入cache。
- 这种方法存在问题
- 一个结构体中所有热字段可能不够64B,cache还是会加载很多的无效数据。
- 结构体中可能会嵌有很多子结构体,不同子结构体的热字段无法并拢。
- 调整后字段顺序后的代码可读性下降。
2.1.2 方法2
这种方法重构了结构体,将热字段单独成立一个结构体,冷字段成立成另外一个结构体。如下图,struct A
被拆分为了struct A hot
和struct A cold
,这样的话,热字段fld3就可以放在一块了,cache line加载可以最大程度上避免冷数据放入cache。
- 这种方法存在问题
- 重构结构体,调整字段顺序,代码可读性大大下降。
- 源代码改造涉及面广,人工修改工作量巨大,易错。
2.2 自动代码变形
另外一种思路是做自动化工具,也就是做一个编译器,这个编译器自动帮我们进行冷热字段分离,这比手工改的逼格高得多了。具体来讲,也有两种方法。
2.2.1 源到源编译器
这种方法其实就是把手工调整数据结构的方法2进行自动化实现:输入.h\.c源代码文件,输出优化后的.h\.c源代码文件。
- 这种方法存在问题
- 源代码中的程序写法千变万化,自动化工具要识别出所有的写法有点不大现实。
2.2.2 IR2IR编译器
这种方法的思路是,既然在源代码层不好做自动化工具,那就考虑改IR,毕竟IR要规整的多。如下图,自动化工具会先运行一遍程序,识别出热字段,然后,在IR层修改,输出优化后的二进制程序。
使用IR2IR编译器优化后的程序,运行时间由6.9ms提升至6.7ms,提速了3%。
这篇关于冷热字段分离提升程序局部性的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!