The Big Bang Theory中的角色与诺贝尔奖

2011年3月10日

在twitter上看见好多人转发说TBBT里的几大男主角都恰好在诺贝尔奖里有重名的,于是我强迫性地去考据了一番,确实基本上都能对上:

剧中人物 历史获奖人物 获奖学科 获奖年份 获奖时所在机构 获奖原因


Sheldon Cooper


Sheldon Lee Glashow
物理 1979 Harvard University, Lyman Laboratory, Cambridge, MA, USA “for their contributions to the theory of the unified weak and electromagnetic interaction between elementary particles, including, inter alia, the prediction of the weak neutral current”


Leonard Hofstadter


Arthur Leonard Schawlow
物理 1981 Stanford University, Stanford, CA, USA “for their contribution to the development of laser spectroscopy”


Howard Wolowitz


Howard Martin Temin
生理医学 1975 University of Wisconsin, Madison, WI, USA “for their discoveries concerning the interaction between tumour viruses and the genetic material of the cell”
其实还有另一位Sir Howard Walter Florey同学,竟然也是得的医学奖,蛮好把howard设计成一个学医的哈,不过那样doctor大概就不够了。。。

至于raj同学呢,没有得过诺贝尔奖的叫这个的,但是有个得了图灵奖的(IT民工飘过,表示承认该奖项。。。),一并列出在这里。


Rajesh Koothrappali


Raj Reddy
图灵奖 1994 School of Computer Science, Carnegie Mellon University, Pittsburgh PA “For pioneering the design and construction of large scale artificial intelligence systems, demonstrating the practical importance and potential commercial impact of artificial intelligence technology.”

看来,几个主角的名字都能和大奖获得者的名字对上,尤其是那个Sheldon和那个Leonard,都是搞物理的。有这么巧吗,还是说主角们的名字确实是跟这几个得奖人有关呢?TBBT的编导们一直很学术,所以几个人物的名字是为了纪念实际获奖者也是很有可能的!于是查证之!查证的结果呢,上面的推测确实错了。。。。4位主角的名字确实与上面4位大学者没有关系。不过他们几位的名字也确实不是拍脑袋想出来的,还是有一定典故的。

Sheldon的Leonard的名字是位了纪念一位兼制作兼导演兼编剧兼演员的影视界的叫做Sheldon Leonard的前辈(哈哈,现在看来这是个神奇的名字),就是下面的这位同学:

至于他们二位的姓则确实是纪念的下面两位诺贝尔奖获得者(Cooper还挺有风度的,Hofstadter的笑容和leonard挺像~):

历史获奖人物 获奖学科 获奖年份 获奖时所在机构 获奖原因

Leon Neil Cooper
物理 1972 Brown University, Providence, RI, USA “for their jointly developed theory of superconductivity, usually called the BCS-theory”

Robert Hofstadter
物理 1962 Stanford University, Stanford, CA, USA “for his pioneering studies of electron scattering in atomic nuclei and for his thereby achieved discoveries concerning the structure of the nucleons”

Howard同学的名字的由来就没这么伟大了,它只是TBBT的制作人Bill Prady认识的一个程序员而已,不过这还算有来例,Raj的名字的由来我就完全没查到了,谁要是知道可以在此留言告诉我,嗯。

PS. 主角名字的来例参考自他们的wiki页面,点击电视人物的名字可以打开。另外如果你对哪位获奖者的详细情况感兴趣,也可以点他们的名字看看他们在诺贝尔奖官网上的介绍页面,不过我猜你需要一些“技术手段”才能打开。。。你懂的。。。

杂记, 文娱

美剧中神奇的中餐外卖盒子

2011年2月7日

过年了比较没事做,于是重头开始看friends,同时顺便对米国中餐的外卖盒产品了浓厚的兴趣。

这是The Big Bang Theory最经典的剧照:

这是我在friends中截的一个屏:

腾讯十二周年出了个挺感人的广告,被大家各种转载,其中主角留学美国期间做chinese food送餐员时撞车摔倒时,撒了一地的是这些东西:

