IOS - method cache for class (NSObject)

In the last article, we briefly analyzed the structure of a class and the storage of its attributes and methods. Next, we will analyze the method cache in the structure of a class: cache.

Class structure:

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

I. Introduction to Cache

1. What does cache do

Class method cache, increase method lookup efficiency.

2. Cache_t internal structure

struct cache_t {
    struct bucket_t *_buckets;
    mask_t _mask;
    mask_t _occupied;

public:
    struct bucket_t *buckets();
    mask_t mask();
    mask_t occupied();
    void incrementOccupied();
    void setBucketsAndMask(struct bucket_t *newBuckets, mask_t newMask);
    void initializeToEmpty();

    mask_t capacity();
    bool isConstantEmptyCache();
    bool canBeFreed();

    static size_t bytesForCapacity(uint32_t cap);
    static struct bucket_t * endMarker(struct bucket_t *b, uint32_t cap);

    void expand();
    void reallocate(mask_t oldCapacity, mask_t newCapacity);
    struct bucket_t * find(cache_key_t key, id receiver);

    static void bad_cache(id receiver, SEL sel, Class isa) __attribute__((noreturn));
};
Copy the code

_buckets: array of the bucket_t structure, which is used to store the SEL memory address and IMP of the method
_mask: the size of the array is -1, used as the mask.
_occupied: indicates the number of cached methods.

