Garbage Collection (3)

上一次談到了 C++11 的 smart pointer, 這次來談談 Qt. 在 Qt 你可以使用的工具有:

  • Smart Pointers
    • QPointer
    • QSharedPointer
    • QWeakPointer
    • QScopedPointer
    • QScopedArrayPointer
  • Based on QObject
    • parent-child relation
    • QObject::deleteLater()
  • Copy On Write
    • QSharedData
    • QSharedDataPointer
    • QExplicitlySharedDataPointer

Smart Pointers

用途基本上跟 STL, Boost 版本差不多, 但細部設計方針有些許不同; 例如 Qt 的版本都提供 raw pointer 的隱式轉換.

不同的 library 在這方面經常會有點出入, 像 Loki 的 smart pointer 就不使用成員函式, 一律使用全域函式對 smart pointer 本身操作.

由於用法都差不多, 本篇也不贄述, 請自行參閱相關文件.

QObject

如果類別是一個 QObject, 就適用這些方式.

Parent-Child relation

QObject 之間有 parent-child 關係, 你可以在 constructor 指定 parent, 該物件就會自動成為 child. Parent 在回收時會負責回收所有的 children, 因此 QObject 物件之間會是樹狀圖, 只要記得回收根部就可以回收整個體系.

這種回收方式又特別適合 QWidget 這種 GUI 類別, 因為它們很少出現環狀參用, 且有很明確的 composition 關係. 仔細回想一下 Qt 的範例是否都是在 main 建立一個 GUI 實體, 該實體所擁有的各種元件都只使用 new 無 delete? 就是因為有這種回收機制存在.

但這 parent-child 關係其實存在某種限制. 起因在 QObject 擁有與 event loop 溝通的能力, 其中一個特性就是它有 thread affinity. 講白話一點就是每個 QObject 都屬於某個 thread, 這樣在 QObject 發 signals 的時候, event loop 才知道這事件是來自哪一個 thread, 有沒有必要丟進 queue 裡分派等等.

QObject 屬於哪個 thread, 是看建立該物件時處在哪個 thread 上. 建立完成的實體也可以用 QObject::moveToThread() 丟到其他 thread 上; 注意, 只能「推」, 不能「拉」, 因為你並不知道別的 thread 目前執行到哪裡, 自然也不能任意修改物件.

噢, 講得有點遠了. 這裡的真正問題是: 如果 parent 的 thread 和 child 不一樣會發生什麼事?

唔, 會發生很多事, 但絕對都不是好事. 一個很明顯的問題是回收機制不再安全. 你永遠不應該直接操作不同 thread 上的 QObject. 如果你使用的是 QRunnable 就更要小心: QRunnable::run() 是跑在不同的 thread 上!

QObject::deleteLater()

當你呼叫了 QObject::deleteLater() 後, 該 QObject 並不會立刻回收, 而是通知 event queue 請它之後幫你回收. 它具有幾個特性:

  • 多次呼叫不會重覆回收
  • 保證 thread-safe, 它會在自己的 thread 回收
  • 它是 slot

最後一點即是它和 smart pointer 的不同處: smart pointer 是依賴 variable scope 觸發, 而 QObject::deleteLater() 則可以交由特定事件觸發回收.

基本上只要需要手動回收通常都建議使用 QObject::deleteLater().

copy-on-write

說到 copy-on-write, 請恕我先離題一下, 來談談常見的字串複製行為.

Mutable String

某些字串內部實作使用的是 mutable string, 即 string 的內容可以改變, 複製時也要複製一份全新的複本. 但如果你其實不會修改這字串, 那完整複製這複本就是很多餘的事了. 以字串的使用情況來說更為極端: 要嘛你會一直修改字串, 要嘛你根本不會修改它. C++ 有 const reference 和 rvalue reference 解決這些問題, 而其他語言則大多採用 immutable string.

Immutable String

Immutable string 在建立之後內容就不會再被更改了, 所有需要修改內容的操作都是回傳一個新的複本. 很多常見的語言使用的都是 immutable string.

