系统底层源码分析(2)——NSCache

今天来探究一下NSCache的底层原理，看看OC和Swift的缓存策略的异同。

NSCache特点：
1.使用方便，类似字典
2.线程安全
3.key不会被copy
4.自定义缓存大小，超出部分自动释放；也可手动释放，内存警告时，便需要手动释放；进入后台全部释放。

(一)NSCache —— OC

先来看个例子：

NSCache *cache = [[NSCache alloc] init];
cache.countLimit = 5;//限制
cache.delegate = self;
//添加
for (int i = 0; i < 10; i++) {
    [cache setObject:[NSString stringWithFormat:@"value%d",i] forKey:[NSString stringWithFormat:@"key%d",i]];
}
for (int i = 0; i < 10; i++) {
    NSLog(@"object:%@, index:%d", [cache objectForKey:[NSString stringWithFormat:@"key%d",i]],i);
}

//NSCacheDelegate-当添加个数超过上限时，移除数据前通知代理
- (void)cache:(NSCache *)cache willEvictObject:(id)obj{
    NSLog(@"obj:%@ will evict by Cache:%@",obj,cache);
}

1. 从GNUstep源码探究NSCache在OC中的缓存策略，先看看NSCache的结构：

@interface GS_GENERIC_CLASS(NSCache, KeyT, ValT) : NSObject
{
#if GS_EXPOSE(NSCache)
  @private
  /** The maximum total cost of all cache objects. */
  NSUInteger _costLimit;//最大缓存
  /** Total cost of currently-stored objects. */
  NSUInteger _totalCost;
  /** The maximum number of objects in the cache. */
  NSUInteger _countLimit;//最大个数
  /** The delegate object, notified when objects are about to be evicted. */
  id _delegate;
  /** Flag indicating whether discarded objects should be evicted */
  BOOL _evictsObjectsWithDiscardedContent;//标识是否实现NSDiscardableContent协议
  /** Name of this cache. */
  NSString *_name;
  /** The mapping from names to objects in this cache. */
  NSMapTable *_objects; //没有copy协议
  /** LRU ordering of all potentially-evictable objects in this cache. */
  GS_GENERIC_CLASS(NSMutableArray, ValT) *_accesses;
  /** Total number of accesses to objects */
  int64_t _totalAccesses;
#endif
#if     GS_NONFRAGILE
#else
  /* Pointer to private additional data used to avoid breaking ABI
   * when we don't have the non-fragile ABI available.
   * Use this mechanism rather than changing the instance variable
   * layout (see Source/GSInternal.h for details).
   */
  @private id _internal GS_UNUSED_IVAR;
#endif
}

NSCache同样是以key-value形式保存数据，内部使用NSMapTable保存数据。

2. 从添加入手：

@implementation NSCache
...
- (void) setObject: (id)obj forKey: (id)key
{
  [self setObject: obj forKey: key cost: 0];
}

@implementation NSCache
...
- (void) setObject: (id)obj forKey: (id)key cost: (NSUInteger)num
{
  _GSCachedObject *oldObject = [_objects objectForKey: key];
  _GSCachedObject *newObject;

  if (nil != oldObject)
    {
      [self removeObjectForKey: oldObject->key];//有旧的要移除
    }
  [self _evictObjectsToMakeSpaceForObjectWithCost: num];//缓存移除
  newObject = [_GSCachedObject new];
  // Retained here, released when obj is dealloc'd
  newObject->object = RETAIN(obj);
  newObject->key = RETAIN(key);//不是copy
  newObject->cost = num;
  if ([obj conformsToProtocol: @protocol(NSDiscardableContent)])
    {
      newObject->isEvictable = YES;//标记是否可以被移除
      [_accesses addObject: newObject];
    }
  [_objects setObject: newObject forKey: key];//添加新的
  RELEASE(newObject);
  _totalCost += num;//总大小添加
}

如果有相同的key，会先移除旧的value再添加新值。最终把数据包装成_GSCachedObject进行保存：

@interface _GSCachedObject : NSObject
{
  @public
  id object;//存储的对象
  NSString *key;//这个对象对应的key
  int accessCount;//这个对象的访问次数
  NSUInteger cost;//这个对象的内存消耗
  BOOL isEvictable;//这个对象是否能够被移除
}
@end

实现NSDiscardableContent协议的对象在不再需要时会被移除，这里便做了判断和标记：

NSDiscardableContent
当一个类的对象具有子组件，这些子组件在不使用时可以被丢弃，从而使应用程序占用更小的内存时，就可以实现这个协议。

@protocol NSDiscardableContent
@required
- (BOOL)beginContentAccess;
- (void)endContentAccess;
- (void)discardContentIfPossible;//释放内存
- (BOOL)isContentDiscarded;//判断
@end

3. 接下来进入_evictObjectsToMakeSpaceForObjectWithCost看看具体的缓存策略：

