Posted on June 8th, 2008 at 15:02 by fr3@K
前一陣子花了些時間寫一個 allocator library. 首要目標就是要能符合 C++ Standard 對 allocator 定義的 requirement. 當然也要相容於 Standard C++ Library 的 container 實作, 能與所有的 container function 正確的 inter-operate. 在這個過程中, 我意外地一腳踏進又一個 C++ 的陰暗角落.
先讓我把這個有點嚇人的結論寫在前面:
-
你所使用的標準 container , 很可能無法完全正確地與 object-stateful1 的 allocator 一起運作. 即便該 allocator 確實是符合標準規範的.
不過先別慌. 只要拿來與 container 搭配使用的是沒有 per instance 狀態的 allocator2, 你就不會遭遇本文所討論的問題.
我在這個 pet project 裏面規劃了兩個 object-instance stateful 的 allocator class template. 第一個是專為 (在 function scope 內用過即丟) temporary object 的 allocation 設計並最佳化, 叫作
tmp_allocator. 第二種是 pool_allocator. 在 Boost 已經有 boost::pool_allocator 的情況下另外做一個 memory pool allocator 的原因是 boost::pool_allocator 其實只不過是 boost::singleton_pool 的一個 adapter/wrapper. 也就是說它是沒有 per instance 狀態的. 而這對無法滿足我設定的一些使用狀況, 我希望相同類別的 container instance 可以使用不同 (memory pool) allcoator instance. 當然, 這些 (現在知道) 無法實際應用的規劃都是在我了解這篇文字要說明的問題之前就已經做好的.
先讓我簡單解釋一下 container 與 allocator 之間的關係以及兩者的相關部份特性.
每一個 container instance 都擁有一個 allocator instance.3 從 C++98 可以清楚了解 allocator 是被設計成可以有 per instance 狀態的. 譬如 lib.allocator.requirements 要求能夠比較同一類別的 allocator instance 的 equality 與 inquality. 更精確的說, 兩個 alloctor instance 的 equality/inequality 比較是在測試從 allocator 1 得到的 memory 是否可以拿到 allocator 2 去釋放. 在 lib.containers 也可以看到, 所有 container 的每一個 constructor 都接受 allocator 當參數.4 Container 在建構的時候都會複製外部傳進來的 allocator. 這隱含了 allocator 的 per instance 狀態不能是直接的 (or 不該是直接的?). 我想沒有一個神智清楚的人會把 allocator 設計成直接管理記憶體, 而導致 allcoator 在 copy-construct 的時候必須把內容 deep copy 到另一個 allocator. 因此, allocator 可以有的 per instance 狀態該是間接的. 一種合理的設計是在 allocator 下層另有某種 memory manager 的機制. 不同的 allocator instance 可以參考到同一個 memory manager, 也可以參考到不同的 memory manager. 於是複製有 per instance 狀態的 allocator 就等同於創建多一個參考到同一個 memory manager 的 allocator instance. 這又間接表示了同一類別的 container instance 可以各自 (間接) 使用不同的 memory manager.
問題來了. 兩個相同類別的 container instance, c1 and c2, swap 是怎麼實作的? 特別是在兩個 container instance 擁有的 allocator 不相等時 (i.e. c1.get_allocator() != c2.get_allocator()), 是怎麼 swap 的?
-
= mini tutorial =
典型的 vector implementation 內部會有三個 member data. 分別指向 vector instance 所管理的連續 object array 的頭尾以及已 allocate 了但目前不是使用中的記憶體末端.
0 ~ 4: managed elements x : allocated but unused memory blocks +---+---+---+---+---+---+---+---+.... | 0 | 1 | 2 | 3 | 4 | x | x | x | : +---+---+---+---+---+---+---+---+.... ^ ^ ^ | | | start finish end of storage
= end mini tutorial =
以 vector 為例. 先看 GCC default 搭配的 libstdc++ 是怎麼做的:
template<typename _Tp, typename _Alloc>
void
vector<_Tp, _Alloc>::swap(vector& __x)
{
std::swap(this->_M_impl._M_start, __x._M_impl._M_start);
std::swap(this->_M_impl._M_finish, __x._M_impl._M_finish);
std::swap(this->_M_impl._M_end_of_storage,
__x._M_impl._M_end_of_storage);
}
不考慮 allocator 就直接 swap 這三個 pointer 可是會造成很大的問題. 在 c1.swap(c2) 時, 兩個 container instance 所管理的 memory 可以是從兩個不同的 stateful memory manager 那邊 allocate 到的, 比方說兩個不同的 memroy pool. 將從 memory pool 1 所 allocate 到的 memory 釋放到 memory pool 2 去, 迎接你的很可能不是 assertion failure (如果有燒香的話, 否則) 就是 undefined behavior, 很難期待會有好的結果.
再來看看另外兩個類似的 implementation. VC++ 2005 (from DINKUMWARE):
template<class _Ty,
class _Ax>
void vector<_Ty, _Ax>::swap(_Myt& _Right)
{ // exchange contents with _Right
if (this->_Alval == _Right._Alval)
{ // same allocator, swap control information
#if _HAS_ITERATOR_DEBUGGING
this->_Swap_all(_Right);
#endif /* _HAS_ITERATOR_DEBUGGING */
std::swap(_Myfirst, _Right._Myfirst);
std::swap(_Mylast, _Right._Mylast);
std::swap(_Myend, _Right._Myend);
}
else
{ // different allocator, do multiple assigns
_Myt _Ts = *this; *this = _Right, _Right = _Ts;
}
}
以及由 Rogue Wave donate 給 Apache 的 STDCXX:
template <class _TypeT, class _Allocator>
void
vector<_TypeT, _Allocator>::swap (vector& _Right)
{
if (get_allocator () == __other.get_allocator ()) {
pointer __tmp = _C_begin;
_C_begin = __other._C_begin;
__other._C_begin = __tmp;
__tmp = _C_end;
_C_end = __other._C_end;
__other._C_end = __tmp;
__tmp = _C_bufend;
_C_bufend = __other._C_bufend;
__other._C_bufend = __tmp;
}
else {
// not exception-safe
_C_unsafe_swap (__other);
}
}
這兩個 implementation 的 swap 基本上是相同的, 都考慮到了 allocator 的 equality. 在兩個 allocator instance 相同的時候都是 swap 三個 pointer. 在不相等的時候則都是用到了一個 temporary 的 vector instance, 做一次 object level 的淺層 swap (e.g. T tmp(*this); *this = other; other = tmp;). 這個策略在 allocator 不相等時的確避開了 libstdc++ 的困境, 但卻引進了另外兩個問題. 一是把本該是 O(1) 的 swap 變成 O(N), swap 不再一定是絕對輕鬆的操作. 另一個是問題是這種 swap 將不再具有 no-throw 的 exception-safety 保證. 這兩個改變 (IMO, 非常糟糕地) 推翻很多用到 swap 的 algorithm 所做的假設或期望, even within the STL itself!!!
C++ Standard Library Active Issues List 的 issue 431 如此寫道:
431. Swapping containers with unequal allocators
Section: 20.1.5 [lib.allocator.requirements], 25 [lib.algorithms] Status: Open Submitter: Matt Austern Date: 20 Sep 2003
Clause 20.1.5 [lib.allocator.requirements] paragraph 4 says that implementations are permitted to supply containers that are unable to cope with allocator instances and that container implementations may assume that all instances of an allocator type compare equal. We gave implementers this latitude as a temporary hack, and eventually we want to get rid of it. What happens when we’re dealing with allocators that don’t compare equal?
根據這段文字, Standard Library 的 implementaion 可以不具備處理本文討論的 allocator instance 不相等的能力, 並允許 implementation 假設它們都相同. 這是個在計畫中將會被移除, 一個給實作者方便的暫時性 hack.
IMHO, 這個方便讓整個 container/allocator 架構跛了腳. 沒有辦法更彈性地將具有特別功能的 allocator 搭配 container 使用, i.e. special purpose allocators those are object stateful.
看到這裡可能已經有人想到, 如果在 swap 的時候不只 swap vector 的三個 pointer, 把 vector 的 allocator instance 也一併 swap 過去就可迴避掉前面提到的兩種實作遭遇到的麻煩. 偏偏 C++08 並不要求 allocator 俱備被 swap 的能力.5 也就是說不能被 swap 的 (user-defined) allocator 也是完全符合規範的. 我猜就是因為這個原因, 使得這些 implementaion 寧願將就 non-swappable (user-defined) allocator,6 而不願意採用這個策略實現 container 的 swap function, 即便 std::allocator 是完全可以被 swap 的.
最後, 我們來看 STLport 的 vector::swap:
template <class _Tp, class _Alloc>
void vector<_Tp, _Alloc>::swap(__Self& __x) {
_STLP_STD::swap(this->_M_start, __x._M_start);
_STLP_STD::swap(this->_M_finish, __x._M_finish);
this->_M_end_of_storage.swap(__x._M_end_of_storage);
}
乍看之下這個 implementation 似乎跟 libstdc++ 的實現是類似的, 往下鑽進去會發現完全不是那麼一回事. 它 swap 的第三個 member data, _M_end_of_storage, 的類別跟其他 implementation 不同, 不是個 pointer. 是一個類別為 _STLP_alloc_proxy<pointer, _Tp, allocator_type> 的 object instance. _STLP_alloc_proxy 提供了兩個功能, pointer to end of storage, 以及針對沒有 per instance 狀態的 allocator 做的 Empty Base Optimization. 所以當 _M_end_of_storage 被 swap 的時候, 是連 allocator 也一起 swap 的. 就這個功能來說 STLport 的實現是最合乎 real world 的真實狀況, 卻必須付出不符合標準的代價, 因為無法與不能被 swap 但符合標準規範的 allocator 一起運作.
從這篇文字討論的問題可以發現, 標準並不一定是完善的. 雖然 遵從標準的規範 通常個好習慣, 但重視標準甚於實際的應用卻是要不得的. 還不確定這個 issue 未來的發展會是如何, 只知道已經進了 C++ 委員會的 issue list, 期望能在 C++0x 得到修正. 讓 STLport 的實現符合標準, 更鼓勵其他的 implementation 也轉而採取更實用也更安全的實現策略.
[Update]
原本我是以理解的角度來看待 VC++ 2005 的 C++ Standard Library 與 STDCXX 這兩個實作為了符合 C++98 的標準所做的妥協.
但想到標準沒有要求 allcator 能夠被繼承 (至少我找不到相關的文字敘述). 也就是說一個 不能被繼承 (另一篇討論這個技巧的文章) 的 allocator class 仍舊可以是符合標準的.
STDCXX 使用了 Empty Base Optimization 這個優化, 讓 vector 繼承自 allocator. 換句話說使用者不能拿一個符合標準但不可以被繼承的 allocator 來與 STDCXX 的 container 一起使用. 因此, STDCXX 是不符合標準規範的.
沒想到檢視一個小小的 vector::swap 所得到的結果, 竟然是 MS 的產品最符合標準.
ps. 本篇談到的四個 implementation 之中, 只有 VC++ 的 container 沒有對 allocator 施以 Empty Base Optimization.
[References]
- Issue 431, C++ Standard Library Active Issues List
- n1599, C++ Standards Committee Papers
- libstdc++
- C++ Standard Library, VC++ 2005
- STDCXX from Apache
- STLport
- 每個同類別的 object instance 可以有各自不同的狀態. 例如 non-static member data [↩]
- 例如
std::allocator與 Boost.Pool 的pool_allocator以及fast_pool_allocator都是沒有 per instance 狀態的 allocator [↩] - 有些 stdlib 的 implementaion 在 contaner 使用沒有 per instance 狀態的 allocator 時, 會最佳化成所有相同類別的 container instance 都使用同一個 allocator instance, 以減少 container instance 的 memory foot print [↩]
- 由於 container 內嵌 allocator, 因此看似沒有 allocator 當參數的 copy-constructor 其實也隱性地傳遞了 allocator [↩]
- 一個方法是在 allocator 的 namespace 內定義 free function 版本的
swap(allocator&, allocator&). 另一種作法是讓 allocator (在已有 copy ctor 的前提下) 具有被指派 (assignment operator) 的能力 [↩] - 在實踐中, 我從沒見過 non-swappable allocator [↩]
        |
|
| Previous Post « Why Const Matters « |
Next Post » Live (MS) Search Spam » |
(But I could be wrong :P)
不過老闆還沒把我 fire 掉, 還是有在幹事啦~~
Allocator per instance is used for performance generally.
The issues you raise is not real problem you gonna happened, unless
you don’t know how the whole idea works.
If you concern too much , nothing will be done before everything is perfect.
It’s not reasonable to exchange data between two same class object by different
allocator. It won’t and should’nt be happened in real work. Unless the coder is idiot.
Comment by Ziyu Huang — October 9, 2008 @ 7:11