[Swift/Objc] NSCache 클래스 분석하기(feat. objc 문법 이해해보기)

최근에 이미지 캐싱 기능을 라이브러리 없이 구현해보고자 여러 레퍼런스들을 분석중이었습니다.

Swift에서 캐싱을 위해 제공하는 기본적인 API로 NSCache가 존재합니다. 공식 문서를 보면 NSCache는 count 및 cost를 통해 object를 관리하는 caching policy를 제공한다고 합니다.

 

이 클래스는 Foundation Framework에 속하기 때문에, apple이 2023년부터 github에 공개한 Foundation framework의 swift implemetation을 확인 가능합니다. 다른 방식의 구현을 확인하고 싶다면, GNUStep Base Libary를 확인할 수 있습니다.

 

GNUstep is a mature Framework, suited both for advanced GUI desktop applications as well as server applications. The framework closely follows Apple's Cocoa (formerly NeXT's OpenStep) APIs but is portable to a variety of platforms and architectures.

 

GNUStep이란 window, linux의 다양한 환경에서 apple의 Cocoa API와 같이 개발할 수 있도록 하는 오픈 소스 프로젝트입니다. objc 언어를 이용하여 프로그래밍이 가능하도록, 애플 API의 외형(public interface)를 GNUStep 프로젝트에서 직접 구현했다고 하네요. 즉, Foundation Framework의 여러 클래스 및 인터페이스를 사용 가능하지만, 실제 그 구현까지 같지는 않다고 합니다. 그러나 여러 방식의 구현을 분석해 보는 것이 도움이 되니 GNUStep의 NSCache도 확인해 보려고 합니다.

 

Caching에 필요한 요소는 다양하게 존재하지만, 그 중에서도 동시성 처리와 Caching Policy에 관련한 부분이 핵심이라고 생각합니다. 따라서 Objc로 작성된 NSCache 클래스를 분석해보며, 사용된 동시성 처리 방법과 caching policy에 대해 알아보겠습니다. 또한 GNUSteps의 NSCache는 objc 코드를 처음 분석하는 것이기 때문에 문법에 대해서도 천천히 정리해보겠습니다.

Apple's NSCache

우선 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

    public override init() {}
    
    open weak var delegate: NSCacheDelegate?
    
    ...
}

 

1. _entries

Dictionary 타입으로 NSCacheKey를 Key로 하여 NSCacheEntry를 가져오도록 합니다.

위의 두 타입에 대해서는 뒤에 다루겠습니다.

2. lock

스레드 안전성 확보를 위해 NSLock을 가집니다.

3. totalCost

NSCache가 가진 object들의 전체 cost를 확인하기 위한 변수입니다.

4. head

양방향 연결 리스트 형태인 NSCacheEntry의 head를 가지고 있습니다.

5. 기타

그 외에 Caching을 위한 limit을 설정할 수 있는 변수, 이름을 설정하는 변수를 가집니다.

6. delegate

필요한 경우 object가 제거되기 전에 delegate를 통해 특정 행동을 수행할 수 있도록 합니다.

 

NSCacheEntry

Cache에 저장될 Value의 형태입니다.

KeyType 및 ObjectType이 AnyObject를 채택하고 있어 Key와 Object 모두 클래스 타입이 되어야 함을 강제합니다.

 

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) {
        self.key = key
        self.value = value
        self.cost = cost
    }
}

 

key, value, cost를 통해 NSCacheEntry 객체를 생성할 수 있고, prevByCost와 nextByCost 프로퍼티를 가지고 있어 Cost를 기준으로 NSCacheEntry의 순서를 지정할 것임을 예측할 수 있습니다. 양방향 연결 리스트의 형태입니다.

 

만약 Caching의 Policy를 다루고 싶다면 NSCacheEntry 내부에 저장 시점, 열람 시점, hitcount 등의 변수를 추가하여 다양한 Caching Policy를 구현할 수 있을 것입니다.

 

NSCacheKey

NSCache에 저장할 Key의 타입입니다. AnyObject를 value로 받아서 생성 가능합니다.

 

fileprivate class NSCacheKey: NSObject {
    
    var value: AnyObject
    
    init(_ value: AnyObject) {
        self.value = value
        super.init()
    }
    
    override var hash: Int {
        switch self.value {
        case let nsObject as NSObject:
            return nsObject.hashValue
        case let hashable as AnyHashable:
            return hashable.hashValue
        default: return 0
        }
    }
    
    override func isEqual(_ object: Any?) -> Bool {
        guard let other = (object as? NSCacheKey) else { return false }
        
        if self.value === other.value {
            return true
        } else {
            guard let left = self.value as? NSObject,
                let right = other.value as? NSObject else { return false }
            
            return left.isEqual(right)
        }
    }
}

 