Friends是上个世纪的美剧了,至今都17年了吧;TBBT是当今最新的美剧;腾讯那个镜头的年代设定则是本世纪初,很明显,他们共同涉及到的是这个东西:

按说17年是个不小的时间跨度了,这么多年中国的餐盒也出现过各种各样的了。然则这么多年,全美国,各种中餐盒馆,都在用这种盒子装外卖(以及打包带走时用的包装),完全相同的形状,连图案都一样,也太神奇了吧。还有,那个阁楼状的图案,究竟是个啥呀是个啥呀。。。于是闲得蛋疼的我开始各种google,竟然还是找到了不少信息的。

首先呢,这个盒子是有个名字的,叫Oyster Pail。这个名字看起来和中餐一点关系都没有哈,说明它本来不是干这个的呗:在20世纪初的时候,美国的牡蛎非常盛产,而且很便宜,所以各种流行。多数人喜欢把牡蛎买回家做着吃,然而它的壳比较难以处理,所以最好是卖家把壳剥掉,买家自己把肉带回家去做,于是就需要一种干净方便的容器来装剥下来的肉。当时不少人都尝试设计这种容器,还发了patent,最后流行下来的则是一位F.W.Wilcox同学发明的oyster pail。这是他1894年申请专利时的草图:

然而,后来到了20世纪中叶,随着过度打捞,牡蛎越来越少,越来越贵,于是大量的oyster pail就用不上了。不过呢,二战之后,人们越来越喜欢从餐馆叫外卖了,于是用不掉的oyster pail就挺顺理成章地用来装外卖食品了。又由于中餐挺受欢迎的,成了oyster pail的最主要使用者,并且这个传统一直流传到了今天。

然后再说说那个“阁楼”的图案吧,这就要提到一个NB的公司,叫做fold-pak,这是一家专门做食品包装盒的公司。在做中餐盒的时候呢,公司决定在盒子上画点icon,至于画什么呢,大家想的是个能体现”chineseness”的图案,它要反映中国的文化和中国的饮食,于是得出了一个看起来没啥逻辑的结论:“Pagoda it is!”。。。看来那个所谓的阁楼suppose是个宝塔。。。然后由于这个fold-pak公司特别NB,以至于它统治了全美国三分之二的oyster pail的生产(上面friends剧照里phoebe里拿的那个上就有foldpak的logo),所以这个pagoda的图案就成了中餐外卖的代表之物啦。似乎也有别的分支图案,比如一个圆的代表fortune的版本(例如上面TBBT剧照里的那种)或者画一个龙的版本,不过pagoda的应该是绝对主流了,大概这些就代表了美国人眼中的”chineseness”吧。。。

References:

  1. http://en.wikipedia.org/wiki/Oyster_pail
  2. In the Archives: Golden Age of Oysters
  3. The fortune cookie chronicles: adventures in the world of Chinese food (还真是研究啥的都有哈,这书里专门有一章讲外卖的,而且这个作者还去哈佛做过演讲,演讲的poster上必然也有oyster pail的图案啦)

杂记

我果然是人脸识别弱智啊

2010年11月16日

长期以来,每次看电影,尤其是外国电影,都会分不清电影里的人物哪个对哪个,这种状态少则持续半小时,多则大半部影片的时间都在迷惑。如果演员是已经熟知的演员,比如《盗梦空间》,那我至少还分得出谁是主角,如果像前几天看《西风烈》或者《Social Network》时,主角的演员我都认不出(虽说演员应该也有名吧,但是我不认识)前面1/3的时间我基本都在不停地问旁边的人,这是谁这是谁。

反映有类似情况的还有yangshuli和forcey同学,难道搞IT的不认人脸的概率会高?

今天做了个不错的测试,好像是哈佛大学的某某某研究中心做的,http://www.faceblind.org/facetests/fgcfmt/fgcfmt_intro.php ,有兴趣的可以做做。下面是我的结果,基本宣判了我是face recognition difficulty患者了。。。

