Sorting : Comparative performance measurement

From: Alex Vinokur (alexvn_at_big-foot.com)
Date: 08/29/04 

Date: Sun, 29 Aug 2004 19:54:39 +0300

===================================
------------- Sorting -------------
Comparative performance measurement
===================================

    Testsuite : Comparing Function Objects to Function Pointers
    Source : Technical Report on C++ Performance
    Tool : The C/C++ Program Perfometer (Version 2.8.1-1.19-Beta)
                  * http://sourceforge.net/projects/cpp-perfometer/

    Environment :
                  Windows 2000 Professional Ver 5.0 Build 2195 Service Pack 4
                  Intel(R) Celeron(R) CPU 1.70 GHz
                  CYGWIN_NT-5.0 1.5.10(0.116/4/2) i686 Cygwin
                  GNU g++ version 3.3.3 (cygming special) - Mingw

    Compilation :
                  g++ -mno-cygwin *.cpp

    DLLs : The names of DLL files on which the C++ Perfometer program depends
                  C:\cygwin\bin\cygwin1.dll
                    C:\WINNT\System32\KERNEL32.dll
                      C:\WINNT\System32\NTDLL.DLL

       #=====================================================================
       # ------------------- Sorting -------------------
       # Comparing Function Objects to Function Pointers
       # ---- Summary ---
       # ----------------
       # ----------------------------------------
       # The testsuite is from
       # Technical Report on C++ Performance
       # ISO/IEC PDTR 18015; Date: 2003-08-11; WG21 N1487=03-0070
       # Appendix D: Timing Code
       # SubAppendix D4
       # ----------------------------------------
       # * http://std.dkuug.dk/JTC1/SC22/WG21/docs/PDTR18015.pdf
       # * http://anubis.dkuug.dk/jtc1/sc22/wg21/docs/papers/2003/n1487.pdf
       # ----------------------------------------
       # Several testsuites have been added
       # - using pointers (instead of iterators) in sort()
       # - stable_sort()
       #---------------------------------------------------------------------
       # Resource Name : CPU-time used
       # Resource Cost Unit : clock
       # Resource State Unit : clock
       #=====================================================================
       # Total repetitions : 100
       # Performance metrics : clock / 100 repetitions
       #=====================================================================

   Measurement has been performed for the following optimization levels:
   * No optimization
   * Optimization O2

   Total 100 repetitions
   Performance = milliseconds per 100 repetitions
   sort is std::sort()
   stable_sort is std::stable_sort()

   Here are summary results of the measurement.
   --------------------------------------------

   ================================================
                   No optimization
   ================================================

|=======================================================================
| sort type : sorted : access : function/functor | data size |
| : object : via : | 1000 : 10000 |
|----------------------------------------------------------------------|
| qsort : array : : function pointer | 93 : 1669 |
| : : : | : |
| : : : | : |
| sort : array : : function pointer | 280 : 4286 |
| sort : array : : user functor | 93 : 1382 |
| sort : array : : user inline functor | 93 : 1348 |
| sort : array : : standard functor | 100 : 1395 |
| sort : array : : native < operator | 80 : 1311 |
| : : : | : |
| sort : vector : iterator : standard functor | 127 : 1779 |
| sort : vector : iterator : native < operator | 107 : 1489 |
| sort : vector : iterator : function pointer | 360 : 5221 |
| : : : | : |
| sort : vector : pointer : standard functor | 93 : 1405 |
| sort : vector : pointer : native < operator | 86 : 1305 |
| sort : vector : pointer : function pointer | 307 : 4199 |
| : : : | : |
| : : : | : |
| stable_sort : array : : function pointer | 297 : 4219 |
| stable_sort : array : : user functor | 93 : 1292 |
| stable_sort : array : : user inline functor | 100 : 1342 |
| stable_sort : array : : standard functor | 93 : 1325 |
| stable_sort : array : : native < operator | 60 : 901 |
| : : : | : |
| stable_sort : vector : iterator : standard functor | 166 : 2253 |
| stable_sort : vector : iterator : native < operator | 150 : 2036 |
| stable_sort : vector : iterator : function pointer | 334 : 4490 |
| : : : | : |
| stable_sort : vector : pointer : standard functor | 62 : 791 |
| stable_sort : vector : pointer : native < operator | 20 : 367 |
| stable_sort : vector : pointer : function pointer | 200 : 2633 |
| : : : | : |
|=======================================================================

   ================================================
                   Optimization O2
   ================================================

|=======================================================================
| sort type : sorted : access : function/functor | data size |
| : object : via : | 1000 : 10000 |
|----------------------------------------------------------------------|
| qsort : array : : function pointer | 113 : 1629 |
| : : : | : |
| : : : | : |
| sort : array : : function pointer | 243 : 2857 |
| sort : array : : user functor | 73 : 1134 |
| sort : array : : user inline functor | 40 : 597 |
| sort : array : : standard functor | 40 : 540 |
| sort : array : : native < operator | 56 : 774 |
| : : : | : |
| sort : vector : iterator : standard functor | 43 : 551 |
| sort : vector : iterator : native < operator | 107 : 1462 |
| sort : vector : iterator : function pointer | 260 : 2991 |
| : : : | : |
| sort : vector : pointer : standard functor | 40 : 524 |
| sort : vector : pointer : native < operator | 56 : 767 |
| sort : vector : pointer : function pointer | 250 : 2954 |
| : : : | : |
| : : : | : |
| stable_sort : array : : function pointer | 73 : 1054 |
| stable_sort : array : : user functor | 70 : 1015 |
| stable_sort : array : : user inline functor | 43 : 684 |
| stable_sort : array : : standard functor | 43 : 704 |
| stable_sort : array : : native < operator | 56 : 804 |
| : : : | : |
| stable_sort : vector : iterator : standard functor | 53 : 684 |
| stable_sort : vector : iterator : native < operator | 70 : 964 |
| stable_sort : vector : iterator : function pointer | 193 : 2500 |
| : : : | : |
| stable_sort : vector : pointer : standard functor | 20 : 323 |
| stable_sort : vector : pointer : native < operator | 20 : 327 |
| stable_sort : vector : pointer : function pointer | 33 : 504 |
| : : : | : |
|======================================================================= 

-- 
   Alex Vinokur
     http://mathforum.org/library/view/10978.html
     http://sourceforge.net/users/alexvn