boost.png (6897 bytes)Boost.MultiIndex Performance

compiler specifics
編譯器的特性
index
索引
examples
例子

Contents目錄

簡介

Boost.MultiIndex 使得程序員在需要多索引的功能時無需手工編寫麻煩的容器。此外，它還具有很高的效率，不論是在空間還是時間方面。為節省空間，其底層的數據結構非常緊湊，每個元素僅需要一個單結點。在時間效率方面，Boost.MultiIndex 大量使用了元編程技術以生成緊湊的成員函數實現來操作每個索引：對於帶有兩個或以上索引的 multi_index_container，運行時間可以縮減到以多個STL容器組成的手工實現的一半以上。

手工模擬 multi_index_container

用multi_index_container替代標準容器一節展示了單索引 multi_index_container與某些STL容器的等價性。現在我們來看一下如何用多個標準容器的組合來模擬帶有兩個或以上索引的multi_index_container.

考慮以下 multi_index_container 實例化： 

typedef multi_index_container<
  int,
  indexed_by<
    ordered_unique<identity<int> >,
    ordered_non_unique<identity<int>, std::greater >,
  >
> indexed_t;

indexed_t 為int類型元素維護兩個內部索引。為了採用標準STL容器來模擬這個數據結構，以下類型是一種方法： 

// 提領比較謂詞
template<typename Iterator,typename Compare>
struct it_compare
{
  bool operator()(const Iterator& x,const Iterator& y)const
  {
    return comp(*x,*y);
  }

private:
  Compare comp;
};

typedef std::set<int>  manual_t1; // 等價於 indexed_t's index #0
typedef std::multiset<
  const int*,
  it_compare<
    const int*,
    std::greater<int>
  >
>                      manual_t2; // 等價於 indexed_t's index #1

此處的 manual_t1 是保存實際元素的"基"容器，而 manual_t2 保存了指向manual_t1的元素的指針。這種設計效率極低，儘管插入元素到該數據結構很簡單： 

manual_t1 c1;
manual_t2 c2;

// 插入元素 5
manual_t1::iterator it1=c1.insert(5).first;
c2.insert(&*it1);
但是刪除操作則需要一個對數查找，而 indexed_t 的刪除操作是常數時間的： 
// 刪除it2所指向的元素
manual_t2::iterator it2=...;
c1.erase(**it2); // 注意! 執行需要對數時間
c2.erase(it2);

正確的方法是：不要在第二個容器中保存裸指針，而應該保存類型為manual_t1::iterator的元素： 

typedef std::set<int>    manual_t1; // 等價於 indexed_t's index #0
typedef std::multiset<
  manual_t1::iterator,
  it_compare<
    manual_t1::iterator,
    std::greater<int>
  >
>                        manual_t2; // 等價 indexed_t's index #1

現在，插入和刪除操作的時間複雜度與indexed_t相同： 

manual_t1 c1;
manual_t2 c2;

// 插入元素 5
manual_t1::iterator it1=c1.insert(5).first;
c2.insert(it1);

// 刪除it2所指向的元素
manual_t2::iterator it2=...;
c1.erase(*it2); // OK: 常數時間
c2.erase(it2);

這個結構可以擴展至處理兩個以上的索引。下面，我們將以這種方法的手工模擬容器來與 multi_index_container 的實例進行比較。

空間效率

multi_index_container的空間效率比它的手工模擬容器要好，這一點通過簡單的理論分析即可得到。為了簡單起見，我們忽略內存對齊的問題(內存對齊更有利於 multi_index_container)。

帶有N個索引的multi_index_container的每個節點持有一個元素的值以及N個含有各個索引的鏈接信息的頭部。所以每個結點的大小為：

SI = e + h0 + ···+ hN-1, 其中
e = 元素的大小，
hi = 第i頭部的大小。

另一方面，手工模擬容器需要為每個元素分配N個結點，其中第一個結點持有元素本身，而其餘結點則保存指向“基”容器的迭代 器。實際上，一個迭代器只是一個指向對應結點的指針，因此其大小與元素的類型無關。以上各部分相加，得到手工模擬容器中每個元素分配的空間為：

SM = (e + h0) + (p + h1) + ··?+ (p + hN-1) = SI + (N-1)p, 其中
p = 指針的大小。

