前言

上文讲解完了类对象的结构体objc_class用来存储类信息的成员bits，整个结构还剩下方法的缓存cache，放在压轴来讲解。

// 简化版
struct objc_class : objc_object {
    // 类对象指针，Class大小是8字节
    Class ISA;
    // 父类对象指针，大小同上8字节
    Class superclass;
    // 方法缓存
    cache_t cache; // formerly cache pointer and vtable
    // 类存储的数据
    class_data_bits_t bits; // class_rw_t * plus custom rr/alloc flags
}

cache的探索

cache字面意思是缓存，接下来探索它的数数据结构c语言版严蔚敏第二版答案据结构。

拿到类对象地址后，根据结构体可知，平移16字节得到cache：

查看源码的cache_t数据结构：

struct cache_t {
private:
    // 8字节
    explicit_atomic<uintptr_t> _bucketsAndMaybeMask;
    union {
        struct {
            explicit_atomic<mask_t>    _maybeMask; // 4字节
#if __LP64__
            uint16_t                   _flags; // 2字节
#endif
            uint16_t                   _occupied; // 2字节
        };
        // 8字节
        explicit_atomic<preopt_cache_t *> _originalPreoptCache;
    };
}

explicit_atom数据结构题库ic原子性，保证线程安全；_bucketsAndM数据结构实验报告aybeMask成员变量占8字节；

还有一个联合体，并且联合体里还有一个结构体；通过计算最大也是占8字节；

结构和LLDB输出对应上了。这些内容又容器英文是什么意思呢？先放着。既然是缓存，就需要插入数据。在结构体内找到insert方法，参数有SEL、IMP，这两者决定了一个方法。参数3是方法的接收者。

void insert(SEL sel, IMP imp, id receiver);

来到方法内部，下面的循源码时代环就是在操作bucket_t *b这个数据；

那就要看看数据结构bucket_t了。

方法缓存的结构体

查看bucket_t结构体，也有imp和sel。

struct bucket_t {
private:
    // IMP-first is better for arm64e ptrauth and no worse for arm64.
    // SEL-first is better for armv7* and i386 and x86_64.
#if __arm64__
    explicit_atomic<uintptr_t> _imp;
    explicit_atomic<SEL> _sel;
#else
    explicit_atomic<SEL> _sel;
    explicit_atomic<uintptr_t> _imp;
#endif
    ...
}

回到循环，查看se源码网站t方法。这是一个函数模板:

// <原子操作，是否需要编码>
template<Atomicity atomicity, IMPEncoding impEncoding>

判断impEncoding:

查看encodeI源码编程器mp，通过注释可知这是方法架构图怎么制作签名用的。

回到set方法，这段是判断原子操作:

这个store就是往内存写入数容器所能容纳什么叫做容器的容积据，load是读取。set方法就是把newIMP和newSel写源码之家入内存，简单概括就是保存方法。

当循环往*b插入数据的时候，插入开始位置通数据结构有哪些过cache_hash算出来。

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);
}

cache_hash(sel, m)架构图怎么制作;入参sel是方法名，那和参数m相关的capacity是什么呢？

回到主方法测试抑郁症，通过函数capacity()得到oldCapacity，意思是旧的buckets()容器长度（下文扩容部分会说明），并架构图赋值给capaci源码ty。

而capacity()代数据结构与算法码：从成员变量_maybeMask读取mask()，

capacity = mask()+1 等价于mask()= cap源码时代acity - 1。

unsigned cache_t::capacity() const
{
    return mask() ? mask() + 1 : 0; 
}
// mask()
mask_t cache_t::mask() const
{
    return _maybeMask.load(memory_order_relaxed);
}

capacity() 函数的作用就是获取当前容器能够缓存方法的最大个数，也就是容器的⻓度。那么入参m就是长度 – 1。

回到hash算法，

sel被转换成uintptr_t，本质是数字。不过这个数字比较大。

#ifndef __has_attribute
typedef unsigned long           uintptr_t;
#else
typedef unsigned long           uintptr_t;
#endif /* __has_attribute */

当value & mask的时候，最大也就等于mask（主方法里的入测试工程师参m），也就是 buckets()容器长度 – 1；

// 例如 mask = 6 = 0110
0110 & 11111111111 = 0110, // 与运算，0与上任何数都是0；

bucket_t是散列表，理解为往数组里插入数据。再好的hash算法都会有冲源码交易平台突，也就是2个不容器云同的方法得到相同的内存地址；

所以系统用了两个判断：1源码网站.sel有没有值（0代表未使用），2.未使用，存进去之后是否相等；

解决哈希冲突

如果都不满足，就要解决哈希冲突：cache_next方法

// CACHE_END_MARKER：缓存结束标记，值跟随架构变化。
#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;
}
#else
#error unexpected configuration
#endif

CACHE_END_MARKER = 1时，方法测试抑郁症的20道题相当于把测试工程师i增大，往之后的地址里存（开放地址法），且得到的i不等于源码编辑器begin；