struct bucket_t { cache_key_t _key; // typedef unsigned long IMP _imp; . };Copy the code

_key: cache_key_t is an unsigned long used to store SEL memory addresses. SEL should be charA string of the type charStrong unsigned long is actually the memory address of SEL.
_IMP: the memory address of the function corresponding to the method.

The main functions in cache_t

1. Cache lookup

bucket_t * cache_t::find(cache_key_t k, id receiver) { assert(k ! = 0); bucket_t *b = buckets(); mask_t m = mask(); mask_t begin = cache_hash(k, m); mask_t i = begin;do {
        if (b[i].key() == 0  ||  b[i].key() == k) {
            return&b[i]; }}while((i = cache_next(i, m)) ! = begin); Class cls = (Class)((uintptr_t)this - offsetof(objc_class, cache)); cache_t::bad_cache(receiver, (SEL)k, cls); } / / -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- find internal call cache_hash -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- the static inline mask_t cache_hash (cache_key_t key, mask_t mask) {return(mask_t)(key & mask); } / / -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- find internal call cache_next (arm64) -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- the static inline mask_t cache_next (mask_t I, mask_t mask) {return i ? i-1 : mask;
}
Copy the code

Analysis:

The buckets hash list and mask are obtained, and the begin index corresponding to the key value is obtained by cache_hash(key & mask).
Assign begin to I to facilitate index switching.
Do a do-while loop lookup
```
(i = cache_next(i, m)) ! = beginCopy the code
```
For example, the initial subscript is 4, and the total length is 8, decreasing successively. When I = 0, return mask, then continue to search from the total length = 8, until index equals 4 again, indicating that the search has been done, but still not found, and the method cache search ends.
```
if (b[i].key() == 0  ||  b[i].key() == k)
Copy the code
```
The value of bucket_t is obtained from the hash table using I as the index. If the key of bucket_t is K, the query succeeds and the bucket_t is returned.

If key = 0, no method has been cached at index I, and bucket_t is returned to terminate the cached query.
If the bucket_t corresponding to the key is not found, or bucket_t is empty, the loop ends, indicating that the search failed, and the bad_cache method is called.

2. Cache fill insert

The cache fill insertion function calls the lookup method, which is also the focus of our attention

static void cache_fill_nolock(Class cls, SEL sel, IMP imp, id receiver)
{
    cacheUpdateLock.assertLocked();

    // Never cache before +initialize is done
    if(! cls->isInitialized())return;

    // Make sure the entry was not added to the cache by some other thread 
    // before we grabbed the cacheUpdateLock.
    if (cache_getImp(cls, sel)) return;

    cache_t *cache = getCache(cls);
    cache_key_t key = getKey(sel);

    // Use the cache as-is if it is less than 3/4 full
    mask_t newOccupied = cache->occupied() + 1;
    mask_t capacity = cache->capacity();
    if (cache->isConstantEmptyCache()) {
        // Cache is read-only. Replace it. cache->reallocate(capacity, capacity ? : INIT_CACHE_SIZE); }else if (newOccupied <= capacity / 4 * 3) {
        // Cache is less than 3/4 full. Use it as-is.
    }
    else {
        // Cache is too full. Expand it.
        cache->expand();
    }

    // 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.
    bucket_t *bucket = cache->find(key, receiver);
    if (bucket->key() == 0) cache->incrementOccupied();
    bucket->set(key, imp);
}
//-------------------------capacity() -----------------------------
mask_t cache_t::capacity() 
{
    return mask() ? mask()+1 : 0; 
}
Copy the code

Make sure the cache is not added by another thread
Mask_t newOccupied = cache-> Occupied () + 1;
Gets the capacity of the current hash table
Determine whether the current cache is read-only, that is, not initialized, and reallocate the cache capacity
If newOccupied is greater than 3/4 of the capacity, expansion is required
The corresponding bucket_t is obtained using the find function.
Check whether the returned bucket->key() is 0

A value of 0 indicates that the location is empty and no method has been cached, so a new cache needs to be added.
```
void cache_t::incrementOccupied() 
{
    _occupied++;
}
Copy the code
```
Save the key and IMP in the cache

3. Cache capacity expansion

void cache_t::expand()
{
    cacheUpdateLock.assertLocked();
    
    uint32_t oldCapacity = capacity();
    uint32_t newCapacity = oldCapacity ? oldCapacity*2 : INIT_CACHE_SIZE;

    if((uint32_t)(mask_t)newCapacity ! = newCapacity) { // mask overflow - can not grow further // fixme this wastes one bit of mask newCapacity = oldCapacity;  } reallocate(oldCapacity, newCapacity); } //-------------------------------------------------------- INIT_CACHE_SIZE = (1 << INIT_CACHE_SIZE_LOG2) // 4Copy the code

If the current cache capacity does not exist, create a cache capacity of the size INIT_CACHE_SIZE (4). If it does exist, double it by *2.

4. Cache allocation

As you can see, the cache allocation function reallocate is used for cache fill insertion and capacity expansion:

void cache_t::reallocate(mask_t oldCapacity, mask_t newCapacity)
{
    bool freeOld = canBeFreed();

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

Functions used:

Bool cache_t::canBeFreed()
{
    return! isConstantEmptyCache(); } bool cache_t::isConstantEmptyCache()
{
    return 
        occupied() == 0  &&  
        buckets() == emptyBucketsForCapacity(capacity(), false);
}

//---------------------------setBucketsAndMask-------------------------------
void cache_t::setBucketsAndMask(struct bucket_t *newBuckets, mask_t newMask)
{
    mega_barrier();

    _buckets = newBuckets;
    _mask = newMask;
    _occupied = 0;
}
Copy the code

Determine if you need to release

The canBeFreed function is used to determine whether the current cache is empty, and if so, there is no need to free it.
New buckets are allocated according to newCapacity
Reassigning the parameters in cache_t points to a new memory space
Release the cache as determined in step 1

Third, summary

The cache of the calling method is stored in the cache of the class structure in the form of the hash hash table bucket_t. If the size of the cache does not exist, a new size of INIT_CACHE_SIZE (4) is created. If the size of the cache exceeds three quarters of the size, a new size is created by *2. And free up the old cache space, and save the call method cache this time.

mo4tech.com (Moment For Technology) is a global community with thousands techies from across the global hang out!Passionate technologists, be it gadget freaks, tech enthusiasts, coders, technopreneurs, or CIOs, you would find them all here.

IOS – method cache for class (NSObject)

I. Introduction to Cache

1. What does cache do

2. Cache_t internal structure

The main functions in cache_t

1. Cache lookup

2. Cache fill insert

3. Cache capacity expansion

4. Cache allocation

Third, summary

IOS – method cache for class (NSObject)

I. Introduction to Cache

1. What does cache do

2. Cache_t internal structure

The main functions in cache_t

1. Cache lookup

2. Cache fill insert

3. Cache capacity expansion

4. Cache allocation

Third, summary

Related Posts

Swift series 19 – Generic

Create Swift package manager from an existing code base

Talk about the underlying iOS RunLoop