In our last post on iOS, cache Analysis (part 1), we had an overview of the cache structure. We also moved away from source code analysis, and from the results of our test prints, the values of _occupied and _maybeMask have changed. So what do _occupied and _maybeMask have to do with easing? How does OC cache at the bottom? With these questions, we will explore exploration, analysis!

Cache_t underlying source code analysis

insert

Cache_t insert is a function of the cache_t insert method.

void cache_t::insert(SEL sel, IMP imp, id receiver)
Copy the code

We enter theinsertLook inside the method

  1. The first step is to calculate the current cache occupancy based on the value of occupied. If there is no attribute assignment or method call, occupied() is 0 and newOccupied () is 1

  2. INIT_CACHE_SIZE = (1 << INIT_CACHE_SIZE_LOG2); INIT_CACHE_SIZE_LOG2 = 2, which means that moving 2 one bit to the left makes it 100, or 4

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

If the number of caches is less than or equal to 3/4, no processing is done

 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.
    }
Copy the code

If the cache usage exceeds 3/4, you need to expand the capacity and re-create the space, which is twice as large as the original space

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

reallocate

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); }}Copy the code
  1. Part 3 Rightbucket_tTo operate,bucketWhat’s in there isselandimpAccording to the incomingselandm(Capacity-1), passedcache_hashThe hashing method gives you oneThe subscriptAnd then enter thedo-whileCycle judgment

cache_hash

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);
}
Copy the code

If sel = 0, store sel and IMP, and increment “occupied” by 1 by incrementOccupied()

void cache_t::incrementOccupied() 
{
    _occupied++;
}

Copy the code

If the current location already stores sel, return directly

if (b[i].sel() == sel) {
            // The entry was added to the cache by some other thread
            // before we grabbed the cacheUpdateLock.
            return;
 }
Copy the code

If the sel stored at the current location is not equal to the SEL we want to insert, we need the cache_next method to redo the hash to get a new index, and then compare and store

while(fastpath((i = cache_next(i, m)) ! = begin));Copy the code

Hash conflict

Resolving hash conflicts,

  • Subscript the current hash+1 & mask, re-hash, get a new subscript.
  • If the current location already existsselBut it’s not the way we cached it beforei-1How do I get all the way to the first positioni-1for0In the case of, the value is directly assigned tomask, fromHash tabletheAt the end ofstartGo to findUntil you find the right place to insert
#if CACHE_END_MARKER
static inline mask_t cache_next(mask_t i, mask_t mask) {
    return (i+1) & mask;
}
#elif __arm64__
static inline mask_t cache_next(mask_t i, mask_t mask) {
    return i ? i- 1 : mask;
}
Copy the code

At this point, the basic analysis of cache_T is complete

conclusion

In iOS cache analysis (part 1), we also called different methods to test the final values of _occupied and _maybeMask, and found that the values of _occupied and _maybeMask were changed. At first, we called two methods to print the final values of _occupied and _maybeMask. Later, we called more methods to print the final values of _maybeMask and _occupied. The order in which the output is printed is different, and some methods print NULL.

  • _occupiedRepresents the hash tableselThe number of methods (already stored in allocated memoryselNumber of methods)
  • _maskIt’s used to compute subscripts in hashing algorithmsmask, includingmask=capacity - 1
  • cacheIt’s method caching, it’s usingHash table(hash table) to cache methods that have been called, which can improve method lookup speed
  • bucket_tIt’s just a hash table. It’s storedselandimp.selIs the method name, askey ,impIs the memory address of the function
  • The cache is greater than theThree quarters ofWill be incapacity(7 methods are greater than the 4 given the first time), is the previous2Double capacity expansion, capacity expansion will empty the previously allocated space, and then hash operation, insert the new space, with space for time, improve the speed of query
  • Due to theHash tableisA disorderlySo after the expansion, we see some printsnull(Because the previous cached methods were cleared after capacity expansion, the following four methods were inserted into the newly expanded place, but were not fully stored. If they were stored in disorder, null appeared), indicating that no method was inserted into this position

More content continues to be updated

🌹 please move your little hands and give a thumbs-up 👍🌹

🌹 like can come a wave, collect + attention, comment + forward, so as not to find me next time, ha ha 😁🌹

🌹 welcome everyone to leave a message exchange, criticism and correction, learn from each other 😁, improve themselves 🌹