由於內容不變, 複製時可以直接共用同一塊空間, 也不需要考慮同步問題, 可說是非常高效的作法. 但相對來說, 修改字串的成本就變大了, 比方說字串連續串接, 過程中會一直產生立即被丟掉的暫時字串. 因此使用 immutable string 的語言通常也會提供工具讓你先在 buffer 內處理字串內容, 再一次生成結果字串, 例如 Java 的 StringBuilder 或是 Python 的 cStringIO 等.

Copy On Write

好啦, 扯這麼遠終於又回到 copy-on-write 啦. COW 基本上是在 mutable 和 immutable 之間取平衡點: 在複製時它先共用同一塊記憶體, 等到第一次要修改時才真正地複製一份完整的複本出來. 這看起來似乎解決了所有的問題.

事情當然是不會那麼美好, COW 的其中一個問題是, 所謂修改語意在程式語言裡很難精確地表達. 在 C++, 一個可能的做法是把所有 non-const 的成員函式呼叫都視為修改, 這正是 QSharedDataPointer 採用的方針.

先談談 Qt 如何透過 QSharedData 以及 pimpl idiom 讓你輕易實作 COW. 架構大致上會像這樣:

class Employee {
public:
    Employee ();
    // other member functions
private:
    class Data;
    QSharedDataPointer<Data> d;
};

class Employee::Data: public QSharedData {
public:
    Data ();
    Data (const Data &);
    // other member variables
};

QSharedData 不只提供型別標記, 也提供一個 thread-safe 的計數器. QSharedDataPointer 就跟一般的 smart pointer 一樣提供 operator-> 的重載, 只是 non-const 版本會自動呼叫 QSharedDataPointer::detach(). detach() 的內容大致上像這樣(已簡化):

void QSharedDataPointer::detach () {
    if( this->d->rc > 1 ) {
        Data * d = this->d;
        this->d = Type(*d);
        --d->rc;
    }
}

Qt 的大部分具有 value 語意的 classes 都實作了 implicit-sharing, 如 QString, QByteArray 以及所有的 template container. 而 gcc 的 std::string 實作也採用 COW.

看起來很完美, 但事情總有例外: 如果物件洩漏了內部的成員, 比方說 container 很常見的 T & operator [], 那麼 detach() 會被輕易地繞過:

String a = "hello";
Char & c = a[0];
String b = a;
c = 'a';
assert(b == "hello");

QString 避免這問題的方法是, 讓 non-const operator [] 回傳一個特別的物件, 其型別為 QCharRef, 在內容修改時為 QString 呼叫 detach(). 但其他的 template container 就沒辦法如法炮製了, 上述問題依然存在. 相較之下 gcc 的解法就比較優雅一些, 它的計數器多了一種狀態: leaked, 呼叫 non-const operator [] 之後計數器的狀態會是 leaked, 下次的複製就一定會是完整複製.

如果對 QSharedDataPointer 的自動化有疑慮, QExplicitlySharedDataPointer 即是為此存在. 它不會為你自動呼叫 detach(), 你必須自行分辨使用時機.

Summary

Qt 原本就設計了兩種回收機制, 全都基於 QObject 運作, 並和 multi-thread 與 event-loop 有緊密的結合. 而為了解決各家 compiler 對新的 C++ 標準支援不一的問題, 提供了常見的數種 smart pointers; 當然, 它們與 Qt-style STL 一樣, 用不用隨你.

Garbage Collection (2)

上一篇提到了 reference counting 以及 weak reference. 這篇我將以 C++11 的 smart pointer 為骨幹做介紹, 但核心概念都是差不多的.

C++11 引入了一系列的 smart pointer, 使用 RAII (Resource Acquisition Is Initialization) 手法來確保資源在生命週期結束後的回收行為.

想法非常簡單: 配置在 stack 上的變數, 在離開 scope 後一定會呼叫 destructor, 因此只要設計一系列的容器, 讓它們在 destructor 裡做回收行為, 就可以讓編譯器為我們回收資源. 而 C++11 的 smart pointer 並不只是自動化的 new/delete 容器, 由於其 allocator/deleter 可自訂, programmer 實際上可用它來管理任何種類的資源.

