遍历?
是的,遍历!遍历本来就是饱受诟病的事情,它就是为低效而生的,若要提高性能,采用别的数据结构多好,干嘛要提高遍历的性能?!
我不会没事瞎写文章充数的,一定是发生了什么,当然,这个我放到最后说。
是的,遍历也需要高性能。特别是在某些万不得已的折中环境下,比如hlist本来就是哈希链表了,为了解决必然会遇到的哈希冲突,遍历就是必须的,比如以下的接口都是hlist_head遍历:
hlist_for_each
hlist_for_each_entry
hlist_for_each_entry_safe
hlist_for_each_entry_rcu
...
当然了,平心而论,如果hlist过长,此时首先要考虑的是增加hash桶的数量以及提高hash算法的散列性能,而不是去优化遍历的性能,但是就事论事,在非hash表的情况下,如果单纯考虑遍历本身,我这里确实有些话要说。
首先,先摆出一个事实:
- 在连续的内存上进行遍历,其性能远超在离散的内存上进行遍历!
这是因为CPU在访问内存地址P时,会把一个cacheline的数据预取到cache,在连续的内存上,随着遍历的进行,链表项的访问和预取将形成一个流水化作业,这个流水线只要不被打断,遍历就好像在cache中进行一样。
现在考虑实际情况,我们的链表项能保证地址连续吗?或者退一步说,能保证其地址尽可能连续吗?
我建议先阅读我前面的一篇文章:
https://blog.csdn.net/dog250/article/details/105544111
kmalloc由于使用全局共享的kmem_cache slab(当前实现是slub,所以这里没有写错)数组,因此很难保证内存对象的连续,那么如果我们自己ceate一个kmem_cache呢?事情会变好吗?
还是看我前面的那篇文章,有个结论:
- kmem_cache是栈式管理对象的!free操作相当于一个push,alloc操作相当于一个pop!
我们看看这种栈式管理的性质:
- 栈式管理保证了kmem_cache的slab本身内部碎片的最小化。
- 栈式管理无法保证连续分配到的对象地址的连续性。
- 栈式管理的slab对象分配顺序取决于已用对象的释放的顺序。
我们做一个实验以证之,还是那个alloc.stp,稍微修改一下:
%{
#include <linux/module.h>
#include <linux/time.h>
struct stub {
struct hlist_node hnode;
unsigned char m[5];
};
#define SIZE 8000
static inline void hlist_add_behind_rcu(struct hlist_node *n,
struct hlist_node *prev)
{
n->next = prev->next;
n->pprev = &prev->next;
rcu_assign_pointer(hlist_next_rcu(prev), n);
if (n->next)
n->next->pprev = &n->next;
}
static void *(*_global_cache_flush)(void);
%}
function kmemcache_test()
%{
struct timeval tstart, tend;
unsigned long tuses = 0, tuseu = 0;
struct hlist_head *hashlist;
struct hlist_node *node;
struct kmem_cache *memcache;
struct stub *p, *ent, *ent_prev;
unsigned long rnd;
unsigned long addr, addr_pre, addr_next;
int i, j, retry = 2, sort = 0;
hashlist = kmalloc(sizeof(struct hlist_head), GFP_KERNEL);
if (!hashlist) {
return;
}
_global_cache_flush = (void *)kallsyms_lookup_name("global_cache_flush");
if (!_global_cache_flush) {
return;
}
INIT_HLIST_HEAD(hashlist);
memcache = kmem_cache_create("test_", sizeof(struct stub), 0, 0, NULL);
if (!memcache) {
return;
}
realloc:
for (i = 0; i < SIZE; i ++) {
p = kmem_cache_alloc(memcache, GFP_KERNEL);
if (p && sort == 0) {
hlist_add_head_rcu(&p->hnode, hashlist);
} else if (p && sort == 1) {
addr = (unsigned long)p;
if (hlist_empty(hashlist)) {
hlist_add_head_rcu(&p->hnode, hashlist);
} else { // 该else分支处理按序插入
hlist_for_each_entry_safe(ent, node, hashlist, hnode) {
addr_pre = (unsigned long)ent;
if (addr < addr_pre) {
hlist_add_head_rcu(&p->hnode, hashlist);
break;
}
if (node == NULL) {
hlist_add_behind_rcu(&p->hnode, &ent->hnode);
break;
} else {
struct stub *ns = hlist_entry(node, struct stub, hnode);
addr_next = (unsigned long)ns;
}
if (addr > addr_pre && addr < addr_next) {
hlist_add_behind_rcu(&p->hnode, &ent->hnode);
break;
}
}
}
}
}
i = j = 0;
/* 排除cache的既有影响:
* 大概率已经在cacheline了,释放掉以凸显链表节点的地址对遍历的影响)
*/
_global_cache_flush();
do_gettimeofday(&tstart);
hlist_for_each_entry_rcu(ent, hashlist, hnode) {
/* 将以下的打印注释释放你将看到细节 */
//STAP_PRINTF("[%d] 0x%p ", i, ent);
if (!strcmp(ent->m, "abcd")) // 稍微做点事,显得很忙。
j ++;
if (i > 0) {
unsigned long hi = (unsigned long)ent;
unsigned long lo = (unsigned long)ent_prev;
signed long delta = hi - lo;
if (delta < 0)
delta = lo - hi;
//STAP_PRINTF("delta [%llx] sort:%d retry:%d\n", delta, sort, retry);
} else {
//STAP_PRINTF("delta [0] sort:%d retry:%d\n", sort, retry);
}
ent_prev = ent;
i ++;
}
do_gettimeofday(&tend);
tuses = (tend.tv_sec - tstart.tv_sec)*1000000 + tend.tv_usec - tstart.tv_usec;
tuseu = tuses/1000000;
tuses = tuses - tuseu*1000000;
if (retry != 2) {
STAP_PRINTF("%ld .. %ld sort:%d retry:%d %d\n", tuseu, tuses, sort, retry, j);
}
begin:
// 随机释放!当然了,可以安排一个精心的释放序列,干点坏事
hlist_for_each_entry_safe(ent, node, hashlist, hnode) {
get_random_bytes(&rnd, sizeof(unsigned long));
if (rnd % 2 == 0) {
hlist_del(&ent->hnode);
kmem_cache_free(memcache, ent);
}
}
if (!hlist_empty(hashlist)) {
goto begin;
}
/* 控制流程:
* 第1次:刚刚初始化的kmem_cache slab分配SIZE个对象并遍历(内存地址是顺序的)
* 第2次:随机顺序将对象全部释放后再重新分配SIZE个对象并遍历(内存地址是散乱的)
* 第3次:随机顺序将对象再次全部释放后重新分配SIZE个对象按照内存地址顺序插入hlist并遍历
*/
if (retry > 0) {
if (retry == 1)
sort = 1;
retry --;
goto realloc;
}
kmem_cache_destroy(memcache);
%}
probe begin
{
kmemcache_test();
exit(); // oneshot模式
}
以下是几次的运行结果:
0 .. 218 sort:0 retry:1 i:0
0 .. 213 sort:1 retry:0 i:0
0 .. 222 sort:0 retry:1 i:0
0 .. 208 sort:1 retry:0 i:0
0 .. 219 sort:0 retry:1 i:0
0 .. 211 sort:1 retry:0 i:0
0 .. 227 sort:0 retry:1 i:0
0 .. 209 sort:1 retry:0 i:0
0 .. 237 sort:0 retry:1 i:0
0 .. 207 sort:1 retry:0 i:0
0 .. 240 sort:0 retry:1 i:0
0 .. 206 sort:1 retry:0 i:0
足以见得按照内存排序对遍历性能的影响。
你可能想知道栈式管理的slab在随机释放对象后再分配时发生了什么,我画一幅图就明白了,为简单起见,我用顺序的自然数编号内存地址:
我们可以得出一些trick式的结论,在确定hash桶无法增加的情况下,为了让hlist桶冲突链表的遍历性能更高,我们需要:
- 尽量保持hlist_node的内存地址的紧凑且单调递增。
- 条件允许的情况下,每个桶一个kmem_cache,单独维护一个slab池子。
想做到保持内存的紧凑,内核已经提供了API:
void hlist_add_after_rcu(struct hlist_node *prev, struct hlist_node *n);
// 低版本内核没有add behind接口,需要自己copy
void hlist_add_behind_rcu(struct hlist_node *n, struct hlist_node *prev);
插入的代价仅仅是执行一次冒泡,如果插入操作是非频操作,建议这么做!
说说我为什么写这篇文章。
昨天发现了使用kmalloc导致的性能问题后,我换成了自行维护的kmem_cache来管理对象的内存,性能相比之前减少了20%的pps损耗,好事啊!
然而,经过频繁的alloc,free操作后,我发现了偶然的性能抖动,难道我自己维护的slab还有什么幺蛾子问题吗?
通过crash工具的kmem -S以及slabinfo,slabtop,我发现我自己的slab也变得零散了…在解决这个问题之前,我首先想到了一个 坏主意:
- 我什么都不用做,只要在一个slab里不断的分配内存,然后按照精心布局的顺序释放掉它们,就能把这个slab打的全是空洞…
然后就又是左右手互搏了。如果我自己碰到了我这样的坏人,我该怎么应对!
旁边的同事建议我自己维护一个预分配好的大池子,自己管理自己的内存,不要使用栈式的slab。当然,我也是蠢蠢欲动地想实现一个 基于位图的连续内存分配算法 :
- 学习buddy系统(管理全局内存)的样子做一个大小固定的buddy系统。
大小不固定和大小固定的内存对象管理算法,说到底就是一个是解决内碎片的问题,一个是解决外碎片的问题,类似于段式(大小不固定)和页式(大小固定)的内存管理方法。
可是我不会编程啊!
说到底还是因为懒,最后发现方法虽然不是很精确,但是足够简单!大多数情况够用了,就是我上面说的 按照node的内存地址重排 的方案。结果测试下来,pps性能照之前的优化又提高了将近一倍!损耗由%4进一步降低到了2%左右!
皮鞋啊皮鞋,买皮鞋👞去咯!
我们知道,机械磁盘的磁头运动是一个重体力劳动,保持顺序读写方能高效,实际上,内存的非机械读写也同样。这一切背后的原则就是数据的局部性!
浙江温州皮鞋湿,下雨进水不会胖!
原文链接: https://blog.csdn.net/dog250/article/details/105566230
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍;
也有高质量的技术群,里面有嵌入式、搜广推等BAT大佬
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/406019
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!