您现在的位置: IOS教程網 >> IOS系統 >  >> iOS 程式開發 >> iOS 開發綜合

當 C++ 遇上 iOS:打造支援 Objective-C 物件的多執行緒 LRU 快取

編輯:iOS 開發綜合

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 快取本體

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++ 與 Objective-C 的注意事項

檔案副檔名。含有 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++ 是合理的補足方式。但上面指出的幾處同步與記憶體問題,在真正上線前都需要修正。

  1. 上一篇文章:
  2. 下一篇文章:
蘋果刷機越獄教程| IOS教程問題解答| IOS技巧綜合| IOS7技巧| IOS8教程
Copyright © IOS教程網 All Rights Reserved