tinySTL

STL源码剖析

Introduction

动手实现tinySTL（这里指SGI-STL V3.3，或者侯捷老师使用的GNU-C2.9）。这里只复现了allocator和container以及部分的functor和adaptor，对于算法algorithm部分没有过多涉及。通过阅读和code，能够发现其中设计思路的巧妙，这里很推荐《STL源码剖析》这本书。

docs是一些笔记和总结，仅以此仓库存档。

小插曲

实现过程中，会有各种debug，此时发现，没有测试过的代码的可靠性几乎为0，测试过的代码虽然也不一定可靠，但是潜在的bug修复过程，其实也是对内存运作理解的一个过程，这里举一些例子：

（1）模板实例化找不到合适的模板

void function(char a, char b){/* */} // 1
void function(int a, int b){/* */}   // 2
// ...
void call(){function(xx,xx);}
template<typename A, typename B>
void function(A a, B b){/* */}       // 3

这里简化了问题，调用call，有些时候可以，但是有些时候编译失败。这是因为当调用是偏特化的函数，也就是1,2这种情况，是没有问题的；但是一旦需要模板，由于定义在call之后，编译器很有可能找不到模板函数，因此出现找不到合适的模板，此时需要将call放置在模板函数之后。

（2）性能 tinySTL和工业界的STL（这里对比了Windows 11 VS v143）。对于简单对象而言（以int为例），在百万级数据的测试结果大致如下：

(i)总体效率表现上

release优于deubg模式，在debug模式下，STL会有很多assert，这是比较耗费时间的操作（tinySTL没有任何assert）。

	stl::vector<int>s;
	s.push_back(2333);
	s.clear();
	std::cout << s[0] << std::endl;

这段代码在debug下会触发assert；但是在release下可以编译通过。当然这段代码本身违反了use after free，实际程序不可能这么写。但是一方面说明了clear函数的本质（只修改指针，并未擦除内存）；也说明了release模式性能比debug好的原因之一，没有过多的assert检查。

(ii) 对比结果例如以vector的插入为例（这是插入中最坏的情况），代码如下：

	srand(NULL);
	stl::vector<int>s;
	for (int i = 0; i < 500000; ++i) {
		s.insert(s.begin(), rand() % 1000000);
	}

tinySTL版本和工业STL耗费时间大约是21s，这里性能分析器显示，消耗内存在3-4M，并且呈现阶梯上升。

不过在一般对象的测试中，工业STL性能会更好，因为借助了std::move和完美转发等技术，减少了内存的拷贝（GNU-C2.9还没有使用这一技术）。性能探测器可以测试出代码的CPU cycle花费在了哪里，有助于分析性能的瓶颈。例如可以将一些偏特化的函数去掉（如copy函数），整个代码性能会下降，花费在Construct函数调用的占比会提升。

在debug模式下，这里能够看到，上述代码大部分CPU cycle花费在了copy_backword上，因为在头部每次insert都会调用这个函数。

这里一旦将copy_backword的特化版本去掉，同样的程序在debug模式下需要耗费5s，性能分析器显示：

这里明显看出copy_backword的中指针的逐个赋值占据了大部分时间，特化版本的::memmove显然对于连续内存移动更快。

djh-sudo/tinySTL

tinySTL

STL源码剖析

Introduction

小插曲

Reference