Boost C++ Libraries Home Libraries People FAQ More

PrevUpHomeNext

設計概覽

"非空" 保證

"非空" 保證

保證

類型 variant<T1,T2,...,TN> 的所有實例 v 均保證,v 具有某個類型 Ti 的已構造內容,即使之前對 v 的某項操作失敗了。

這意味著 variant 可以被視為其有界類型的一個聯合。這個 "非空" 的特性使得用戶不會遇到未定義的 variant 內容,因此也不需要額外的複雜用法。

實現的問題

雖然 非空保證 看上去很 "明顯",實際上如何在通常的情況下(即,不給 有界類型 增加不合理的限制)實現它卻一點都不簡單。

主要的困難在於 variant 賦值的細節上。給定某個 variant 類型的兩個實例 v1v2, 在賦值 v1 = v2 時,我們必須考慮兩種截然不同的情形。

首先考慮 v1v2 含有相同類型的值的情形。我們稱這個類型為 T. 在這種情況下,賦值很簡單:使用 T::operator= 就行了。

不過,我們還必須考慮 v1v2 含有不同類型的值的情形。我們分別稱這兩類型為 TU. 這時,由於 variant 是在棧上管理其內容的,賦值的左操作數(即 v1)必須銷毀其內容並允許就地複製構造右操作數(即 v2)的內容。最後,v1 以類型 T 內容開始而以類型 U 的內容結束,具有 v2 的內容的拷貝。

該問題的癥結在於:如果對 v2 內容的複製構造失敗,那麼 v1 如何維持其 "非空" 保證?在嘗試對 v2 進行複製構造時,v1 已經銷毀了它的內容了!

"完美的" 方案:錯誤的期望

在瞭解了這一困難局面後,聰明的程序員可能會提出以下方法,希望可以解決這個問題:

  1. 提供一些"後備"存儲,進行適當的對齊,用以保存左操作數所含的值。
  2. 將左操作數的存儲內存複製(如,使用 memcpy)到後備的存儲中。
  3. 嘗試將右操作數複製到(現在已備份)左操作數的存儲中。
  4. 如果複製操作出現異常,則從備份中進行恢復(即,從後備存儲中複製內存到左操作數的存儲中)。
  5. 否則,複製成功,將左操作數的存儲內存複製到另一個"臨時"的對齊存儲中。
  6. 現在恢復備份(即再次複製內存)到左操作數的存儲中;在"舊的"內容恢復後,調用左操作數所含類型的析構函數。
  7. 最後,從臨時存儲中複製內存到(現在為空)左操作數的存儲中。

雖然有點複雜,但看起來這個方法以相對高效的方式提供了想要的安全性。實際上,本庫的幾個早期版本正是以這一方法實現的。

不幸的是,正如 Dave Abraham 首先指出的,這個方法會導致未定義行為:

"從頭讀下來,這有很多代碼,不過,如果這段代碼確實是按照我所想的去做的話,它將是一個未定義的行為。

"將一個已有對象的 bits 移動到另一個緩衝區,好讓我們可以試驗性地在這片內存中構造一個新的對象,然後再從臨時存儲中將 bits 移回並銷毀舊的對象,這是否是一個騙局?

"標準中並沒有允許這樣做:在一個時候只能有一個對象可以擁有一個給定的地址。請見標準的 3.8 節,特別是第4段。"

此外,後來的測試很快就表明,這個方法在並行環境下有可能會創建矛盾的競爭條件。

最後,即使以上方法可以在特定平台的特定編譯器上工作,也還需要找到可移植的解決方案。

初步的方案:雙存儲

瞭解到以上方法的不可行之後,Anthony Williams 在 [Wil02] 中提議了另一個方法,作為可移植的 variant 的預發佈版本實現。

這個方法的基本思想被稱為 "雙存儲",為一個 variant 提供足夠的空間來保存任意兩個有界類型的值。

有了第二份存儲,就可以在不銷毀左操作數的內容的前提下嘗試對右操作數的複製;因此,在發生異常時左操作數的內容仍保持有效。

所以,基於此方法,variant 的實現只需跟蹤哪一份存儲保存了當前內容 -- 從而對所有訪問請示、查詢等進行分派。

這一方法最明顯的缺點就是空間的開銷。雖然在特殊情況下可以進行一些優化以消除對兩份存儲的需要 -- 對於特定的有界類型或在某些情形下(相關細節請看 “進行優化” 一節) -- 但是在 Boost 郵件列表中的大多數用戶還是強烈反對使用雙存儲。具體地說,雙份存儲的的開銷幾乎在所有時間都需要 -- 即使從未對 variant 進行過賦值。由於這些那些的原因,我們開發了新的方法。

當前的方法:臨時的堆備份

