一、Eset和std::Set在同等条件下的性能比较
1.使用perf采样分析耗时
测试结果：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| # Children Self Samples Command Shared Object Symbol
94.35% 0.00% 0 Eset libc-2.31.so [.] __libc_start_main
|
---main
|
|--25.99%--eset_insert
|
|--16.38%--eset_iteration
|
|--12.99%--eset_bound_query
|
|--12.43%--stdset_insert
|
|--7.34%--eset_erase
|
|--6.78%--stdset_erase
|
|--5.65%--stdset_bound_query
|
|--4.52%--stdset_iteration
|
|--1.13%--stdset_find
|
--0.56%--eset_find
|
获得各函数比率：
1
2
3
4
5
6
7
| | 测试项 | 比率 |
|---------------|-------|
| Insert | 2.09 |
| Find | 2.02 |
| Erase | 1.08 |
| Iteration | 3.62 |
| Range Query | 2.29 |
|
2.自行测试
使用通用测试框架测试
- 预热运行：3 次（消除冷启动误差）
- 正式测试：5 次取平均
测试结果：
1
2
3
4
5
6
7
| | 测试项 | ESet (ms) | std::set (ms) | 比率 |
|---------------|-----------|---------------|-------|
| Insert | 95.20 | 45.61 | 2.09 |
| Find | 105.41 | 56.33 | 1.87 |
| Erase | 148.58 | 98.59 | 1.51 |
| Iteration | 173.13 | 68.03 | 2.54 |
| Range Query | 422.63 | 168.67 | 2.51 |
|
3.旋转次数分析
取插入次数为1e5时，旋转次数为58103，删除次数为1e5时，旋转次数为8612（测试数据均已使用shuffle打乱处理）
但是，由于我无法查看std::set的旋转次数，数据随机，暂且认为我的旋转次数符合预期。（理由：完全按照红黑树的教程进行分类处理，且处理步骤无过多冗余成分）
二、分析问题
通过上面的测试，可以看出，Eset各函数的性能均差于std::set，下面进行逐一分析：
1.插入操作
耗时在std::set的两倍左右，分析原因：
旋转次数过多，导致常数较大。
每次调用new RBNode()，而std::set使用内存池优化，std::set 的节点通常压缩到 32 bytes。（比如，为了实现range的 log(n) 时间复杂度，对每个节点新增了size，这意味着每次更新都要对size进行操作，这在一般的红黑树以及std::set中是不存在的，会减小常数大小。
2.查找
1
2
3
4
5
6
7
8
9
10
11
12
13
| iterator find(const Key &x) const {
RBNode *t = root;
whil e (t) {
if (comp(*t->data, x)) {
t = t->right;
} else if (comp(x, *t->data)) {
t = t->left;
} else {
return iterator(t,this);
}
}
return iterator(endNode,this);
}
|
根据我的代码，推测能优化的地方不多，考虑其他可能。
可能：
1.缓存不友好
ESet 的节点大小为 48 bytes，std::set 为 32 bytes。在 64KB L1 缓存中，ESet 每个缓存行（64B）只能存 1 个节点，而 std::set 可存 2个。
2.std::set 使用三路比较运算符，优化比较这一步骤。
3.迭代器与范围
由于本次大作业新增要求：ESet 拥有迭代器 iterator。在ESet中插入元素，之前老迭代器不会失效；删除时，指向删除点位置的迭代器失效，但是其他迭代器不会失效，包括end()。所以可能这是导致性能较差的原因之一。
三、改进措施
1.自我改进1
由于每个节点较为臃肿，我尝试着将每个节点压缩进32比特以内（见附件），使得缓存未命中可能性显著减少。
1
2
3
4
5
6
7
| | 测试项 | ESet (ms) | std::set (ms) | 比率 |
|---------------|-----------|---------------|-------|
| Insert | 87.20 | 49.20 | 1.77 |
| Find | 88.89 | 54.71 | 1.62 |
| Erase | 137.36 | 94.14 | 1.46 |
| Iteration | 174.47 | 80.89 | 2.16 |
| Range Query | 393.91 | 170.01 | 2.32 |
|
2.自我改进2
对于常数优化，我的basic代码版本已经是经过了一定优化的版本，并且经过尝试优化比例极小，说明常数优化较为困难。下面是另一个优化：
由于我的源代码将红黑树作为一个单独的类，每次执行Eset操作的时候都要调用Eset里的函数，这可能导致很多不必要的开销。我将红黑树删去，直接在Eset里实现（代码见附件），速度有了很大的提升：
1
2
3
4
5
6
7
| | 测试项 | ESet (ms) | std::set (ms) | 比率 |
|---------------|-----------|---------------|-------|
| Insert | 93.47 | 53.22 | 1.76 |
| Find | 88.09 | 55.41 | 1.59 |
| Erase | 133.20 | 99.73 | 1.34 |
| Iteration | 132.44 | 62.44 | 2.12 |
| Range Query | 238.52 | 156.25 | 1.53 |
|
在上面两个优化之后，我将其进行了整合，测试速度如下：
1
2
3
4
5
6
7
| | 测试项 | ESet (ms) | std::set (ms) | 比率 |
|---------------|-----------|---------------|-------|
| Insert | 78.41 | 45.03 | 1.74 |
| Find | 77.80 | 50.06 | 1.55 |
| Erase | 117.83 | 96.18 | 1.23 |
| Iteration | 134.98 | 79.17 | 1.70 |
| Range Query | 216.11 | 141.03 | 1.53 |
|
提升非常显著。
3.Skiplist实现
跳表是显而易见的一个能用来改进的数据结构，我们实现了insert和find功能，（代码在附件里），经过测试，速度比std::set快。
测试程序下的速度比较：
perf测试：
1
2
3
4
5
6
7
8
9
10
11
12
13
| # Children Self Samples Command Shared Object Symbol
80.00% 0.00% 0 Eset libc-2.31.so [.] __libc_start_main
|
---__libc_start_main
main
|
|--42.50%--stdset_insert
|
|--27.50%--eset_insert
|
|--5.00%--stdset_find
|
--5.00%--eset_find
|
自行测试：
1
2
3
4
| | 测试项 | ESet (ms) | std::set (ms) | 比率 |
|---------------|-----------|---------------|-------|
| Insert | 35.55 | 47.98 | 0.74 |
| Find | 35.06 | 50.00 | 0.70 |
|
4.Treap实现
我还实现了Treap（树堆）的insert功能，它的速度也优于std::set（见附件），测试下速度如下：
perf测试：
1
2
3
4
5
6
7
8
9
10
11
| # Children Self Samples Command Shared Object Symbol
88.96% 0.00% 0 Eset libc-2.31.so [.] __libc_start_main
|
---__libc_start_main
main
|
|--42.97%--stdset_insert
|
|--40.56%--treap_insert
|
--5.22%--other
|
自行测试：
1
2
3
| | 测试项 | ESet (ms) | std::set (ms) | 比率 |
|---------------|-----------|---------------|-------|
| Insert | 35.22 | 56.15 | 0.63 |
|
