Re: [問題] 用變數宣告陣列

看板C_and_CPP作者 ( )時間16年前 (2009/11/29 11:25), 編輯推噓3(3推 0噓 9→)
留言12則, 4人參與, 最新討論串4/5 (看更多)
推
11/29 02:23,
vector並不能完全取代array，在你很重視random access的
11/29 02:23
→
11/29 02:23,
效率的時侯..vector的random access operator []比傳統的
11/29 02:23
→
11/29 02:23,
陣列取值操作慢..
11/29 02:23
→
11/29 02:24,
所以在travel一個很大的vector時，請使用iterator，而不
11/29 02:24
→
11/29 02:25,
要使用for迴圈配上vec[i]這種寫法　因為慢很多
11/29 02:25
→
11/29 09:05,
向樓上的holy兄請教, 很大, 大約多大?QQ 因為我常用v@@
11/29 09:05
SGI STL 裡 vector<T>::operator[] 的實作： reference operator[](size_type __n) { return *(this->_M_impl._M_start + __n); } const_reference operator[](size_type __n) const { return *(this->_M_impl._M_start + __n); } 這種 inline 又直接 return 類似 *(base + offset) 的實作， random access 跑起來並不會差到哪去。 FreeBSD 7.2-STABLE / gcc version 4.5.0 20091119 (experimental) (GCC) // vra.cxx #include <vector> int foo(const std::vector<int> &v) { return v[5]; } int bar(int *v) { return v[5]; } > g++ -O3 -S vra.cxx > cat vra.s | c++filt .file "vra.cxx" .text .p2align 2,,3 .globl foo(std::vector<int, std::allocator<int> > const&) .type foo(std::vector<int, std::allocator<int> > const&), @function foo(std::vector<int, std::allocator<int> > const&): .LFB438: pushl %ebp .LCFI0: movl %esp, %ebp .LCFI1: movl 8(%ebp), %eax movl (%eax), %eax movl 20(%eax), %eax leave .LCFI2: ret .LFE438: .size foo(std::vector<int, std::allocator<int> > const&), .-foo(std::vector<int, std::allocator<int> > const&) .p2align 2,,3 .globl bar(int*) .type bar(int*), @function bar(int*): .LFB439: pushl %ebp .LCFI3: movl %esp, %ebp .LCFI4: movl 8(%ebp), %eax movl 20(%eax), %eax leave .LCFI5: ret .LFE439: .size bar(int*), .-bar(int*) .ident "GCC: (GNU) .5.0 20091119 (experimental)" 差別也只有紅色那一行， 沒猜錯的話 8(%ebp) 是傳入的 vector 實際位址， 然後 _M_start 剛好是 vector<int> 的第一個 data member， 所以 0(%eax) 省略成 (%eax)， 因此 movl (%eax), %eax 抓出來就是 &v[0] 這樣的東西； 至於 20(%eax) 的 20 就是 sizeof(int) * 5， 所以 20(%eax) 應該就是指 *(&v[0] + 5)， movl 20(%eax), %eax 就是把 *(&v[0] + 5) 的結果當成傳回值， 所以唯一的 overhead 就是那個 this pointer， 這個部分用 iterator 也避不掉， 因為 iterator 也是 class 包 pointer。 現在的 CPU 應該是沒差到需要計較那一道指令 (一個 cycle 大概才 0.3 - 0.6 ns)， 如果發一篇 paper 說有辦法可以省掉那道指令應該也是投不上； 不過講正經的， programmer 要避免那個 overhead 也不是不可能， 就用 int *raw_array = &v[0] 把 vector 當普通 array 用， 這樣再用 raw_array[i] 去 random access 就不會有 this pointer 的 overhead， 不過其實聰明的 compiler 還是會幫你去完成這件事的， 當然前提是 register 要夠用， x86 的話普遍那個 movl (%eax), %eax 還是會被帶到 loop 裡， 就算你用了上面講的那招手動轉成 int * 還是一樣。 -- Ling-hua Tseng (uranus@tinlans.org) Department of Computer Science, National Tsing-Hua University Interesting: C++, Compiler, PL/PD, OS, VM, Large-scale software design Researching: Software pipelining for VLIW architectures Homepage: https://www.tinlans.org -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 118.160.111.116 ※ 編輯: tinlans 來自: 118.160.111.116 (11/29 12:35)
推
11/29 12:45, , 1F
我是覺得 profiling tool 跟你說有差，才有差
11/29 12:45, 1F
→
11/29 12:45, , 2F
不然去改演算法可能加速得還比較快 orz
11/29 12:45, 2F
→
11/29 12:48, , 3F
本來就是看 profiling tool 決定要 optimize 哪段 code，
11/29 12:48, 3F
→
11/29 12:48, , 4F
不需要在寫的時候就去搞一些有的沒的，累死自己。
11/29 12:48, 4F
→
11/29 16:19, , 5F
看到那段 vector 效率較差的推文就覺得很疑惑...
11/29 16:19, 5F
推
11/30 00:15, , 6F
可是這是implementation-dependent
11/30 00:15, 6F
→
11/30 00:17, , 7F
#1B0FT4pi有在VC下測試的結果，vector比array慢了兩倍
11/30 00:17, 7F
推
11/30 02:10, , 8F
剛剛在linux 2.6.31 amd64的機器上用g++ 4.3.4 -O2測
11/30 02:10, 8F
→
11/30 02:10, , 9F
vector operator[]也是比native array和iterator來得慢
11/30 02:10, 9F
→
11/30 02:12, , 10F
測試方法是跑陣列的累加，固定跑十萬次　陣列大小random
11/30 02:12, 10F
→
11/30 02:12, , 11F
決定以避掉array size可能在compile time就被optimize掉
11/30 02:12, 11F
→
11/30 02:12, , 12F
的情況
11/30 02:12, 12F
‣ 更多 tinlans 的文章
文章代碼(AID): #1B4Ucs4C (C_and_CPP)
討論串 (同標題文章)
本文引述了以下文章的的內容：
以下文章回應了本文：
完整討論串 (本文為第 4 之 5 篇)：
排序： 最新先 | 最舊先 | 留言數
在新視窗開啟完整討論串 (共5篇)
‣ 更多 tinlans 的文章
文章代碼(AID): #1B4Ucs4C (C_and_CPP)