類(lèi)結(jié)構(gòu)分析中怎燥，只看了大致看了一下cache的基本結(jié)構(gòu)，接下來(lái)我來(lái)深入了解一下cache_t在類(lèi)對(duì)象中的作用蜜暑。
cache_t的結(jié)構(gòu)
//簡(jiǎn)化后的cache_t
struct cache_t {
struct bucket_t *_buckets;
mask_t _mask;
mask_t _occupied;
}
//簡(jiǎn)化后的 bucket_t
//存儲(chǔ)著方法實(shí)現(xiàn)imp 和 緩存的key
struct bucket_t {
MethodCacheIMP _imp;
cache_key_t _key;
};
-
_buckets是一個(gè)緩存方法的散列表 -
_mask表示散列表長(zhǎng)度 - 1 -
_occupied表示已經(jīng)占用數(shù)量
cache_t中的函數(shù)分析
前面只看了cache_t的結(jié)構(gòu)铐姚，接下來(lái)看一下它提供有哪些函數(shù)
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));
};
- buckets()
這個(gè)方法的實(shí)現(xiàn)很簡(jiǎn)單就是_buckets對(duì)外的一個(gè)獲取函數(shù) - mask()
獲取緩存容量_mask - occupied()
獲取已經(jīng)占用的緩存?zhèn)€數(shù)_occupied - incrementOccupied()
增加緩存，_occupied自++
void cache_t::incrementOccupied()
{
_occupied++;
}
- setBucketsAndMask(,)
這個(gè)函數(shù)是設(shè)置一個(gè)新的Buckets
void cache_t::setBucketsAndMask(struct bucket_t *newBuckets, mask_t newMask)
{
_buckets = newBuckets; //設(shè)置新的_buckets
_mask = newMask; //設(shè)置新buckets的容量
_occupied = 0; //新buckets默認(rèn)占用為0
}
- initializeToEmpty()
初始化cache并設(shè)置為空
void cache_t::initializeToEmpty()
{
bzero(this, sizeof(*this)); //將cache 所有內(nèi)容都抹除 （將所有cache的空間都填充為'\0'）
_buckets = (bucket_t *)&_objc_empty_cache; //把_buckets指向cache empty的實(shí)現(xiàn)
}
_objc_empty_cache 為已經(jīng)提供了的空cache
struct objc_cache _objc_empty_cache =
{
0, // mask
0, // occupied
{ NULL } // buckets
};
- capacity()
//獲取buckets的容量
mask_t cache_t::capacity()
{
return mask() ? mask()+1 : 0;
}
capacity()經(jīng)過(guò)了出來(lái)肛捍，當(dāng)mask() == 0時(shí),返回0隐绵；當(dāng)mask() > 0時(shí)，返回mask() + 1
-
mask() == 0表示了buckets為空的狀態(tài) -
mask() > 0表示了buckets已經(jīng)存在緩存
那什么需要mask() + 1 ?
擴(kuò)容算法需要：expand()中的擴(kuò)容算法基本邏輯(最小分配的容量是4拙毫，當(dāng)容量存滿3/4時(shí)依许，進(jìn)行擴(kuò)容，擴(kuò)容當(dāng)前容量的兩倍)缀蹄；這樣最小容量4的 1/4就是1峭跳，這就是mask() + 1的原因。
isConstantEmptyCache()
判斷buckets是否為空canBeFreed()
isConstantEmptyCache()取反缺前，表示buckets不為空可以釋放bytesForCapacity()
expand()
void cache_t::expand()
{
//拿到原有的buckets容量
uint32_t oldCapacity = capacity();
/*
計(jì)算新buckets的容量
INIT_CACHE_SIZE = 4
如果 oldCapacity == 0蛀醉，則使用最小容量4
如果 oldCapacity > 0，則擴(kuò)容兩倍
*/
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);
}
- reallocate()
void cache_t::reallocate(mask_t oldCapacity, mask_t newCapacity)
{
bool freeOld = canBeFreed();
//拿到原有buckets
bucket_t *oldBuckets = buckets();
//創(chuàng)建一個(gè)新的buckets
bucket_t *newBuckets = allocateBuckets(newCapacity);
//設(shè)置新的buckets 和 mask（capacity - 1）
setBucketsAndMask(newBuckets, newCapacity - 1);
//抹掉原有buckets的數(shù)據(jù)
if (freeOld) {
cache_collect_free(oldBuckets, oldCapacity);
cache_collect(false);
}
}
- 為什么要?jiǎng)?chuàng)建新的
新的buckets來(lái)替換原有的buckets并抹掉原有的buckets的方案诡延，而不是在在原有buckets的基礎(chǔ)上進(jìn)行擴(kuò)容滞欠？
- 減少對(duì)方法快速查找流程的影響：調(diào)用
objc_msgSend時(shí)會(huì)觸發(fā)方法快速查找，如果進(jìn)行擴(kuò)容需要做一些讀寫(xiě)操作肆良，對(duì)快速查找影響比較大筛璧。- 對(duì)性能要求比較高：開(kāi)辟新的
buckets空間并抹掉原有buckets的消耗比在原有buckets上進(jìn)行擴(kuò)展更加高效
- find()
bucket_t * cache_t::find(cache_key_t k, id receiver)
{
bucket_t *b = buckets();
mask_t m = mask();
//計(jì)算 key 的 index
mask_t begin = cache_hash(k, m);
mask_t i = begin;
do {
//key = 0 ，表示i索引的bucket 還沒(méi)有緩存方法惹恃，返回bucket 中止查找
//key = k, 表示查詢成功夭谤，返回該bucket
if (b[i].key() == 0 || b[i].key() == k) {
return &b[i];
}
} while ((i = cache_next(i, m)) != begin); //當(dāng)出現(xiàn) 當(dāng)出現(xiàn)hash碰撞 cache_next 查找下一個(gè),直到回到begin
// hack
Class cls = (Class)((uintptr_t)this - offsetof(objc_class, cache));
cache_t::bad_cache(receiver, (SEL)k, cls);
}
- 通過(guò)
cache_key_t查找receiver中的bucket_t * - 如果碰到hash 沖突，則通過(guò)
cache_next偏移 -
cache_next把散列表的頭尾相連 （(i +1) % mask)
Hash
static inline mask_t cache_hash(cache_key_t key, mask_t mask)
{
//取余法計(jì)算索引
return (mask_t)(key & mask);
}
- key 就是 SEL
- 映射關(guān)系其實(shí)就是 key & mask = index
- mask = 散列表長(zhǎng)度 - 1
- 所以 index 一定是 <= mask
Hash表的原理： f(key) = index
Hash碰撞
兩個(gè)方法key & mask,是完全有可能計(jì)算出相同的結(jié)果巫糙，這里是通過(guò)這個(gè)函數(shù)處理
// do { } while ((i = cache_next(i, m)) != begin);
static inline mask_t cache_next(mask_t i, mask_t mask) {
return (i+1) & mask;
}
- 當(dāng)發(fā)生hash碰撞就查找下一個(gè)朗儒，
cache_next就提供了這種方法，每次 +1當(dāng) (i+1) = mask時(shí)参淹，因?yàn)橛?& mask所以索引i = 0又回到了散列表頭部醉锄。 - 這樣就會(huì)把散列表頭尾連接起來(lái)形成一個(gè)環(huán)。
什么時(shí)候存儲(chǔ)到cache中
objc_msgSend第一次發(fā)送消息會(huì)觸發(fā)方法查找浙值，找到方法后會(huì)調(diào)用cache_fill()方法把方法緩存到cache中
cache添加緩存的核心代碼
//方法查找后會(huì)調(diào)該方法來(lái)緩存方法
void cache_fill(Class cls, SEL sel, IMP imp, id receiver)
{
//這里省略了 lock的代碼
//填充cache
cache_fill_nolock(cls, sel, imp, receiver);
}
static void cache_fill_nolock(Class cls, SEL sel, IMP imp, id receiver)
{
// 如果能找到緩存就直接返回恳不，確保沒(méi)有其它線程把方法加入到cache中
if (cache_getImp(cls, sel)) return;
//獲取cls的cache
cache_t *cache = getCache(cls);
//換算出sel的key
cache_key_t key = getKey(sel);
//加上即將加入緩存的占用數(shù)
mask_t newOccupied = cache->occupied() + 1;
//拿到當(dāng)前buckets的容量
mask_t capacity = cache->capacity();
if (cache->isConstantEmptyCache()) {
/*
當(dāng)cache為空時(shí)，則重新分配空間开呐；
當(dāng) capacity == 0時(shí) 烟勋，使用最小的緩存空間 INIT_CACHE_SIZE = 4
*/
cache->reallocate(capacity, capacity ?: INIT_CACHE_SIZE);
}
else if (newOccupied <= capacity / 4 * 3) {
// Cache is less than 3/4 full. Use it as-is.
// 使用的空間 newOccupied < 3/4, 不需要擴(kuò)容
}
else {
// Cache is too full. Expand it.
// 使用的空間 newOccupied >= 3/4, 對(duì)cache進(jìn)行擴(kuò)容
cache->expand();
}
//find 使用hash找到可用的bucket指針
bucket_t *bucket = cache->find(key, receiver);
//判斷 bucket 是否可用，如果可用對(duì)齊occupied +1
if (bucket->key() == 0) cache->incrementOccupied();
//把緩存方法放到bucket中
bucket->set(key, imp);
}
總結(jié)
- mask = 散列表長(zhǎng)度 - 1
- 除了Empty筐付，最小的buckets大小是 4（為了支持?jǐn)U容算法需要）
- cache 擴(kuò)容策略是 >= 3/4,擴(kuò)容兩倍
- cache擴(kuò)容是創(chuàng)建一個(gè)更大的buckets卵惦，替換原有的buckets
- 替換策略為了讓方法快速查找更加安全穩(wěn)定和提高效率
