续C++STL中std::string的缓冲问题

Question

前段时间发了个类似的问题都问不出个答案来，貌似用STL的人多，但真正要深究STL的人少啊，为了证实我的猜测，STL的string的内存实际运行时被CACHE命中的概率比我的string高，哥蛋疼的去搞了个intel VTune Amplifier XE 2011，来进行分析，不过2011原版没有哥笔记本I3 2代的分析配置，要去升级了下，今天终于可以分析了。这个分析器功能非常强大，连很多CPU事件都能分析出来，（原帖问题http://www.oschina.net/question/253717_79668）

下面的是内存访问情况的分析：

第一行的参数是CPU的指令周期,第2行开始按下图解说的顺序

STL string在一级缓存下的数据远比我的多，测试环境是WIN7 I3 2代智能处理器,编译器ICC XE 12，和VC10编译器，在这个测试环境下都是STL的string快，而且不是快一点，至少是20%以上。在这个环境下，使用我的string，三叉树搜索字符串的速度要比avl树的快1~20%。

但同样的程序在XP SP3 I3 1代智能处理器测试，使用ICC和VC的编译器编出来两个运行时间是一样的。这个环境下，使用我的string，avl树的搜索字符串的速度要比三叉树的快1~20%。

这个搞不清是系统的问题还是处理器的问题，看谁有同时装了WIN7和XP的电脑来试试。

 Intel Parallel Studio XE 2011可以自行到intel的官方网下，我有老番的lic，用上去就不是30天的试用版，可以在线升级的长期版，不过涉及版权的问题，出于学习研究目的的可以向哥索要老番的lic，或者自己到网上下。

Answer 1

发现果然是这个做法能提供cache的命中率，哥将这种短字符的字符串放自身小内存机制加到自己的string上面去，速度就能与stl的string持平。

不过不知道是不是win7的cache机制，还是怎么，目前暂时没在其他操作系统测试过

发现提高cache的命中率的做法，比做指令数算法优化更加靠谱，在cache取值跟dram里取值在带宽省的速度就能比算法优化的多得多。

Answer 2

呃 std::string的实现确实会有你说的这种情况，对于小字符串直接保存所用空间，对于大一点的字符串保存指向的指针.然后照着这种理解的话，std::string会把那部分空间直接放到cache中，而指针每次都必须从dram中获取内容，不知道是不是这样。。。没有windows测试环境。

Answer 3

今天用CPU带宽测试了下，对着汇编看了看，发现比较字符串的时候，用作key比较用的字符是从cache中取，而另一个比较参数的字符则STL取的从cache上取，而我的string 从dram里取，然后我准备跳到std::string的alloc怎么实现的时候发现，原来intel ComposerXE-2011并没有带上intel的c++标准库，虽然vs2010已经将编译器选择成icc，但库还是使用vc的stl库，而vc的stl库的alloc不知道藏在什么地方，知道的大神告诉下。

Answer 4

      感觉你描述问题不清楚. 那天你说你的代码就是一个比较函数就和string差异巨大.现在文章里又提什么3叉树, avl树....... 能单纯说某个函数吗? 如果是复杂的逻辑, 当然cache命中率就不一样了.  如果就是简单的字符串比较, 我不理解你的字符数组和string内部的字符数组在相同内容的情况怎么可能让CPU区别对待.

　　提高cache命中率就2点, 接下来访问的内存都在最近访问的内存附近, 最近访问的内存很快还会访问.  cache的2大原理. 你没提到的那些复杂的代码是否考虑了这些呢? 像快速排序比堆排序快, 有些研究就谈到了cache的原因.

       是你外部复杂的操作导致了cache的差异, 而不是string的实现.

Answer 5

我用来测试的代码，用的一个模板类，而且两个string比较都是只使用字符首指针操作和字符长度，没用其他过于复杂的操作，而反汇编后代码也比较一致。实在想不出你说的外面复杂操作是哪些操作。

Answer 6

这个是用测试软件测试出来的，不是乱吹，我也想知道为什么，那样我的string也一样能提高在cache L1的命中率。这个测试源自于同样的字符串比较函数，加上几乎同样的release汇编比较，而字符串只取字符首指针和字符长度进行操作，结果却出现一个速度远超于另外一个的情况，而且这个多次测试结果一致。

Answer 7

恩，哥们您能不能给我们科普下： cpu cache 和 命中率。以及现在cpu的cache有多大？以及 cpu 一二级缓存是怎么跟std::string 扯上关系的。还有别跟我说用google和百度及bing。因为我想听听您的高见。

Answer 8

cache不透明，但不知道怎么弄的，我测试好多次，显示结果都一样，std::string就是在cache L1的比我的多，在我那电脑测试icc和vc的编译器都是std::string会出现那个情况，在我单位的电脑上两个编译器出来的运行时间是一样的。

Answer 9

