Sorting : Comparative performance measurement

[Alex Vinokur]

===================================
------------- 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 |
| : : : | : |
|=======================================================================