segment_vector

项目介绍

segment_vector 实现了分段式的std::vector容器，以避免内存不足时需要进行内存的扩充并重新拷贝所带来的性能开销，接口与std::vector基本保持一致，由于segment_vector自身维护数据的内存位置，数据在实现内部分段不连续，因此便没有实现 data（）这一接口函数。

目录结构

• 源代码

  • include/: 包含源代码
    • segment_vector.h: segment_vector源代码文件
  • test/: 包含测试代码
    • acc_test.cc: 对segment_vector进行正确性测试的测试文件
    • speed_test.cc: 进行容器间的性能对比

• 运行文件

  • CMakeLists.txt
  • run.sh: 运行脚本

• 文档

  • README.md

项目运行

执行 ./run.sh 脚本，即可自动编译运行

性能测试

编写的 segment_vector 与 STL库中的 std::vector进行了性能测试，测试时间均以s为单位。

push_back 函数

push_back 函数对int 变量 类型变量进行了不同数量级下的性能测试，如下表所示，测试表示 segment_vector在push_back时的性能占据优势。

容器名	5000次	10000次	100000次	1000000次
segment_vector	0.000129162	0.000409277	0.00432841	0.0213822
std::vector	0.000222913	0.000587767	0.00501664	0.0271753

emplace_back 函数

emplace_back 函数 对 TestNode 类进行进行了不同次数下的右值拷贝的测试，如下表所示，测试表示 segment_vector在emplace_back 时的性能占据优势。

容器名	5000次	10000次	100000次	1000000次
segment_vector	0.000955368	0.00192321	0.0116304	0.123705
std::vector	0.00247594	0.00439323	0.0229091	0.178426

resize 函数

resize 函数 对 TestNode 类进行了不同容量的一次函数调用，如下表所示,测试表示 resize() 函数两者性能几乎持平。

容器名	10000个	100000个	1000000个	10000000个
segment_vector	0.00126714	0.00500408	0.067069	0.656882
std::vector	0.00111948	0.0103967	0.0728873	0.613539

traverse 遍历

traverse 遍历是对两个容器中的元素进行逐一访问来测试遍历性能，即下标[]函数的性能，测试表示，segment_vector的遍历性能较差，由于segment_vector内部是分段的，因此在取下标元素时，会进行乘法计算所占内存位置，因此损耗一定的性能。

容器名	5000个	10000个	100000个	1000000个
segment_vector	0.000512227	0.000980857	0.00892861	0.0486841
std::vector	5.305e-05	9.72714e-05	0.000969034	0.00443647

pop_back 函数

pop_back 函数 对两个容器进行了不同数量级次数下的性能测试，如下表所示,测试表示，segment_vector的pop_back性能差于std::vector，由于segment_vector内部是分段的，因此删除末尾元素时，会进行跨段的删除，即段的重定位，因此损耗一定的性能。

容器名	5000次	10000次	100000次	1000000次
segment_vector	0.000445837	0.000742018	0.00391022	0.0582047
std::vector	0.000174653	0.000277605	0.00194354	0.0157801

assign 函数

assign 函数 对 TestNode 类进行了不同容量的一次性赋值，如下表所示。

容器名	10000个	100000个	1000000个	10000000个
segment_vector	0.000556672	0.00286591	0.0297002	0.249144
std::vector	0.00043339	0.00232303	0.0238401	0.209576

assign 函数 对 TestNode 类进行了不同容量的一次性初始化列表形式的赋值，如下表所示。

容器名	10000个	100000个	1000000个	10000000个
segment_vector	0.000556672	0.00286591	0.0297002	0.249144
std::vector	0.00043339	0.00232303	0.0238401	0.209576