while (fastpath((i = cache_next(i, m)) != begin))

综上所述，ca数据结构有哪些che应该就是方法的缓存。

接着验证。将几个属性都源码编辑器打印一下；结果都不是…没有容器云一个成员带有sel和imp信息；

不要慌，找cache_t提供的方法。这不就是返回刚才插入的那些bucket_t吗？

这就打印看看：

接着从bucket_t结构体里找到imp()方法：第一个入参base不知道啥，先传nil试试：

拿到imp之后；同理能找到sel。

既然bucket_t是数组，那么存放的可能不止一个方法。通过指针地址+1获得下一个元素地址：由于是哈希表，可能存在nil，于是地址+2得到了respondsToSelector方法地址。源码时代

越界的情景：sel已经是null了，value居然有容器对桌面的压强怎么算值，这应该是用到其他地方的内存。

没调用过这些方法，为什么会有？

调用方法testInstancePrint之后，重新获取buckets，发现方法丢失了…

按理说testInstancePrint方法缓存进cache里了，首地址的方法怎么也不应该是空的。这就涉及到缓存扩容了。

cache的扩容

回到容器insert方法：

这两个if是判断初始化等。接着是架构师和程序员的区别occupied()

方数据结构教程第5版李春葆答案法内部：

mask_t cache_t::occupied() const
{
    return _occupied;
}

返回成员变容器英文量_occupied，初始0；

那么newOccupied = 0 + 1 = 1;

接下来，第一次没有缓存，必定会进入if判断里源码编程器。初始容器云值就是INIT_CACHE_SIZE

这个初始值是1左移INIT_CACH架构师工资E_SIZE_LOG2位数得到的。

CACHE_END_MARKER之前也见过数据结构实验报告。

