The underlying structure of the cache:
Is a hash table with the corresponding element bucket_t, with an initial size of 2 to the 1st and a maximum size of 2 to the 16th
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;
};
// The value of capacity -1
int32_t mask(a) const
{
return _bucketsAndMaybeMask >> maskShift;
}
// Buckets array address
struct bucket_t *buckets(a) const
{
return (bucket_t*)(_bucketsAndMaybeMask & bucketsMask); }}struct bucket_t {
explicit_atomic<uintptr_t> _imp;
explicit_atomic<SEL> _sel;
}
Copy the codeHash algorithm:
The address of the SEL, xor moves 7 bits to the right of itself, and the hash table (capacity -1) does &
Ps: If the capacity is 2 to the m, then the & operation with (capacity -1) is equal to % capacity
Hash conflict:
Use the hash algorithm to calculate the subscript. If the subscript has a value, run the subscript down to -1. When the subscript decreases to 0, run the subscript down to -1 until an empty position is found, and then put it in
Hash table expansion:
Capacity expansion conditions:
Check whether the current capacity is greater than 8. If the capacity is greater than 8, the loading factor is greater than 7/8 and the capacity is expanded; if the capacity is less than or equal to 8, the capacity is expanded after the loading factor is equal to 1
Loading factor: (used space/total space)
Scale operation
Create a new space with an old size of 2, at which point the old cache is thrown away
Source:
/ / basic macros
INIT_CACHE_SIZE_LOG2 = 1,
INIT_CACHE_SIZE = (1 << INIT_CACHE_SIZE_LOG2), // Initial size
MAX_CACHE_SIZE_LOG2 = 16,
MAX_CACHE_SIZE = (1 << MAX_CACHE_SIZE_LOG2), // Maximum size
// Determine whether expansion is required
static inline mask_t cache_fill_ratio(mask_t capacity) {
return capacity * 7 / 8;
}
// Resolve hash conflicts
static inline mask_t cache_next(mask_t i, mask_t mask) {
return i ? i- 1 : mask;
}
// Hash algorithm
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);
}
/ / capacity
void cache_t::reallocate(mask_t oldCapacity, mask_t newCapacity, bool freeOld)
{
bucket_t *oldBuckets = buckets(a);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); }}// Insert a new cache
void cache_t::insert(SEL sel, IMP imp, id receiver)
{
runtimeLock.assertLocked(a);// 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);
}
// Determine whether the capacity needs to be expanded (whether the used space is greater than 7/8 of the capacity; if the space is larger than 7/8 of the capacity, the capacity needs to be expanded; if the space is smaller than 7/8 of the capacity, the capacity does not need to be expanded)
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
// Before capacity expansion, the system checks whether the capacity is less than or equal to 8. If the capacity is less than or equal to 8, the capacity can be used up
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 {
// Create a new space
capacity = capacity ? capacity * 2 : INIT_CACHE_SIZE;
if (capacity > MAX_CACHE_SIZE) {
capacity = MAX_CACHE_SIZE;
}
reallocate(oldCapacity, capacity, true);
}
bucket_t *b = buckets(a);mask_t m = capacity - 1;
// Hash algorithm
mask_t begin = cache_hash(sel, m);
mask_t i = begin;
// Resolve hash conflicts
// 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(a); 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
}
Copy the codeDEMO
#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; // Parent pointer
wy_cache_t cache; // Method cache
uintptr_t bits; / / class information
};
@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(a)
@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 -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- - the 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] Catitest1 2021-11-04 14:51:50.790157+0800 CacheApp[29923:8662404] CatiTEST 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 ---------------- */
Copy the code