cache准确来说对于写上层软件的人来说是不透明的，如果裸奔，或者写驱动的另当别论，如果想要lic的话，将邮箱留下。

Answer 10

回复
tianxialangui@gmail.com，万分感谢

Answer 11

楼主威武，特别佩服打破沙锅问到底的精神。不过我总觉得似乎不太可能，cache不是对程序员透明么？难道又被大学的教科书害了？？而且intel的编译器都没有做这种优化。最后表示想要那个lis。

Answer 12

你回帖是为啥呢？ 看到这标题不喜欢就别点开，世界不就安静了？

Answer 13

研究这个, 是为啥呢?

Answer 14

貌似哥发现为啥stl的string cache命中那么高了，std::string里面vc版的_String_val
里面存的一个叫_Bx的联合，里面有16个字符的栈空间BUFFER，std::string是继承这个类的，在data里面掉c_str里面掉_Myptr里面的调用是这样的

const _Elem *_Myptr() const
		{	// determine current pointer to buffer for nonmutable string
		return (this->_BUF_SIZE <= this->_Myres ? this->_Bx._Ptr
			: this->_Bx._Buf);
		}

在16个字符以下的字符串直接用联合里面的字符空间，超过16个字符的用堆指针空间的字符。

// TEMPLATE CLASS _String_val
template<class _Elem,
	class _Alloc>
	class _String_val
		: public _Container_base
	{	// base class for basic_string to hold data
public:
 #if _ITERATOR_DEBUG_LEVEL == 0
	typedef typename _Alloc::template rebind<_Elem>::other _Alty;

	_String_val(_Alty _Al = _Alty())
		: _Alval(_Al)
		{	// construct allocator from _Al
		}

	~_String_val()
		{	// destroy the object
		}

 #else /* _ITERATOR_DEBUG_LEVEL == 0 */
	typedef typename _Alloc::template rebind<_Elem>::other _Alty;

	_String_val(_Alty _Al = _Alty())
		: _Alval(_Al)
		{	// construct allocator from _Al
		typename _Alloc::template rebind<_Container_proxy>::other
			_Alproxy(_Alval);
		this->_Myproxy = _Alproxy.allocate(1);
		_Cons_val(_Alproxy, this->_Myproxy, _Container_proxy());
		this->_Myproxy->_Mycont = this;
		}

	~_String_val()
		{	// destroy the object
		typename _Alloc::template rebind<_Container_proxy>::other
			_Alproxy(_Alval);
		this->_Orphan_all();
		_Dest_val(_Alproxy, this->_Myproxy);
		_Alproxy.deallocate(this->_Myproxy, 1);
		this->_Myproxy = 0;
		}
 #endif /* _ITERATOR_DEBUG_LEVEL == 0 */

	typedef typename _Alty::size_type size_type;
	typedef typename _Alty::difference_type difference_type;
	typedef typename _Alty::pointer pointer;
	typedef typename _Alty::const_pointer const_pointer;
	typedef typename _Alty::reference reference;
	typedef typename _Alty::const_reference const_reference;
	typedef typename _Alty::value_type value_type;

	enum
		{	// length of internal buffer, [1, 16]
		_BUF_SIZE = 16 / sizeof (_Elem) < 1 ? 1
			: 16 / sizeof (_Elem)};
	enum
		{	// roundup mask for allocated buffers, [0, 15]
		_ALLOC_MASK = sizeof (_Elem) <= 1 ? 15
			: sizeof (_Elem) <= 2 ? 7
			: sizeof (_Elem) <= 4 ? 3
			: sizeof (_Elem) <= 8 ? 1 : 0};

	union _Bxty
		{	// storage for small buffer or pointer to larger one
		_Elem _Buf[_BUF_SIZE];
		_Elem *_Ptr;
		char _Alias[_BUF_SIZE];	// to permit aliasing
		} _Bx;

	size_type _Mysize;	// current length of string
	size_type _Myres;	// current storage reserved for string
	_Alty _Alval;	// allocator object for strings
	};

看这个，这个就是我所说的联合

union _Bxty
		{	// storage for small buffer or pointer to larger one
		_Elem _Buf[_BUF_SIZE];
		_Elem *_Ptr;
		char _Alias[_BUF_SIZE];	// to permit aliasing
		} _Bx;

不过哥不确认这样用小buffer空间是否一定能提高cache的命中率，还有这个会不会带来的副作用。还有char _Elem _Buf[_BUF_SIZE];这里存的是16个字符空间的数据还是这16字符空间的首指针，按我的理解是存16个字符空间的数据，这样的话才可能尽最大的可能使用到栈空间的资源，那样被cache的可能性才更高。

而这样的设置在我的string里面并不存在，而测试数据的大部分数据都是小于16字节的字符串。所以是不是用大量超过16字节字符串的测试数据就能出现一样的测试结果还是怎么，有这样的测试数据的，希望谁能提供下。