Dictionary의 Key로 사용하기 위해 hash와 isEqual를 override하고 있습니다.

 

object -> ObjectType?

key를 입력하여 Cache에 저장된 object를 가져올 수 있는 function입니다.

open func object(forKey key: KeyType) -> ObjectType? {
    var object: ObjectType?

    let key = NSCacheKey(key)

    _lock.lock()
    if let entry = _entries[key] {
        object = entry.value
    }
    _lock.unlock()

    return object
}

 

NSLock을 통해 저장된 값을 스레드 안전하게 가져오고 있습니다.

 

insert(_ entry: NSCacheEntry)

object를 저장하는 setObject를 알아보기 전에, 내부에서 호출되는 insert를 먼저 살펴보겠습니다.

 

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
        }
        
        guard entry.cost > currentElement.cost else {
            // Insert entry at the head
            entry.prevByCost = nil
            entry.nextByCost = currentElement
            currentElement.prevByCost = entry
            
            _head = entry
            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
    }

 

우선 entry를 인자로 받아서 head에 존재하는 current Element를 가져옵니다. 만약 nil이라면 cache가 비어 있는 것이기 떄문에, 새로 입력할 entry의 prev와 next도 nil처리합니다.

 

만약 cache에 내용이 존재한다면, entry의 cost와 head의 cost를 비교합니다.

entry의 cost가 더 큰 쪽이 next가 되는 식입니다.

이후 while문을 돌리면서 entry보다 더 큰 cost를 가진 object가 나올 때 까지 currentElement를 갱신해줍니다.

이후에는 연결 리스트에서 next와 prev를 교환해주는 작업이 진행됩니다.

 

결론적으로 insert를 호출하면 entry의 연결 리스트를 업데이트하며, head에는 cost가 가장 적은 entry가 저장됩니다.

 

setObjet(_ obj: objectType, forKey: KeyType, cost g: Int)

이번에는 object를 cache에 저장하는 메서드입니다. cost를 지정하지 않으면 0으로 입력되고 있습니다.

 

open func setObject(_ obj: ObjectType, forKey key: KeyType) {
    setObject(obj, forKey: key, cost: 0)
}

open func setObject(_ obj: ObjectType, forKey key: KeyType, cost g: Int) {
    let g = max(g, 0)
    let keyRef = NSCacheKey(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)
        _entries[keyRef] = entry
        insert(entry)

        costDiff = g
    }

    _totalCost += costDiff

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

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

 

setObject 메서드 내부에서는 object를 삭제하는 메서드도 실행되기 때문에, 안전한 입출력을 위해 NSLock을 이용해 Lock을 걸고 라인을 실행합니다.

 

우선 받은 key를 바탕으로 NSCacheKey를 생성하여 entries 내부에 저장되어 있는지 확인합니다.

1. 이미 저장되어 있는 경우

cost의 차이를 계산하고 차이가 존재하는 경우에는 entry의 위치를 다시 계산합니다.

2. 새로운 key인 경우

단순히 insert를 호출하여 양방향 연결 리스트를 갱신합니다.

 

이후 totalCost에 현재 entry의 cost를 더해줍니다. 이미 저장되어 있었던 경우의 diff도 반영됩니다.

 

다음은 totalCostLimit과 countLimit을 통해 기존에 존재하는 object들의 삭제 여부를 결정합니다.

totalCostLimit 또는 countLimit이 존재하는 경우, totalCost 또는 entries의 count의 차이를 계산합니다.

 

그런 다음 이 차이가 0보다 크다면 반복해서 아래의 작업을 실행합니다.

1. head에 있는 entry를 가져옵니다. 이는 현재 가장 cost가 작은 object입니다.

2. head에 entry가 존재하는 경우, 즉 cache 내부에 object가 있는 경우에 해당 object를 삭제합니다.

 

결론적으로 setObject 과정에서 용량을 확보하기 위해 가장 cost가 작은 object를 삭제합니다.

비교적 알려진 페이지 교체 알고리즘(FIFO, LRU, LFU, MFU, NUR) 중의 어느 것도 사용하지 않고 있습니다.

개인적인 생각으로는, 개발자가 cost를 부여하고 갱신하도록 하여 페이지 교체 알고리즘을 직접 구현할 수 있도록 하기 위한 방법인 것 같습니다.