Out of 72 faces, you correctly identified 41.
In other words, you got 57% correct.


On our previous version of this test, the average person with normal face recognition was able to recognize about 80% of the faces. If you correctly identified less than 65% of the faces, this may indicate face recognition difficulties.

杂记

猜猜这几个韩国字的意思吧

2010年4月26日

从去第一天到首尔,就在以地铁站为首的各种大街小巷见到这个标识,一直在猜它的含义,但是被各种遇到的反例否决。直到几天后离开首尔才突然想到一个解释,连自己都觉得靠谱,并且后来看到一个多国文字版本的该标识,得到confirm。

各位有闲的同学在此留言猜猜它的意思吧,看谁最先猜对,嗯。会韩语的某某某某就可以不参加了。

猜猜这是啥意思。。

杂记

韩国游记-总结篇

2010年4月19日

韩国旅游归来一周多了,还没写过游记yet,今天刚刚整理完照片,先写点总结的东西吧,以后闲下来的时候再写详细的。

一、国家篇

韩国的物价,可以大致认为是中国的两倍吧。这包括了吃饭、地铁、出租、旅馆、自动售货机里的饮料,甚至连机场给行李打包的价格也是2倍的关系。

韩国国民素质挺高的,而且很有礼貌。比如地铁上被让了座会鞠躬答谢,我们爬山的时候几乎所有迎面经过的人都会说你好(然后我们不知道回答啥。。),爬山时吃的泡面等垃圾会装在袋子里亲自带下山。印象最深的是他们的司机,看到你想过马路,离很远就会停下来,以至于是我多次怀疑他是在给我让路还是自己有事停车了,直到我走过马路他才前进我才确定那是在给我让路。

韩国服务业也很发达,首先是餐饮、公共交通、机场、旅游景区等的从业人员态度很好,连济州岛开长途车的农民伯伯态度也很nice(想想917的司机之类的。。。)。其次是公共场所的建设比较专业,特别是跟交通有关的,指示清晰明确,中日英文标志也比较全面(至少首尔如此,其它地方稍差)。我回到北京仔细观察了一下机场大巴和地铁,如果我是个不认识中文的外国人的话,还是挺困难的。

韩国的MM pp率挺高,她们的服装有个很共同的特点,绝大多数人穿的直接是连裤袜,下面就是帆布鞋或高跟鞋之类的,穿牛仔裤的都很少,就算穿了也是很瘦的那种,orz

二、城市篇

首尔:是个很大的城市,韩国人口的1/4都在首尔。乍看没有北京发达,至少没有像国贸那种繁华的景象。不过市政建设感觉比北京好,比如公交、购物等。首尔没有很大很宽的马路,我走过的双向6车道的已经算宽的了,不过人家肯定没有北京堵,就像有人说的那样,马路越宽越堵车,对北京不抱希望了……。首尔也算个山城,各地高高低低的,可能没重庆那么山,但是从住处窗口向外望,各种房子错落的景致不错。

釜山:釜山就比首尔小很多了,也破一些。只在釜山呆了半天,没啥评论可给出。不过可以确定的是,如果拿首尔跟北京做类比,肯定不能拿釜山跟上海做类比,呵呵。

济州:济州岛是个生活安逸的小岛,呵呵。不过这的人英文水平很低,公交、出租等的司机完全不会英文,连4花酒店的大堂都几乎交流不能!所以感觉这里还不太适合自助游……。不过另一个角度说,这边车很少,所以应该租个车玩,这样就避免了公交或打车的交流困难了。

三、交通篇

这次韩国之行把能坐的交通工具坐了个遍,哈哈。

