最近在做一个性能要求较高的项目,有个服务器需要处理每秒2万个udp包,每个包内有40个元素(当然这是高峰期)。服务器需要一个链表,算法中有个逻辑要把每个元素添加到链表末尾(只是这个元素对象的指针,不存在对象复制的问题),再从链表中把这些元素取出(另一个时间点)。就是一个单线程在做这件事。
既然逻辑这么简单,我自然选用了C++的标准STL容器List(Linux GNU,sgi的实现),想来如此简单的事情,不过是一次末尾插入,一次头部取出而已,就用STL的List容器吧。没有想到这是痛苦的开始。我预想中每秒处理80万元素应该是很轻松写意的,没想到每秒一千个包时服务器就顶不住了,处理算法的线程占用CPU达到百分之百,大量的包得不到及时处理而超时。由于算法较为复杂,定位这问题耗了不少时间,终于感觉到LIST容器似乎有严重性能问题。
于是干脆自己写了个简单的链表,替代了STL的容器后性能有了极大的提升。为此我特意写了个简单的程序,大致模仿我算法中的场景,程序流程如下:
每3秒中向链表中插入N个元素(指针),再把这N个元素从链表中取出释放。之后查看耗时t,如果t小于3秒,就sleep(3-t)秒,并打印出睡眠的时间。
在我的测试机上,出现了差异很大的测试结果,大约每3秒测试2万个元素时,使用STL LIST的压力程序导致CPU已经达到70%了,而使用自己写的简单链表几乎没有感觉。直到每3秒测试2000万个元素时,才导致CPU占用80%。结果有一千倍的差距!这里没有对象的复制,我插入链表的都只是指针而已!
(下面附测试程序,这里只是对比两种list的性能,机器的参数并不重要。请大家注意71行代码)
#include <list> #include <sys/time.h> #include <iostream> using namespace std; //待测试的对象,链表中的每个元素就是对象A的指针 class A {}; //每3秒钟插入链表末尾/从链表首部取出的元素个数 int testPressureNum = 40000; //测试的STL链表 list<A*> testList; //自己写的链表 typedef struct { A* p; void* prev; void* next; } SelfListElement; SelfListElement* myListHead; SelfListElement* myListTail; int myListSize; //向自己写的链表首部添加元素 bool add(A* packet) { SelfListElement* ele = new SelfListElement; ele->p = packet; myListSize++; if (myListHead == NULL) { myListHead = myListTail = ele; ele->prev = NULL; ele->next = NULL; return true; } ele->next = myListHead; myListHead->prev = ele; ele->prev = NULL; myListHead = ele; return true; } // 从自己写的链表尾部取出元素 SelfListElement* get() { if (myListTail == NULL) return NULL; myListSize--; SelfListElement* p = myListTail; if (myListTail->prev == NULL) { myListHead = myListTail = NULL; } else { myListTail = (SelfListElement*)myListTail->prev; myListTail->next = NULL; } return p; } //从STL链表中取出元素并删除 void testDelete1() { while (testList.size() > 0)//这行语句有严重性能问题,size的复杂度不是常量级,而是O(N),请注意!就是这里跳坑里去了 { A* p = testList.back(); testList.pop_back(); delete p; p = NULL; } } //从简单链表中取出元素并删除 void testDelete2() { do { SelfListElement* packet = myListTail; if (packet == NULL) break; packet = get(); delete packet->p; delete packet; packet = NULL; } while (true); } //向Stl链表中添加元素 void testAdd1() { for (int i = 0; i < testPressureNum; i++) { A* p = new A(); testList.push_front(p); } } //向简单链表中添加元素 void testAdd2() { for (int i = 0; i < testPressureNum; i++) { A* p = new A(); add(p); } } void printUsage(int argc, char**argv) { cout<<"usage: "<<argv[0]<<" [1|2] [oneRoundPressueNum]"<<endl <<"1 means STL, 2 means simple list\noneRoundPressueNum means in 3 seconds how many elements add/del in list"<<endl; } int main(int argc, char** argv) { //为方便测试可使用2个参数 if (argc < 2) { printUsage(argc, argv); return -1; } int type = atoi(argv[1]); if (type != 1 && type != 2) { printUsage(argc, argv); return -2; } if (argc >= 2) testPressureNum = atoi(argv[2]); cout<<"every 3 seconds add/del element number is "<<testPressureNum<<endl; struct timeval time1, time2; gettimeofday(&time1, NULL); while (true) { gettimeofday(&time1, NULL); if (type == 1) { testAdd1(); cout<<"stl list has "<<testList.size()<<" elements"<<endl; } else { testAdd2(); cout<<"my list has "<<myListSize<<" elements"<<endl; } //每3秒一个周期 gettimeofday(&time2, NULL); unsigned long interval = 1000000*(time2.tv_sec-time1.tv_sec)+ time2.tv_usec-time1.tv_usec; if (interval < 3000000) { cout<<"after add sleep "<<3000000-interval<<" usec"<<endl; usleep(3000000-interval); } else cout<<"add cost time too much"<<interval<<endl; gettimeofday(&time1, NULL); if (type == 1) { testDelete1(); cout<<"stl list has "<<testList.size()<<" elements"<<endl; } else { testDelete2(); cout<<"my list has "<<myListSize<<" elements"<<endl; } //每3秒一个周期 gettimeofday(&time2, NULL); interval = 1000000*(time2.tv_sec-time1.tv_sec)+ time2.tv_usec-time1.tv_usec; if (interval < 3000000) { cout<<"after delete sleep "<<3000000-interval<<" usec"<<endl; usleep(3000000-interval); } else cout<<"delete cost time too much"<<interval<<endl; } return 0; }
一千倍的性能差距太夸张了。究竟是什么原因导致STL性能这么差呢?之前对在一些性能要求高的场景下我没怎么用过STL容器,对它还不够熟悉。这篇博客发出后,陈硕帮忙指出原来是第71行的size()方法出了问题! 将size()方法改为 empty()方法后,list性能有了大幅度提高,当然与上面自己写的链表相比还有差距,大概自写链表性能比STL的list还要高出70%左右!
我很好奇究竟size()方法干了些什么?看看它的实现!(STL的代码我下的是sgi 3.3版本)
size_type size() const { size_type __result = 0; distance(begin(), end(), __result); return __result; }
原来这个size()方法并不像自己写的链表那样,用一个变量来存储着链表的长度,而是去调用了distance方法来获取长度。那么这个distance方法又做了些什么呢?
template <class _InputIterator, class _Distance> inline void distance(_InputIterator __first, _InputIterator __last, _Distance& __n) { __STL_REQUIRES(_InputIterator, _InputIterator); __distance(__first, __last, __n, iterator_category(__first)); }
又封了一层__distance,看看它又做了什么?
template <class _InputIterator> inline typename iterator_traits<_InputIterator>::difference_type __distance(_InputIterator __first, _InputIterator __last, input_iterator_tag) { typename iterator_traits<_InputIterator>::difference_type __n = 0; while (__first != __last) { ++__first; ++__n; } return __n; }
原来是遍历!为什么获得链表长度必须要遍历全部的链表元素才能获得,而不是用一个变量来表示呢?sgi设计list的思路何以如此与众不同呢(话说微软的STL实现就没有这个SIZE方法的效率问题)?
看看作者自己的解释:http://home.roadrunner.com/~hinnant/On_list_size.html
开篇点题,原来作者是为了
splice(iterator position, list& x, iterator first, iterator last);
方法所取的折衷,为了它的实现而把size方法设计成了O(N)。
splice方法就是为了把链表A中的一些元素直接串联到链表B中,如果size()设计为O(1)复杂度,那么做splice时就需要遍历first和last间的长度(然后把链表A保存的链表长度减去first和last(待移动的元素)之间的长度)!于是作者考虑到size方法设计为O(N),就无需在splice方法执行时做遍历了!
看看splice的实现:
void splice(iterator __position, list&, iterator __first, iterator __last) { if (__first != __last) this->transfer(__position, __first, __last); }再看看transfer干了些什么:
void transfer(iterator __position, iterator __first, iterator __last) { if (__position != __last) { // Remove [first, last) from its old position. __last._M_node->_M_prev->_M_next = __position._M_node; __first._M_node->_M_prev->_M_next = __last._M_node; __position._M_node->_M_prev->_M_next = __first._M_node; // Splice [first, last) into its new position. _List_node_base* __tmp = __position._M_node->_M_prev; __position._M_node->_M_prev = __last._M_node->_M_prev; __last._M_node->_M_prev = __first._M_node->_M_prev; __first._M_node->_M_prev = __tmp; } }作者确实是考虑splice执行时,不用再做遍历,而是仅仅移动几个指针就可以了,因此牺牲了size的效率!
怎么评价这种设计呢?作者的出发点是好的,但是,毕竟绝大多数程序员都会潜意识认为 size方法的复杂度是常量级的,同时size方法也是最常用的!这个确实是作者在给我们挖坑哈!
这个例子真是告诉我们,必须谨慎使用第三方软件,特别是对它有较高的要求时,务必对将要使用它的所有方法都有足够的了解,不是满足于它能做什么,还必须要知道它怎么做到的,否则,还是老老实实用自己熟悉的工具吧。