예를 들어 LRU를 구현하고 싶다면 NSCache외에 새로운 Dictioanry를 만들어서 Key의 위치를 갱신하도록 할 수도 있고, LFU를 구현하고 싶다면 hitCount를 따로 저장하고 그에 따라 cost를 갱신해줄 수 있습니다.

 

그러나 NSCache의 내부 구현을 보고 이해할 수 있다면, 확장성 및 효율성을 위해 NSCache 대신에 Custom Cache Class를 만들어 구현하는 방식이 선호될 것입니다.

GNUSteps' NSCache

다음은 Apple의 public interface를 모방한 GNUSteps의 NSCache를 살펴보겠습니다. Objc를 처음 다루기 떄문에 문법 위주의 설명이 될 수 있습니다.

 

NSCache.h

Objc에서는 Swift와 다르게 클래스, 변수, 메서드의 선언을 헤더 파일에 해야 합니다. 이후 구현 부분은 .m 파일에 작성할 수 있습니다.

우선 헤더 파일을 살펴보겠습니다.

 

#ifndef __NSCache_h_GNUSTEP_BASE_INCLUDE
#define __NSCache_h_GNUSTEP_BASE_INCLUDE
#import	<GNUstepBase/GSVersionMacros.h>

#if OS_API_VERSION(MAC_OS_X_VERSION_10_6, GS_API_LATEST)

#import <Foundation/NSObject.h>

#if	defined(__cplusplus)
extern "C" {
#endif

 

우선 전처리문과 import 부분을 볼 수 있습니다. 가장 눈에 띄는 부분은 import를 통해 NSObject.h를 가져오고 있네요.

 

@class NSString;
@class NSMapTable;
@class GS_GENERIC_CLASS(NSMutableArray, ElementT);

 

이후 Foundation Framework에 존재하는 여러 Class들을 Forward Class Delaration하고 있습니다. 이렇게 하면 전체 파일을 컴파일 할 때 NSString 등의 클래스가 존재한다는 것을 알려줘서 빌드 속도가 빨라진다고 합니다. 또는 순환 참조를 피할 수 있게 하는데, 다른 파일에서 해당 클래스를 참조하고자 할 때 import 없이 사용하도록 할 수 있습니다.

 

이후 메서드를 선언합니다.

 

@interface GS_GENERIC_CLASS(NSCache, KeyT, ValT) : NSObject

NSUInteger _costLimit;

NSUInteger _totalCost;

NSUInteger _countLimit;

id _delegate;

BOOL _evictsObjectsWithDiscardedContent;

- (NSUInteger) countLimit;

- (NSUInteger) totalCostLimit;

- (id) delegate;

- (BOOL) evictsObjectsWithDiscardedContent;

- (NSString*) name;

- (void) removeAllObjects;

- (void) removeObjectForKey: (GS_GENERIC_TYPE(KeyT))key;

- (void) setCountLimit: (NSUInteger)lim;

- (void) setDelegate: (id)del;

- (void) setEvictsObjectsWithDiscardedContent: (BOOL)b;

- (void) setName: (NSString*)cacheName;

- (void) setObject: (GS_GENERIC_TYPE(ValT))obj
            forKey: (GS_GENERIC_TYPE(KeyT))key
              cost: (NSUInteger)num;

- (void) setObject: (GS_GENERIC_TYPE(ValT))obj
            forKey: (GS_GENERIC_TYPE(KeyT))key;

- (void) setTotalCostLimit: (NSUInteger)lim;

@end

 

1. Objc에서는 @interface와 @end 사이에 클래스에 들어가는 메서드를 선언한다.

2. 메서드의 형태는 ' - ({타입}) {함수명}: ({매개변수 타입}){매개변수명} ' 이다.

3. 변수의 형태는 ' {타입} {변수명} 이다.

4. 세미콜론을 끝에 붙여야 한다.

 

전체적인 메서드를 보면, Apple에서 제공하는 NSCache의 인터페이스와 동일한 것을 알 수 있습니다.

 

NSCache.m

이제 구현 파일을 살펴보겠습니다.

 

우선 Caching에 필요한 entry가 될 gsCachedObject를 정의합니다.

 

@interface _GSCachedObject : NSObject
{
  @public
  id object;
  NSString *key;
  int accessCount;
  NSUInteger cost;
  BOOL isEvictable;
}
@end

 

위 코드를 보면 accessCount와 cost가 존재하여 LFU와 같은 알고리즘을 구현하려는 것으로 보입니다.

 

다음으로는 NSCache의 생성자입니다.

 

@implementation NSCache
- (id) init
{
  if (nil == (self = [super init]))
    {
      return nil;
    }
  ASSIGN(_objects,[NSMapTable strongToStrongObjectsMapTable]);
  _accesses = [NSMutableArray new];
  return self;
}

...

- (void) dealloc
{
  [_name release];
  [_objects release];
  [_accesses release];
  [super dealloc];
}

@end

 

 

1. 구현 부분은 @implementation과 @end 사이에 작성한다.

2. init 메서드도 기존의 함수 선언과 같이 작성하면 된다.

3. 중괄호 사이에 코드를 작성한다.

4. C 기반이기 때문에 메모리를 release하고 dealloc할 필요가 있다.

 

(void) setObject

가장 핵심이라고 할 수 있는 setObject 메서드만 살펴보겠습니다.

 

- (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);
  newObject->cost = num;
  if ([obj conformsToProtocol: @protocol(NSDiscardableContent)])
    {
      newObject->isEvictable = YES;
      [_accesses addObject: newObject];
    }
  [_objects setObject: newObject forKey: key];
  RELEASE(newObject);
  _totalCost += num;
}

 

