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

[tinlans ( )]

推 holymars:vector並不能完全取代array，在你很重視random access的
→ holymars:效率的時侯..vector的random access operator []比傳統的
→ holymars:陣列取值操作慢..
→ holymars:所以在travel一個很大的vector時，請使用iterator，而不
→ holymars:要使用for迴圈配上vec[i]這種寫法　因為慢很多
→ devilarise:向樓上的holy兄請教, 很大, 大約多大?QQ 因為我常用v@@
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 ([e-mail])
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)
推 legnaleurc:我是覺得 profiling tool 跟你說有差，才有差
→ legnaleurc:不然去改演算法可能加速得還比較快 orz
→ tinlans:本來就是看 profiling tool 決定要 optimize 哪段 code，
→ tinlans:不需要在寫的時候就去搞一些有的沒的，累死自己。
→ james732:看到那段 vector 效率較差的推文就覺得很疑惑...
推 holymars:可是這是implementation-dependent
→ holymars:#1B0FT4pi有在VC下測試的結果，vector比array慢了兩倍
推 holymars:剛剛在linux 2.6.31 amd64的機器上用g++ 4.3.4 -O2測
→ holymars:vector operator[]也是比native array和iterator來得慢
→ holymars:測試方法是跑陣列的累加，固定跑十萬次　陣列大小random
→ holymars:決定以避掉array size可能在compile time就被optimize掉
→ holymars:的情況