The source code

Objc_class structure

struct objc_class : objc_object { // Class ISA; Class superclass; cache_t cache; // formerly cache pointer and vtable class_data_bits_t bits; // class_rw_t * plus custom rr/alloc flags class_rw_t *data() const { return bits.data(); }... }Copy the code

Cache_t structure

struct cache_t { #if CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_OUTLINED explicit_atomic<struct bucket_t *> _buckets; explicit_atomic<mask_t> _mask; #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(); . };Copy the code

The overall structure

Process analysis

Partially important variables

_buckets _buckets is a hash table of type struct bucket_t, and a cache of methods (storing bucket_t as a hash table)

For example, cache_t is initially allocated a certain amount of memory such as 10, doubles when it runs low, and so on.

Index on the left, index on the rightbucket_tThe structure of the body

_mask _mask is the mask data used to calculate the hash subscript in the hash algorithm or hash conflict algorithm. Mask is equal to capacity-1 (the critical capacity value of the array length of _buckets).

Why bitwise &_mask? Bitwise and are guaranteed to get a value <=_mask so that the allocated space is not exceeded

_occupied indicates the occupied capacity of the hash table

Hash table storage principle

  • Initially, of the objectcach_tAllocate a space and the value is zeroNULL
  • When a method is called, one is sent for the objectSELThe message, such as@selector(test)Caches this method
  • The system useSELwith_maskTo do bitwise and calculation:@selector(test) & _mask, assuming its value ==2,
  • Check whether the space corresponding to index 2 isNULLIf forNULLWill thisbucket_tCached in space corresponding to index 2
  • If it is not empty, subtract 1 from the index and check whether it isNULLIf the index <0, make the index =_mask-1 until the corresponding space of the index is foundNULLAnd then the cache

Partially important function

incrementOccupied()

void cache_t::incrementOccupied() 
{
    _occupied++;
}
Copy the code

\ is only called in void cache_t::insert(Class CLS, SEL SEL, IMP IMP, id receiver)

void cache_t::insert(Class cls, SEL sel, IMP imp, id receiver)

Cache_t, and sel-IMP is stored in cache, so caching starts with the INSERT method

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 <= capacity / 4 * 3)) { // Cache is less than 3/4 full. Use it as-is. } 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 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; } 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)); cache_t::bad_cache(receiver, (SEL)sel, cls); }Copy the code

It is mainly divided into the following parts: 1. Calculate the current cache usage; 2. Determine the operation to be performed according to the cache usage; 3

Calculates the current cache usage

Calculate the current cache usage based on the value of occupied. When there is no attribute assignment and no method call, occupied() is 0 and newOccupied is 1, as shown below

mask_t newOccupied = occupied() + 1;
Copy the code

Now, when we alloc, the object is already created, if we call init, we’ll call the set method, and we’ll increment occupied, that is, we’ll have several property assignments, we’ll add a few to the occupied one and when we call the method, “Occupied” will also be added, meaning that it will be called several times

Determine what to do based on cache usage

If it is the first creation, four are created by default

if (slowpath(isConstantEmptyCache())) { // Cache is read-only. Replace it. // INIT_CACHE_SIZE = (1<<2) = 4 if (! capacity) capacity = INIT_CACHE_SIZE; reallocate(oldCapacity, capacity, /* freeOld */false); }Copy the code

If the cache usage is less than or equal to 3/4, no processing is done

else if (fastpath(newOccupied <= capacity / 4 * 3)) {
    // Cache is less than 3/4 full. Use it as-is.
}
Copy the code

If the cache usage exceeds 3/4, you need to double the capacity and respace

else {
    capacity = capacity ? capacity * 2 : INIT_CACHE_SIZE;
    if (capacity > MAX_CACHE_SIZE) {
        capacity = MAX_CACHE_SIZE;
    }
    reallocate(oldCapacity, capacity, true);
}
Copy the code

Reallocate method: Open up space

ALWAYS_INLINE
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) {
        cache_collect_free(oldBuckets, oldCapacity);
    }
}
Copy the code

SetBucketsAndMask: cache_COLLect_free: clears the previous cache. The setBucketsAndMask method is used to store the temporary buckets in the cache

static void cache_collect_free(bucket_t *data, mask_t capacity)
{
#if CONFIG_USE_CACHE_LOCK
    cacheUpdateLock.assertLocked();
#else
    runtimeLock.assertLocked();
#endif
​
    if (PrintCaches) recordDeadCache(capacity);
​
    _garbage_make_room ();
    garbage_byte_size += cache_t::bytesForCapacity(capacity);
    garbage_refs[garbage_count++] = data;
    cache_collect(false);
}
Copy the code

If it is not the first time, the memory segment is enlarged, that is, the original memory *2 records are stored in the current bucket cache_collect method

Internal IMP and SEL assignments are performed for the buckets that need to be stored

  • If sel = 0, store SEL-IMP and increment the occupied value by 1
  • Returns directly if the sel stored in the current hash subscript is equal to the sel to be inserted
  • If the sel stored in the current hash subscript is not equal to the sel to be inserted, the cache_next (hash collision) algorithm is used to re-hash the sel to obtain the new subscript and then compare and store the sel

Cache_hash Hash algorithm

static inline mask_t cache_hash(SEL sel, mask_t mask) 
{
    return (mask_t)(uintptr_t)sel & mask;
}	
Copy the code

The cache_next hash collision algorithm has a -1 algorithm because bitwise and, because different values of &_mask may result in the same result. Minus 1 if it’s already occupied

static inline mask_t cache_next(mask_t i, mask_t mask) {
    return i ? i-1 : mask;
}
Copy the code

conclusion

_mask: mask is used to calculate the subscript in the hash algorithm or in the hash conflict algorithm. Mask: capacity-1; _occupied: sel-IMP occupied; _occupied: sel-IMP occupied;

  • initCan lead tooccupiedchange
  • Property assignment is also called implicitlysetMethod, result inoccupiedchange
  • Method call, which causesoccupiedchange

If the number of sel-IMPs (newOccupied+CACHE_END_MARKER) exceeds three quarters of the total cache size, for example, newOccupied+CACHE_END_MARKER; if the number of sel-IMPs (newOccupied+CACHE_END_MARKER; 4. In hash data structures, there is a concept used to indicate the number of empty Spaces called the load factor — the larger the load factor, the fewer free Spaces, the more collisions, and the lower the hash table performance. When the load factor is 3/4, the space utilization rate is relatively high, and avoids quite a lot of Hash conflicts, and improves the space efficiency. 5. Sel-imp storage is calculated by Hash algorithm subscript, its calculated subscript may have stored SEL, so it needs to recalculate the Hash subscript through Hash conflict algorithm. So the subscripts are random, they’re not fixed.