iOS 的 Objective-C 是 C 的超集,因此可以直接在專案中混用 C++。本文示範如何用 C++ 實作一個 LRU(Least Recently Used)快取,並讓它能快取 Objective-C 物件,同時在多執行緒環境下保持安全。
整個實作由三個部分組成:單例基類、讀寫鎖、以及 LRU 快取本體。
快取通常實作為單例。与其每個類別各寫一次單例,不如用 C++ 模板做一個基類,子類只要繼承就自動具備單例能力:
#ifndef SingltonT_h
#define SingltonT_h
#include <iostream>
#include <tr1/memory>
using namespace std;
using namespace std::tr1;
template <typename T>
class Singlton {
public:
static T* instance();
~Singlton() {
cout << "destruct singlton" << endl;
}
protected:
Singlton();
static std::tr1::shared_ptr<T> s_instance;
};
template <typename T>
std::tr1::shared_ptr<T> Singlton<T>::s_instance;
template <typename T>
Singlton<T>::Singlton() {
cout << "construct singlton" << endl;
}
template <typename T>
T* Singlton<T>::instance() {
if (!s_instance.get())
s_instance.reset(new T);
return s_instance.get();
}
#endif
兩個設計細節:靜態成員變數必須在類別外提供定義(s_instance 那行),否則會連結失敗;用 shared_ptr 而非裸指標持有實例,可以在程式結束時自動釋放,避免靜態物件銷毀順序造成的問題。
不過要誠實指出:這個版本的 instance() 不是執行緒安全的,多執行緒同時首次呼叫會產生競態。若你的快取會被多執行緒存取,需要額外加上雙重檢查鎖定或改用 std::call_once。
快取在多執行緒下被操作時,需要同步機制。這裡沒有直接用 pthread_mutex_t,而是基於 GCC 的 __sync 原子內建函式實作一把讀寫鎖:
#ifndef _RWLOCK_H_
#define _RWLOCK_H_
#define LOCK(q) while (__sync_lock_test_and_set(&(q)->lock, 1)) {}
#define UNLOCK(q) __sync_lock_release(&(q)->lock);
struct rwlock {
int write;
int read;
};
static inline void
rwlock_init(struct rwlock *lock) {
lock->write = 0;
lock->read = 0;
}
static inline void
rwlock_rlock(struct rwlock *lock) {
for (;;) { // 不斷循環,直到讀計數器累加成功
while (lock->write) {
__sync_synchronize();
}
__sync_add_and_fetch(&lock->read, 1);
if (lock->write) { // 若此時已有寫鎖,退還讀計數
__sync_sub_and_fetch(&lock->read, 1);
} else {
break;
}
}
}
static inline void
rwlock_wlock(struct rwlock *lock) {
__sync_lock_test_and_set(&lock->write, 1);
while (lock->read) {
// 很重要:若去掉這行,以 g++ -O3 最佳化編譯後可能發生死鎖
__sync_synchronize();
}
}
static inline void
rwlock_wunlock(struct rwlock *lock) {
__sync_lock_release(&lock->write);
}
static inline void
rwlock_runlock(struct rwlock *lock) {
__sync_sub_and_fetch(&lock->read, 1);
}
#endif
讀寫鎖的設計意圖是讀取可並行、寫入須獨佔。快取的存取特性恰好符合這個模型:讀遠多於寫,因此讓多個讀者同時進入能顯著提升吞吐。
rwlock_rlock 中的「先加一、再檢查、若有寫鎖則退回」這個三步驟,是為了避免在累加與檢查之間被寫者插入而導致讀者進入臨界區。而 rwlock_wlock 中的 __sync_synchronize() 是記憶體屏障,少了它,在 -O3 最佳化下編譯出的程式可能發生死鎖——編譯器會把這個空迴圈最佳化掉。這是本段程式碼最不顯眼卻最關鍵的一行。
關於效能:文獻中有人主張這類自旋鎖比 pthread_mutex_t 快數倍。筆者未做實測,有興趣者可自行驗證。但要注意自旋鎖的前提是臨界區極短且執行緒數不超過核心數,否則自旋只會白白浪費 CPU 時間片。
LRU 的核心資料結構是「雜湊表 + 時間序索引」的組合:雜湊表負責 O(1) 查找,時間序表負責找出最久未使用的項目。這裡用兩個 map 實作,並針對 Objective-C 的 NSString key 提供特化的比較器:
namespace lru_cache {
static const int DEF_CAPACITY = 100000; // 預設快取記錄數
typedef unsigned long long virtual_time;
typedef struct _HashKey {
NSString* key;
} HashKey;
typedef struct _HashValue {
id value_;
virtual_time access_;
} HashValue;
// 通用比較器
template <class key_t>
struct hashkey_compare {
bool operator()(key_t x, key_t y) const {
return x < y;
}
};
// 針對 HashKey 的特化版本:把 NSString 轉成 std::string 再比較
template <>
struct hashkey_compare<HashKey> {
bool operator()(HashKey __x, HashKey __y) const {
string x = [__x.key UTF8String];
string y = [__y.key UTF8String];
return x < y;
}
};
template <typename K, typename V, typename _Compare = hashkey_compare<K>,
typename _Alloc = std::allocator<std::pair<const K, V> > >
class lru_map: public map<K, V, _Compare, _Alloc>{};
這段模板特化的作用是:std::map 需要能比較 key 的大小,但 NSString 沒有定義小于運算子。透過特化 hashkey_compare,把 Objective-C 字串轉成 C++ 字串再比較,就能讓 map 正常運作。
快取類別的關鍵方法:
class CLRUCache {
public:
CLRUCache() : _now(0) {
_lru_list = shared_ptr<lru_map<virtual_time, HashKey> >(new lru_map<virtual_time, HashKey>);
_hash_table = shared_ptr<lru_map<HashKey, HashValue> >(new lru_map<HashKey, HashValue>);
}
int set(const HashKey& key, const id &value) {
HashValue hash_value;
hash_value.value_ = value;
hash_value.access_ = get_virtual_time();
pair< map<HashKey, HashValue>::iterator, bool > ret =
_hash_table->insert(make_pair(key, hash_value));
if (!ret.second) {
// key 已存在:從 LRU 表移除舊的時間戳記錄,再插入新的
virtual_time old_access = (*_hash_table)[key].access_;
map<virtual_time, HashKey>::iterator iter = _lru_list->find(old_access);
if (iter != _lru_list->end()) {
_lru_list->erase(iter);
}
_lru_list->insert(make_pair(hash_value.access_, key));
(*_hash_table)[key] = hash_value;
} else {
_lru_list->insert(make_pair(hash_value.access_, key));
if (_hash_table->size() > DEF_CAPACITY) {
// 取出最久未使用的 key(時間戳最小者在 map 開頭)
map<virtual_time, HashKey>::iterator iter = _lru_list->begin();
_hash_table->erase(iter->second);
_lru_list->erase(iter);
}
}
return 0;
}
HashValue* get(const HashKey& key) {
map<HashKey, HashValue>::iterator iter = _hash_table->find(key);
if (iter != _hash_table->end()) {
virtual_time old_access = iter->second.access_;
iter->second.access_ = get_virtual_time();
// 調整該 key 在 LRU 表中的時間戳位置
map<virtual_time, HashKey>::iterator it = _lru_list->find(old_access);
if (it != _lru_list->end()) {
_lru_list->erase(it);
}
_lru_list->insert(make_pair(iter->second.access_, key));
return &(iter->second);
}
return NULL;
}
private:
virtual_time get_virtual_time() { return ++_now; }
shared_ptr<lru_map<virtual_time, HashKey> > _lru_list;
shared_ptr<lru_map<HashKey, HashValue> > _hash_table;
virtual_time _now;
};
這裡有個值得注意的細節:get() 不只是讀取,它還會更新時間戳——這正是 LRU 不同於 FIFO 的地方,「最近使用過」的項目會被移到較新的位置,因此在容量滿時被淘汰的是真正最久沒被存取的項目。
using namespace lru_cache;
class DZCache: public Singlton<DZCache> {
friend class Singlton<DZCache>;
private:
shared_ptr<CLRUCache> clu_cache;
rwlock *lock;
DZCache() {
lock = (rwlock*) malloc(sizeof(rwlock));
rwlock_init(lock);
clu_cache = shared_ptr<CLRUCache>(new CLRUCache());
}
public:
~DZCache() {
free(lock);
}
static DZCache& getInstance() {
return *instance();
}
void set(NSString* key, id value) {
rwlock_wlock(lock); // 寫入需獨佔
HashKey hash_key;
hash_key.key = key;
clu_cache->set(hash_key, value);
rwlock_wunlock(lock);
}
id get(NSString* key) {
HashKey hash_key;
hash_key.key = key;
HashValue* value = clu_cache->get(hash_key);
if (value == NULL) {
return nil;
} else {
return value->value_;
}
}
};
注意 set 加了寫鎖,而 get 沒有加讀鎖。這個不對稱在單純讀取的情境下看似合理,但實際上是個 bug——因為前面提過,CLRUCache::get() 內部會修改 access_ 並操作 _lru_list,本質上是寫入行為。多執行緒同時 get 同一份快取時,map 的並行修改會導致未定義行為。正確做法是在 get 也加上 rwlock_rlock 保護(或乾脆用寫鎖,因為方法本身就會改狀態)。
void testLRUCache() {
// 指標方式
DZCache::instance()->set(@"name", @"daizhj");
NSString* name = (NSString*)DZCache::instance()->get(@"name");
std::cout << [name UTF8String] << endl;
NSNumber *age = [NSNumber numberWithInt:123123];
DZCache::instance()->set(@"age", age);
age = (NSNumber*)DZCache::instance()->get(@"age");
// 物件方式
DZCache::getInstance().set(@"name", @"daizhenjun");
name = (NSString*)DZCache::getInstance().get(@"name");
std::cout << [name UTF8String] << endl;
age = [NSNumber numberWithInt:123456];
DZCache::getInstance().set(@"age", age);
age = (NSNumber*)DZCache::getInstance().get(@"age");
}
檔案副檔名。含有 C++ 程式碼的實作檔必須命名為 .mm,編譯器才會以 Objective-C++ 模式處理。
ARC 與 retain/release。快取中存的是 id 型別的 Objective-C 物件,但 C++ 的 shared_ptr 不會自動管理 Objective-C 物件的引用計數。在 ARC 專案下,把物件存進 C++ 容器時,所有權語意会变得模糊,容易出現「物件已被釋放但快取仍持有指標」的懸空參考。實務上應在存入時 retain、在淘汰時 release,或改用能明確表達所有權的包裝。
virtual_time 用 incrementing counter 而非真實時間。這裡的時間戳是一個單調遞增的整數,而非 gettimeofday。好處是比較時不必處理系統時間回撥的問題,且運算極快;缺點是 _now 遞增本身也不是原子操作,多執行緒下需要保護。
淘汰時的記憶體歸屬。set 在超過容量時直接 erase 掉最舊的項目,但沒有對被移除的 Objective-C 物件做任何釋放處理。若物件所有權在快取手上,這裡就會洩漏。
整體而言,這個實作的價值在於示範了「用 C++ 的模板與 STL 為 Objective-C 專案補上資料結構能力」這個思路——Objective-C 標準庫缺少類似 std::map 的有序容器,混用 C++ 是合理的補足方式。但上面指出的幾處同步與記憶體問題,在真正上線前都需要修正。