slab着色--一种必然认输的妥协

2024-05-07 11:18

本文主要是介绍slab着色--一种必然认输的妥协,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

在最新的linux2.6.28内核当中已经不见slab着色的踪迹了,记得研究2.6.9的时候,我还为理解slab着色大伤脑筋,而实际上我当时根本没有理解它的设计初衷以及最终的效果,只是把它当成了一个纯粹的“算法”来玩,还玩得不亦乐乎... 
      slab的目的是什么?其实它是为了在软件缓存和硬件缓存冲突的时候达成的一种妥协,而普遍的观点是只有相互平等的当事者才具有妥协的可能,如果关系根本 tmd就不平等,那么妥协只是可怜的一厢情愿而已。那么硬件和软件平等吗?在高处看的话是平等的,我们常说硬件的功能完全可以用软件模拟,想象一下,一个cpu 就可以模拟很多的专业电路,靠的就是cpu执行的软件指令,内部是布尔逻辑解决的,诸多的布尔逻辑组成了复杂的算法,完全模拟了专业的硬件连线逻辑,但是 我们不从功能上谈,从别的方面想想,它们就不那么平等了,首先它们的层次不同,计算机硬件往往只是提供了一个平台,一个场地,它提供的是彼此正交的指令系 统,具体怎么发挥要看软件的算法设计,可以说硬件提供了机制而软件实现了策略,如果所有的策略都由硬件直接实现,那么就回到了工业革命或者电气革命时代, 软件工业就消失了,可现实是软件发展的如火如荼,现在硬件发展的已经相当成熟了(摩尔定律制约),我们说一旦出了问题,先不要想是不是机制有问题,而是先 想想是不是我的策略没有用好机制,就好像你在linux上写了一个程序,结果出了些问题,那么不要一开始就怀疑内核出了问题,当然问题的修正,不管是本质 问题还是效率问题都应该应用程序来修正而不能为了迎合一个应用程序的策略而大修改内核机制。同样的道理,当slab代表的软件缓存和cpu硬件cache 有冲突的时候,那么需要修正的也是软件slab缓存。在具体分析之前我为了节省脑细胞(呵呵,主要是我的文笔太差,想表达一个意思对我来说很有难度,因此 我老婆总说读我的东西总像在读翻译得很糟糕的中译本)我先引用一段: 
另一个slab allocator注意到的问题是cpu cache的使用率.一般的cache算法是 
           cache location = address % cache_size 
一 般的power of two配置法配置的内存都会经过align(对齐)(首次模仿袁老), 并且大多数程式的习惯会把最常用的资料栏位放在一个结构的最前面. 这两个效应合在一起, 造成这些栏位互相的清掉彼此的cache. 512kb的cache可能只有部分有作用. 更甚者, 如果主记忆体使用interleave的方式, 比如说SPARC center 2000 使用两个bus, 较低的256byte使用第一个bus,较高的256byte使用第二个bus, 那麽所有的data可能会集中在第一个bus上, 造成不平衡现象. 
     Slab的解决方法是在向paging系统取得一块block之後, (假设为1KB), Slab把他要用的资料摆在这个block最後面, 假设占y bytes. 假设所要配置的是inode, 大小跟前面Mach的例子一样皆是104. 那麽这块记 忆体可以提供(1024-y)/104个inode. 并且有一些馀数, 也就是剩下一些多馀的记忆体.Slab善用这些记忆体, 将之二等分, 一份摆在这块记忆体的最前面,一块摆在最後面. 最前面那块称为coloring area. Slab设法在每次配置的page上使用不同大小的coloring area, 以有效的 分散资料map到cache中的位置,增加cache rate. 
