NSCache源码阅读与分析

NSCache

NSCache一个可变集合，用于临时存储在资源不足时可能被收回的临时键值对。 NSCache的特点：

• 使用方便，类似字典，但与字典不同

• 线程安全

• 可以设置最大限额和最大数量，内存不足时，NSCache会自动释放存储对象

• NSCache是Key-Value数据结构，其中key是强引用，不实现NSCoping协议，作为key的对象不会被拷贝

• NSDiscardableContent 可以改进缓存回收行为

基于GNUstep源码探索NSCache

GNUstep下载地址github.com/gnustep

打开源码，在headers/Foundation下找到NSCache.h文件

@interface GS_GENERIC_CLASS(NSCache, KeyT, ValT) : NSObject
{
#if GS_EXPOSE(NSCache)
  @private
  NSUInteger _costLimit;//缓存的最大开销，所有对象的内存加起来
  NSUInteger _totalCost;// 当前储存的对象的总开销
  NSUInteger _countLimit;// 缓存对象的最大数量
  /** The delegate object, notified when objects are about to be evicted. */
  id _delegate;
  BOOL _evictsObjectsWithDiscardedContent;//表示是否应该回收废弃内容的标志,默认YES
  NSString *_name;//缓存的名字
  NSMapTable *_objects;//对象的名字与对象的映射, 跟字典很相似，下文会分析
  /** LRU ordering of all potentially-evictable objects in this cache. */
  GS_GENERIC_CLASS(NSMutableArray, ValT) *_accesses;//缓存中可回收对象的LRU算法排序，将按此排序来释放对象
  int64_t _totalAccesses;// 当前对象的总访问次数
  - (NSUInteger) countLimit;
  - (void) setCountLimit: (NSUInteger)lim;
  - (NSUInteger) totalCostLimit;
  - (void) setTotalCostLimit: (NSUInteger)lim;

外界能给开发者使用的只有_countLimit,totalCostLimit和_evictsObjectsWithDiscardedConten

NSMapTable解析

/** Return a map table initialised using the specified options for
 * keys and values.
 */
+ (instancetype) mapTableWithKeyOptions: (NSPointerFunctionsOptions)keyOptions
                           valueOptions: (NSPointerFunctionsOptions)valueOptions;
/** Initialiser using option bitmasks to describe the keys and values.
 */
- (instancetype) initWithKeyOptions: (NSPointerFunctionsOptions)keyOptions
                       valueOptions: (NSPointerFunctionsOptions)valueOptions
                           capacity: (NSUInteger)initialCapacity;

/** Initialiser using full pointer function information to describe
 * the keys and values.
 */
- (instancetype) initWithKeyPointerFunctions: (NSPointerFunctions*)keyFunctions
                       valuePointerFunctions: (NSPointerFunctions*)valueFunctions
                                    capacity: (NSUInteger)initialCapacity;

• NSMapTable 有两个指定初始化方法和一个便捷初始化方法
• 初始化方法的参数keyOptions和valueOptions，都是NSPointerFunctionsOptions类型，点进去可以看到它是一个枚举类型

enum {
  NSPointerFunctionsStrongMemory = (0<<0),//常用 强引用存储对象
  NSPointerFunctionsZeroingWeakMemory = (1<<0),
  NSPointerFunctionsOpaqueMemory = (2<<0),
  NSPointerFunctionsMallocMemory = (3<<0),
  NSPointerFunctionsMachVirtualMemory = (4<<0),
  NSPointerFunctionsWeakMemory = (5<<0),//常用 弱引用存储对象
  NSPointerFunctionsObjectPersonality = (0<<8),
  NSPointerFunctionsOpaquePersonality = (1<<8),
  NSPointerFunctionsObjectPointerPersonality = (2<<8),
  NSPointerFunctionsCStringPersonality = (3<<8),
  NSPointerFunctionsStructPersonality = (4<<8),
  NSPointerFunctionsIntegerPersonality = (5<<8),
  NSPointerFunctionsCopyIn = (1<<16)//常用 copy存储对象
}; 
typedef NSUInteger NSPointerFunctionsOptions;

• 常用的枚举值是
  • NSPointerFunctionsStrongMemory: 强引用存储对象
  • NSPointerFunctionsWeakMemory: 弱引用存储对象
  • NSPointerFunctionsCopyIn：copy存储对象

NSDcitionary或者NSMutableDictionary中对于key和value的内存管理是，对key进行copy，对value进行强引用，只有满足NSCopying协议的对象才能成为key值。

NSMaptable可以通过弱引用来持有keys和values，所以当key或者value被deallocated的时候，所存储的实体也会被移除

然后来到NSCache.m

@interface _GSCachedObject : NSObject
{
  @public
  id object;                // 对象
  NSString *key;        // 键值
  int accessCount;  // 当前对象的访问次数  LRU算法排序的计数
  NSUInteger cost;  // 开销
  BOOL isEvictable; // 是否应该被释放
}
@end

然后找到NSCache到初始化方法

- (id) init
{
  if (nil == (self = [super init]))
    {
      return nil;
    }
  ASSIGN(_objects,[NSMapTable strongToStrongObjectsMapTable]);
  _accesses = [NSMutableArray new];//可变数组存储LRU算法排序的计数
  return self;
}
+ (id) strongToStrongObjectsMapTable
{
  return [self mapTableWithKeyOptions: NSPointerFunctionsObjectPersonality
                         valueOptions: NSPointerFunctionsObjectPersonality];
}
  /** Use the -hash and -isEqual: methods for storing objects, and the
   * -description method to describe them. */
  NSPointerFunctionsObjectPersonality = (0<<8),

• 可以看到NSCache初始化的时候使用strongToStrongObjectsMapTable创建的objects，然后去查看strongToStrongObjectsMapTable这个创建方法，里面key和value都是NSPointerFunctionsObjectPersonality这个枚举类型
• NSCache的key会强引用缓存对象，作为key的对象不会被拷贝, 不会被拷贝意味着添加缓存对象的时候是0消耗的

缓存方法解析

直接来到NSCache.m，看看设置缓存对象的方法

- (void) setObject: (id)obj forKey: (id)key cost: (NSUInteger)num
{
  _GSCachedObject *oldObject = [_objects objectForKey: key];//上文中有GSCachedObject的定义
  _GSCachedObject *newObject;

  if (nil != oldObject)//判断之前是否储存了相同key值的对象，有则移除旧对象
    {
      [self removeObjectForKey: oldObject->key];
    }
  [self _evictObjectsToMakeSpaceForObjectWithCost: num];//NSCache的自动回收内存算法
  newObject = [_GSCachedObject new];
  newObject->object = RETAIN(obj); //强引用对象
  newObject->key = RETAIN(key);      //强引用key
  newObject->cost = num;
  if ([obj conformsToProtocol: @protocol(NSDiscardableContent)])
    {//判断是否实现了NSDiscardableContent协议，实现了就把它加到lru排序的这个可变数组_accesses里
      newObject->isEvictable = YES;
      [_accesses addObject: newObject];
    }
  [_objects setObject: newObject forKey: key];
  RELEASE(newObject);
  _totalCost += num;//更新总开销
}

• 首先判断是否有旧对象，如果有则调用removeObjectForKey移除
• 接下来做了缓存淘汰[self _evictObjectsToMakeSpaceForObjectWithCost: num]
• 点进去看看是如何实现缓存淘汰算法的（以下方法内容比较多，请仔细阅读）

- (void)_evictObjectsToMakeSpaceForObjectWithCost: (NSUInteger)cost
{
  NSUInteger spaceNeeded = 0; //需要清除的空间
  NSUInteger count = [_objects count];

  if (_costLimit > 0 && _totalCost + cost > _costLimit)
    {
      spaceNeeded = _totalCost + cost - _costLimit;//计算需要清除的空间
    }

  // 需要清除空间才需要执行以下代码
  if (count > 0 && (spaceNeeded > 0 || count >= _countLimit))
    {
      NSMutableArray *evictedKeys = nil;
    // _totalAccesses / (double)count 总访问次数/缓存对象个数 = 平均访问次数
      NSUInteger averageAccesses = ((_totalAccesses / (double)count) * 0.2) + 1;//计算平均访问次数 关键公式
      NSEnumerator *e = [_accesses objectEnumerator];//获取LRU算法排序后的对象数组
      _GSCachedObject *obj;

      if (_evictsObjectsWithDiscardedContent)//NSCache是否自动回收废弃内容
  {
        evictedKeys = [[NSMutableArray alloc] init];//自动回收则创建evictedKeys，用来存放可回收对象
    }
    
      while (nil != (obj = [e nextObject]))//按LRU排序后的对象数组遍历对象
    {
      // 如果对象的访问次数小于平均访问次数，
      if (obj->accessCount < averageAccesses && obj->isEvictable)
        {
          [obj->object discardContentIfPossible];//标识这个对象是可销毁的，如果计数变量为0时将会释放这个对象
          if ([obj->object isContentDiscarded])
        {
          NSUInteger cost = obj->cost;
          obj->cost = 0;
          obj->isEvictable = NO;
          if (_evictsObjectsWithDiscardedContent)//查看对象是否可回收 可回收则加入可回收数组
            {
              [evictedKeys addObject: obj->key];
            }
          _totalCost -= cost;//当前总开销 减去 已经释放的开销
          if (cost > spaceNeeded)// 释放开销大于需要清除空间时则退出循环
            {
              break;
            }
          spaceNeeded -= cost; //需要清除空间 减去 已经释放的开销
        }
        }
    }
      if (_evictsObjectsWithDiscardedContent)
    {//如果NSCache自动回收废弃内容，则将需自动回收数组的对象都回收
      NSString *key;
      e = [evictedKeys objectEnumerator];
      while (nil != (key = [e nextObject]))
        {
          [self removeObjectForKey: key];//回收对象以后，将对应Key移除
        }
    }
    [evictedKeys release];
    }
}

从以上源码分析，我们可以知道NSCache的自动回收机制的实现是依赖于lru算法的，每当NSCache超出限额需要释放空间时，系统就会按照LRU算法排序后的缓存对象数组进行遍历，通过公式算出平均访问次数，只要缓存对象的访问次数小于平均访问次数就将该缓存对象放进可回收数组中，当释放开销大于需要清除空间时则退出遍历循环，释放可回收对象。

LRU 最少最近使用算法 ，缓存替换时总是替换最少最近使用的对象，保留最近使用的对象。

参考资料：NSCache OC及Swift底层源码详解 - 掘金 (juejin.cn)