multi_index_container的內存大小與手工模擬容器相比，即 SI / SM，計算如下：

SI / SM = SI / (SI + (N-1)p).

由此公式可見索引的數量越多，multi_index_container節省的內存越多。這裡有一個假定，multi_index_container 索引節點的頭部與它們的STL容器模擬物是同樣大小的；但這只是一個特例而不是常例：有序索引使用了 spatial optimization technique空間優化技術 而 std::set 的多數實現都沒有使用, 這給了 multi_index_containers 額外的優勢，每個有序索引少一個系統字的空間。如果算上這一點，以上公式應調整為：

SI / SM = SI / (SI + (N-1)p + Ow),

其中 O 為容器中的有序索引數量，而 w 為系統字的大小(在32位體系中為4字節)。

從這些分析還可以看出一個重要的事實：multi_index_container僅為每個元素分配一個結點，而手工模擬容器則分配多個不同大小的結點，這更容易造成內存碎片，因此前者有更多可用空間以及性能更佳。

時間效率

從計算複雜度(即大-O分析)的角度看，multi_index_container 與其手工模擬容器是等價的：插入元素到multi_index_container可歸納為向每個索引插入元素的總和，刪除操作也是一樣。因此，最多也就是執行時間減少(或增加)一個常量因子。我們在後面將看到，兩個或以上的 multi_index_container 的執行時間會有明顯的減少。

對於只有一個索引的 multi_index_container 的特殊情況，我們可以期望的最好結果就是相同的性能：測試表明在這種特殊情況下，性能的下降是可忽略或很少的，取決於所使用的不同編譯器。

性能測試

測試所用的源代碼請見 source code.

為了評估 multi_index_container 的效率，以下算法： 

multi_index_container<...> c;
for(int i=0;i<n;++i)c.insert(i);
for(iterator it=c.begin();it!=c.end();)c.erase(it++);

用於對不同的multi_index_container實例進行測試，其中 n 的值為1,000, 10,000 和 100,000，然後將執行時間與基於STL容器數據結構的手工模擬容器進行比較。測試使用了以下編譯器的缺省發佈設置：

測試環境
編譯器 設置 OS 和 CPU
GCC 3.4.5 (mingw special) -O3 Windows 2000 Pro on P4 1.5 GHz, 256 MB RAM
Intel C++ 7.1 缺省發佈設置 Windows 2000 Pro on P4 1.5 GHz, 256 MB RAM
Microsoft Visual C++ 8.0 缺省發佈設置, _SECURE_SCL=0 Windows XP on P4 Xeon 3.2 GHz, 1 GB RAM

相對內存耗用比(即multi_index_container所佔用的內存量與手工模擬容器相比)是指一個 multi_index_container 結點的大小除以組成手工模擬容器的所有容器的結點大小之和所得的比。

1 個有序索引的結果

以下 multi_index_container 實例被用於測試： 

multi_index_container<
  int,
  indexed_by<
    ordered_unique<identity<int> >
  >
>

其功能等價於 std::set<int>.

內存耗用

GCC 3.4.5 ICC 7.1 MSVC 8.0
80% 80% 80%
表 1: 1個有序索引的multi_index_container的相對內存耗用比

減少的內存使用來自於 Boost.MultiIndex 有序索引的優化技術實現，解釋見前文。

執行時間

performance of multi_index_container with 1 ordered index
圖 1: 1個有序索引的 multi_index_container 的性能

有點驚訝，multi_index_container 的表現稍微好於 std::set. 最可能的解釋是 multi_index_container 使用了較少內存，從而提高了處理器緩衝的命中率。GCC的性能提升最小，可能是由於其優化程度較差掩蓋了緩衝區的得益。

1 個序列索引的結果

以下 multi_index_container 實例用於測試： 

multi_index_container<
  int,
  indexed_by<
    sequenced<>
  >
>

其功能相當於 std::list<int>.

內存耗用

GCC 3.4.5 ICC 7.1 MSVC 8.0
100% 100% 100%
表 2: 1個序列索引的multi_index_container的相對內存耗用比

可見此 multi_index_container 結點的大小與對應的 std::list 相同。

執行時間