(**)Allocator Footprint指的是Allocator在配置记忆体的时候将自己,以及所参考到的资料写到cpu cache/ TLB (translation lookaside buffer), 在cache/TLB上面产生的"脚印". Allocator在cache/TLB内 所留下的资料基本上是没有用的, 并且妨碍真正有用的资料留在cache上. buddy演算法需要参考许多资料才能配置记忆体, 会产生大量的"footprint", 导致cache miss增加. McKusick-Karels和zone allocator的足迹皆很小, 原因是配置记忆体的时候直接从free list上把第一个element抓出来而已. 所以一个好的配置法应该使用简单的演算来配置 物件.Slab也是使用相同的原则, 不论是配置或者是释放,都是简单的一两行运算而已,所以foot print也很小. 
原文是台湾的繁体中文,而且用不同的表达词汇,我就不翻译了,大致可以看懂(我们都是炎黄子孙)。slab是好的,因为提前缓存了初始化好的频繁被用到的 结构体,但是由于对齐问题而会造成cpu的cache频频失效,那么软件的解决方法就是slab着色,注意,cpu的cache频频失效就是所谓的冲突, 冲突发生了,软件解决之,不能让cpu cache进行改进,因为那是机制,软件才是策略,于是slab着色由运而生。slab着色的本质就是让slab缓存的对象在cpu的cache里面彼此 错开,这样就不会造成cpu cache频频失效了,否则,经过对齐的很多slab对象都会map到cpu cache的相同位置,这实在不是我们想看到的,cpu cache失效带来的损失抵消了一部分slab缓存带来的性能提高。以上引用的仅仅是从原理上描述的,下面我列举出linux内核中的实现代码: 
struct slab { 
         struct list_head list; 
         unsigned long colouroff; //该slab的第一个对象的偏移,这个偏移实现了slab对象的错位 
         void *s_mem;             //对象的内存地址,需要对象的时候从这里分配。 
         unsigned int inuse;      //slab中的活动对象数目。 
         kmem_bufctl_t free; 
         unsigned short nodeid; 
}; 
struct kmem_cache * kmem_cache_create (const char *name, size_t size, size_t align, unsigned long flags, void (*ctor)(void*, struct kmem_cache *, unsigned long), void (*dtor)(void*, struct kmem_cache *, unsigned long)) 

         size_t left_over, slab_size, ralign; 
         struct kmem_cache *cachep = NULL; 
         struct list_head *p; 
...  
         cachep = kmem_cache_zalloc(&cache_cache, SLAB_KERNEL); 
         size = ALIGN(size, align); 
         left_over = calculate_slab_order(cachep, size, align, flags); //这个left_over就是上述引用的文字中的“多馀的记忆体” 
... 
         slab_size = ALIGN(cachep->num * sizeof(kmem_bufctl_t) + sizeof(struct slab), align); 
... 
         cachep->colour_off = cache_line_size(); //偏移就是cpu cache line的大小 
... 
         cachep->colour = left_over / cachep->colour_off; //颜色的大小就是能错位的最大的数目,比如剩余的内存大小是20,cpu缓存行的大小是4,那么最多可以偏移到5个单位,一个单位是20/5=4 
... 

static int cache_grow(struct kmem_cache *cachep, gfp_t flags, int nodeid) 

         struct slab *slabp; 
         void *objp; 
         size_t offset; 
... 
         struct kmem_list3 *l3; 
... 
         offset = l3->colour_next; 
         l3->colour_next++;  //colour_next字段代表的就是当前偏移到第几个单位了 
         if (l3->colour_next >= cachep->colour) //当偏移的单位超过了总的最大的偏移单位数目,那么当前偏移单位值回归为0。 
                 l3->colour_next = 0; 
         spin_unlock(&l3->list_lock); 
         offset *= cachep->colour_off; //当前要分配的slab的对象要从offset开始,这个offset和上一个slab错开了l3->colour_next和单位,每个单位的大小为colour_off 
... 
         objp = kmem_getpages(cachep, flags, nodeid); 
... 
         slabp = alloc_slabmgmt(cachep, objp, offset, local_flags, nodeid); //分配slab 
... 
         list_add_tail(&slabp->list, &(l3->slabs_free)); 
... 

static struct slab *alloc_slabmgmt(struct kmem_cache *cachep, void *objp, int colour_off, gfp_t 
local_flags, int nodeid) 

         struct slab *slabp; 
... 
         slabp->inuse = 0; 
         slabp->colouroff = colour_off;  //初始化偏移 
         slabp->s_mem = objp + colour_off; //该slab的对象地址从当前偏移处开始,这里可以看出这个slab的对象和上一个错开了colour_off大小,这样可能就在cpu的cache里 面错开了,但是大多数情况效果甚微 
