https://www.youtube.com/watch?v=vElZc6zSIXM&t=1157s 

LLVM internal data structures

LLVM 内部数据结构

 

下面是 SmallVector 的简化版本。这是 LLVM 里最基本的数据结构，到处被使用。

问题：为什么不直接使用 STL 的 vector? 因为在 STL 里，如果对 vector 进行 move 操作，按照规范，迭代器还要保持有效。这个特性虽好，但带来的问题是，不能进行 small-size 优化。

 

左边：仅仅有缓存 (char Buffer[])

右边：基类看起来像个 vector，但是没有缓存。缓存是通过基类的构造函数传入的。这种模式是非常强大的，因为类型擦除了 N

类型擦除N的好处？跨越接口边界的时候，不用关心这个N

 

It is a smalll size optimized set. Unlike std::unordered_set, instead we use open addressing here, an array of buckets, flat in memory. We use quadratic probing (二次探测). The traits class is related to hashing.

 

The map uses the same traits class.

For empty and tombstone buckets, don‘t put complete pair into those buckets. Acutually, just put the keys into them (special code).

 

LLVM，对于通用的数据机构，99%都是基于以上三个small size optimized containers。

 

 

上图是有人一种建议的实现方式（使用allocators二不是custom containers）。这个solution是能工作的，但是...

 

问题1：有人可能会忘了让这些数字在所有的callers都同步，否则...booom。也许有办法解决这个问题，但是很难找到简单有效的方法

 

问题2：返回这个vector对象的时候，很有可能这个vector包含memory在stack里面。也许也是有办法解决了，但是很challenging

使用costomed containers，而不是allocators，所有这些问题都消失了。

 

works way better when the values are really small. 这是最最critical的！这样才有足够高的密度。所以真正的challenges，是优化这些values，使他们足够小。这比有上面那些containers更重要。Containers不难，但是有效的使用好它们需要很多的工作。

 

address identity: 对象有内在的ID吗？something unique about the object。如果仔细分配，可以借用地址作为ID

借用地址做ID，可以如上使用container。

问题：为什么不使用forward list?上面的用法比forward list效果好很多！因为地址是连续的，对缓存相对友好。如果遍历forward list,必须先要读出一个对象，才能知道下一个对象的地址在哪里。也就是如果有一次cache miss，就会有一序列的cache misses.

但是以上的用法也有问题，这些大对象本事没有locality。他们内存分配的时候一般都是随意哪里有内存就在哪里，根本没有locality。所以LLVM使用下面可怕的BumpPtrAllocator

 

"World‘s worst malloc implementation". Nice thing about this:

 

 

结合之后的提问：这里的bit operations基本上cost非常低，大多都是compile time的cost

 

TinyPtrVector can be a T or a vector of T

The most useful case of this is for multi map:

  template <typename KeyT, typename ValueT>

  using SmallMultiMap = SmallDenseMap<KeyT, TinyPtrVector<ValueT>>;

 

 

 

  不能依赖hash or set的ordering

  When possible, sort vectors

  有时候，按照什么排序不重要，但一定需要deterministic，也就是需要一个确定的顺序

 

  类似的有 template class SmallMapVector;

  可以进一步优化，当数量小的时候，只使用vector, 线性搜索有更高的效率