@implementation NSCache
...
- (void)_evictObjectsToMakeSpaceForObjectWithCost: (NSUInteger)cost
{       
  NSUInteger spaceNeeded = 0;
  NSUInteger count = [_objects count];
  //根据_costLimit和_countLimit移除缓存
  if (_costLimit > 0 && _totalCost + cost > _costLimit)
    {//需要移除的空间 = 总消耗的缓存空间 + 这个对象的内存消耗 - 上限
      spaceNeeded = _totalCost + cost - _costLimit;
    }

  // Only evict if we need the space.
  if (count > 0 && (spaceNeeded > 0 || count >= _countLimit))
    {
      NSMutableArray *evictedKeys = nil;
      // Round up slightly.
      //计算平均访问次数；乘0.2是因为二八定律；加1是因为返回值是NSUInteger会取整，也就是前面乘0.2取整可能为0
      NSUInteger averageAccesses = ((_totalAccesses / (double)count) * 0.2) + 1;
      NSEnumerator *e = [_accesses objectEnumerator];
      _GSCachedObject *obj;
      //将会移除少于平均访问次数的对象
      if (_evictsObjectsWithDiscardedContent)
    {
      evictedKeys = [[NSMutableArray alloc] init];
    }
      while (nil != (obj = [e nextObject]))
    {
      // Don't evict frequently accessed objects.
      if (obj->accessCount < averageAccesses && obj->isEvictable)//遍历数组，如果元素访问次数少于平均，且标记为可移除
        {
          [obj->object discardContentIfPossible];//发送消息，释放内存
          if ([obj->object isContentDiscarded])//释放完成
        {
          NSUInteger cost = obj->cost;

          // Evicted objects have no cost.
          obj->cost = 0;
          // Don't try evicting this again in future; it's gone already.
          obj->isEvictable = NO;
          // Remove this object as well as its contents if required
          if (_evictsObjectsWithDiscardedContent)
            {
              [evictedKeys addObject: obj->key];
            }
          _totalCost -= cost;
          // If we've freed enough space, give up
          if (cost > spaceNeeded)
            {
              break;
            }
          spaceNeeded -= cost;//根据大小全部移除
        }
        }
    }
      // Evict all of the objects whose content we have discarded if required
      if (_evictsObjectsWithDiscardedContent)
    {
      NSString *key;

      e = [evictedKeys objectEnumerator];
      while (nil != (key = [e nextObject]))
        {
          [self removeObjectForKey: key];//直接移除
        }
    }
    [evictedKeys release];
    }
}

• 计算出平均访问次数，当缓存大小或个数超出上限时，移除超出上限的缓存，优先把少于平均访问次数的数据移除释放。

4. 移除前会调用代理回调：

@interface _GSCachedObject : NSObject
...
- (void) removeObjectForKey: (id)key
{
  _GSCachedObject *obj = [_objects objectForKey: key];

  if (nil != obj)
    {
      [_delegate cache: self willEvictObject: obj->object];//代理回调
      _totalAccesses -= obj->accessCount;
      [_objects removeObjectForKey: key];//移除
      [_accesses removeObjectIdenticalTo: obj];
    }
}

简单来说，在OC中的NSCache进行缓存时，先移除再添加，会根据_costLimit和_countLimit的大小移除超出上限的缓存，核心是优先移除少于平均访问次数的数据。

(二)NSCache —— Swift

先来看个例子：

let cache = NSCache<AnyObject, AnyObject>.init()
cache.countLimit = 5
cache.delegate = self
for i in 0..<10 {
    cache.setObject(NSString(string: "value\(i)"), forKey:NSString(string: "key\(i)"))
}
for i in 0..<10 {
    print("object:\(cache.object(forKey: NSString(string: "key\(i)"))), index:\(i)")
}

func cache(_ cache: NSCache<AnyObject, AnyObject>, willEvictObject obj: Any) {
    print("obj:\(obj) will evict by Cache:\(cache)")
}

1. 从swift-corelibs-foundation源码探究NSCache在Swift中的缓存策略，先看看NSCache的结构：

open class NSCache<KeyType : AnyObject, ObjectType : AnyObject> : NSObject {
    
    private var _entries = Dictionary<NSCacheKey, NSCacheEntry<KeyType, ObjectType>>()//包装的类型
    private let _lock = NSLock()
    private var _totalCost = 0
    private var _head: NSCacheEntry<KeyType, ObjectType>?
    
    open var name: String = ""
    open var totalCostLimit: Int = 0 // limits are imprecise/not strict
    open var countLimit: Int = 0 // limits are imprecise/not strict
    open var evictsObjectsWithDiscardedContent: Bool = false
    ...
}

NSCache同样是以key-value形式保存数据，内部使用Dictionary保存数据。

2. 从添加入手：

open class NSCache<KeyType : AnyObject, ObjectType : AnyObject> : NSObject {
    ...
    open func setObject(_ obj: ObjectType, forKey key: KeyType) {
        setObject(obj, forKey: key, cost: 0)
    }
    ...
}

