google.sparsetable 实现细节
与现有的一些“标准”实现不同，sparsehashtable 使用二次探测法，而不是链接，来解决hash冲突。sparsetable 就更奇特了，它是一个两级结构，第一级使用直接索引法，而第二级使用的是顺序查找。
不过，第二级的尺寸比较小，可以放入cpucache，并且它的顺序查找使用的是popcount（bitmap[i]=count of (j< i andbitmap[j]==1)）。在实现中它使用的是字节直接索引法，速度还行。第二级索引使用位图实现，如果值存在，bitmap[i]被置为1，否则为
0，当值不存在时，不会消耗内存。具体说，sparsetable::operator[i]是这样执行的：
|
1 2 3 4 5 6 7 8 9 10 11 |
// google 的代码比较长，并且不够直接，用这个直接且较短的代码来表示 value_type& sparsetable::operator[](int i) { int j = i % GroupSize; sparsegroup* group = m_groups[i / GroupSize]; unsigned char* bitmap = group->bitmap; if (bitmap[j/8] & 1 << j%8) { // value existed int valueIndex = popcount(bitmap, j); return group->values[valueIndex]; } return s_default_value; } |
还有一个顺序查找/插入的地方：group->values是一个value_type数组，它的插入、删除是O(n)，当然，在这里，因为n<=GroupSize，而GroupSize是一个编译时常量，并且不太大，google说它是O(1)也不算错。
google.GroupSize的默认值是48, 是为了更好地对齐sparsegroup结构，在64位系统上，sizeof(sparsegroup)==sizeof(void*)+(GroupSize+7)/8 +2 == 16).
其实，在intel 和 amd的新cpu的SSE4.2指令集中，有一个popcnt指令，其它一些cpu中也有popcount指令。并且，在icc/msvc/gcc的新版中都有intrinsic 支持，这比软件实现要快得多。理想上，google应该在检测有cpu支持时就直接用硬件popcount。
gcc 有以下内建函数（相当于msvc/icc的intrinsic），并且可以用于所有实现了popcount指令的cpu
|
1 2 3 |
int __builtin_popcount (unsigned int); int __builtin_popcountl (unsigned long); int __builtin_popcountll (unsigned long long); |
根据我的测试: Intel Xeon 64bit，64bit popcount, cycle unroll 8硬件popcount比 google 的软件算法快了30倍，而 sparsetable 查询时最慢的地方就在这里，事实上现在大部分主流cpu都支持硬件popcount，希望google可以改进。
要开启gcc硬件popcount，加编译选项 -mpopcnt。
goolge.sparse*系列容器依赖关系:
– sparsetable
+- sparsehashtable
++- sparse_hash_map
++- sparse_hash_set