performance of multi_index_container with 1 sequenced index
圖 2: 1個序列索引的 multi_index_container 的性能

multi_index_container 的性能不如對應的STL容器，雖然數字非常接近。最差的結果同樣還是GCC，差距達7%，而ICC 和 MSVC不超過5%。

2 個有序索引的結果

以下 multi_index_container 實例用於測試： 

multi_index_container<
  int,
  indexed_by<
    ordered_unique<identity<int> >,
    ordered_non_unique<identity<int> >
  >
>

內存耗用

GCC 3.4.5 ICC 7.1 MSVC 8.0
70% 70% 70%
表 3: 2個有序索引的multi_index_container的相對內存耗用比

以上結果從理論公式得到，SI = 28, N = O = 2 和 p = w = 4.

執行時間

performance of multi_index_container with 2 ordered indices
圖 3: 2個有序索引的 multi_index_container 的性能

測試結果證實了我們的假設，multi_index_container 執行時間的提高近似於一個常量因子，本例中常量因子約為 60%。對於 n=105 時MSVC的明顯優勢，沒有顯然的解釋。

1 個有序索引 + 1 個序列索引的結果

以下 multi_index_container 實例用於測試： 

multi_index_container<
  int,
  indexed_by<
    ordered_unique<identity<int> >,
    sequenced<>
  >
>

內存耗用

GCC 3.4.5 ICC 7.1 MSVC 8.0
75% 75% 75%
表 4: 1個有序索引+1個序列索引的multi_index_container的相對內存耗用比

以上結果由公式推導得出，SI = 24, N = 2, O = 1 and p = w = 4.

執行時間

performance of multi_index_container with 1 ordered index + 1 sequenced index
圖 4: 1個有序索引+1個序列索引的 multi_index_container 的性能

對於 n=103 和 n=104，測試結果與我們的理論分析一致，常量因子比為 50-65%。奇怪的是，當n=105時，有兩個編譯器的執行速度提高了許多，即GCC和ICC。為了避免誤差，我們執行了多次測試，得到了同樣的結果。兩個測試環境配置在同一台機器，說明這種現象是某種與OS相關的原因。

3 個有序索引的結果

以下 multi_index_container 實例用於測試： 

multi_index_container<
  int,
  indexed_by<
    ordered_unique<identity<int> >,
    ordered_non_unique<identity<int> >,
    ordered_non_unique<identity<int> >
  >
>

內存耗用

GCC 3.4.5 ICC 7.1 MSVC 8.0
66.7% 66.7% 66.7%
表 5: 3個有序索引的multi_index_container的相對內存耗用比

以上結果由公式推導得出，SI = 40, N = O = 3 and p = w = 4.

執行時間

performance of multi_index_container with 3 ordered indices
圖 5: 3個有序索引的 multi_index_container 的性能

這種情況下的執行時間比基於STL的手工模擬容器快 45% 到 55%。

2 個有序索引 + 1 個序列索引的結果

以下 multi_index_container 實例用於測試： 

multi_index_container<
  int,
  indexed_by<
    ordered_unique<identity<int> >,
    ordered_non_unique<identity<int> >,
    sequenced<>
  >
>

內存耗用

GCC 3.4.5 ICC 7.1 MSVC 8.0
69.2% 69.2% 69.2%
表 6: 2個有序索引+1個序列索引的multi_index_container的相對內存耗用比

以上結果由公式推導得出，SI = 36, N = 3, O = 2 and p = w = 4.

執行時間

performance of multi_index_container with 2 ordered indices + 1 sequenced index
圖 6: 2個有序索引+1個序列索引的 multi_index_container 的性能

與預期的一樣，執行時間的提高接近常量因子，約為 45% 到 55%。

結論

我們已經看到，multi_index_container 在空間和時間效率上均優於用STL容器模擬的等價數據結構。索引的數量越多，改善越大。

特殊的情況是以單索引的 multi_index_container替代標準容器，Boost.MultiIndex 的性能與相應的STL實現相比，在空間耗用和執行時間兩方面都有提升。

compiler specifics
編譯器的特性
index
索引
examples
例子


Revised May 9th 2006

© Copyright 2003-2006 Joaquín M López Muñoz. Distributed under the Boost Software License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)