YYMemoryCache是YYCache中的內(nèi)存緩存模塊,是采用了LRU算法實(shí)現(xiàn)的經(jīng)典源碼捻激。YYMemoryCache用一個(gè)字典對(duì)象來存取緩存數(shù)據(jù)季俩,當(dāng)緩存數(shù)據(jù)超過指定容量上限時(shí)吕嘀,會(huì)刪除部分緩存弯院。
1、LRU
LRU全稱是Least recently used纵潦,是一種常用的緩存淘汰算法徐鹤,遵循最近最少使用原則,當(dāng)發(fā)生內(nèi)存警告或者緩存值達(dá)到上限,會(huì)優(yōu)先淘汰時(shí)間戳靠前的對(duì)象,最近使用的不被淘汰邀层。
常見的實(shí)現(xiàn)方式是使用雙鏈表配合哈希表來存儲(chǔ)緩存數(shù)據(jù)返敬,哈希表保存key和節(jié)點(diǎn),避免了遍歷鏈表的耗時(shí)寥院,雙向鏈表控制節(jié)點(diǎn)順序劲赠,當(dāng)位置需要更改時(shí),可以直接更改節(jié)點(diǎn)秸谢,避免遍歷鏈表的耗時(shí)凛澎。
當(dāng)有新數(shù)據(jù)要緩存時(shí),先將緩存數(shù)據(jù)包裝成一個(gè)節(jié)點(diǎn)估蹄,插入雙向鏈表的頭部塑煎。如果訪問鏈表中存在該緩存數(shù)據(jù),將該數(shù)據(jù)對(duì)應(yīng)的節(jié)點(diǎn)移動(dòng)至鏈表的頭部臭蚁。這樣的做法保證了被使用的數(shù)據(jù)(存儲(chǔ)/訪問)始終位于鏈表的前部最铁。當(dāng)緩存的數(shù)據(jù)總量超出容量時(shí),先刪除末尾的緩存數(shù)據(jù)節(jié)點(diǎn)刊棕,因?yàn)槟┪驳臄?shù)據(jù)最少被使用過炭晒。
根據(jù)這個(gè)算法的原理,我們探索下YYMemoryCache的源碼實(shí)現(xiàn)
2甥角、YYMemoryCache
2.1 鏈表的實(shí)現(xiàn)
(1) _YYLinkMap
@interface _YYLinkedMap : NSObject {
@package
CFMutableDictionaryRef _dic; //哈希字典,存放緩存數(shù)據(jù)
NSUInteger _totalCost; //緩存總大小
NSUInteger _totalCount; //緩存節(jié)點(diǎn)總個(gè)數(shù)
_YYLinkedMapNode *_head; //頭結(jié)點(diǎn)
_YYLinkedMapNode *_tail; //尾結(jié)點(diǎn)
BOOL _releaseOnMainThread; //在主線程釋放
BOOL _releaseAsynchronously;//在異步線程釋放
}
_YYLinkMap負(fù)責(zé)實(shí)現(xiàn)緩存和LRU的功能识樱,其中使用了C語言中的CFMutableDictionaryRef來替代了OC中的NSMutableDictionary嗤无,主要原因有二:
- 速度相對(duì)較快
- key無需遵守NSCopying協(xié)議
(2) _YYLinkedMapNode
@interface _YYLinkedMapNode : NSObject {
@package
__unsafe_unretained _YYLinkedMapNode *_prev; //前向前一個(gè)節(jié)點(diǎn)的指針
__unsafe_unretained _YYLinkedMapNode *_next; //指向下一個(gè)節(jié)點(diǎn)的指針
id _key; //緩存數(shù)據(jù)key
id _value; //緩存數(shù)據(jù)value
NSUInteger _cost; //節(jié)點(diǎn)占用大小
NSTimeInterval _time; //節(jié)點(diǎn)操作時(shí)間戳
}
_YYLinkedMapNode封裝了緩存數(shù)據(jù)的信息
(3)添加新節(jié)點(diǎn)
// 將一個(gè)node對(duì)象插到隊(duì)列最前面
- (void)insertNodeAtHead:(_YYLinkedMapNode *)node {
CFDictionarySetValue(_dic, (__bridge const void *)(node->_key), (__bridge const void *)(node)); //存入字典中
_totalCost += node->_cost; //更新總大小
_totalCount++; //更新總數(shù)
if (_head) { //節(jié)點(diǎn)置于鏈表頭部
node->_next = _head;
_head->_prev = node;
_head = node;
} else {
_head = _tail = node;
}
}
(4) 移動(dòng)節(jié)點(diǎn)
// 將一個(gè)node放到隊(duì)列最前面
- (void)bringNodeToHead:(_YYLinkedMapNode *)node {
if (_head == node) return;//如果當(dāng)前節(jié)點(diǎn)是表頭
if (_tail == node) {//如果當(dāng)前節(jié)點(diǎn)是尾節(jié)點(diǎn)
_tail = node->_prev;//將node的前驅(qū)結(jié)點(diǎn)指向尾節(jié)點(diǎn)
_tail->_next = nil;//將尾節(jié)點(diǎn)的后繼節(jié)點(diǎn)置空
} else {
node->_next->_prev = node->_prev;//將node指向的下一個(gè)節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn),指向node的前驅(qū)節(jié)點(diǎn)
node->_prev->_next = node->_next;//將node指向的上一個(gè)節(jié)點(diǎn)的后繼節(jié)點(diǎn),指向node的后繼節(jié)點(diǎn),從鏈表中剝離出node
}
node->_next = _head;//將node的后繼節(jié)點(diǎn)指向當(dāng)前頭節(jié)點(diǎn)
node->_prev = nil;//將node的前驅(qū)節(jié)點(diǎn)置空
_head->_prev = node;//此時(shí)的頭節(jié)點(diǎn)的前驅(qū)指向node
_head = node;//將此時(shí)的node置為頭節(jié)點(diǎn)
}
(5)刪除節(jié)點(diǎn)
//移除掉指定node震束,前提是node為鏈表中的一個(gè)節(jié)點(diǎn)
- (void)removeNode:(_YYLinkedMapNode *)node {
CFDictionaryRemoveValue(_dic, (__bridge const void *)(node->_key));
_totalCost -= node->_cost;//調(diào)整總開銷
_totalCount--;//調(diào)整總緩存數(shù)
if (node->_next) node->_next->_prev = node->_prev;//如果node 存在后繼節(jié)點(diǎn),則將node的后繼節(jié)點(diǎn)的前驅(qū)指向node的前驅(qū)結(jié)點(diǎn)
if (node->_prev) node->_prev->_next = node->_next;//如果node 存在前驅(qū)節(jié)點(diǎn),則將node的前驅(qū)節(jié)點(diǎn)的后繼指向node的后繼節(jié)點(diǎn)
if (_head == node) _head = node->_next;//如果node是頭節(jié)點(diǎn),則將node的后繼節(jié)點(diǎn)置為頭節(jié)點(diǎn)
if (_tail == node) _tail = node->_prev;//如果node是尾節(jié)點(diǎn), 則將node的前驅(qū)結(jié)點(diǎn)置為尾節(jié)點(diǎn)
}
(6)刪除尾結(jié)點(diǎn)
//將最后一個(gè)node移除
- (_YYLinkedMapNode *)removeTailNode {
if (!_tail) return nil;
_YYLinkedMapNode *tail = _tail;
CFDictionaryRemoveValue(_dic, (__bridge const void *)(_tail->_key));
_totalCost -= _tail->_cost;
_totalCount--;
if (_head == _tail) {
_head = _tail = nil;
} else {
_tail = _tail->_prev;
_tail->_next = nil;
}
return tail;
}
(7)清除鏈表
- (void)removeAll {
_totalCost = 0;
_totalCount = 0;
_head = nil;
_tail = nil;
if (CFDictionaryGetCount(_dic) > 0) {
CFMutableDictionaryRef holder = _dic;
_dic = CFDictionaryCreateMutable(CFAllocatorGetDefault(), 0, &kCFTypeDictionaryKeyCallBacks, &kCFTypeDictionaryValueCallBacks);
if (_releaseAsynchronously) {
dispatch_queue_t queue = _releaseOnMainThread ? dispatch_get_main_queue() : YYMemoryCacheGetReleaseQueue();
dispatch_async(queue, ^{
CFRelease(holder); // hold and release in specified queue
});
} else if (_releaseOnMainThread && !pthread_main_np()) {
dispatch_async(dispatch_get_main_queue(), ^{
CFRelease(holder); // hold and release in specified queue
});
} else {
CFRelease(holder);
}
}
}
2.2 鏈表的使用
2.2.1 鎖
(1)為什么要用鎖
多線程很容易引起資源的搶奪,所以開放時(shí)都需要用到鎖來保證線程安全
在YYCache中前期使用的是OSSpinLock当犯,但由于iOS系統(tǒng)的更新迭代垢村,系統(tǒng)維護(hù)了 5 個(gè)不同的線程優(yōu)先級(jí)/QoS: background,utility嚎卫,default嘉栓,user-initiated,user-interactive拓诸。高優(yōu)先級(jí)線程始終會(huì)在低優(yōu)先級(jí)線程前執(zhí)行侵佃,一個(gè)線程不會(huì)受到比它更低優(yōu)先級(jí)線程的干擾。這種線程調(diào)度算法會(huì)產(chǎn)生潛在的優(yōu)先級(jí)反轉(zhuǎn)問題奠支,從而破壞了 spin lock馋辈。(具體查看不再安全的 OSSpinLock),所以現(xiàn)在采用的是pthread_mutex倍谜。
(2)pthread_mutex
pthread_mutex是互斥鎖迈螟,當(dāng)涉及多線程執(zhí)行代碼的情況下,通過pthread_mutex_lock(&_lock)方法給下面的代碼塊加互斥鎖尔崔,這樣其它線程會(huì)被阻塞答毫,直到pthread_mutex_unlock(&_lock)被調(diào)用。如下:
pthread_mutex_lock(&_lock);
//代碼塊1
pthread_mutex_unlock(&_lock);
pthread_mutex_lock(&_lock);
//代碼塊2
pthread_mutex_unlock(&_lock);
線程A執(zhí)行代碼塊1季春,線程B執(zhí)行代碼塊2烙常,如果線程A先執(zhí)行代碼塊1,_lock被鎖住鹤盒,這樣線程B被阻塞蚕脏,直到線程A執(zhí)行完代碼塊1后,調(diào)用pthread_mutex_unlock(_lock)侦锯,線程B開始執(zhí)行代碼塊2驼鞭。
2.2.2 使用
(1)初始化
- (instancetype)init {
self = super.init;
pthread_mutex_init(&_lock, NULL);
_lru = [_YYLinkedMap new];
_queue = dispatch_queue_create("com.ibireme.cache.memory", DISPATCH_QUEUE_SERIAL);
_countLimit = NSUIntegerMax;
_costLimit = NSUIntegerMax;
_ageLimit = DBL_MAX;
_autoTrimInterval = 5.0;
_shouldRemoveAllObjectsOnMemoryWarning = YES;
_shouldRemoveAllObjectsWhenEnteringBackground = YES;
[[NSNotificationCenter defaultCenter] addObserver:self selector:@selector(_appDidReceiveMemoryWarningNotification) name:UIApplicationDidReceiveMemoryWarningNotification object:nil];
[[NSNotificationCenter defaultCenter] addObserver:self selector:@selector(_appDidEnterBackgroundNotification) name:UIApplicationDidEnterBackgroundNotification object:nil];
[self _trimRecursively];
return self;
}
- (void)_trimRecursively {
__weak typeof(self) _self = self;
dispatch_after(dispatch_time(DISPATCH_TIME_NOW, (int64_t)(_autoTrimInterval * NSEC_PER_SEC)), dispatch_get_global_queue(DISPATCH_QUEUE_PRIORITY_LOW, 0), ^{
__strong typeof(_self) self = _self;
if (!self) return;
[self _trimInBackground]; //在異步隊(duì)列中執(zhí)行邊界檢測(cè)
[self _trimRecursively]; //循環(huán)調(diào)用本方法
});
}
- (void)_trimInBackground {
dispatch_async(_queue, ^{
[self _trimToCost:self->_costLimit];
[self _trimToCount:self->_countLimit];
[self _trimToAge:self->_ageLimit];
});
}
初始化中,創(chuàng)建了lru對(duì)象尺碰,設(shè)置了基本參數(shù)挣棕,添加了內(nèi)存警告和進(jìn)入后臺(tái)通知,_trimRecursively是緩存空間邊界檢測(cè)
(2)邊界檢測(cè)
- (void)_trimToCost:(NSUInteger)costLimit {
BOOL finish = NO;
pthread_mutex_lock(&_lock);
if (costLimit == 0) {
[_lru removeAll];
finish = YES;
} else if (_lru->_totalCost <= costLimit) {
finish = YES;
}
pthread_mutex_unlock(&_lock);
if (finish) return;
NSMutableArray *holder = [NSMutableArray new];
while (!finish) {
if (pthread_mutex_trylock(&_lock) == 0) {
if (_lru->_totalCost > costLimit) {
_YYLinkedMapNode *node = [_lru removeTailNode];
if (node) [holder addObject:node];
} else {
finish = YES;
}
pthread_mutex_unlock(&_lock);
} else {
usleep(10 * 1000); //10 ms
}
}
if (holder.count) {
dispatch_queue_t queue = _lru->_releaseOnMainThread ? dispatch_get_main_queue() : YYMemoryCacheGetReleaseQueue();
dispatch_async(queue, ^{
[holder count]; // release in queue
});
}
}
- (void)_trimToCount:(NSUInteger)countLimit {
BOOL finish = NO;
pthread_mutex_lock(&_lock);
if (countLimit == 0) {
[_lru removeAll];
finish = YES;
} else if (_lru->_totalCount <= countLimit) {
finish = YES;
}
pthread_mutex_unlock(&_lock);
if (finish) return;
NSMutableArray *holder = [NSMutableArray new];
while (!finish) {
if (pthread_mutex_trylock(&_lock) == 0) {
if (_lru->_totalCount > countLimit) {
_YYLinkedMapNode *node = [_lru removeTailNode];
if (node) [holder addObject:node];
} else {
finish = YES;
}
pthread_mutex_unlock(&_lock);
} else {
usleep(10 * 1000); //10 ms
}
}
if (holder.count) {
dispatch_queue_t queue = _lru->_releaseOnMainThread ? dispatch_get_main_queue() : YYMemoryCacheGetReleaseQueue();
dispatch_async(queue, ^{
[holder count]; // release in queue
});
}
}
- (void)_trimToAge:(NSTimeInterval)ageLimit {
BOOL finish = NO;
NSTimeInterval now = CACurrentMediaTime();
pthread_mutex_lock(&_lock);
if (ageLimit <= 0) {
[_lru removeAll];
finish = YES;
} else if (!_lru->_tail || (now - _lru->_tail->_time) <= ageLimit) {
finish = YES;
}
pthread_mutex_unlock(&_lock);
if (finish) return;
NSMutableArray *holder = [NSMutableArray new];
while (!finish) {
if (pthread_mutex_trylock(&_lock) == 0) {
if (_lru->_tail && (now - _lru->_tail->_time) > ageLimit) {
_YYLinkedMapNode *node = [_lru removeTailNode];
if (node) [holder addObject:node];
} else {
finish = YES;
}
pthread_mutex_unlock(&_lock);
} else {
usleep(10 * 1000); //10 ms
}
}
if (holder.count) {
dispatch_queue_t queue = _lru->_releaseOnMainThread ? dispatch_get_main_queue() : YYMemoryCacheGetReleaseQueue();
dispatch_async(queue, ^{
[holder count]; // release in queue
});
}
}
- _trimToCost 方法判斷了鏈表中所有節(jié)點(diǎn)占用大小之和totalCost是否大于costLimit亲桥,如果超過洛心,則從鏈表末尾開始刪除節(jié)點(diǎn),直到totalCost小于等于costLimit為止
- _trimToCount 方法判斷鏈表中的所有節(jié)點(diǎn)個(gè)數(shù)之和是否大于countLimit题篷,如果超過词身,則從鏈表末尾開始刪除節(jié)點(diǎn),直到個(gè)數(shù)之和小于等于countLimit為止
- _trimToAge 方法遍歷鏈表中的節(jié)點(diǎn)番枚,刪除那些和now時(shí)刻的時(shí)間間隔大于ageLimit的節(jié)點(diǎn)
- 這里作者還使用了pthread_mutex_trylock法严,這個(gè)函數(shù)是非阻塞鎖损敷,如果沒有獲取到鎖就會(huì)立刻返回不會(huì)阻塞當(dāng)前線程,獲取鎖成功會(huì)返回0,否則返回其他值來說明鎖的狀態(tài).但是pthread_mutex_lock如果沒有獲取到鎖會(huì)一直等待從而發(fā)生阻塞.
(3)讀寫數(shù)據(jù)
- (id)objectForKey:(id)key {
if (!key) return nil;
pthread_mutex_lock(&_lock);
_YYLinkedMapNode *node = CFDictionaryGetValue(_lru->_dic, (__bridge const void *)(key)); //從字典中讀取key相應(yīng)的節(jié)點(diǎn)
if (node) {
node->_time = CACurrentMediaTime(); //更新節(jié)點(diǎn)訪問時(shí)間
[_lru bringNodeToHead:node]; //將節(jié)點(diǎn)移動(dòng)至鏈表頭部
}
pthread_mutex_unlock(&_lock);
return node ? node->_value : nil;
}
- (void)setObject:(id)object forKey:(id)key withCost:(NSUInteger)cost {
if (!key) return;
if (!object) {
[self removeObjectForKey:key];
return;
}
pthread_mutex_lock(&_lock); //上鎖
_YYLinkedMapNode *node = CFDictionaryGetValue(_lru->_dic, (__bridge const void *)(key)); //從字典中取節(jié)點(diǎn)
NSTimeInterval now = CACurrentMediaTime();
if (node) { //如果能取到,說明鏈表中之前存在key對(duì)應(yīng)的緩存數(shù)據(jù)
//更新totalCost
_lru->_totalCost -= node->_cost;
_lru->_totalCost += cost;
node->_cost = cost;
node->_time = now; //更新節(jié)點(diǎn)的訪問時(shí)間
node->_value = object; //更新節(jié)點(diǎn)中存放的緩存數(shù)據(jù)
[_lru bringNodeToHead:node]; //將節(jié)點(diǎn)移至鏈表頭部
} else { //如果不能取到深啤,說明鏈表中之前不存在key對(duì)應(yīng)的緩存數(shù)據(jù)
node = [_YYLinkedMapNode new]; //創(chuàng)建新的節(jié)點(diǎn)
node->_cost = cost;
node->_time = now; //設(shè)置節(jié)點(diǎn)的時(shí)間
node->_key = key; //設(shè)置節(jié)點(diǎn)的key
node->_value = object; //設(shè)置節(jié)點(diǎn)中存放的緩存數(shù)據(jù)
[_lru insertNodeAtHead:node]; //將新的節(jié)點(diǎn)加入鏈表頭部
}
if (_lru->_totalCost > _costLimit) {
dispatch_async(_queue, ^{
[self trimToCost:_costLimit];
});
}
if (_lru->_totalCount > _countLimit) {
_YYLinkedMapNode *node = [_lru removeTailNode];
if (_lru->_releaseAsynchronously) {
dispatch_queue_t queue = _lru->_releaseOnMainThread ? dispatch_get_main_queue() : YYMemoryCacheGetReleaseQueue();
dispatch_async(queue, ^{
[node class]; //hold and release in queue
});
} else if (_lru->_releaseOnMainThread && !pthread_main_np()) {
dispatch_async(dispatch_get_main_queue(), ^{
[node class]; //hold and release in queue
});
}
}
pthread_mutex_unlock(&_lock); //解鎖
}
每次YYMemoryCache在進(jìn)行讀寫的時(shí)候都會(huì)添加互斥鎖拗馒,更新對(duì)應(yīng)的linkedMapNode對(duì)象的時(shí)間戳屬性,并且把該對(duì)象放到隊(duì)列的最前面,從而調(diào)整了緩存中對(duì)象的順序。
(4)異步線程釋放
static inline dispatch_queue_t YYMemoryCacheGetReleaseQueue() {
return dispatch_get_global_queue(DISPATCH_QUEUE_PRIORITY_LOW, 0);
}
dispatch_queue_t queue = _lru->_releaseOnMainThread ? dispatch_get_main_queue() : YYMemoryCacheGetReleaseQueue();
dispatch_async(queue, ^{
[holder count]; // release in queue
});
其實(shí)認(rèn)真看可以發(fā)現(xiàn)源碼中很多地方都有諸如這樣的異步線程溯街,這其實(shí)是個(gè)非常巧妙的做法(具體可以查看iOS 保持界面流暢的技巧)
Note: 對(duì)象的銷毀雖然消耗資源不多诱桂,但累積起來也是不容忽視的。通常當(dāng)容器類持有大量對(duì)象時(shí)呈昔,其銷毀時(shí)的資源消耗就非常明顯挥等。同樣的,如果對(duì)象可以放到后臺(tái)線程去釋放韩肝,那就挪到后臺(tái)線程去触菜。這里有個(gè)小 Tip:把對(duì)象捕獲到 block 中,然后扔到后臺(tái)隊(duì)列去隨便發(fā)送個(gè)消息以避免編譯器警告哀峻,就可以讓對(duì)象在后臺(tái)線程銷毀了涡相。
YYMemoryCacheGetReleaseQueue 是一個(gè)低優(yōu)先級(jí)DISPATCH_QUEUE_PRIORITY_LOW的全局隊(duì)列,這實(shí)際上是為了讓銷毀線程不占用主要的CPU使用時(shí)間剩蟀,在相對(duì)空閑時(shí)進(jìn)行銷毀催蝗,提升性能。