LLVM自定義資料結構概述

主要參考資料：

http://llvm.org/docs/ProgrammersManual.html

http://llvm.org/docs/doxygen/html/

自定義資料結構的好處在于，STL在不同平台的性能不一樣，而且缺一些需要的資料結構，例如C++11之前沒有HashMaps。同時專門的資料結構會比一般化的快。

Vector

SmallVector

類似std::Vector。首先是固定容量的，其次可以如果達到上限還add元素，則會增大。

SmallVector<Instruction *, 10> worklist;
Instruction *I = ...;
worklist.push_back(I);
I = worklist.pop_back_val();
           

SmallVector的插入性能明顯優于 std::vector，提升可達1倍左右。

Maps

DensMap

DenseMap 是使用 quadratically probed HashMap，用 H+1^2, H+2^2, H+3^2...解決哈希沖突。時間高效，但是空間比一般HashMap用的多。插入後會導緻 Iterator 失效。與HashMap相比插入時間相同，查詢有明顯提升。

StringMap

專門用于String作為Key的Map。插入是使用 GetOrCreateValue()。效果StringMap<Data>的效果卻不如std::map<std:;string, Data>好。

Set

SmallSet

SmallSet<int*,1500>性能最差， SmallSet<int*, 10>與 set<int*>類似