飞机:此次北京到首尔往返及首尔到济州都是韩亚航空的飞机,服务还不错。那边整体航空业很不错,比如办理值机,是我平生首次被主动问有没有星联的会员卡,感动啊。想到国航值机的时候一般就是把不问要窗还是过道,也不问会员卡号,直接就把登机牌打了,于是只得让伊补登卡号,而且也不一定补得上……。仁川机场承诺的是起飞前5分钟关闭登机口,效率很高啊,北京T1的南航承诺20分钟登机已经做为亮点宣传了。ICN有免费的wifi,还有500Won/10min的台式机(还能用USB),还有专门的中文值机柜台,难怪人家多年被评为世界服务最佳机场了。对了,还有海关,在韩国海关通过很快,回到北京的时候到海关排队排了30分钟 ><

火车:我坐了从釜山到首尔的高铁——KTX,买的头等座,呵呵。时速上看,最高时速并没有CRH高,也就刚刚300kM/h。不过他们车站和车本身还是挺好的。

地铁:首尔的地铁相当发达,覆盖面很大,在首尔期间的行空完全靠的地铁。站内指标很清楚,颜色、数字符号很统一。车内提示也比较充分,有很多途径知道当前是啥站,下一站是哪里,哪边开门等信息。首尔地铁很大——车站很多,标准配置是3层,有些更大,里面商店也很多(这点上海就比比较好);车也很大,宽且长,单车的运量应该是北京一辆车的2倍以上。

船:从济州坐的船到釜山,住的10人一间的舱,没啥亮点。

四、设备篇

GPS:我的水货E66手机自带了GPS,但是完全不可用,信号强度一直为0. 后来改用外置的蓝牙GPS,还是不错的。我后来会发使用报告,嗯。

相机:出门 玩,用单反的话,有个背包或者腰包还是必不可少的,否则无论是手提还是挂脖子上都很痛苦。

手机:韩国的手机完全是CDMA的,不过我也没带我的XV6700过去,反正漫游也太贵。直接在机场租的手机,仿佛是韩国最大的运营商,叫SHOW,租金一天3000KRW,往中国打国际长途的话,大约一分钟7RMB左右。

杂记

Consistent Hashing算法

2010年3月12日

网络应用中经常会用到缓存机制,例如memcached。当需要缓存的数据量较大,一个memcached实例存不下的时候,就需要一定的策略将不同的对象分配到不同的memcached实例上。比较常见的方法是对对象的key值做hash,再求余,根据余数分配到不同的cache中。这种简单的方法的扩展性相当差一些,主要体现在cache结点的增加和删除上。假设本来有a个cache结点,因数据量扩大而扩大至b个结点,可以计算得到有 min(a, b) / [a, b]比例的对象的余数没有发生变化,也就是说这些对象仍可以存在于原来的cache结点上。如果每次cache结点数量的扩展都是翻番的,即b=2a,则有50%的对象的缓存失效。但是如果是原有5个结点,增加了2个结点,则会有86%的对象缓存失效,这将对系统的性能造成较大冲击。

所以出现了consistent hashing算法,它可以减少节点变动带来的缓存失效。consistent hashing的实现方法是把缓存对像的key和cache结点本身,分别用一定的算法映射到一个相同的hash空间上,例如一个32位的整数。然后将这个空间想像成一个圆,然后将各key及各cache结点都画在这个圆上。对于每个key,它顺时针碰到的最近的一个cache结点就是它应该存在的地方。如下图所示:

为了防止由于对cache结点的hash算法结果的不均匀,导致cache结点在圆环上的分布过于不均,使得每个cache的负载不同,consistent hashing算法还引用了virtual node的概念。也就是在对cache结点计算hash的时候,通过对hash过程的微调,使每个结点都算出很多(例如200个)hash值,这些值以virtual node的形式添加到环上,所有属于这些virtual node的缓存对象都映射到该实际结点上,这样就基本能保持每个cache结点在hash空间中cover住基本同样多的对象了。

这样,在保证结点基本均匀分布的情况下,将cache结点数从a提高到b,只有(b-a)/b比例的对象缓存失效。对于上文提到的从5个结点添加2个结点的情况,缓存失效率为28%,相比传统算法的86%,性能提高了不少。

