push_back(...) vs. insert(end(), ...)

明らかに前者の方が速いだろうと思っていたがコンパイラをなめていたようだ。

g++ (Ubuntu 4.3.3-5ubuntu4) 4.3.3
Copyright (C) 2008 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE

on

model name	: Intel(R) Xeon(R) CPU           W3520  @ 2.67GHz

で、次のコードを試してみた。

#include <iostream>
#include <vector>
#include <utility>
#include <sys/time.h>

inline double current_time()
{
    struct ::timeval now;
    ::gettimeofday(&now, NULL);
    return static_cast<double>(now.tv_sec)
            + static_cast<double>(now.tv_usec) / 1e6;
}

inline void bench(char const* label, void(*fun)())
{
    double b(current_time());
    fun();
    std::cout << label << ": " << current_time() - b << std::endl;
}

#define BENCH(fun) bench(#fun, fun)

void test1()
{
    std::vector<int> a;

    for (int i = 100000000; --i >= 0;) 
        a.push_back(0);
}

void test2()
{
    std::vector<int> a;

    for (int i = 100000000; --i >= 0;) 
        a.insert(a.end(), 0);
}

int main()
{
    for (int j = 3; --j >= 0;) {
        BENCH(test1);
        BENCH(test2);
    }
    return 0;
}

結果

最適化オプション	test1 (avg.)	test2 (avg.)
g++ -O0	1.51375	5.382957
g++ -O1	0.654851	0.846941
g++ -O2	0.625644	0.620839
g++ -O3	0.657522	0.657844

-O0 では 3.5 倍ほどの差が出てしまっているが、-O1 ではその差はある程度縮まり、-O2以降で有効になっている最適化オプションにより劇的に改善し、性能差はほとんどなくなっている。

STLport だとどうなる?

STLport 5.2.1 で試してみた。

最適化オプション	test1 (avg.)	test2 (avg.)
g++ -O0	1.89813	7.491233
g++ -O1	0.663089	1.666443
g++ -O2	0.623017	1.240863
g++ -O3	0.618588	1.17658

という感じ。

どのオプションが効いてるの?

追記: とくに出力結果に差異はないものの gcc となっていたのを修正。

-O? で有効にされる最適化オプション (-fXXX) の一覧は、

g++ -Q -O2 --help=optimizers

などとすることで知ることができる。

join /tmp/list1 /tmp/list2 | grep -v '\[\([^]]*\)\][ \t]*\[\1\]'

の結果は

-falign-jumps [disabled] [enabled]
-falign-labels [disabled] [enabled]
-falign-loops [enabled] [disabled]
-fcaller-saves [disabled] [enabled]
-fcrossjumping [disabled] [enabled]
-fcse-follow-jumps [disabled] [enabled]
-fdelete-null-pointer-checks [disabled] [enabled]
-fexpensive-optimizations [disabled] [enabled]
-fforward-propagate [disabled] [enabled]
-fgcse [disabled] [enabled]
-fhandle-exceptions  
-finline-small-functions [disabled] [enabled]
-foptimize-register-move [disabled] [enabled]
-foptimize-sibling-calls [disabled] [enabled]
-fpack-struct=<number>  
-fpeephole2 [disabled] [enabled]
-fregmove [disabled] [enabled]
-freorder-blocks [disabled] [enabled]
-freorder-functions [disabled] [enabled]
-frtti  
-fschedule-insns2 [disabled] [enabled]
-fshort-double  
-fshort-enums  
-fshort-wchar  
-fstrict-aliasing [disabled] [enabled]
-fthread-jumps [disabled] [enabled]
-fno-threadsafe-statics  
-ftree-pre [disabled] [enabled]
-ftree-store-ccp [disabled] [enabled]
-ftree-vrp [disabled] [enabled]

とりあえずいろいろあるなあ、全部試すかなーとか思いつつ勘で -finline-small-functions を -O1 に追加する形で試してみたら一発で速くなったので、これが一番効いてるっぽい (適当)。