|
|
|
马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。
您需要 登录 才可以下载或查看，没有帐号？FreeOZ用户注册
x
写了一个链接数据结构，程序及相关文件如附件。附件中包括：
1. oneway_link.h 头文件
2. oneway_link.cpp 实现部分
3. oneway_link_test.cpp 一个简单的测试程序
4. Makefile 简单的Makefile
5. oneway_test_link.s 没有优化时的编译结果（汇编代码）
6. oneway_test_link_opt.s 采用-O2优化后的编译结果
我重要分析的代码是这一段：
oneway_link.h- 16 template<class T>
- 17 class MyLinkNode
- 18 {
- 21 public:
- 35 MyLinkNode * removeNext();
- 36 };
- 38 template <class T> class MyLink
- 39 {
- 40 MyLinkNode<T> * m_pHead;
- 41 MyLinkNode<T> * m_pTail; //for appending method
- 46 public:
- 48 ~MyLink();
- 64 };
- 58 template<class T> inline MyLinkNode<T> * MyLinkNode<T>::removeNext()
- 59 {
- 60 if(m_pNext==NULL)
- 61 return NULL;
- 62
- 63 MyLinkNode * pNextNext = m_pNext->m_pNext;
- 64 m_pNext->m_pNext = NULL;
- 65
- 66 MyLinkNode * pRetNext = m_pNext;
- 67 m_pNext = pNextNext;
- 68
- 69 return pRetNext;
- 70 }
- 75 template<class T> MyLink<T>::~MyLink()
- 76 {
- 77 if(m_pHead == NULL)
- 78 return;
- 79
- 80 MyLinkNode<T> * pNext;
- 81
- 82 while((pNext = m_pHead->removeNext())!=NULL)
- 83 {
- 84 delete pNext;
- 85 }
- 86
- 87 delete m_pHead;
- 88 }
所以MyLink不能直接操作MyLinkNode，这种情况下，他只能通过MyLinkNode::removeNext()这个接口
来实现逐个元素的删除。
如果我采用了friend的方式来写代码，一个比较“优化”的实现可能是：- pNext = m_pHead->m_pNext;
- while(pNext!=NULL;)
- {
- pNext2 = pNext->pNext;
- delete pNext;
- pNext = pNext2;
- }
1. 没有采用函数调用的方式来获取下一个元素
2. 没有设置获取的元素的next指针值为NULL
3. 没有把原有的链表重构起来
由于我采用了inline的方式来实现代码，第1点自然可以被优化掉，关键是看第2/3两点。
不过，老实说，2和3两点都是很小的代码，是否有需要优化掉也是一个问题。姑且看看吧。
如果我没有搞错，下面这段汇编应该就是MyLink::~MyLink()的析构代码的优化结果（从*_opt.s从取出）- 350 .weak _ZN6MyLinkISsED1Ev
- 351 .type _ZN6MyLinkISsED1Ev, @function
- 352 _ZN6MyLinkISsED1Ev:
- 353 .LFB1458:
- 354 pushl %ebp
- 355 .LCFI30:
- 356 movl %esp, %ebp
- 357 .LCFI31:
- 358 pushl %esi
- 359 .LCFI32:
- 360 pushl %ebx
- 361 .LCFI33:
- 362 subl $16, %esp
- 363 .LCFI34:
- 364 movl 8(%ebp), %esi
- 365 movl (%esi), %ecx 这个地方备份%ecx的值，这个是m_pHead的值
- 366 testl %ecx, %ecx
- 367 jne .L57 #跳到While循环判断处
- 368 jmp .L53 #函数返回
- 369 .p2align 4,,7
- 370 .L56: #While循环体
- 371 movl 4(%edx), %eax %eax = %edx指向的对象的->m_pNext
- 372 movl $0, 4(%edx) %edx指向的对象->m_pNext设置为NULL，$0是不是0我不是太有把握
- 373 movl 4(%ecx), %ebx %ebx=%ecx指向的对象->m_pNext
- 374 movl %eax, 4(%ecx) %ecx指向的对象->m_pNext改为%eax
- 375 testl %ebx, %ebx 测试%ebx是否0值
- 376 je .L53 While循环break出来，似乎对pNext!=NULL做了两个判断
- 377 movl %ebx, (%esp)
- 378 call _ZN10MyLinkNodeISsED1Ev 调用MyLinkNode的析构函数
- 379 movl %ebx, (%esp)
- 380 call _ZdlPv 调用free()之类的函数
- 381 movl (%esi), %ecx [从%esi备份中取出m_pHead放回%ecx中]
- 382 .L57: #.L57 while循环判断
- 383 movl 4(%ecx), %edx [%ecx指向m_pHead，所以这里是m_pHead->next放到%edx中去]
- 384 testl %edx, %edx 384/385两行用来测试%edx是不是0值，对应while循环中的pNext!=NULL语句
- 385 jne .L56
- 386 .L53: #.L53 函数出口
- 387 addl $16, %esp
- 388 popl %ebx
- 389 popl %esi
- 390 popl %ebp
- 391 ret
通过汇编代码的分析，这个优化后的while循否可以写成：- do {
- pNextNext = m_pNext->m_pNext; //oneway_link.cpp: 63
- m_pNext->m_pNext = NULL; //oneway_link.cpp: 64
- pRetNext = m_pHead->m_pNext; //相当于oneway_link.cpp: 66, pRetNext = m_pNext;
- m_pHead->next = pNextNext; //相当于oneway_link.cpp: 67, m_pNext = pNextNext;
- if(py == NULL) //这个操作应该是来自MyLinkNode::removeNext():60行if(m_pNext==NULL)的代码的优化结果
- break;
- delete py;
- }while((pNode = m_pHead->next)!=NULL)
我试着把优化级别由-O2一直升至-O5，那5行while循环代码学是没有改变。
结论：
编译器并没有象我想象那样“智能”地优化代码，基本上还是忠实于原来的实现。
所以，如果很需要注重性能的话，还是有必要用友元的方式重写相应的程序
[ 本帖最后由 key 于 16-5-2009 01:11 编辑 ] |
评分
-
查看全部评分
|
发表于 16-5-2009 01:07:40
收藏
赞
踩
发表于 16-5-2009 01:29:05
楼主