不少新的memcached client都已经支持这种算法,如libketama等。但是不同语言的客户端的实现依赖于该语言对对象的serialization实现,可能分配的结果也不一致。我最近做的项目需要同时从Java和C客户端访问同一组cache server,所以我还是自己实现了一个简单的consistent hashing机制。其中,算法中的环结构对应一个SortedMap,每个cache结点均为该树中的一个点,某key顺时针碰到的第一个结点的问题转化成排序树上大于该key的最小结点。(无关代码已略去)

public class ConsistentHashingPartitionStrategy <TTarget, TKey> {

    public static final int                    DEFAULT_REPLICA = 64;

    private final SortedMap <Integer, TTarget> circle          = new TreeMap <Integer, TTarget> ();

    /**
     * Number of virtual nodes we create for a target
     */
    private final int                          replica;

    public void addTarget (TTarget target) {

        for (int i = 0; i < replica; i++) {
            circle.put (this.getTargetHashingFunction ().hash (target.toString() + i), target);
        }
    }

    public void removeTarget (TTarget target) {

        for (int i = 0; i < replica; i++) {
            circle.remove (this.getTargetHashingFunction ().hash (target.toString() + i));
        }
    }

    /**
     * Find the nearest target next to the key hash on the circle.
     */
    public TTarget getTargetForKey (TKey key) {

        if (circle.isEmpty ()) {
            return null;
        }

        int hash = getKeyHashingFunction ().hash (key);

        if (!circle.containsKey (hash)) {
            SortedMap <Integer, TTarget> tailMap = circle.tailMap (hash);
            hash = tailMap.isEmpty () ? circle.firstKey () : tailMap.firstKey ();
        }

        return circle.get (hash);
    }
}

编程 ,

办了一张光大银行万里行卡

2010年2月19日

水木mywallet版传说中的搬钱工具,没有年费,没有各种异地的费用,没有各种跨行的费用。

北京的光大办不了这个卡,版上的人们基本上都是来天津办的,特别是科技支行,所以趁过年回家办了一张。先打电话给家门口的白堤路支行说不能办,于是也是去的科技支行办的,不需要存款就能办,传中的0开,不错。

杂记

glibc中malloc()的空间overhead

2010年2月13日

在linux下调用malloc()分配内存的时候,实际占用的内存与请求的内存尺寸的关系是什么呢,这个需要研究一下glibc中malloc()的实现。现在常见linux发行版中带的glibc中采用的都是Doug Lea的实现,下面的分析取自他的2.8.4版本的malloc.c

glibc对内存的管理是以chunk为单位的,未分配的chunk之间用双向链表连接成一个环,遍历的时候用指针遍历,已分配的chunk在其首部有chunk的大小,并以此字节数做遍历。每个chunk的首部要放置一个叫做malloc_chunk的struct,故每个chunk的大小至少是这个struct的大小,如果分配的空间或者free的空间大于这个大小,则struct的后面是raw的数据或者是空白空间。chunk的定义如下所示:

struct malloc_chunk {
  size_t               prev_foot;  /* Size of previous chunk (if free).  */
  size_t               head;       /* Size and inuse bits. */
  struct malloc_chunk* fd;         /* double links -- used only if free. */
  struct malloc_chunk* bk;
};

对于已分配的和未分配的chunk,使用的都这个结构,只是用到的成员不一样。对于这两种情况,head变量存放的都是本chunk的尺寸,由于chunk的大小有对齐的规定(见下文),所以head变量的最后三位一定是0的,用不到,所以这三位被做为三个标志位使用,其实本文涉及的是最低位P,它表示当前chunk紧跟着的上一个chunk是不是一个free的chunk,以及倒数第三位A,它表明当前chunk是否被使用中。如果上一个chunk是free的,prev_foot变量就是有用的,它表明了上一个chunk的尺寸,如果上一个chunk也是分配了的,prev_foot变量就是不使用的(在内存上直接和前一个chunk重叠起来,见下文的图示)。如果当前chunk是个空chunk,那么fd和bk两个指针就会分别指向空闲chunk环中的上一个和下一个,如果当前chunk已经分配了,fd和bk所在的内存存放的就是用户实际申请到的数据空间了。

