runtime08 - 方法缓存Cache_t
缓存的底层结构:
是一个hash表, 对应的元素是bucket_t, 初始尺寸是2的1次方, 最大尺寸是2的16次方
struct cache_t { private: explicit_atomic<uintptr_t> _bucketsAndMaybeMask; union { struct { explicit_atomic<mask_t> _maybeMask; #if __LP64__ uint16_t _flags; #endif uint16_t _occupied; }; explicit_atomic<preopt_cache_t *> _originalPreoptCache; }; // 容量 - 1的值 int32_t mask() const { return _bucketsAndMaybeMask >> maskShift; } // buckets数组的地址 struct bucket_t *buckets() const { return (bucket_t *)(_bucketsAndMaybeMask & bucketsMask); } } struct bucket_t { explicit_atomic<uintptr_t> _imp; explicit_atomic<SEL> _sel; } 复制代码哈希算法:
sel的地址, 异或右移7位的自身, 与hash表的(容量 - 1)做&操作
ps: 如果容量是2的m次方, 那么与(容量-1)做&操作, 相当于%容量
哈希冲突:
通过hash算法算出下标, 如果发现该下边已经有值时, 将下标一直-1, 当下标减到0时, 将下标改成容量 - 1, 直到遇到空的位置, 然后放进去
哈希表扩容:
扩容条件:
插入时, 判断当前容量是否大于8, 大于8的话, 装填因子 大于 7/8, 就扩容, 小于等于8的话, 装填因子等于1后再扩容
装填因子: (已使用空间 / 整体空间)
扩容操作
新开辟一处旧容量大小 * 2的空间, 这个时候旧的缓存就直接扔了
源码:
// 基础宏 INIT_CACHE_SIZE_LOG2 = 1, INIT_CACHE_SIZE = (1 << INIT_CACHE_SIZE_LOG2), // 最初尺寸 MAX_CACHE_SIZE_LOG2 = 16, MAX_CACHE_SIZE = (1 << MAX_CACHE_SIZE_LOG2), // 最大尺寸 // 判断是会否需要扩容 static inline mask_t cache_fill_ratio(mask_t capacity) { return capacity * 7 / 8; } // 解决哈希冲突 static inline mask_t cache_next(mask_t i, mask_t mask) { return i ? i-1 : mask; } // 哈希算法 static inline mask_t cache_hash(SEL sel, mask_t mask) { uintptr_t value = (uintptr_t)sel; #if CONFIG_USE_PREOPT_CACHES value ^= value >> 7; #endif return (mask_t)(value & mask); } // 扩容 void cache_t::reallocate(mask_t oldCapacity, mask_t newCapacity, bool freeOld) { bucket_t *oldBuckets = buckets(); bucket_t *newBuckets = allocateBuckets(newCapacity); // Cache's old contents are not propagated. // This is thought to save cache memory at the cost of extra cache fills. // fixme re-measure this ASSERT(newCapacity > 0); ASSERT((uintptr_t)(mask_t)(newCapacity-1) == newCapacity-1); setBucketsAndMask(newBuckets, newCapacity - 1); if (freeOld) { collect_free(oldBuckets, oldCapacity); } } // 插入新缓存 void cache_t::insert(SEL sel, IMP imp, id receiver) { runtimeLock.assertLocked(); // Never cache before +initialize is done if (slowpath(!cls()->isInitialized())) { return; } if (isConstantOptimizedCache()) { _objc_fatal("cache_t::insert() called with a preoptimized cache for %s", cls()->nameForLogging()); } #if DEBUG_TASK_THREADS return _collecting_in_critical(); #else #if CONFIG_USE_CACHE_LOCK mutex_locker_t lock(cacheUpdateLock); #endif ASSERT(sel != 0 && cls()->isInitialized()); // Use the cache as-is if until we exceed our expected fill ratio. 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); } // 判断是否需要扩容 (已使用的空间 是否 大于容量的 7/8, 大于则扩容, 小于则不需要扩容) else if (fastpath(newOccupied + CACHE_END_MARKER <= cache_fill_ratio(capacity))) { // Cache is less than 3/4 or 7/8 full. Use it as-is. } #if CACHE_ALLOW_FULL_UTILIZATION // 在需要扩容时, 会先判断容量是否小于等于8, 小于等于8的话允许占满整个容量 else if (capacity <= FULL_UTILIZATION_CACHE_SIZE && newOccupied + CACHE_END_MARKER <= capacity) { // Allow 100% cache utilization for small buckets. Use it as-is. } #endif else { // 扩容操作, 重新开辟一份空间 capacity = capacity ? capacity * 2 : INIT_CACHE_SIZE; if (capacity > MAX_CACHE_SIZE) { capacity = MAX_CACHE_SIZE; } reallocate(oldCapacity, capacity, true); } bucket_t *b = buckets(); mask_t m = capacity - 1; // 哈希算法 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. do { if (fastpath(b[i].sel() == 0)) { incrementOccupied(); b[i].set<Atomic, Encoded>(b, sel, imp, cls()); return; } if (b[i].sel() == sel) { // The entry was added to the cache by some other thread // before we grabbed the cacheUpdateLock. return; } } while (fastpath((i = cache_next(i, m)) != begin)); bad_cache(receiver, (SEL)sel); #endif // !DEBUG_TASK_THREADS } 复制代码DEMO
#import "ViewController.h" #import <objc/runtime.h> // 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; struct wy_objc_object { void* isa; }; struct bucket_t { uintptr_t _imp; SEL _sel; }; struct wy_cache_t { uintptr_t _bucketsAndMaybeMask; union { struct { int32_t _maybeMask; #if __LP64__ uint16_t _flags; #endif uint16_t _occupied; }; void * _originalPreoptCache; }; int32_t mask() const { return _bucketsAndMaybeMask >> maskShift; } struct bucket_t *buckets() const { return (bucket_t *)(_bucketsAndMaybeMask & bucketsMask); } }; struct wy_objc_class: wy_objc_object { // Class ISA; wy_objc_class *superclass; // 父类指针 wy_cache_t cache; // 方法缓存 uintptr_t bits; // 类信息 }; @interface Person : NSObject @end @implementation Person - (void)categoryTest { NSLog(@"+ test"); } - (void)categoryTest1 { NSLog(@"+ test"); } - (void)categoryTest2 { NSLog(@"+ test"); } - (void)categoryTest3 { NSLog(@"+ test"); } @end @interface ViewController () @end @implementation ViewController - (void)viewDidLoad { [super viewDidLoad]; struct wy_objc_class *cls = (__bridge struct wy_objc_class *)[Person class]; struct bucket_t *buckets = cls->cache.buckets(); int32_t mask = cls->cache.mask(); NSLog(@" %d ----------------", mask); class_getInstanceMethod([Person class], @selector(categoryTest)); buckets = cls->cache.buckets(); mask = cls->cache.mask(); for(int i = 0; i <= mask; i++) { NSLog(@"%@", NSStringFromSelector((buckets + i)->_sel) ); } NSLog(@" %d ----------------", mask); class_getInstanceMethod([Person class], @selector(categoryTest1)); buckets = cls->cache.buckets(); mask = cls->cache.mask(); for(int i = 0; i <= mask; i++) { NSLog(@"%@", NSStringFromSelector((buckets + i)->_sel) ); } NSLog(@" %d ----------------", mask); class_getInstanceMethod([Person class], @selector(categoryTest2)); buckets = cls->cache.buckets(); mask = cls->cache.mask(); for(int i = 0; i <= mask; i++) { NSLog(@"%@", NSStringFromSelector((buckets + i)->_sel) ); } NSLog(@" %d ----------------", mask); } @end /** 2021-11-04 14:51:50.790030+0800 CacheApp[29923:8662404] 0 ---------------- 2021-11-04 14:51:50.790074+0800 CacheApp[29923:8662404] (null) 2021-11-04 14:51:50.790100+0800 CacheApp[29923:8662404] categoryTest 2021-11-04 14:51:50.790117+0800 CacheApp[29923:8662404] 1 ---------------- 2021-11-04 14:51:50.790136+0800 CacheApp[29923:8662404] categoryTest1 2021-11-04 14:51:50.790157+0800 CacheApp[29923:8662404] categoryTest 2021-11-04 14:51:50.790171+0800 CacheApp[29923:8662404] 1 ---------------- 2021-11-04 14:51:50.790186+0800 CacheApp[29923:8662404] (null) 2021-11-04 14:51:50.790201+0800 CacheApp[29923:8662404] (null) 2021-11-04 14:51:50.790267+0800 CacheApp[29923:8662404] categoryTest2 2021-11-04 14:51:50.790329+0800 CacheApp[29923:8662404] (null) 2021-11-04 14:51:50.790391+0800 CacheApp[29923:8662404] 3 ---------------- */
作者：潘森
链接：https://juejin.cn/post/7026651464168636430