最近在做一个性能要求较高的项目,有个服务器需要处理每秒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方法也是最常用的!这个确实是作者在给我们挖坑哈!
这个例子真是告诉我们,必须谨慎使用第三方软件,特别是对它有较高的要求时,务必对将要使用它的所有方法都有足够的了解,不是满足于它能做什么,还必须要知道它怎么做到的,否则,还是老老实实用自己熟悉的工具吧。
分享到:
相关推荐
这种设计使得随机访问元素变得较慢,但同时也确保了在任意位置插入或删除元素的时间复杂度仅为O(1)。 #### List的主要成员函数 1. **构造与赋值** - `assign()`:给list赋值。 - `clear()`:删除list中的所有元素...
- **构造与初始化**:`list()`无参构造函数创建一个空链表,`list(size_t n)`创建包含n个默认元素的链表,`list(Container& c)`从另一个容器复制元素。 - **插入与删除**:`push_back()`和`push_front()`分别在链表...
这种设计使得在链表中插入或删除元素的时间复杂度为O(1),因为只需要改变相邻节点的指针即可。与之相比,数组型容器如`vector`在中间位置插入或删除元素时需要移动大量元素,效率较低。 `list`容器提供了丰富的成员...
通过`list<T> name(initializer_list)`或者`list<T> name(size_t n, const T& value)`来初始化list,前者使用列表初始化,后者指定元素个数和值。 2. **插入元素**: `list::insert`函数允许在指定位置插入元素,例如...
js代码-1. 给定一个数组 nums,编写一个函数将所有 3 移动到数组的末尾,同时保持其他元素的相对顺序。 示例: 输入: [0,1,0,3,12, 3, 1, 6, 3] ...- 尽量减少操作次数,争取时间复杂度为 O(n)。
- `vector`:在`vector`中,随机访问元素的时间复杂度为O(1),但插入和删除元素(尤其是中间位置)的时间复杂度为O(n),因为可能需要移动后面的元素。 3. **空间消耗** - `list`:由于每个元素都有额外的指针存储...
序列式容器是基于元素在内存中连续或接近连续存储的特点设计的,主要包括vector、deque、list等几种类型。 ##### 1. Vector 容器 - **定义**:`vector`是一种动态数组,能够自动管理内存,支持随机访问。 - **特点...
js删除数组中指定元素--splice 注意:splice() 方法会改变原始数组。 如果要保留原始数组并返回新的数组, 请使用 Array.filter() 方法。
这使得在链表中间插入或删除元素的时间复杂度为O(1)。 2. **`list`的主要成员函数** - `push_back()`:在链表尾部添加元素。 - `push_front()`:在链表前端添加元素。 - `pop_back()`:移除链表尾部的元素。 - ...
### C++容器知识点总结 #### 一、Vector **理论** `Vector` 是 C++ 标准库中的一个动态数组容器。它支持随机访问,并且能够自动管理内存。`Vector` 的内部实现是一个连续的内存区域,这使得它可以提供快速的随机...
下载的"list容器.zip"教程可能包含了各种`std::list`的实际应用示例,如动态构建、遍历、插入和删除操作,以及如何与其他容器(如`std::set`或`std::map`)配合使用。 6. **STL的其他容器** 了解`std::list`的...
`list`中的元素是通过双向链接连接的,这使得在链表中间插入或删除元素的时间复杂度为O(1)。`list`的主要类型定义如下: ```cpp #include <list> using namespace std; // 声明一个包含整型元素的list list<int> ...
- `erase()`可以按键删除元素,`empty()`检查容器是否为空,`size()`返回元素数量。 4. **pair**: - `pair`是用于存储两个元素的结构体,通常用于表示键值对或者临时存储两个相关的值。 - `make_pair()`函数...
`list`容器内部通过节点间的指针链接,使得插入和删除元素时,只需要改变相邻节点的指针,而不需要移动元素本身,这使得`list`在进行这些操作时的时间复杂度较低,通常是O(1)。 **STL中的`list`** 1. **定义和初始...
但注意,列表不支持随机访问,所以访问第N个元素的时间复杂度为O(N)。 - **列表操作**:包括合并(`splice`)、反转(`reverse`)、排序(`sort`)等。 2. **列表的传递与返回**: - **按值传递**:由于`std::list`是类...
- vector的插入和移除操作的时间复杂度为O(n)。 **4. list** **4.1 容器的迭代器设计** list的迭代器支持重载运算符,允许方便地进行++、--等操作。 **4.2 list的迭代器** list的迭代器是结构体,包含node节点,可...
`splice-feats`是Kaldi语音识别工具包中的一个命令行工具,主要用于处理声学特征,尤其是用于在训练声学模型之前对特征进行拼接(splice)操作。这个操作是深度学习模型,如循环神经网络(RNN)或卷积神经网络(CNN...
在JavaScript中,`Array.prototype.splice()` 是一个非常重要的方法,它允许我们对数组进行增、删、改操作。本篇文章将深入探讨`splice()`方法的工作原理,并通过自定义实现来帮助理解其内部机制。 `splice()` 方法...
在C++编程语言中,`List`是一种标准模板库(STL)中的容器,它实现了一个双向链表。链表的特点是元素在内存中不是连续存储的,因此在链表中进行插入和删除操作通常比向量(vector)更快,但随机访问元素的速度较慢。...