Doug Lea在malloc.c的源代码中画了图来描述实际分配中的内存使用情况,首先是对于已分配的chunk:

chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        | Size of previous chunk (if P = 0)                             |
        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        | Size of this chunk                                     |1| |P|+
  mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        |                                                               |
        +-                                                             -+
        |                                                               |
        +-                                                             -+
        |                                                               :
        +-      size - sizeof(size_t) available payload bytes          -+
        :                                                               |
chunk-> +-                                                             -+
        |                                                               |
        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        | Size of next chunk (may or may not be in use)              |1|+
  mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

图中,chunk箭头所指的位置是malloc_chunk struct的起始位置,mem箭头所指的位置是malloc()等函数返回给用户的指针的位置,也就是实际数据的位置,mem和chunk箭头之前的2*size_t字节的空间可认为是overhead。但是注意第二个chunk,它的上一个chunk也就是第一个chunk是已经分配的,所以它的head字段的P标志位为1,并且它的prev_foot字段其实是不存在的,因为它和第一个chunk的payload数据的最后size_t个字节是重叠的。如果第二个chunk也被分配了的话,它的overhead就是第二个mem箭头上面的那一条当前chunk尺寸(也就是head变量)的那size_t字节的空间。

对于空闲的chuck是这样的:

chunk-> +-                                                             -+
        | User payload (must be in use, or we would have merged!)       |
        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        | Size of this chunk                                     |0| |P|+
  mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        | Next pointer                                                  |
        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        | Prev pointer                                                  |
        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        |                                                               :
        +-      size - sizeof(struct chunk) unused bytes               -+
        :                                                               |
chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        | Size of this chunk                                            |
        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        | Size of next chunk (must be in use, or we would have merged|0|+
  mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        |                                                               :
        +- User payload                                                -+
        :                                                               |
        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

如图中注释所说,两个free的chunk如果是相邻的,会被合并,所以不会存在两个free的chunk相连的情况。(对于较小的刚刚被free的chunk,glibc中存在一种调度算法,把这种小free chunk加入一个叫fastbins的队列管理,这时尽管被free,它们的A标志位会保持为1,因此就算相邻也不会被合并)。

注意图中的第二个chunk,它是一个被分配了的chunk,它的第一个字段prev_foot表示的是第一个free的chunk的大小。其实这个prev_foot变量也是位于上一个chunk的尾部。真正属于第二个chunk的空间还是从“size of the next chunk”开始的,它距离用户数据的空间mem是size_t字节。

综合上面两个例子可以看出,对于一个已分配了的chunk,如果它的上一个chunk也是分配了的,它的prev_foot就是完全被前一个chunk覆盖的;如果它的上一个chunk是未分配的,它的prev_foot存的是该空间chunk的大小,且prev_foot变量位于前一个chunk的最后size_t个字节。这样看来,已分配的chunk的第一个成员prev_foot总是位于别的chunk内的,所以overhead就是head一个变量的大小,即site_t字节。这样一种chunk之间重叠的设计,使得prev_foot与其说是当前chunk的第一个变量,不如说是上一个chunk结尾尺寸标记(从它的名字foot就可以看出这一点)。这使得对于一个空闲chunk来说,其头(自身的header变量)和尾(下一个chunk的prev_foot)都是此空闲chunk的尺寸,这使得从正向两个方向按字节数遍历都很容易,是个不错的设计。

除了上面讨论的overhead以外,chunk的存储还涉及对齐的问题,glibc中规定chunk的以size_t的两倍大小对齐。与此相关的一些代码如下:

#define MALLOC_ALIGNMENT       (2 * SIZE_SZ)  //在我下载的malloc.c中不是这样定义的,而是分情况讨论的
#define CHUNK_ALIGN_MASK    (MALLOC_ALIGNMENT - SIZE_T_ONE)

#define CHUNK_OVERHEAD      (SIZE_T_SIZE)

#define MCHUNK_SIZE         (sizeof(mchunk))

/* The smallest size we can malloc is an aligned minimal chunk */
#define MIN_CHUNK_SIZE\
  ((MCHUNK_SIZE + CHUNK_ALIGN_MASK) & ~CHUNK_ALIGN_MASK)

/* pad request bytes into a usable size */
#define pad_request(req) \
   (((req) + CHUNK_OVERHEAD + CHUNK_ALIGN_MASK) & ~CHUNK_ALIGN_MASK)

/* pad request, checking for minimum (but not maximum) */
#define request2size(req) \
  (((req) < MIN_REQUEST)? MIN_CHUNK_SIZE : pad_request(req))

request2size这个宏汇合了上文的各个因素,给出一个要申请的空间大小,它返回的就是实际分配的内存大小。只申请1个字节的时候,实际至少也要分配malloc_chunk的大小那么多空间,当申请的字节更多直到一个malloc_chunk的空间放不下后,实际空间会以2倍的size_t为步长增长。

这里写了一个程序验证:

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>

#define N 1

int main() {
    int i = 0;
    char *p;
    char *p0, *p1;

    size_t *psize;

    for (i = 0; i < 1000000; i++) {
        p = (char*) malloc(N);
        if (i == 0) p0 = p;
        if (i == 1) p1 = p;
    }
    printf("%d\n", p1 - p0);    //看两个chunk的mem指针相差多少

    psize = (size_t*)(p1 - sizeof(size_t));
    printf("%d\n", (*psize) & ~7);    //看head变量的值,& ~7的作用是把后三个标志位过滤掉

    getchar();
    return 0;

}

在32系统下,size_t和指针均为4字节,当N为1至12时,程序的内存占用为16M,当N为13时,程序占用内存涨到24M。
在64系统下,size_t和指针均为8字节,当N为1至24时,程序的内存占用为32M,当N为25时,程序占用内存涨到48M。

上述程序在centos 5.3下,gcc 4.1.2下测试通过。另外,由于C++的new操作底层调用的也是malloc,所以上述讨论对new同样适用。

最后附上本文主要的参考材料,一个讲述glibc的pdf和malloc.c源代码。

Understanding the heap by breaking it
malloc.c

编程

c语言中struct的内存对齐

2010年2月8日

为了让CPU能够更舒服地访问到变量,struct中的各成员变量的存储地址有一套对齐的机制。这个机制概括起来有两点:第一,每个成员变量的首地址,必须是它的类型的对齐值的整数倍,如果不满足,它与前一个成员变量之间要填充(padding)一些无意义的字节来满足;第二,整个struct的大小,必须是该struct中所有成员的类型中对齐值最大者的整数倍,如果不满足,在最后一个成员后面填充。

各种类型的变量的align值如下,参考的是wikipedia的页面:Data structure alignment

The following typical alignments are valid for compilers from MicrosoftBorland, and GNU when compiling for 32-bit x86:

  • char (one byte) will be 1-byte aligned.
  • short (two bytes) will be 2-byte aligned.
  • An int (four bytes) will be 4-byte aligned.
  • float (four bytes) will be 4-byte aligned.
  • double (eight bytes) will be 8-byte aligned on Windows and 4-byte aligned on Linux.
  • long double (twelve bytes) will be 4-byte aligned on Linux.
  • Any pointer (four bytes) will be 4-byte aligned on Linux. (eg: char*, int*)

The only notable difference in alignment for a 64-bit linux system when compared to a 32 bit is:

  • double (eight bytes) will be 8-byte aligned.
  • long double (Sixteen bytes) will be 16-byte aligned.
  • Any pointer (eight bytes) will be 8-byte aligned.

这里写了个程序来验证这些事:

#include <stdio.h>

struct s {
    char a;
    short b;
    char c;
    double d;
    char e;
};

int main() {

    struct s s1;

    printf("%d, %d, %d, %d, %d\n",
        (char*)(&s1.a) - (char*)(&s1),
        (char*)(&s1.b) - (char*)(&s1),
        (char*)(&s1.c) - (char*)(&s1),
        (char*)(&s1.d) - (char*)(&s1),
        (char*)(&s1.e) - (char*)(&s1));
    printf("%d\n", sizeof(struct s));

    return 0;
}

在64位linux下面运行这段代码的结果是:

0, 2, 4, 8, 16
24

由于对齐机制的存在,实际上上面的struct在内存中是长这个样子的,共计24个字节:

struct s {
    char a;             //在地址为0的位置
    char padding1[1];   //由于下面一个元素是short,对齐字节数为2的位数,需要补1字节
    short b;            //对齐到了地址为2的位置
    char c;             //在地址为4的位置
    char padding2[3];   //由于下面一个元素是double,对齐字节数为8的倍数,需要补3字节
    double d;           //对齐到了地址为8的位置
    char e;             //在地址为16的位置
    char padding3[7];   //整个struct的大小需要是对齐数最大者,也就是double的8字节的整数倍
};

如果是在32位的linux下跑上面的程序,由于double的长度还是8字节,但是对齐是4字节的了,所以前面几个成员的位置不变,而最后的padding只需要补3个字节就可以了,所以输出的结果是0, 2, 4, 8, 16及20.

对于windows,其32位和64位下double都是8字节对齐的,所以在32位和64位下跑这个程序结果都是0, 2, 4, 8, 16及24.

最后,整个struct的大小的要求是对齐值最大者的整数倍,没有什么默认的4或者8的倍数一说。如果把上面程序中的a,b,c,d,e的类型全变成char,那么最后的他们的地址会是0,1,2,3,4,整个struct的大小 sizeof(struct s)的值是5,没有任何padding发生。

以上程序实验的环境在64位centos x64上的gcc 4.1.2(32位结果加-m32参数)及Visual Studio 2008上得出。

编程

Facebook神作: HipHop for PHP

2010年2月4日

PHP很容易开发,它的弱类型的变量和近乎万能的array,可以节约很多开发的时间,当然这也导致它的运行效率不高。有一些扩展例如APC 和 eAccelerator 致力于缓存PHP编译成的opcode来提高速度,不过facebook花了一年半的时间做了更彻底的事情,他们不想容忍连$a=1; $b=1; $c = $a + $b这样简单的事情都要去判断zval的类型,于是他们写出了HipHop for PHP——直接把PHP往C++上转换。

主创人员的blog文章:HipHop for PHP: Move Fast
一个关于HipHop for PHP的talk的视频:http://www.ustream.tv/recorded/4409735

PHP的语法大致被分为两类,一种是传统的,几乎可以和C++直接对应的语法,一种是所谓的”magic”语法。magic语法包括诸如:

$$$$$foo = 1;(动态变量)
$$$$foo();  (动态函数)
extract(array(‘a’ => 1, ‘b’ => 2));

从上面的视频可以看到,动态变量,动态函数乃至extract()都被支持了,不过他们没说是怎么实现的,好奇中。而且对于下面这种code,会是如何编译的呢,a到底要声明为一个int还是查表呢,或者莫非只要scope中有extract()的存在一切变量都要查表?

$a = 1;
$arr['a'] = “2″;
extract($arr);
$b = $a + 1;

另外还有明确说了不支持的,包括eval()的功能,还有is_function_exists()这样的运行时的判断,到是不太用得着。另外在视频中的Q&A环节,看意思是PHP的已有extension都要rewrite一下,感觉这个的代价是不是太大了?

还不知道啥时能用上这个技术,facebook说他们已经有90%的服务已经在用了,用了6个月部署。不清楚它的开源度如何,其它人能不能随便用。HTTP Server方面,facebook方面用了一个自已写的http server以及non-multithreading的apache 1.3,multithreading的暂时还不可用的样子,所以说短期内至少未名是不能用上这个技术的。

ps. 这个技术如果真的发达了,是不是广大C++民工身价会小跌呢。。。

编程