Strong Reference

在 C++ 裡: std::shared_ptr 即是使用 strong reference, 也是最常被用到的 smart pointer. 用法如下:

std::shared_ptr<Object> sp(new Object);
sp.get();                        // get raw pointer
sp.reset();                      // ref count -1, set to null pointer
sp.reset(new Object);            // manage another pointer
std::shared_ptr<Object> sp2(sp); // ref count +1

用同一個 pointer 建立兩個不同的 std::shared_ptr 是錯誤用法, 會造成一次以上的回收:

Object o = new Object;
std::shared_ptr<Object> sp1(o);
std::shared_ptr<Object> sp2(o); // bad

Weak Reference

在 C++11, weak reference 對應的 smart pointer 是 std::weak_ptr. 前篇提到了 weak reference 可以用來解決 cyclic reference, 那麼是怎麼做到的呢? 很簡單, 因為 weak reference 不參與 reference counting, 也就是說它的生成, 複製, 銷毀都不會影響計數器, 自然也不會做任何回收的動作. 那麼為什麼我們需要 weak reference, 而不是簡單地用 raw pointer 呢? 差別就在 weak reference 雖然不參與 reference counting, 但它仍然知道該 pointer 目前的計數器資訊, 這讓它可以確認資源是否已被回收, 並在需要時暫時轉換為 strong reference. 這在多緒環境時尤其重要:

void thread1 () {
    // ...
    // sp is a std::shared_ptr
    sp.reset(); // (1)
    // ...
}

void thread2 () {
    // ...
    // wp is a std::weak_ptr
    wp.get() // (2)
    // ...
}

如果 std::weak_ptrstd::shared_ptr 一樣只用 get() 取得 raw pointer, 那麼在上述的例子中, (1) 如果觸發了回收, 那麼 (2) 拿到的 pointer 就會因而腐敗. 因此 std::weak_ptr 必須要使用 lock() 函式取得一個 std::shared_ptr, 讓計數器暫時不歸零, 就可以避免這個狀況:

{
    std::shared_ptr<Object> sp = wp.lock();
    // counter will not be 0 in this scope
}

Strong Reference From This

考慮以下的二元樹節點實作:

class Node {
public:
    void setParent (std::weak_ptr<Node> n) {
        this->p = n;
    }
    void setLeft (std::shared_ptr<Node> n) {
        this->l = n;
        n->setParent(std::shared_ptr<Node>(this));
    }
    void setRight (std::shared_ptr<Node> n) {
        this->r = n;
        n->setParent(std::shared_ptr<Node>(this));
    }
private:
    std::weak_ptr<Node> p;
    std::shared_ptr<Node> l, r;
};

以上的程式片段犯了大忌: 直接使用 this 建立 std::shared_ptr, 導致離開該函式後會讓計數器馬上歸零, this 被意外地 delete. 由於我們的確需要取得目前正在管理 this 的 std::shared_ptr, 這時我們需要使用 std::enable_shared_from_this. 繼承自 std::enable_shared_from_this 的類別, 可以使用 shared_from_this() 函式取得管理 this 的 std::shared_ptr. 實作原理基本上是儲存一個 std::weak_ptr, 外部建立 std::shared_ptr 時更新這個 std::weak_ptr, 呼叫 shared_from_this() 時再轉換回 std::shared_ptr. 用法如下:

class Node: public std::enable_shared_from_this<Node> {
public:
    void setParent (std::weak_ptr<Node> n) {
        this->p = n;
    }
    void setLeft (std::shared_ptr<Node> n) {
        this->l = n;
        n->setParent(this->shared_from_this());
    }
    void setRight (std::shared_ptr<Node> n) {
        this->r = n;
        n->setParent(this->shared_from_this());
    }
private:
    std::weak_ptr<Node> p;
    std::shared_ptr<Node> l, r;
};

Unique Reference

