[toc]
散列表
哈希表
散列表效率比数组高, 以 空间换时间
按位与算法
一个数值a 按位与 另一个数值b, 得出的结果c ≤ min(a, b); 即 a & b ≤ min(a, b);
预先设定mask, 值为散列表长度-1;
那么, key & mask, 得到的结果 idx ≤ mask, idx 就作为该 key 在散列表中的索引。
求余算法也能保证 idx ≤ mask
方法缓存
介绍
struct objc_class 有一个成员 cache_t cache, 用来做方法缓存; 用散列表来缓存曾经调用过的方法, 可以提高方法的查找速度。
关系图
image
以 selector 作为key, 按位与 selector&mask, 得到idx, 存储到散列表中
cache_t
struct cache_t {
#if CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_OUTLINED
explicit_atomic<struct bucket_t *> _buckets; // 散列表
explicit_atomic<mask_t> _mask; // 掩码, 散列表的长度 -1
#elif CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_HIGH_16
explicit_atomic<uintptr_t> _maskAndBuckets;
mask_t _mask_unused;
// How much the mask is shifted by.
static constexpr uintptr_t maskShift = 48;
// Additional bits after the mask which must be zero. msgSend
// takes advantage of these additional bits to construct the value
// `mask << 4` from `_maskAndBuckets` in a single instruction.
static constexpr uintptr_t maskZeroBits = 4;
// The largest mask value we can store.
static constexpr uintptr_t maxMask = ((uintptr_t)1 << (64 - maskShift)) - 1;
// The mask applied to `_maskAndBuckets` to retrieve the buckets pointer.
static constexpr uintptr_t bucketsMask = ((uintptr_t)1 << (maskShift - maskZeroBits)) - 1;
// Ensure we have enough bits for the buckets pointer.
static_assert(bucketsMask >= MACH_VM_MAX_ADDRESS, "Bucket field doesn't have enough bits for arbitrary pointers.");
#elif CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_LOW_4
// _maskAndBuckets stores the mask shift in the low 4 bits, and
// the buckets pointer in the remainder of the value. The mask
// shift is the value where (0xffff >> shift) produces the correct
// mask. This is equal to 16 - log2(cache_size).
explicit_atomic<uintptr_t> _maskAndBuckets;
mask_t _mask_unused;
static constexpr uintptr_t maskBits = 4;
static constexpr uintptr_t maskMask = (1 << maskBits) - 1;
static constexpr uintptr_t bucketsMask = ~maskMask;
#else
#error Unknown cache mask storage type.
#endif
#if __LP64__
uint16_t _flags;
#endif
uint16_t _occupied; // 已缓存的方法数量
public:
static bucket_t *emptyBuckets();
struct bucket_t *buckets();
mask_t mask();
mask_t occupied();
void incrementOccupied();
void setBucketsAndMask(struct bucket_t *newBuckets, mask_t newMask);
void initializeToEmpty();
unsigned capacity();
bool isConstantEmptyCache();
bool canBeFreed();
#if __LP64__
bool getBit(uint16_t flags) const {
return _flags & flags;
}
void setBit(uint16_t set) {
__c11_atomic_fetch_or((_Atomic(uint16_t) *)&_flags, set, __ATOMIC_RELAXED);
}
void clearBit(uint16_t clear) {
__c11_atomic_fetch_and((_Atomic(uint16_t) *)&_flags, ~clear, __ATOMIC_RELAXED);
}
#endif
#if FAST_CACHE_ALLOC_MASK
bool hasFastInstanceSize(size_t extra) const
{
if (__builtin_constant_p(extra) && extra == 0) {
return _flags & FAST_CACHE_ALLOC_MASK16;
}
return _flags & FAST_CACHE_ALLOC_MASK;
}
size_t fastInstanceSize(size_t extra) const
{
ASSERT(hasFastInstanceSize(extra));
if (__builtin_constant_p(extra) && extra == 0) {
return _flags & FAST_CACHE_ALLOC_MASK16;
} else {
size_t size = _flags & FAST_CACHE_ALLOC_MASK;
// remove the FAST_CACHE_ALLOC_DELTA16 that was added
// by setFastInstanceSize
return align16(size + extra - FAST_CACHE_ALLOC_DELTA16);
}
}
void setFastInstanceSize(size_t newSize)
{
// Set during realization or construction only. No locking needed.
uint16_t newBits = _flags & ~FAST_CACHE_ALLOC_MASK;
uint16_t sizeBits;
// Adding FAST_CACHE_ALLOC_DELTA16 allows for FAST_CACHE_ALLOC_MASK16
// to yield the proper 16byte aligned allocation size with a single mask
sizeBits = word_align(newSize) + FAST_CACHE_ALLOC_DELTA16;
sizeBits &= FAST_CACHE_ALLOC_MASK;
if (newSize <= sizeBits) {
newBits |= sizeBits;
}
_flags = newBits;
}
#else
bool hasFastInstanceSize(size_t extra) const {
return false;
}
size_t fastInstanceSize(size_t extra) const {
abort();
}
void setFastInstanceSize(size_t extra) {
// nothing
}
#endif
static size_t bytesForCapacity(uint32_t cap);
static struct bucket_t * endMarker(struct bucket_t *b, uint32_t cap);
void reallocate(mask_t oldCapacity, mask_t newCapacity, bool freeOld);
void insert(Class cls, SEL sel, IMP imp, id receiver);
static void bad_cache(id receiver, SEL sel, Class isa) __attribute__((noreturn, cold));
};
bucket_t
struct bucket_t {
private:
// IMP-first is better for arm64e ptrauth and no worse for arm64.
// SEL-first is better for armv7* and i386 and x86_64.
#if __arm64__
explicit_atomic<uintptr_t> _imp; // 方法实现
explicit_atomic<SEL> _sel; // sel作为key
#else
explicit_atomic<SEL> _sel;
explicit_atomic<uintptr_t> _imp;
#endif
// Compute the ptrauth signing modifier from &_imp, newSel, and cls.
uintptr_t modifierForSEL(SEL newSel, Class cls) const {
return (uintptr_t)&_imp ^ (uintptr_t)newSel ^ (uintptr_t)cls;
}
// Sign newImp, with &_imp, newSel, and cls as modifiers.
uintptr_t encodeImp(IMP newImp, SEL newSel, Class cls) const {
if (!newImp) return 0;
#if CACHE_IMP_ENCODING == CACHE_IMP_ENCODING_PTRAUTH
return (uintptr_t)
ptrauth_auth_and_resign(newImp,
ptrauth_key_function_pointer, 0,
ptrauth_key_process_dependent_code,
modifierForSEL(newSel, cls));
#elif CACHE_IMP_ENCODING == CACHE_IMP_ENCODING_ISA_XOR
return (uintptr_t)newImp ^ (uintptr_t)cls;
#elif CACHE_IMP_ENCODING == CACHE_IMP_ENCODING_NONE
return (uintptr_t)newImp;
#else
#error Unknown method cache IMP encoding.
#endif
}
public:
inline SEL sel() const { return _sel.load(memory_order::memory_order_relaxed); }
inline IMP imp(Class cls) const {
uintptr_t imp = _imp.load(memory_order::memory_order_relaxed);
if (!imp) return nil;
#if CACHE_IMP_ENCODING == CACHE_IMP_ENCODING_PTRAUTH
SEL sel = _sel.load(memory_order::memory_order_relaxed);
return (IMP)
ptrauth_auth_and_resign((const void *)imp,
ptrauth_key_process_dependent_code,
modifierForSEL(sel, cls),
ptrauth_key_function_pointer, 0);
#elif CACHE_IMP_ENCODING == CACHE_IMP_ENCODING_ISA_XOR
return (IMP)(imp ^ (uintptr_t)cls);
#elif CACHE_IMP_ENCODING == CACHE_IMP_ENCODING_NONE
return (IMP)imp;
#else
#error Unknown method cache IMP encoding.
#endif
}
template <Atomicity, IMPEncoding>
void set(SEL newSel, IMP newImp, Class cls);
};
cache_t::insert
将新调用的方法插入到方法缓存中
// objc-cache.mm
ALWAYS_INLINE
void cache_t::insert(Class cls, SEL sel, IMP imp, id receiver)
{
#if CONFIG_USE_CACHE_LOCK
cacheUpdateLock.assertLocked();
#else
runtimeLock.assertLocked();
#endif
ASSERT(sel != 0 && cls->isInitialized());
// Use the cache as-is if it is less than 3/4 full
mask_t newOccupied = occupied() + 1;
unsigned oldCapacity = capacity(), capacity = oldCapacity;
if (slowpath(isConstantEmptyCache())) {
// Cache is read-only. Replace it.
if (!capacity) capacity = INIT_CACHE_SIZE;
reallocate(oldCapacity, capacity, /* freeOld */false);
}
else if (fastpath(newOccupied + CACHE_END_MARKER <= capacity / 4 * 3)) {
// Cache is less than 3/4 full. Use it as-is.
}
else {
// 扩容, 容量×2 ★
capacity = capacity ? capacity * 2 : INIT_CACHE_SIZE;
if (capacity > MAX_CACHE_SIZE) {
capacity = MAX_CACHE_SIZE;
}
// 扩容时, mask改变, 计算得到的idx也会发生变化, 所以会直接把缓存清掉
// reallocate内部会调用 cache_collect_free(oldBuckets, oldCapacity); 清除缓存
// 并设置 mask = 新容量 - 1
reallocate(oldCapacity, capacity, true);
}
bucket_t *b = buckets();
// mask掩码
mask_t m = capacity - 1;
// cache_hash 内部实现: sel & m 计算得到索引
mask_t begin = cache_hash(sel, m);
mask_t i = begin;
// Scan for the first unused slot and insert there.
// There is guaranteed to be an empty slot because the
// minimum size is 4 and we resized at 3/4 full.
do {
// 插入到空位
if (fastpath(b[i].sel() == 0)) {
incrementOccupied();
b[i].set<Atomic, Encoded>(sel, imp, cls);
return;
}
// 已经缓存过, 直接return
if (b[i].sel() == sel) {
// The entry was added to the cache by some other thread
// before we grabbed the cacheUpdateLock.
return;
}
// __arm64__下, cache_next(i, m) 内部实现: (i ? i-1 : m)
// 走到这里就说明当前位置被别的sel占用, 就继续查找空位
// 从begin位置向上查找空位(i = i - 1), 减到 0 就回到 mask 位置继续向上查找, 直到找到空位
} while (fastpath((i = cache_next(i, m)) != begin));
cache_t::bad_cache(receiver, (SEL)sel, cls);
}
总结
第一次调用实例方法时, 会将方法缓存到类对象的 cache_t 中
方法调用过程(轨迹)
实例方法调用过程:
当发送消息给实例对象时, 消息是在寻找这个对象的类的方法列表 (实例方法)
- 首先在自身 isa 指向的
objc_class(自己的类)的methodLists中查找该方法, 找到就调用; - 若找不到则会通过
objc_class的super_class指针找到其父类, 然后从其methodLists中查找该方法; - 若仍然找不到, 则继续通过
super_class向上一级父类结构体中查找, 直至根类; - 若根类也找不到, 则报错。
例: [obj makeText]; 运行时编译器会将代码转化为 objc_msgSend(obj, @selector (makeText));
在 objc_msgSend函数中首先通过obj(对象)的isa指针找到obj对应的class;
在 class 中, 先去cache中, 通过SEL(方法的编号)查找对应method(方法);
若 cache 中未找到, 再去 methodLists 中查找, 若 methodists 中未找到, 则去 superClass 中查找;
若能找到, 则将method加入到 cache 中, 以方便下次查找, 并通过 method 中的函数指针跳转到对应的函数中去执行。
类方法调用过程:
当发送消息给类对象时, 消息是在寻找这个类的元类的方法列表(类方法)
- 首先通过自己的
isa指针找到metaClass, 并从其methodLists中查找该类方法, 找到就调用; - 若找不到, 则会通过
metaClass的super_class指针找到父元类, 然后从methodLists中查找该方法; - 若仍然找不到, 则继续通过
super_class向上一级父元类中查找, 直至根类 (注意不是根元类); - 若根类也找不到, 则报错。
总结:
沿着super_class指针一直往上找, 直到找到要调用的方法调用, 或者super_class指针为nil报错;
调用父类的方法, 也会缓存到自己类对象的cache中
