1 : // ソートテスト その４ スマートポインタを用いた場合.
    2 : #include <stdio.h>
    3 : #include <stdlib.h>
    4 : #include <time.h>
    5 : #include <assert.h>
    6 : #include <algorithm>
    7 : #include <functional>
    8 : #include <vector>
    9 : #include <list>
   10 : #include <string>
   11 : 
   12 : #if _MSC_VER >= 1500
   13 : #include <memory>
   14 : using namespace std::tr1;
   15 : #else
   16 : #include <boost/shared_ptr.hpp>
   17 : using namespace boost;
   18 : #endif
   19 : 
   20 : 
   21 : template<typename RAIte, class C >
   22 : void quick_sort(RAIte first, RAIte last, C cmp)
   23 : {
   24 :     typedef typename std::iterator_traits<RAIte>::value_type    T;
   25 : 
   26 :     using std::iter_swap;
   27 :     std::size_t size = last - first;
   28 :     if (size <= 32) {
   29 :         if (size <= 1)
   30 :             return;
   31 :         RAIte i = first;
   32 :         while (++i != last) {
   33 :             T       tmp( *i );
   34 :             RAIte j = i;
   35 :             RAIte k = i;
   36 :             do {
   37 :                 --k;
   38 :                 if (!cmp(tmp, *k))
   39 :                     break;
   40 :                 *j = *k;
   41 :                 --j;
   42 :             } while (k != first);
   43 :             *j = tmp;
   44 :         }
   45 :         return;
   46 :     }
   47 :     const T m( *(first + size/2) );
   48 :     RAIte   l = first;
   49 :     RAIte   r = last;
   50 :     for (;;) {
   51 :         while (cmp(*l, m))
   52 :             ++l;
   53 :         do {
   54 :             --r;
   55 :         } while (cmp(m, *r));
   56 :         if (!(l < r))
   57 :             break;
   58 :         iter_swap(l, r);
   59 :         ++l;
   60 :     }
   61 :     quick_sort(first, l   , cmp);
   62 :     quick_sort(l    , last, cmp);
   63 : }
   64 : 
   65 : 
   66 : 
   67 : template<typename RAIte> inline
   68 : void quick_sort(RAIte first, RAIte last) {
   69 :     quick_sort( first, last, std::less<typename std::iterator_traits<RAIte>::value_type>() );
   70 : }
   71 : 
   72 : 
   73 : 
   74 : // ===========================================================================
   75 : #ifdef _WIN32
   76 : #include <windows.h>
   77 : typedef unsigned __int64 PerfCnt_tick_t;
   78 : PerfCnt_tick_t PerfCnt_getTick()    { PerfCnt_tick_t c; QueryPerformanceCounter((LARGE_INTEGER*)&c); return c; }
   79 : PerfCnt_tick_t PerfCnt_tickPerSec() { static PerfCnt_tick_t s = 0; if (!s) QueryPerformanceFrequency((LARGE_INTEGER*)&s); return s; }
   80 : #else
   81 : #include <time.h>
   82 : typedef clock_t PerfCnt_tick_t;
   83 : #define PerfCnt_getTick()           clock()
   84 : #define PerfCnt_tickPerSec()        CLOCKS_PER_SEC
   85 : #endif
   86 : 
   87 : 
   88 : 
   89 : // ===========================================================================
   90 : 
   91 : template<typename T>
   92 : T random() {
   93 :     return T(rand());
   94 : }
   95 : 
   96 : template<>
   97 : std::string random<std::string>() {
   98 :     char buf[128];
   99 :     sprintf(buf, "%d%d%d", rand(),rand(),rand());
  100 :     return std::string(buf);
  101 : }
  102 : 
  103 : 
  104 : 
  105 : // ===========================================================================
  106 : #ifdef USE_SMPCLASS
  107 : #if USE_SMPCLASS != 1
  108 : #include <tr1/array>
  109 : #endif
  110 : #include <boost/intrusive_ptr.hpp>
  111 : 
  112 : class SmpClass {
  113 : public:
  114 :     ~SmpClass() { free(name_); }
  115 :     SmpClass() : name_(0), x_(0),y_(0),z_(0),argb_(0xFFFFFFFF),refCnt_(0) { /*buf_.resize(256);*/ }
  116 : 
  117 :     SmpClass(const SmpClass& r)
  118 :         : name_(strdup(r.name_)), x_(r.x_), y_(r.y_), z_(r.z_), argb_(r.argb_), refCnt_(0), buf_(r.buf_) {}
  119 : 
  120 :     SmpClass(const char* name, double x, double y, double z, unsigned argb=0xffffffff)
  121 :         : name_(strdup(name)), x_(x), y_(y), z_(z), argb_(argb), refCnt_(0)
  122 :     {
  123 :       #if USE_SMPCLASS == 1
  124 :         buf_.resize(256);
  125 :       #endif
  126 :     }
  127 : 
  128 :     SmpClass& operator=(const SmpClass& r) { SmpClass(r).swap( *this ); return *this; }
  129 : 
  130 :     void swap(SmpClass& r);
  131 :     bool operator<(const SmpClass& r) const;
  132 : 
  133 :     void     incRef() { if (this) ++refCnt_; }
  134 :     void     decRef_and_release() { if (this && refCnt_) { if (!(--refCnt_)) delete this; } }
  135 :     unsigned ref_count() const { return refCnt_; }
  136 : 
  137 : private:
  138 :     char*                       name_;
  139 :     double                      x_, y_, z_;
  140 :     unsigned                    argb_;
  141 :     unsigned                    refCnt_;
  142 :   #if USE_SMPCLASS == 1
  143 :     std::vector<char>           buf_;
  144 :   #else
  145 :     std::tr1::array<char,160>   buf_;
  146 :   #endif
  147 : };
  148 : 
  149 : 
  150 : inline bool SmpClass::operator<(const SmpClass& r) const {
  151 :     if (z_ < r.z_)
  152 :         return 1;
  153 :     if (z_ > r.z_)
  154 :         return 0;
  155 :     if (y_ < r.y_)
  156 :         return 1;
  157 :     if (y_ > r.y_)
  158 :         return 0;
  159 :     return strcmp(name_, r.name_) < 0;
  160 : }
  161 : 
  162 : 
  163 : inline void SmpClass::swap(SmpClass& r) {
  164 :     using std::swap;
  165 :     swap(name_, r.name_);
  166 :     swap(x_   , r.x_   );
  167 :     swap(y_   , r.y_   );
  168 :     swap(z_   , r.z_   );
  169 :     swap(argb_, r.argb_);
  170 :     swap(refCnt_, r.refCnt_);
  171 :     swap(buf_ , r.buf_ );
  172 : }
  173 : 
  174 : 
  175 : void intrusive_ptr_add_ref(SmpClass* p) { p->incRef(); }
  176 : void intrusive_ptr_release(SmpClass* p) { p->decRef_and_release(); }
  177 : 
  178 : 
  179 : 
  180 : template<>
  181 : SmpClass random<SmpClass>() {
  182 :     char name[128];
  183 :     sprintf(name, "%c%c%d", 'A'+rand()%26,'a'+rand()%26,'a'+rand()%26, rand());
  184 :     return SmpClass(name, rand(), rand(), rand());
  185 : }
  186 : 
  187 : 
  188 : 
  189 : #define TYPE        SmpClass
  190 : #endif
  191 : 
  192 : 
  193 : 
  194 : // ===========================================================================
  195 : 
  196 : template<typename T>
  197 : struct ptr_less {
  198 :     bool operator()(T l, T r) const {
  199 :         return *l < *r;
  200 :     }
  201 : };
  202 : 
  203 : 
  204 : 
  205 : // vector<T>に確保したデータを その要素へのポインタの配列を作ってソート.
  206 : template<typename T>
  207 : double benchmark1(unsigned size, unsigned count=1, int seed=1) {
  208 :     srand(seed);
  209 :     PerfCnt_tick_t  elapsed = 0;
  210 :     for (unsigned j = 0; j < count; ++j) {
  211 :         std::vector<T> data;
  212 :         for (unsigned i = 0; i < size; ++i)
  213 :             data.push_back(random<T>());
  214 : 
  215 :         PerfCnt_tick_t  start_time = PerfCnt_getTick();
  216 :         std::vector<T*> ent(size);
  217 :         typename std::vector<T*>::iterator vi = ent.begin();
  218 :         for (typename std::vector<T>::iterator li = data.begin(); li != data.end(); ++li) {
  219 :             *vi = &*li;
  220 :             ++vi;
  221 :         }
  222 :         quick_sort(ent.begin(), ent.end(), ptr_less<T*>() );
  223 :         elapsed    += PerfCnt_getTick() - start_time;
  224 : 
  225 :         for (unsigned i = 0; i < size-1; ++i) { // ソート状態 チェック.
  226 :             if (*ent[i+1] < *ent[i])
  227 :                 printf("error %d : > \n", i);
  228 :         }
  229 :     }
  230 :     return elapsed * 1.0 / (PerfCnt_tickPerSec() * count);
  231 :     //printf("%s:%13.3fμ秒\n", name, elapsed * 1000000.0 / (PerfCnt_tickPerSec() * count));
  232 : }
  233 : 
  234 : 
  235 : // vector をソート
  236 : template<typename T>
  237 : double benchmark2(unsigned size, unsigned count=1, int seed=1) {
  238 :     srand(seed);
  239 :     PerfCnt_tick_t  elapsed = 0;
  240 :     for (unsigned j = 0; j < count; ++j) {
  241 :         std::vector<T> data;
  242 :         data.reserve(size);
  243 :         for (unsigned i = 0; i < size; ++i)
  244 :             data.push_back(random<T>());
  245 :         PerfCnt_tick_t  start_time = PerfCnt_getTick();
  246 :         quick_sort(data.begin(), data.end() );
  247 :         elapsed    += PerfCnt_getTick() - start_time;
  248 : 
  249 :         for (unsigned i = 0; i < size-1; ++i) { // ソート状態 チェック.
  250 :             if (data[i+1] < data[i])
  251 :                 printf("error %d : > \n", i);
  252 :         }
  253 :     }
  254 :     return elapsed * 1.0 / (PerfCnt_tickPerSec() * count);
  255 : }
  256 : 
  257 : 
  258 : 
  259 : // vector<T>に確保したデータを その要素へのポインタの配列を作ってソートし、それを基にvector<T>データを再構築.
  260 : template<typename T>
  261 : double benchmark3(unsigned size, unsigned count=1, int seed=1) {
  262 :     srand(seed);
  263 :     PerfCnt_tick_t  elapsed = 0;
  264 :     for (unsigned j = 0; j < count; ++j) {
  265 :         std::vector<T> data;
  266 :         data.reserve( size );
  267 :         for (unsigned i = 0; i < size; ++i)
  268 :             data.push_back(random<T>());
  269 : 
  270 :         PerfCnt_tick_t  start_time = PerfCnt_getTick();
  271 :         {
  272 :             std::vector<T*> ent(size);
  273 :             typename std::vector<T*>::iterator vi = ent.begin();
  274 :             for (typename std::vector<T>::iterator it = data.begin(); it != data.end(); ++it) {
  275 :                 *vi = &*it;
  276 :                 ++vi;
  277 :             }
  278 :             quick_sort(ent.begin(), ent.end(), ptr_less<T*>() );
  279 :             std::vector<T> data2;
  280 :             data2.reserve( size );
  281 :             for (unsigned i = 0; i < size; ++i)
  282 :                 data2.push_back( *ent[i] );
  283 :             std::swap(data, data2);
  284 :         }
  285 :         elapsed    += PerfCnt_getTick() - start_time;
  286 : 
  287 :         for (unsigned i = 0; i < size-1; ++i) { // ソート状態 チェック.
  288 :             if (data[i+1] < data[i])
  289 :                 printf("error %d : > \n", i);
  290 :         }
  291 :     }
  292 :     return elapsed * 1.0 / (PerfCnt_tickPerSec() * count);
  293 : }
  294 : 
  295 : 
  296 : 
  297 : // スマートポインタのvectorをソート.
  298 : template<typename T>
  299 : double benchmark4(unsigned size, unsigned count=1, int seed=1) {
  300 :     srand(seed);
  301 :     PerfCnt_tick_t  elapsed = 0;
  302 :     for (unsigned j = 0; j < count; ++j) {
  303 :         typedef shared_ptr<T>  T_ptr;
  304 :         std::vector< T_ptr >   data;
  305 :         data.reserve( size );
  306 :         for (unsigned i = 0; i < size; ++i)
  307 :             data.push_back( T_ptr( new T( random<T>() ) )  );
  308 : 
  309 :         PerfCnt_tick_t  start_time = PerfCnt_getTick();
  310 :         quick_sort(data.begin(), data.end(), ptr_less<T_ptr>() );
  311 :         elapsed    += PerfCnt_getTick() - start_time;
  312 : 
  313 :         for (unsigned i = 0; i < size-1; ++i) { // ソート状態 チェック.
  314 :             if (*data[i+1] < *data[i])
  315 :                 printf("error %d : > \n", i);
  316 :         }
  317 :     }
  318 :     return elapsed * 1.0 / (PerfCnt_tickPerSec() * count);
  319 : }
  320 : 
  321 : 
  322 : #ifdef USE_SMPCLASS
  323 : // intrusive_ptrのvectorをソート.
  324 : template<typename T>
  325 : double benchmark5(unsigned size, unsigned count=1, int seed=1) {
  326 :     srand(seed);
  327 :     PerfCnt_tick_t  elapsed = 0;
  328 :     for (unsigned j = 0; j < count; ++j) {
  329 :         typedef boost::intrusive_ptr<T>  T_ptr;
  330 :         std::vector< T_ptr > data;
  331 :         data.reserve( size );
  332 :         for (unsigned i = 0; i < size; ++i)
  333 :             data.push_back( T_ptr( new T( random<T>() ) )  );
  334 : 
  335 :         PerfCnt_tick_t  start_time = PerfCnt_getTick();
  336 :         quick_sort(data.begin(), data.end(), ptr_less<T_ptr>() );
  337 :         elapsed    += PerfCnt_getTick() - start_time;
  338 : 
  339 :         for (unsigned i = 0; i < size-1; ++i) { // ソート状態 チェック.
  340 :             if (*data[i+1] < *data[i])
  341 :                 printf("error %d : > \n", i);
  342 :         }
  343 :     }
  344 :     return elapsed * 1.0 / (PerfCnt_tickPerSec() * count);
  345 : }
  346 : 
  347 : 
  348 : // vector<T>に確保したデータを その要素へのポインタの配列を作ってソートし、それを基にvector<T>データを再構築.
  349 : template<typename T>
  350 : double benchmark6(unsigned size, unsigned count=1, int seed=1) {
  351 :     srand(seed);
  352 :     PerfCnt_tick_t  elapsed = 0;
  353 :     for (unsigned j = 0; j < count; ++j) {
  354 :         typedef boost::intrusive_ptr<T>  T_ptr;
  355 :         std::vector< T_ptr > data;
  356 :         data.reserve( size );
  357 :         for (unsigned i = 0; i < size; ++i)
  358 :             data.push_back( T_ptr( new T( random<T>() ) )  );
  359 : 
  360 :         PerfCnt_tick_t  start_time = PerfCnt_getTick();
  361 :         {
  362 :             std::vector<T*> ent(size);
  363 :             typename std::vector<T*>::iterator vi = ent.begin();
  364 :             for (typename std::vector<T_ptr>::iterator it = data.begin(); it != data.end(); ++it) {
  365 :                 *vi = it->get();
  366 :                 ++vi;
  367 :             }
  368 :             quick_sort(ent.begin(), ent.end(), ptr_less<T*>() );
  369 :             {
  370 :                 std::vector<T_ptr> data2;
  371 :                 data2.reserve( size );
  372 :                 for (unsigned i = 0; i < size; ++i)
  373 :                     data2.push_back( T_ptr(ent[i]) );
  374 :                 std::swap(data, data2);
  375 :             }
  376 :         }
  377 :         elapsed    += PerfCnt_getTick() - start_time;
  378 : 
  379 :         for (unsigned i = 0; i < size; ++i) {   // 参照数が誤ってないかチェック.
  380 :             if (data[i]->ref_count() != 1)
  381 :                 printf("error %d\n", i);
  382 :         }
  383 :         for (unsigned i = 0; i < size-1; ++i) { // ソート状態 チェック.
  384 :             if (*data[i+1] < *data[i])
  385 :                 printf("error %d : > \n", i);
  386 :         }
  387 :     }
  388 :     return elapsed * 1.0 / (PerfCnt_tickPerSec() * count);
  389 : }
  390 : #endif
  391 : 
  392 : 
  393 : 
  394 : #ifndef TYPE
  395 : #define TYPE    int
  396 : #endif
  397 : 
  398 : struct St {
  399 :     size_t      size;
  400 :     size_t      count;
  401 :     double      elaped[6];
  402 : };
  403 : 
  404 : //
  405 : int main(int argc, char **argv) {
  406 :     if (argc < 2) {
  407 :         printf("usage> sort_test4 size1 count1 [size2 count2 ...]\n");
  408 :         return 1;
  409 :     }
  410 :     std::vector<St> st;
  411 :     unsigned n = 0;
  412 :     for (unsigned i = 1; i < argc; i += 2) {
  413 :         St  t;
  414 :         t.size   = atoi(argv[i]);
  415 :         t.count  = (i+1 < argc) ? atoi(argv[i+1]) : 1;
  416 :         std::fill(t.elaped, t.elaped+6, 0.0);
  417 :         st.push_back(t);
  418 :         ++n;
  419 :     }
  420 :     printf("\nsort_test4 : sizeof(TYPE)=%dbytes\n", sizeof(TYPE));
  421 :     int    seed  = 1; //time(0);
  422 :     for (unsigned i = 0; i < n; ++i) {
  423 :         St& t = st[i];
  424 :         printf("個数 %9d, 処理回数 %9d\n", t.size, t.count);
  425 :         t.elaped[0] = benchmark1<TYPE>(t.size, t.count, seed);  // "vector要素へのポインタのvectorのみをsort       "
  426 :         t.elaped[1] = benchmark2<TYPE>(t.size, t.count, seed);  // "vectorを sort                                  "
  427 :         t.elaped[2] = benchmark3<TYPE>(t.size, t.count, seed);  // "ポインタでソートして、その結果でvector再構築   "
  428 :         t.elaped[3] = benchmark4<TYPE>(t.size, t.count, seed);  // "shared_ptrのvectorを sort                      "
  429 :       #ifdef USE_SMPCLASS
  430 :         t.elaped[4] = benchmark5<TYPE>(t.size, t.count, seed); // "intrusive_ptrのvectorを sort                   "
  431 :         t.elaped[5] = benchmark6<TYPE>(t.size, t.count, seed); // "intrusive_ptrのvectorを生ポインタソートで再構築"
  432 :       #endif
  433 :     }
  434 : 
  435 :     // 結果表示.
  436 :     static const char* ttl[] = {
  437 :         "vector要素へのポインタのvectorのみをsort       ",  // 1
  438 :         "vectorを sort                                  ",  // 2
  439 :         "ポインタでソートして、その結果でvector再構築   ",  // 3
  440 :         "shared_ptrのvectorを sort                      ",  // 4
  441 :       #ifdef USE_SMPCLASS
  442 :         "intrusive_ptrのvectorを sort                   ",  // 5
  443 :         "intrusive_ptrのvectorを生ポインタソートで再構築",  // 6
  444 :       #endif
  445 :         NULL,
  446 :     };
  447 :     printf("\n");
  448 :     printf("%47s ,", "個数");
  449 :     for (unsigned i = 0; i < n; ++i) {
  450 :         printf("%9d個,", st[i].size);
  451 :     };
  452 :     printf("\n");
  453 :     for (unsigned j = 0; ttl[j]; ++j) {
  454 :         printf("%-47s ,", ttl[j]);
  455 :         for (unsigned i = 0; i < n; ++i) {
  456 :             printf("%11.3f,", st[i].elaped[j]*1000000.0);
  457 :         };
  458 :         printf("\n");
  459 :     }
  460 :     return 0;
  461 : }