在特殊情況下, 可能會需要確保同一時間只有一個物件有擁有權, 這時候 std::unique_ptr 就派上用場了. std::unique_ptrstd::auto_ptr 的改良版本. std::auto_ptr 的複製行為是「摧毀式複製」, 發生複製時會轉移資源的擁有權, 這使得它無法被用於標準容器, 並且在作為參數傳入函式時, 會意外地被轉移擁有權, 並在函式結束時觸發回收:

void f1 () {
    std::auto_ptr<Object> a(new Object);
    // ownership moved into f2
    f2(a);
}

void f2(std::auto_ptr<Object> b) {
    // destructs b and delete pointee
}

std::unique_ptr 改良了這點, 它不具有 copy 語意, 但具有 move 語意. 需要複製時必須要明確使用 std::move 轉移擁有權.

Garbage Collection (1)

這篇只是介紹比較知名的方法,預計之後還會再發一兩篇討論 C++/Qt 的回收手法。

Reference Counting

C/C++ 裡最常被使用的方式, 也有部分 GC 演算法會混合 reference counting. 其原理是每個物件都有一個計數器, 記錄目前有多少其他物件指向它. 第一次建立時計數器是 1, 每次複製時計數器加 1, 每少一個物件指向它就減 1, 如果計數器降到 0 就代表此物件不需要存在, 這時它會被刪除. 圖解如下:

但 reference counting 有一個重大的缺點, 就是在有 cyclic reference 的狀況下, 它無法回收物件. 圖例:

變數 c 若因為某些原因而需要持有 b (比方說要保存 parent-child 關係), 就形成了 cyclic reference, 此時就算變數 a 不再指向它們, 但因為計數器不會歸零, 它們永遠無法被回收. 圖例:

要解決這個問題可以使用 weak reference counting (後述), 但因為它的使用方式與 strong reference counting 不同, programmer 必須要自行檢查是否會造成 cyclic reference, 再視情況改用 weak reference. 然而很多時候 cyclic reference 是很難被發現的, 對 programmer 來說是一項不小的負擔.

JavaScript

JavaScript 的 closure 常會意外地造成 cyclic reference, 以下是其中一個簡單的例子:

window.onload = function () {
    var tmp = document.getElementById('...');
    tmp.onclick = function () {
        // tmp may reference here because closure
    };
};

通常在 DOM event handler 中經常會出現這種寫法, 畢竟如果不使用 closure, 寫法會變得很不自然. 所幸目前大部分的 JavaScript engine 都已經使用 mark and sweep (後述), 基本上也不太需要過於擔心這問題 ... 除了早期的 IE 以外(講明一點, 在 Windows XP 上的 IE 版本似乎都還在用 reference counting).

Mark and Sweep

近代的 GC 有許多都是以 mark and sweep 為主,再混合一點變型(如 Python 也有用上 reference counting). Mark and sweep 的想法也很簡單: 首先走訪目前存在的所有變數, 把碰得到的物件標記起來,此為 mark; 接著檢查所有物件, 把剛剛沒被標記的物件回收, 有被標記的物件清除標記以供下回使用, 此為 sweep. 寫成演算法即:

def mark(variables):
    for v in variables:
        if not v.marked:
            v.marked = True
            mark(v.children)

def sweep(objects):
    for o in objects:
        if o.marked:
            o.marked = False
        else:
            del o

由於 mark and sweep 是直接走訪所有的變數及物件, 不像 reference counting 只知道 parent-child 的關係, 因此它不受 cyclic reference 的影響. 但也因此, C/C++ 很難直接原生支援, 因為它經常需要在 memory pool 上再做一些額外處理. 另外,在 mark and sweep 執行時, 為了 thread safety, 通常會先暫停所有的 thread, 這對效能可能是另一項衝擊.

就算有 VM 可以幫 programmer 做資源回收, 但「資源」並不只限於 heap. 對於 sockets, IO devices, shared memory 等外部資源, VM 還是無法完全幫 programmer 監視所有資源的使用, 因此 client 還是有必要手動呼叫回收函式(如 close(), release() 等).

Contents © 2014 Wei-Cheng Pan - Powered by Nikola

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License .