... 

看到最后一个函数alloc_slabmgmt的最后一段注释,说效果甚微,这是为什 么呢?这其实就是最终撤销slab着色的原因之一。我们看到如果slab的数目只有cachep->colour个的话,这个slab着色的效果就 太好了,但是这往往不太现实,slab的数目有时是相当大的,这样的话,slab着色实际上只是帮了一点点小忙而已,它仅仅保证了最开始的几个slab不 会map到同一个cpu cache line,但是待slab逐渐增加以后,后面的slab将还是会无情的打仗,从而造成cpu访问cache频频失效,这种能救几个算几个的思想可能对于人 类救灾是有效的,毕竟生命高于一切(当然不包括三氯氰胺事件),但是对于系统设计,这种效果的机制不如不要,因为我们用大量的代码维持了一个效果甚微的方 案,这是不值得的,软件设计就是这样,每笔账都要算清,赔本的生意绝对不做,内核开发者的慧眼识别出了这个滥竽充数的所谓的巧妙算法,绝然地移除了它,在 分配器从slab发展到slub以后,这个问题相对减轻了许多,slub的思想就是简单,不要那么多花里胡哨的算法,就是简单,简单就是美,这确实是一句 真理,冲突就冲突呗,只要我们带来的益处超过了冲突带来的麻烦,这就是值得的,鸵鸟算法在这种情况下就是有效的,确实是这样。上述引用的**段其实表明了 这一思想,可以好好体会一下。 

作任何事情都是这样,巧妙如果变成了花拳绣腿,那它除了表演就没有别的价值了,毕竟你要维护这种巧妙需要的心血是很大的,有时可能远远大于它带来的回报。回归本真是最好的方式,简单,简单,简单就是一切!


注:同一硬件高速缓存行可以映射RAM中多个不同的块,相同大小的对象倾向于存放在高速缓存内相同的偏移量处。在不同slab内具有相同偏移量的对象最终很可能映射到同一高速缓存行中。而使用slab分配器的对象通常是频繁使用的小对象,高速缓存的硬件可能因此而花费内存周期在同一高速缓存行与RAM内存单元之间来来往往的传送两个对象。
 
如下例:假设cache行为32Bytes,CPU包含512个cache行(缓存大小16K)。
假设对象A,B均为32B,且A的地址从0开始,B的地址从16K开始,则根据组相联或直接相联映射方式(全相联方式很少使用),A,B对象很可能映射到cache的第0行,此时,如果CPU交替的访问A,B各50次,每一次访问cache第0行都失效,从而需要从内存传送数据。而slab着色就是为解决该问题产生的,不同的颜色代表了不同的起始对象偏移量,对于B对象,如果将其位置偏移向右偏移32B,则其可能会被映射到cache的第1行上,这样交替的访问A,B各50次,只需要2次内存访问即可。
 
这里的偏移量就代表了slab着色中的一种颜色,不同的颜色代表了不同的偏移量,尽量使得不同的对象的对应到不同的硬件高速缓存行上,以最大限度的提高效率。实际的情况比上面的例子要复杂得多,slab的着色还要考虑内存对齐等因素,以及slab内未用字节的大小,只有当未用字节数足够大时,着色才起作用。

来源:

http://blog.csdn.net/dog250/article/details/5303421

http://blog.chinaunix.net/uid-20196318-id-28854.html


这篇关于slab着色--一种必然认输的妥协的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/967193

相关文章

一种改进的red5集群方案的应用、基于Red5服务器集群负载均衡调度算法研究

转自: 一种改进的red5集群方案的应用: http://wenku.baidu.com/link?url=jYQ1wNwHVBqJ-5XCYq0PRligp6Y5q6BYXyISUsF56My8DP8dc9CZ4pZvpPz1abxJn8fojMrL0IyfmMHStpvkotqC1RWlRMGnzVL1X4IPOa_  基于Red5服务器集群负载均衡调度算法研究 http://ww

一种快速生成CSV的方法

