1.前言
- NSCache是蘋果提供的一個用于內(nèi)存緩存的工具财破;我們可以看到一些優(yōu)秀的三方框架(例如:SDWebImage)也會用到這個類橄唬;
- 通過閱讀GNU的源碼匹中,了解到它內(nèi)部是有用到LRU、LFU這些淘汰算法來處理當內(nèi)存達到設定的閥值的時候去自動淘汰掉數(shù)據(jù)
補充2個概念
- LRU
Least Recently Used的縮寫焰宣,即最近最少使用七蜘,是一種常用的數(shù)據(jù)置換算法保檐,選擇最近最久未使用的數(shù)據(jù)予以淘汰
- LFU
Least Frequently Used,最不經(jīng)常使用策略,在一段時間內(nèi),數(shù)據(jù)被使用頻次最少的,優(yōu)先被淘汰
本文就跟大家一起通過源碼和例子來學習內(nèi)部是如何實現(xiàn)的;GNU的源碼實現(xiàn)不一定就是Foundation中的真實實現(xiàn)崔梗,不過還是有學習的參考價值的
2.基本使用
2.1 我們設置一個countLimit為5的cache,查看當元素超過限制之后的表現(xiàn)
@interface NSCacheTest () <NSCacheDelegate>
@property (nonatomic, strong) NSCache *memoryCache;
@end
@implementation NSCacheTest
- (instancetype)init {
self = [super init];
if (self) {
_memoryCache = [[NSCache alloc] init];
_memoryCache.countLimit = 5;
_memoryCache.totalCostLimit = 1024;
_memoryCache.delegate = self;
}
return self;
}
- (void)test {
[self testOverlimit];
}
#pragma mark - NSCacheDelegate
- (void)cache:(NSCache *)cache willEvictObject:(id)obj {
// 我們設置了代理垒在,當有對象要被淘汰掉的時候就會觸發(fā)該代理函數(shù)蒜魄,通過打印我們來看數(shù)據(jù)是怎么被淘汰的
NSLog(@"willEvictObject = %@", obj);
}
#pragma mark - Private Method
- (void)testOverlimit {
NSInteger loopCount = 10;
for (NSInteger i = 0; i < loopCount; i++) {
NSString *urlString = [NSString stringWithFormat:@"https://www.test.%ld", (long)i];
NSURL *obj = [NSURL URLWithString:urlString];
[self.memoryCache setObject:obj forKey:@(i).stringValue];
}
// loopCount == 10的時候當執(zhí)行之后會輸出:
// RuntimeLearning[19309:858051] willEvictObject = https://www.test.0
// RuntimeLearning[19309:858051] willEvictObject = https://www.test.1
// RuntimeLearning[19309:858051] willEvictObject = https://www.test.2
// RuntimeLearning[19309:858051] willEvictObject = https://www.test.3
// RuntimeLearning[19309:858051] willEvictObject = https://www.test.4
// 可以看到先加入cache的元素被移除了
[self logAllCachedData];
/*
RuntimeLearning[19858:902352] (
"https://www.test.5",
"https://www.test.6",
"https://www.test.7",
"https://www.test.8",
"https://www.test.9"
)
*/
// 清除數(shù)據(jù)
[self.memoryCache removeAllObjects];
}
- 我們設置了代理
_memoryCache.delegate = self
,當有對象要被淘汰掉的時候就會觸發(fā)代理函數(shù)- (void)cache:(NSCache *)cache willEvictObject:(id)obj
场躯,通過打印我們來看數(shù)據(jù)是怎么被淘汰的 - 我們發(fā)現(xiàn)當cache中添加的元素個數(shù)大于countLimit的時候谈为,就會淘汰掉數(shù)據(jù);并且看到是先加入的數(shù)據(jù)先被淘汰了踢关,輸出結(jié)果可參照代碼中的打印信息伞鲫,有點那個先進先出的意思
2.2 真機調(diào)試時app切換到后臺看看表現(xiàn)
-
打個符號斷點
圖片.png -
app切換到后臺
圖片.png
看到退到后臺之后,cache清空了數(shù)據(jù)
3.LRU
優(yōu)先淘汰最近最久未使用的
// 最近未使用原則
- (void)checkIfHasLRU {
NSInteger loopCount = 5;
for (NSInteger i = 0; i < loopCount; i++) {
NSString *urlString = [NSString stringWithFormat:@"https://www.test.%ld", (long)i];
NSURL *obj = [NSURL URLWithString:urlString];
[self.memoryCache setObject:obj forKey:@(i).stringValue];
}
[self.memoryCache objectForKey:@"0"];
[self.memoryCache objectForKey:@"3"];
[self logAllCachedData];
NSString *urlString = @"https://www.test.6";
NSURL *obj = [NSURL URLWithString:urlString];
[self.memoryCache setObject:obj forKey:@"6"];
// RuntimeLearning[19541:877142] willEvictObject = https://www.test.1
NSString *urlString1 = @"https://www.test.7";
NSURL *obj1 = [NSURL URLWithString:urlString1];
[self.memoryCache setObject:obj1 forKey:@"7"];
// RuntimeLearning[19541:877142] willEvictObject = https://www.test.2
// RuntimeLearning[19541:877142] willEvictObject = https://www.test.2
NSString *urlString2 = @"https://www.test.8";
NSURL *obj2 = [NSURL URLWithString:urlString2];
[self.memoryCache setObject:obj2 forKey:@"8"];
// RuntimeLearning[19541:877142] willEvictObject = https://www.test.4
// 清除數(shù)據(jù)
[self.memoryCache removeAllObjects];
}
- 我們通過調(diào)用
objectForKey
來使用cache中的數(shù)據(jù)签舞;這樣本來最先插入的key為0的數(shù)據(jù)就不是最近未使用的了
[self.memoryCache objectForKey:@"0"];
[self.memoryCache objectForKey:@"3"];
- 此時我們向cache中加入數(shù)據(jù)秕脓,發(fā)現(xiàn)跟一開始打印的不一樣,key為0的沒有被淘汰儒搭,而是key為1的數(shù)據(jù)被淘汰了
NSString *urlString = @"https://www.test.6";
NSURL *obj = [NSURL URLWithString:urlString];
[self.memoryCache setObject:obj forKey:@"6"];
//輸出: RuntimeLearning[19541:877142] willEvictObject = https://www.test.1
4.LFU
最不經(jīng)常使用淘汰策略
// 最不經(jīng)常使用原則
- (void)checkIfHasLFU {
NSInteger loopCount = 5;
for (NSInteger i = 0; i < loopCount; i++) {
NSString *urlString = [NSString stringWithFormat:@"https://www.test.%ld", (long)i];
NSURL *obj = [NSURL URLWithString:urlString];
[self.memoryCache setObject:obj forKey:@(i).stringValue];
}
[self.memoryCache objectForKey:@"1"];
[self.memoryCache objectForKey:@"1"];
[self.memoryCache objectForKey:@"3"];
[self.memoryCache objectForKey:@"3"];
[self.memoryCache objectForKey:@"4"];
[self.memoryCache objectForKey:@"0"];
[self logAllCachedData];
/*
RuntimeLearning[19795:898814] (
"https://www.test.2",
"https://www.test.0",
"https://www.test.3",
"https://www.test.1",
"https://www.test.4"
)
*/
NSString *urlString = @"https://www.test.6";
NSURL *obj = [NSURL URLWithString:urlString];
[self.memoryCache setObject:obj forKey:@"6"];
// RuntimeLearning[19628:885142] willEvictObject = https://www.test.2
NSString *urlString1 = @"https://www.test.7";
NSURL *obj1 = [NSURL URLWithString:urlString1];
[self.memoryCache setObject:obj1 forKey:@"7"];
// RuntimeLearning[19628:885142] willEvictObject = https://www.test.4
NSString *urlString2 = @"https://www.test.8";
NSURL *obj2 = [NSURL URLWithString:urlString2];
[self.memoryCache setObject:obj2 forKey:@"8"];
// RuntimeLearning[19628:885142] willEvictObject = https://www.test.0
NSString *urlString3 = @"https://www.test.9";
NSURL *obj3 = [NSURL URLWithString:urlString3];
[self.memoryCache setObject:obj3 forKey:@"9"];
// RuntimeLearning[19628:885142] willEvictObject = https://www.test.6
// 這里看起來好像使用頻次的優(yōu)先級會高于最近使用
}
- 我們通過控制調(diào)用
objectForKey
的次數(shù)吠架,來實現(xiàn)元素的使用次數(shù)的不同,這里key為1搂鲫、3的使用次數(shù)為2傍药,key為4、0的使用次數(shù)為1
[self.memoryCache objectForKey:@"1"];
[self.memoryCache objectForKey:@"1"];
[self.memoryCache objectForKey:@"3"];
[self.memoryCache objectForKey:@"3"];
[self.memoryCache objectForKey:@"4"];
[self.memoryCache objectForKey:@"0"];
- 此時向cache中添加元素,看淘汰的現(xiàn)象拐辽;可以看到key為2沒有使用它最先被淘汰了拣挪,其次開始淘汰了使用一次的key為4、0的
NSString *urlString = @"https://www.test.6";
NSURL *obj = [NSURL URLWithString:urlString];
[self.memoryCache setObject:obj forKey:@"6"];
// RuntimeLearning[19628:885142] willEvictObject = https://www.test.2
NSString *urlString1 = @"https://www.test.7";
NSURL *obj1 = [NSURL URLWithString:urlString1];
[self.memoryCache setObject:obj1 forKey:@"7"];
// RuntimeLearning[19628:885142] willEvictObject = https://www.test.4
NSString *urlString2 = @"https://www.test.8";
NSURL *obj2 = [NSURL URLWithString:urlString2];
[self.memoryCache setObject:obj2 forKey:@"8"];
// RuntimeLearning[19628:885142] willEvictObject = https://www.test.0
- 至此繼續(xù)添加元素俱诸,本來以為是會把使用次數(shù)為2的元素淘汰菠劝,結(jié)果發(fā)現(xiàn)是新加入的元素被淘汰了;這里看起來使用頻次高的數(shù)據(jù)優(yōu)先級會高于最近未使用的
NSString *urlString3 = @"https://www.test.9";
NSURL *obj3 = [NSURL URLWithString:urlString3];
[self.memoryCache setObject:obj3 forKey:@"9"];
// RuntimeLearning[19628:885142] willEvictObject = https://www.test.6
// 這里看起來好像使用頻次的優(yōu)先級會高于最近使用
5. GNU源碼分析
被緩存的對象內(nèi)部結(jié)構
我們緩存對象的時候乙埃,內(nèi)部會封裝成一個_GSCachedObject
的對象闸英,記錄了對象的大小、key介袜、使用次數(shù)等信息
/**
* _GSCachedObject is effectively used as a structure containing the various
* things that need to be associated with objects stored in an NSCache. It is
* an NSObject subclass so that it can be used with OpenStep collection
* classes.
*/
@interface _GSCachedObject : NSObject
{
// 內(nèi)部存儲的數(shù)據(jù)結(jié)構
@public
id object; // 緩存的對象
NSString *key; // 緩存的對象的key
int accessCount; // 實現(xiàn)LFU 全稱是:Least Frequently Used,最不經(jīng)常使用策略,在一段時間內(nèi),數(shù)據(jù)被使用頻次最少的,優(yōu)先被淘汰
NSUInteger cost; // 對象的大小
BOOL isEvictable; // 對象能否被收回
}
@end
-
int accessCount
實現(xiàn)LFU 甫何,當我們通過objectForKey
訪問某個key對于的數(shù)據(jù)時,這個值會++
如何實現(xiàn)LRU
- 初始化的時候遇伞,內(nèi)部會初始化一個可變數(shù)組
_accesses
- (id) init
{
if (nil == (self = [super init]))
{
return nil;
}
ASSIGN(_objects,[NSMapTable strongToStrongObjectsMapTable]);
_accesses = [NSMutableArray new]; // 實現(xiàn)LRU辙喂;每次添加新的都放到數(shù)組的尾部,當需要刪除的時候從頭開始遍歷鸠珠,當使用了對象的時候[objectForKey:]則先將數(shù)據(jù)刪除再添加到數(shù)組的尾部;
return self;
}
- 當調(diào)用
objectForKey
的時候巍耗,這個時候元素的使用狀態(tài)就變化了;這里的做法就是把用到的元素從_accesses
中移除渐排,然后在添加到數(shù)組的尾部炬太;同時可以看到這里也對緩存對象的accessCount
和一個記錄總使用次數(shù)的_totalAccesses
做了++操作;
- (id) objectForKey: (id)key
{
_GSCachedObject *obj = [_objects objectForKey: key];
if (nil == obj)
{
return nil;
}
if (obj->isEvictable)
{
// Move the object to the end of the access list.
[_accesses removeObjectIdenticalTo: obj];
[_accesses addObject: obj];
}
obj->accessCount++;
_totalAccesses++;
return obj->object;
}
- 當我們向緩存中增加數(shù)據(jù)的時候驯耻,如果超過限制了就會觸發(fā)淘汰數(shù)據(jù)的方法
- (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;
}
可以看到做數(shù)據(jù)淘汰的關鍵函數(shù)就是_evictObjectsToMakeSpaceForObjectWithCost
- (void)_evictObjectsToMakeSpaceForObjectWithCost: (NSUInteger)cost
{
NSUInteger spaceNeeded = 0;
NSUInteger count = [_objects count];
// 判斷是否需要釋放空間【超過了內(nèi)存限制】
if (_costLimit > 0 && _totalCost + cost > _costLimit)
{
spaceNeeded = _totalCost + cost - _costLimit;
}
// Only evict if we need the space. 當個數(shù)超出限制或者空間超限制的時候就需要需釋放
if (count > 0 && (spaceNeeded > 0 || count >= _countLimit))
{
NSMutableArray *evictedKeys = nil;
// Round up slightly.
NSUInteger averageAccesses = (_totalAccesses / count * 0.2) + 1; // 計算平均使用次數(shù)亲族,用于LFU規(guī)則
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;當滿足空間需要之后就退出循環(huán)
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];
}
}
其中遍歷的時候用的是NSEnumerator *e = [_accesses objectEnumerator]
,上面我們分析了由于新訪問的數(shù)據(jù)會被加到數(shù)組的尾部可缚,那么在淘汰的時候從前到后遍歷霎迫,淘汰的數(shù)據(jù)就是越久遠未被使用的數(shù)據(jù)了,那么就實現(xiàn)了LRU
如何實現(xiàn)LFU
- 被緩存對象的accessCount記錄了對象被訪問的次數(shù)
- _totalAccess記錄了緩存的對象的總訪問次數(shù)
分析_evictObjectsToMakeSpaceForObjectWithCost
函數(shù)發(fā)現(xiàn)有個
平均使用次數(shù)averageAccesses
帘靡;定義如下:
NSUInteger averageAccesses = (_totalAccesses / count * 0.2) + 1; // 計算平均使用次數(shù)知给,用于LFU規(guī)則
那么就很清晰了,內(nèi)部得到平均使用次數(shù)描姚,然后拿對象的使用次數(shù)跟這個平均值做比較涩赢,就能達到優(yōu)先淘汰使用不頻繁的數(shù)據(jù)了;代碼實現(xiàn)如下:
while (nil != (obj = [e nextObject]))
{
// Don't evict frequently accessed objects.不頻繁使用并且沒有標記為可收回
if (obj->accessCount < averageAccesses && obj->isEvictable)
{
}
}
到這里我們基本學習了代碼的整體實現(xiàn)了轩勘。
6. 總結(jié)
- GNU的源碼可以發(fā)現(xiàn)谒主,他實現(xiàn)LRU用的是數(shù)組,當然也可以使用鏈表赃阀;可以參照YYMemoryCache的實現(xiàn)
- NSCache內(nèi)部是沒有做收到內(nèi)存警告就清除數(shù)據(jù)的邏輯霎肯;我們看SDWebImage內(nèi)部內(nèi)存緩存也用的NSCache擎颖,但加了個收到內(nèi)存警告的通知;處理內(nèi)存警告的時候移除掉內(nèi)存緩存的內(nèi)容
- NSCache主要是做內(nèi)存緩存观游,假如做多級緩存比如:內(nèi)存+本地的方式搂捧,當內(nèi)存警告時,如果移除了內(nèi)存中的數(shù)據(jù)懂缕,那么下次讀緩存的時候允跑,就會觸發(fā)磁盤讀數(shù)據(jù)了;關于這一點的優(yōu)化也可以參照SDWebImage的weakCache搪柑。