儘管對於雙存儲方案有很多的反對意見,但是我們還是認識到不存在沒有缺點的替代方案。因此,我們需要一些折衷。

最後,Dave Abrahams 建議對 variant 的賦值行為增加以下規定:"從一個類型到另一個類型的 variant 賦值可能引起動態分配"。即,雖然 variant 依然保持在構造後以及在賦予相同類型的值後,原位保存其內容,但是如果被賦予不同類型的值,則 variant 可能將其內容保存在堆上。

賦值的算法將如下處理:

  1. 將右操作數的內容複製構造到堆上;該數據的指針稱為 p.
  2. 銷毀左操作數的內容。
  3. p 複製到左操作數的存儲中。

因為所有對指針的操作都是不會拋出的,該方法將使得 variant 滿足其非空保證。

對於這個方法,最值得留意的是,雖然它的確消除了雙份存儲的空間開銷,但是它將動態分配的開銷引入到了 variant 的賦值之中 -- 不僅是初始的分配,而且內容將被長期保存在堆上。雖然前一個問題是不可避免的,但後一個問題可以通過以下 "臨時的堆備份" 技術得以避免:

  1. 將左操作數的內容複製構造到堆上;該數據的指針稱為 backup.
  2. 銷毀左操作數的內容。
  3. 將右操作數的內容複製構造到(現在為空的)左操作數的存儲中。
  4. 如果失敗,則將 backup 複製到左操作數的存儲中。
  5. 如果成功,則釋放 backup 所指的數據。

通過這種技術:1) 只使用了單份存儲;2) 只有當賦值失敗時,堆上的分配才是長期的;3) 成功賦值後,variant 的存儲得以保證。對於本庫的初次發佈的目的,這些特性已經可以被認為是一個滿意的折衷方案。

不過,還有一些值得注意的缺點。具體地說,可能有些用戶要求不惜代價必須避免堆分配;而其它用戶則要求通過一個用戶提供的分配器來進行堆分配。這些問題將在以後解決(請見 “未來的方向:基於策略的實現” 一節)。目前,本庫將內容的存儲方式作為一個實現細節。雖然如此,就像下一節所要講述的,有一些事情是用戶可以做的,以確保 variant 實例具有最高的效率(詳情請見 “進行優化” 一節)。

進行優化

正如在 “實現的問題” 一節 中所講,實現"非空保證"的主要困難在於,在 variant 賦值的過程中有可能發生複製構造的失敗。不過,具有不拋出異常的複製構造函數的類型顯然不會面臨這種可能性。同樣,如果 variant 的某個有界類型可以無拋出地缺省構造,那麼這一類型就可被用作複製構造失敗後的安全 "回退" 類型。

因此,variant 被設計為如果其有界類型符合以下標準,就可以使用以下優化:

  • 對於每個可以無拋出複製構造(就像 boost::has_nothrow_copy 那樣)的有界類型 T, 本庫保證 variant 只使用單份存儲且就地進行 T 的構造。
  • 如果任一有界類型可以無拋出缺省構造(就像 boost::has_nothrow_constructor 那樣),本庫保證 variant 只使用單份存儲且可以對 variant 中的每一個有界類型進行就地構造。不過請注意,如果賦值失敗,某個不確定的可無拋出缺省構造的有界類型將被缺省構造到左操作數中,以提供非空保證。

警告:在多數平台上,Type Traits 模板 has_nothrow_copyhas_nothrow_constructor 缺省對於所有 classstruct 類型返回 false. 因此需要為用戶自定義類型提供這些模板的適當的特化版本,示範如下:

// ...在你的代碼中 (文件域)...

namespace boost {

template <>
struct has_nothrow_copy< myUDT >
: mpl::true_ { }; }

實現說明:為了使得在遇到異常後 variant 的行為更可預測,當前的實現在 boost::blank 被指定為有界類型時會優先缺省構造 boost::blank 而不是其它可以無拋出缺省構造的有界類型。(如果這一點被認為是有用的,則它將成為 variant 規格的一部分;否則它將被廢棄。請向 Boost 郵件列表提供反饋。)

未來的方向:基於策略的實現

正如前一節中的示例,我們進行了更多的努力,以在性能、數據大小和堆的使用之間提供一個平衡。而且,基於 variant 的有界類型的特定 traits,還可以進行特殊的優化。

不過,還是有些用戶對於選定的折衷不滿意(例如:堆的分配必須不惜代價地避免;如果要用堆分配,就必須使用定制的分配器;等等)。因此,本庫的未來版本將支持 variant 的一個基於策略的實現。雖然它不能完全解決前面章節中所說的問題,但是它允許折衷的決定由用戶而不是庫的設計者來作出。

Copyright © 2002, 2003 Eric Friedman, Itay Maman

PrevUpHomeNext