探究 cache_t (方法缓存)的本质

Class 内部中有个方法缓存 cache_t,用散列表来缓存调用过的方法,可以提高访问方法的速度。

一、cache_t结构

struct cache_t {
    struct bucket_t *_buckets;//数组
    mask_t _mask;//
    mask_t _occupied;

public:
    struct bucket_t *buckets();
    mask_t mask();
    mask_t occupied();
    void incrementOccupied();
    void setBucketsAndMask(struct bucket_t *newBuckets, mask_t newMask);
    void initializeToEmpty();

    mask_t capacity();
    bool isConstantEmptyCache();
    bool canBeFreed();

    static size_t bytesForCapacity(uint32_t cap);
    static struct bucket_t * endMarker(struct bucket_t *b, uint32_t cap);

    void expand();
    void reallocate(mask_t oldCapacity, mask_t newCapacity);
    struct bucket_t * find(cache_key_t key, id receiver);

    static void bad_cache(id receiver, SEL sel, Class isa) __attribute__((noreturn));
};

1.struct bucket_t *_buckets:数组

struct bucket_t {
private:
    cache_key_t _key;//@selector()
    IMP _imp;//函数地址

public:
    inline cache_key_t key() const { return _key; }
    inline IMP imp() const { return (IMP)_imp; }
    inline void setKey(cache_key_t newKey) { _key = newKey; }
    inline void setImp(IMP newImp) { _imp = newImp; }

    void set(cache_key_t newKey, IMP newImp);
};

1)cache_key_t _key:@selector(),方法名字
2)IMP _imp:函数地址
2.mask_t _mask:总槽位-1
3.mask_t _occupied:实际使用槽位

二、如何映射?


B3A8F221-2234-42E0-A4DD-AE019CBC7867.png
9ECD7C15-13D8-4933-89D4-B27519F81DF3.png
image.png

1)发现了映射关系是 key & mask = index
2)key 是什么?@selector(方法名)
3)mask 是什么?总槽位-1
4)key & mask = index: index 一定是<=_ mask
**Hash表的原理其实是:f(key) = index。通过一个函数 直接找到 index。

结构示意图:


image.png

Hash 表会有碰撞的问题(@selector(test) & _mask 和 @selector(test1) & _mask 值相同),看看苹果是如何解决的:


image.png
image.png

发现当发生碰撞的时候,索引会-1,查找下一个。

三、验证方法缓存

#ifndef MyClass_h
#define MyClass_h

typedef uint32_t mask_t;
typedef uintptr_t cache_key_t;
typedef unsigned long        uintptr_t;


struct bucket_t {
    char *_key;//@selector()
    IMP _imp;//函数地址
};

struct cache_t {
    struct bucket_t *_buckets;//数组
    mask_t _mask;//数组count - 1
    mask_t _occupied;//实际使用槽位
};


struct gl_objc_class{
    Class isa;
    Class superclass;
    struct cache_t cache;             // formerly cache pointer and vtable
    uintptr_t bits;
};

#endif /* MyClass_h */

没有模拟碰撞

image.png

现在默认的_mask 是 3 ,说明槽位是 4 个,实际占用槽位是3个。然后我们再多调用一个方法:

image.png

发现_occupied数量等于_mask时,再次加入一个缓存方法时,槽位的总量会变大,槽位会变为原来的2倍,源码中有写到:

void cache_t::expand()
{
    cacheUpdateLock.assertLocked();
    
    uint32_t oldCapacity = capacity();
    uint32_t newCapacity = oldCapacity ? oldCapacity*2 : INIT_CACHE_SIZE;

    if ((uint32_t)(mask_t)newCapacity != newCapacity) {
        // mask overflow - can't grow further
        // fixme this wastes one bit of mask
        newCapacity = oldCapacity;
    }

    reallocate(oldCapacity, newCapacity);
}

同时发现,扩容的时候将Hash 表里的内容进行了清空。

再看一个现象,Kid 是继承自 Person 的类

image.png

当子类没有方法时候,会调用父类的方法,并且将父类的方法缓存到了本类的cache 里。

总结:
1、每个Class 里会有一个cache 方法缓存。
2、cache 本质是一个 Hash表。
3、hash 函数式 f(@selector()) = index, @selector() & _mask。
4、槽位如果不够,_mask 会变换,变为原来的2倍,并且扩展槽位的时候,会清空数组里原有的缓存内容。
5、子类没有实现方法会调用父类的方法,会将父类方法加入到子类自己的cache 里。

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 206,126评论 6 481
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 88,254评论 2 382
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 152,445评论 0 341
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 55,185评论 1 278
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 64,178评论 5 371
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 48,970评论 1 284
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 38,276评论 3 399
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 36,927评论 0 259
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 43,400评论 1 300
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,883评论 2 323
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,997评论 1 333
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 33,646评论 4 322
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 39,213评论 3 307
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,204评论 0 19
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,423评论 1 260
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 45,423评论 2 352
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 42,722评论 2 345