1. 처음에는 [_objects objectForKey: Key]를 호출하여 이미 저장되어 있는 object를 가져옵니다. objc는 객체를 다룰 때 포인터를 사용하기에 *를 이용하여 포인터라는 것을 명시해야 합니다.

2. 다음으로 저장되어 있는 object가 존재한다면 해당 참조를 전달하여 removeObject를 호출합니다. objc에서는 구조체의 멤버에 접근하기 위해 '->'를 사용할 수 있습니다. oldObject->key는 oldObject의 Key라는 프로퍼티에 접근하는 것입니다.

3. 그리고 evictObjectsToMakesSpaceForObjectWithCost를 호출하여 새로운 object를 저장할 공간을 확보합니다. 이 함수는 뒤에 다루겠습니다.

4. 마찬가지로 newObject->object 새로운 object의 멤버 프로퍼티에 새로운 object들을 할당하고 있습니다.

5. 다음 부분에서는 protocol의 conformance를 확인하는 방법을 알 수 있습니다. NSDiscardableContent를 채택하고 있다면 isEvictable을 true로 전환합니다.

6. 마지막 부분에서 totalCost를 증가시킵니다.

 

마지막으로 교체 알고리즘의 핵심인 evictObjectsToMakesSpaceForObjectWithCost를 확인하겠습니다.

 

- (void)_evictObjectsToMakeSpaceForObjectWithCost: (NSUInteger)cost
{
  NSUInteger spaceNeeded = 0;
  NSUInteger count = [_objects count];

  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.
      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];
    }
}

 

1. 우선 _objects의 count를 호출합니다. 현재 저장된 object의 수를 알 수 있습니다.

2. 필요한 공간의 크기를 계산합니다.

3. 공간이 필요하다면, 방출할 object를 선정합니다.

4. averageAccessCount를 보면, 평균 접근 횟수에 0.2를 곱하고 있습니다. 이는 '접근 횟수가 낮다'의 기준이 됩니다.

5. _accesses에는 key의 접근 순서가 저장되어 있습니다. 최근에 접근한 key가 배열의 끝에 존재합니다. 이 배열을 기준으로 enumerator를 만듭니다.

6. 이제 반복문을 돌면서, 평근 접근 횟수보다 낮으며, evictable한 경우이면서, 해당 object가 버릴 수 있는 경우에 object를 evictedKeys에 등록합니다. 동시에 totalCost를 버린 object의 cost 만큼 감소시키며 해당 object의 cost가 필요 공간보다 큰 경우에는 멈춥니다. 이 경우를 충분한 공간이 확보된 것으로 판단하는 것 같습니다.

7. 마지막으로 eivctedKeys에 등록된 key들을 기준으로 실제 object들을 삭제합니다.

 

결론적으로 GNUStep의 NSCache는 LRU와 LFU의 혼합으로 구성되어 있습니다. 캐싱의 구현에서 가장 효율적이다, 라고 단언할 수 있는 정책은 없습니다. 여러 Caching 라이브러리에서도 개발자에게 다양한 선택권을 주고 있습니다. 그렇기 때문에 iOS 환경에서 여러 정책을 테스트해 보고, 가장 적절한 정책을 채택하는 것이 좋을 것입니다.