接着执行reallocate(oldCapacity, capacity, /源码精灵永久兑换码* freeOld */**false**);，方法内源码时代部：

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) {
        collect_free(oldBuckets, oldCapacity);
    }
}

头2行就是获取老bucket_t，生成新bucket_t。

setBucketsAndMask方法：

arm是32位，arm64才是64位；也就是arm64下，啥也没干。方法本意是给成员变量赋值。第一次来由于没有旧bucket_t，所以freeold = false；不会释放旧bucket_t。

小结一下：

occupied() 函数的作用就是获取当前容器已经缓架构师和程序员的区别存的方法的个数。
INIT_CACHE_SIZE 在arm64架构下为2，在x86_64架构下为4。
那么当容器苗cache中缓存方法的架构工程师容器为空时，在arm64架构下初始化容器的⻓度为2，在x84_64架构下初始化容器的⻓度为4。

那么下一步：

这个cache_fill_ratio方法又得回到前面的这张图：

函数在x86_64架构下为容器⻓度capacity的3/4，在arm64架构下为7/8。

那么这个分支的判断就是：在x86_64架构下，实际存储的方法的个数小于等于容器的总容量的3/4再减1时，啥也不干。在arm64架构下，实际存储的方法的个数小于等于容器的总容量的 7/8时，啥也不干。

由此可以猜测，fastpath代表大概率会源码之家执行到，slowpath测试代表小概率会执行到。

C架构工程师ACHE_A数据结构c语言版LLOW_FULL_UTILIZATION 在arm64架构下等于1，会多数据结构题库出以下分支：架构图怎么制作

FULL_UTILIZATION_CACHE_SIZE在arm64架构下等于8；

逻辑就是：在arm64架构下，当容器的源码时代⻓度小于或容器对桌面的压强怎么算等于8时 && 实际存储的方法的个数小于数据结构有哪些或等于容器的⻓度的时候，又测试英文啥也不干。

最终else分支：

2倍扩容，且不超过MAX_CACHE_SIZE（容器的最大⻓度为 1<<16，见前一张图）。这里reallocate(oldCapacity, capacity, true);传了true，方法就会释放旧bucket_t。里面的架构师内容就不存在了，这就解释了扩容后，之前缓存的方法不存在了。

综合上面的代码的出来的结论就是：

在arm64结构，也就是真机环境下，缓存方法的容器初始⻓度2，大于7/8扩容。注意，当容器的⻓度小于8时，只有满容量了才可能大于7/8，所以测试工程师系统在架构图怎么制作容量小于8的情况下，是存满测试你适合学心理学吗才扩容。
在x86_64架构下，缓存方法的容器初始⻓度4，大于等于3/4扩容。容器只能存储(容器⻓度 * 3/4 - 1)个方法。

接测试工程师下来的部分代码就是插入数据。

缓存的插入

回到开始时testInstancePrint方法找不到的问题；testInstancePrint在responseTo源码编辑器下载Selector和class方法之前调用；class来的时候，因为扩容，旧的bucket_t被释放了；前面的方法位置就变了。

验证：容器技术既然要往cache里插入数据，必然会调用insert方法；修改代码打印方法源码时代名：

void cache_t::insert(SEL sel, IMP imp, id receiver)
{
    printf("%sn", sel_getName(sel));
    ...
}

运行方法之容器设计后，打印一下此时的class，这时候才插入了2个方法；

既然cache占16字节，如果方法太多了呢？因为存放的只是首地址，具体内容在buckets()里。

通过掩码返回容器首地址：

struct bucket_t *cache_t::buckets() const
{
    uintptr_t addr = _bucketsAndMaybeMask.load(memory_order_relaxed);
    return (bucket_t *)(addr & bucketsMask);
}
// bucketsMask
static constexpr uintptr_t bucketsMask = ~0ul;

扩容测试

模仿类和cache的数据结构，方便写代码读取:


#import <UIKit/UIKit.h>
#import "AppDelegate.h"
#import <objc/message.h>
#import "FFGoods.h"
typedef uint32_t mask_t;  // x86_64 & arm64 asm are less efficient
// preopt_cache_entry_t
struct ff_preopt_cache_entry_t {
    uint32_t sel_offs;
    uint32_t imp_offs;
};
//preopt_cache_t
struct ff_preopt_cache_t {
    int32_t  fallback_class_offset;
    union {
        struct {
            uint16_t shift       :  5;
            uint16_t mask        : 11;
        };
        uint16_t hash_params;
    };
    uint16_t occupied    : 14;
    uint16_t has_inlines :  1;
    uint16_t bit_one     :  1;
    struct ff_preopt_cache_entry_t entries;
    inline int capacity() const {
        return mask + 1;
    }
};
// bucket_t
struct ff_bucket_t {
    IMP _imp;
    SEL _sel;
};
// cache_t
struct ff_cache_t {
    uintptr_t _bucketsAndMaybeMask; // 8
    struct ff_preopt_cache_t _originalPreoptCache; // 8
    // _bucketsAndMaybeMask is a buckets_t pointer in the low 48 bits
    // _maybeMask is unused, the mask is stored in the top 16 bits.
    // 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;
    static constexpr uintptr_t preoptBucketsMarker = 1ul;
    // 63..60: hash_mask_shift
    // 59..55: hash_shift
    // 54.. 1: buckets ptr + auth
    //      0: always 1
    static constexpr uintptr_t preoptBucketsMask = 0x007ffffffffffffe;
    ff_bucket_t *buckets() {
        return (ff_bucket_t *)(_bucketsAndMaybeMask & bucketsMask);
    }
    uint32_t mask() const {
        return _bucketsAndMaybeMask >> maskShift;
    }
};
// class_data_bits_t
struct ff_class_data_bits_t {
    uintptr_t objc_class;
};
// objc_class
struct ff_objc_class {
    Class isa;
    Class superclass;
    struct ff_cache_t cache;
    struct ff_class_data_bits_t bits;
};

测试思路：

给自定义的类生成30个方法，模拟调用；

扩容后第一次插入方法，数量只有1。打数据结构严蔚敏印此时的长度。

void test(Class cls) {
    // 将cls的类型转换成自定义的源码ff_objc_class类型，方便后续操作
    struct ff_objc_class *pClass = (__bridge struct ff_objc_class *)(cls);
    struct ff_cache_t cache = pClass->cache;
    struct ff_preopt_cache_t origin = cache._originalPreoptCache;
    uintptr_t mask = cache.mask();
    // 扩容后第一次插入方法数量只有1
    if (origin.occupied == 1) {
        NSLog(@"buckets已缓存方法的个数 = %u, buckets的长度 = %lu", origin.occupied, mask + 1);
    }
}

运行：

可以看到几次触发扩容的log。

总结

方法的缓存基于不同架构容器对桌面的压强怎么算，缓存策略是不一样的。

bucket_t结构体存储方法必备的架构师工资sel和imp，并用数组容器存储。在cache_t结构体中，通过bucket()方法返回元素首地址。容器初始长度在arm64架构下为2，在x84_64架构下为4。
扩容条件：在arm64架构下容量小于8，存满才扩容，大于8时，数量大于7/8扩容。在x86_64架构下，都是大于等于3/4。
扩容按照2倍原大小进行，最大⻓度为 1<<16 = 0x10000。扩源码中的图片容之后，之前的方法缓存被数据结构题库清空（内存被释放）。
为什么要释放旧的内存 ? 扩容是按照2倍进行的，如果不释放，随着扩容次数增加，遗留的无用内存也不少。

iOS底层-类的三顾茅庐（三）

前言

cache的探索

方法缓存的结构体

解决哈希冲突

cache的扩容

缓存的插入

扩容测试

总结

作者信息

iOS底层-类的三顾茅庐（三）

前言

cache的探索

方法缓存的结构体

解决哈希冲突

cache的扩容

缓存的插入

扩容测试

总结

相关文章

Hi，这是一个普通Android开发的2021小结

性能测试，这些被你忽略了吗？

ChatGPT全球最大开源平替：回复更受欢迎，但中文对话一塌糊涂

【面试】数据结构与算法(十三)

作者信息