open class NSCache<KeyType : AnyObject, ObjectType : AnyObject> : NSObject {
    ...
    open func setObject(_ obj: ObjectType, forKey key: KeyType, cost g: Int) {
        let g = max(g, 0)//比较大小
        let keyRef = NSCacheKey(key)//包装key
        
        _lock.lock()//加锁操作安全
        
        let costDiff: Int
        //如果存在旧的值
        if let entry = _entries[keyRef] {
            costDiff = g - entry.cost
            entry.cost = g
            
            entry.value = obj
            
            if costDiff != 0 {
                remove(entry)//不是真正的移除
                insert(entry)//添加
            }
        } else {
            let entry = NSCacheEntry(key: key, value: obj, cost: g)//包装value
            _entries[keyRef] = entry
            insert(entry)
            
            costDiff = g
        }
        
        _totalCost += costDiff
        //淘汰策略：totalCostLimit 总大小限制
        var purgeAmount = (totalCostLimit > 0) ? (_totalCost - totalCostLimit) : 0
        while purgeAmount > 0 {
            if let entry = _head {
                delegate?.cache(unsafeDowncast(self, to:NSCache<AnyObject, AnyObject>.self), willEvictObject: entry.value)//先调用代理
                
                _totalCost -= entry.cost//总消耗 减去 当前对象的内存消耗
                purgeAmount -= entry.cost//应减去的消耗 减去 当前对象的内存消耗
                
                remove(entry) // _head will be changed to next entry in remove(_:)
                _entries[NSCacheKey(entry.key)] = nil//移除
            } else {
                break
            }
        }
        //淘汰策略：countLimit 总数量限制
        var purgeCount = (countLimit > 0) ? (_entries.count - countLimit) : 0
        while purgeCount > 0 {
            if let entry = _head {
                delegate?.cache(unsafeDowncast(self, to:NSCache<AnyObject, AnyObject>.self), willEvictObject: entry.value)//先调用代理
                
                _totalCost -= entry.cost
                purgeCount -= 1
                
                remove(entry) // _head will be changed to next entry in remove(_:)
                _entries[NSCacheKey(entry.key)] = nil//移除
            } else {
                break
            }
        }
        
        _lock.unlock()
    }
    ...
}

如果有相同的key，会先处理旧的value再添加新值。最终把key-value分别包装成NSCacheKey和NSCacheEntry进行保存：

private class NSCacheEntry<KeyType : AnyObject, ObjectType : AnyObject> {
    var key: KeyType
    var value: ObjectType
    var cost: Int
    var prevByCost: NSCacheEntry?
    var nextByCost: NSCacheEntry?
    init(key: KeyType, value: ObjectType, cost: Int) { ... }
}

fileprivate class NSCacheKey: NSObject {
    
    var value: AnyObject
    
    init(_ value: AnyObject) { ... }
    //重写方法根据类型操作
    override var hash: Int { ... }
    //重写方法根据类型操作
    override func isEqual(_ object: Any?) -> Bool { ... }
    }
}

3. 在添加缓存时，就会进行排序：

open class NSCache<KeyType : AnyObject, ObjectType : AnyObject> : NSObject {
    ...
        private func insert(_ entry: NSCacheEntry<KeyType, ObjectType>) {
        guard var currentElement = _head else {
            // The cache is empty
            entry.prevByCost = nil
            entry.nextByCost = nil
            
            _head = entry
            return
        }
        //根据cost排序；当前对象cost大于现在的节点cost时，放在前头
        guard entry.cost > currentElement.cost else {
            // Insert entry at the head
            entry.prevByCost = nil
            entry.nextByCost = currentElement
            currentElement.prevByCost = entry
            
            _head = entry//所以_head一直是最小的，而小的cost会被优先移除
            return
        }
        //否则把当前对象放到适当的位置
        while let nextByCost = currentElement.nextByCost, nextByCost.cost < entry.cost {
            currentElement = nextByCost
        }
        
        // Insert entry between currentElement and nextElement
        let nextElement = currentElement.nextByCost
        
        currentElement.nextByCost = entry
        entry.prevByCost = currentElement
        
        entry.nextByCost = nextElement
        nextElement?.prevByCost = entry
    }
    ...
}

4. 移除前会调用代理回调，移除是通过把字典对应的value置空，而remove的作用不是移除而是更新_head：

open class NSCache<KeyType : AnyObject, ObjectType : AnyObject> : NSObject {
    ...
    private func remove(_ entry: NSCacheEntry<KeyType, ObjectType>) {
        let oldPrev = entry.prevByCost
        let oldNext = entry.nextByCost
        
        oldPrev?.nextByCost = oldNext
        oldNext?.prevByCost = oldPrev
        
        if entry === _head {
            _head = oldNext//head更新
        }
    }
    ...
}

简单来说，在Swift中的NSCache进行缓存时，先添加后移除，会根据totalCostLimit和countLimit的大小移除超出上限的缓存，但没有平均访问数，而是根据cost排序，移除cost较小的数据。