Note of Justin

关于工作和读书的笔记

  C++博客 :: 首页 :: 联系 :: 聚合  :: 管理
  47 Posts :: 0 Stories :: 45 Comments :: 0 Trackbacks

留言簿(14)

搜索

  •  

积分与排名

  • 积分 - 51720
  • 排名 - 433

最新评论

阅读排行榜

评论排行榜

 

[原创文章欢迎转载,但请保留作者信息]

Justin 于 2009-10-28

看的版本是 侯捷的繁体版 ,有些术语乃至字都有些难懂。进度和理解程度竟然也没比英文的好多少@#¥%

侯捷把allocator译为配置器。配置器的接口大多不被STL用户看到,它的重要性在于几乎所有的其他STL对象都会请到它来配置(内存)资源。

STL自己的配置器有两套。第一套allocate是简单的对C++的operator new和delete的封装,STL自己没有用,也不推荐别人用(那你写来做啥捏?);第二套alloc是基于malloc、realloc和free实现的。alloc自身又有两级:

  • 二级配置器实际上是个内存仓库管理员。当有资源申请需求时,alloc会先判断所需空间的大小。如果等于或小于128bytes,就使用二级配置器。这个内存仓库管理员有16个储藏室,分别存放着分配好的8bytes、16bytes、24bytes直至128bytes的内存块。二级配置器的设计基本就是STL allocator的精华了,本文最后会继续记录有什么需要注意的地方。
  • 当需求空间大于128bytes时,我们就需要一级配置器申请。它没有什么现成的资源可以直接分配,而是用malloc/realloc向系统讨的。对于申请失败的处理,STL仿照C++的处理机制,提供了接口由客户指定函数作为new handler,以处理内存不足的情况。如果用户没有指定相应的函数,则直接抛出异常。

OK,重新回到二级配置器的可圈可点之处:

  1. union的使用。“内存仓库管理员”的16个“储藏室”实际上是16个单向的linked-list,list中的每个节点就是一块内存。一块挂在list上的内存是没有被人用的,所以书上说它叫free list。说实话,如果是我来做这样的list的话,节点的设计一定是小学生水平,用一个struct,里面两个指针:一个指向空闲的内存,一个指向下一个节点。STL给我上了一课:使用union。(好吧,我还是要抄一下代码):
    union obj {
          union obj
    * free_list_link;
          
    char client_data[1]; /* The client sees this. */
    }
    ;

    我认为这里巧妙的利用了free list的这一个特点:当一块内存还挂在list上时,没有人在意这块内存里是什么;当真的有人要读写这块内存的时候(也就是已经分配给用户使用的时候),这块内存已经和list没有任何瓜葛了。
    因此,同一块内存就可以在不同的时间扮演不同的角色:挂在list的时候就储存下一块内存的地址,脱离list后就随便你存放什么了。union几乎就是为这一功能量身定做的!减少了原来小学生设计的50%空间消耗!哇呀呀,太巧妙啦~~(请原谅我的浅薄,不知为不知,是知也……)
  2. 当申请空间的大小不是8bytes的整数倍时,用一个函数ROUND_UP向上取整为8bytes的整数倍数。这个函数是用位操作一次实现的。(好吧,我会去看Hacker’s Delight的……)
  3. 当没有某一个“储藏室”内内存用完了,而且这个时候又有用户申请时(哪壶不开提哪壶啊)的处理方法比较曲折,以下是我的解读(当然还是要免责一下:极小可能是完全正确的@#¥%)
       碰到开门后发现“储藏室”没有存货的时候,二级配置器的第一个反应就是向内存池(memory pool)求助(外援?):
    • 如果内存池有足够的货,就直接把需要的内存拨到相应的list上(发货到储藏室)。大功告成。
    • 如果内存池还有空余内存,但是不能完全满足需要,那就本着互助互惠的原则,能给多少就给多少并且告诉你我只能给你XX个了,剩下的你自己去想办法吧。仁至义尽。
    • 如果内存池的库存连一个单元的需求都满足不了了,面对的事情就比较罗嗦了:
      • 先看看内存池还有没有剩下的资源,如果有,虽然不能满足当前的申请需要(比如说是56bytes),但可以放到更小一些的“储藏室”里嘛(比如说24bytes)。既然来了,能拿走的就拿走,总比空手回去好……
      • 通过malloc向系统要资源(爸,我要你的钱)。因为是malloc,所以是在堆上(heap)找空闲的内存。既然是申请,自然就有以下两种结果:
        • malloc成功,总算抓住一根救命稻草。后面的工作就简单了,把堆上的内存扔到内存池,然后通过函数嵌套重新回到内存池里申请资源。
        • malloc失败(儿啊,家里也不宽裕了……)。外援是援不了了,这次真的是只能靠自己了。重新检查free list(储藏室)里的可用资源,不过这回是看看更大尺寸的free list里有没有可以用的(比如申请的是56bytes,这次回头看看有没有64bytes、72bytes等可以利用的内存块),如果有,就拿出一块,放回到内存池里。接下来就是通过函数嵌套重新回到内存池里去找资源了。说白了这种做法就是拆东墙补西墙@#¥%

          如果自己家里也没存货了(所有大的储藏室都没有空余的内存块可以返回到内存池里),还真是屋漏偏逢连夜雨啊……没有其他办法了,只好求助本家兄弟——一级配置器,反正如果它也搞不定,就抛出异常,谁爱管就管去吧,老子管不了也不想管了@#¥%
  4. __true_type与__false_type的使用。这个我会再专门写一篇学习笔记。【链接临时占位】

其实真正的STL配置器应该要更加复杂,因为侯捷在写这本书的时候为了省事就把多线程(书中称为多绪)的部分给跳过了。

posted on 2009-12-15 11:11 Justin.H 阅读(1104) 评论(0)  编辑 收藏 引用 所属分类: STL源码剖析 读书笔记

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理