8
回答
续C++STL中std::string的缓冲问题
利用AWS快速构建适用于生产的无服务器应用程序,免费试用12个月>>>   

前段时间发了个类似的问题都问不出个答案来,貌似用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,或者自己到网上下。

STL
举报
cut
发帖于5年前 8回/2K+阅
共有8个答案 最后回答: 5年前

貌似哥发现为啥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字节字符串的测试数据就能出现一样的测试结果还是怎么,有这样的测试数据的,希望谁能提供下。

楼主威武,特别佩服打破沙锅问到底的精神。不过我总觉得似乎不太可能,cache不是对程序员透明么?难道又被大学的教科书害了??而且intel的编译器都没有做这种优化。最后表示想要那个lis。
--- 共有 3 条评论 ---
永远在一起回复 @cut : tianxialangui@gmail.com,万分感谢 5年前 回复
cutcache准确来说对于写上层软件的人来说是不透明的,如果裸奔,或者写驱动的另当别论,如果想要lic的话,将邮箱留下。 5年前 回复
cutcache不透明,但不知道怎么弄的,我测试好多次,显示结果都一样,std::string就是在cache L1的比我的多,在我那电脑测试icc和vc的编译器都是std::string会出现那个情况,在我单位的电脑上两个编译器出来的运行时间是一样的。 5年前 回复

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

--- 共有 1 条评论 ---
cut这个是用测试软件测试出来的,不是乱吹,我也想知道为什么,那样我的string也一样能提高在cache L1的命中率。这个测试源自于同样的字符串比较函数,加上几乎同样的release汇编比较,而字符串只取字符首指针和字符长度进行操作,结果却出现一个速度远超于另外一个的情况,而且这个多次测试结果一致。 5年前 回复
      感觉你描述问题不清楚. 那天你说你的代码就是一个比较函数就和string差异巨大.现在文章里又提什么3叉树, avl树....... 能单纯说某个函数吗? 如果是复杂的逻辑, 当然cache命中率就不一样了.  如果就是简单的字符串比较, 我不理解你的字符数组和string内部的字符数组在相同内容的情况怎么可能让CPU区别对待.
  提高cache命中率就2点, 接下来访问的内存都在最近访问的内存附近, 最近访问的内存很快还会访问.  cache的2大原理. 你没提到的那些复杂的代码是否考虑了这些呢? 像快速排序比堆排序快, 有些研究就谈到了cache的原因.
       是你外部复杂的操作导致了cache的差异, 而不是string的实现.
--- 共有 1 条评论 ---
cut我用来测试的代码,用的一个模板类,而且两个string比较都是只使用字符首指针操作和字符长度,没用其他过于复杂的操作,而反汇编后代码也比较一致。实在想不出你说的外面复杂操作是哪些操作。 5年前 回复
今天用CPU带宽测试了下,对着汇编看了看,发现比较字符串的时候,用作key比较用的字符是从cache中取,而另一个比较参数的字符则STL取的从cache上取,而我的string 从dram里取,然后我准备跳到std::string的alloc怎么实现的时候发现,原来intel ComposerXE-2011并没有带上intel的c++标准库,虽然vs2010已经将编译器选择成icc,但库还是使用vc的stl库,而vc的stl库的alloc不知道藏在什么地方,知道的大神告诉下。
呃 std::string的实现确实会有你说的这种情况,对于小字符串直接保存所用空间,对于大一点的字符串保存指向的指针.然后照着这种理解的话,std::string会把那部分空间直接放到cache中,而指针每次都必须从dram中获取内容,不知道是不是这样。。。没有windows测试环境。

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

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

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

顶部