事情是这个样子的 在QQ群在聊把如何100万数据导出成CSV文件?会不会很慢? 俺回了一句“现在的机器性能好,没啥问题”。 然后大家开始谈论机器的配置了。哎,俺的机器配置有点差。 然后俺就进行了一个测试。 测试数据 数据定义         public struct Rec         {             public int v1;             publi

【Visual Studio 报错】未加载 wntdll.pdb(一种可行的解决办法)

调试程序时,会出现下面这个报错 分析原因: 出现未加载 wntdll.pdb 报错大概率是你的指针使用错误 ,比如使用野指针、越界访问、或者堆区空间释放方式错误等。 这里以 堆区空间释放方式错误 为例子 1、堆区开辟的数组空间使用 delete 释放 // 堆区开辟的数组空间使用 delete 释放int* p = new int[10];delete p; 正

CVPR 2024最新论文分享┆YOLO-World:一种实时开放词汇目标检测方法

论文分享简介 本推文主要介绍了CVPR 2024上的一篇论文《YOLO-World: Real-Time Open-Vocabulary Object Detection》,论文的第一作者为Tianheng Cheng和Lin Song,该论文提出了一种开放词汇目标检测的新方法,名为YOLO-World。论文通过引入视觉-语言建模和大规模预训练解决了传统YOLO检测器在固定词汇检测中的局限性。论

JWT详解:一种轻量级的身份验证和授权机制

引言 JSON Web Token(JWT)是一种基于JSON格式的开放标准(RFC 7519),它定义了一种紧凑且自包含的方式,用于在各方之间安全地传输信息。JWT因其轻量级、可扩展性和安全性,在Web应用程序和RESTful API中得到了广泛应用。本文将详细解析JWT的概念、结构、工作原理、应用场景以及使用时的安全注意事项。 JWT的基本概念 JWT是一种用于在用户和服务器之间传递安全

JD 1147:Jugs(一种用最少步骤求解的方法)

OJ题目:click here~~ 题目分析:九度上这道没有要求最少步数,只要得到最后结果即可AC , bfs , dfs都行。最少步骤的方法肯定也能AC啦,分析如下。 输入的三个数:a,b,n;> 由题不定方程ax+by=n必定有解> 如果b=n,则fill B即可,否则用试探法求出这样的两组解(a1,b1)及(a2,b2),其中a1 >0,b1<0;a1是满足方程的最小正整数;a2

一种实现微观单线程,宏观上多线程的方法

1. 纵所周知的是,C语言是顺序程序设计的,那么在一些MCU中,例如STM32,Atmega168等等,在微观上程序都是单线程的,那么应该如何实现微观上的多线程呢?这个用到两个东西:一是中断,二是switch语句。听老夫为你细细道来。   2. 举个例子来说,比如我想要实现的是:MCU每2秒通过6个USART向外发送数据。一般大家首先想到的是,配置一个定时器,每2S进入一个中断函数,然后中

一种在C++中外部强行访问私有成员的方法

问题 C++在设计上,是不允许类的私有成员在外部被访问读写的。 然而,有时是想要在外部访问私有成员的。我目前常见的情况是:想要访问UE引擎代码中的类的私有成员,但又不想“污染”其源代码将其private改为public。 方法 一种方法是,再建立一个完全相同结构的类,只不过将成员改为public: class MyClassA_MirrorPublic{public:int dat

Java参数传递机制的一种打开方式

传值 or 传址?实参 or 形参?基本数据类型 or 引用数组类型?学习过Java,相信你对这些概念肯定熟悉,然,时间久了,某一天突然被问到这些,又一脸懵逼,它们讲的是啥,如何区分?来,让我们通过实践操练起来,请看下面一题,思考输出结果。 import java.util.Arrays;public class Exam4 {public static void main(String[] a

第一章 感受mac之美-换一种方式用电脑,开启新历程

感谢关注我的读者一直以来的追随与信任。去年到今年以来大环境都不是很好。裁员,机构优化,工厂倒闭,公司破产,贸易战等消息传来,不少还是身边发生的。今年开年以来更是有病毒横行,天降蝗灾等灾害。愿大家都好好的,同时希望这场战役早早告捷。今天是二月二 ,民间传说龙抬头,祝愿大家从此事业腾飞,从此出人头地。 我在这断更的两年中的一些情况,一直处于闭关的状态,一直在学习与实践。后续再和大家一起分享这俩年