fork download
copy 
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  4.  
  5. typedef unsigned long long      i64u;
  6.  
  7. // Benchmark ----------------------------------------------------------------
  8.  
  9. #ifdef _MSC_VER
  10.     #include <intrin.h>
  11. #else
  12. 	#define CHAR_BIT 8
  13.     inline unsigned long long __rdtsc()
  14.     {
  15.         i64u tick;
  16.         __asm volatile ( ".byte 0x0f, 0x31" : "=A" ( tick ) );
  17.         return tick;
  18.     }
  19. #endif
  20.  
  21. #define _min( a, b )            ( (a) < (b)? (a): (b) )
  22. #define _max( a, b )            ( (a) > (b)? (a): (b) )
  23. #define update_min( a, b )      ( (a) = _min( (a), (b) ) )
  24. #define update_max( a, b )      ( (a) = _max( (a), (b) ) )
  25.  
  26. //---------------------------------------------------------------------------
  27.  
  28. class                           SOME_RUNNER
  29. {
  30. private:
  31.     const   char*               function_name;
  32.     i64u                        elapsed;
  33.  
  34. protected:
  35.     i64u                        sum;
  36.  
  37. public:
  38.                                 SOME_RUNNER( const char* function_name )
  39.         : function_name( function_name ) { init(); }
  40.     virtual                    ~SOME_RUNNER() {};
  41.     virtual void                init()
  42.     {
  43.         sum = 0;
  44.         elapsed = -1;
  45.     }
  46.     virtual void                run() = 0;
  47.     void                        check()
  48.     {
  49.         i64u    begin    = __rdtsc();
  50.         run();
  51.         i64u    duration = __rdtsc() - begin;
  52.         update_min( elapsed, duration );
  53.     }
  54.     const   char*               set_length( const char* str, const size_t size )
  55.     {
  56.         static  char    temp[80];
  57.         size_t          index;
  58.         for( index = 0; str[index]; ++index ) temp[index] = str[index];
  59.         for( ; index < size; ++index ) temp[index] = ' ';
  60.         temp[index] = 0;
  61.         return  temp;
  62.     }
  63.     const   char*               report()
  64.     {
  65.         static  char temp[80];
  66.         sprintf( temp, "[%15llu] %s %15llu clocks", sum,
  67.             set_length( function_name, 20 ), elapsed );
  68.         return  temp;
  69.     }
  70.     const   i64u                elapsed_clocks(){ return elapsed; }
  71.     const   char*               name(){ return function_name; }
  72. };
  73. //---------------------------------------------------------------------------
  74.  
  75. #include <vector>
  76. template < size_t LOOP_COUNT >
  77. class                           BENCH
  78. {
  79. private:
  80.     std::vector< SOME_RUNNER* > runner_list;
  81.  
  82. public:
  83.     /*con*/                     BENCH() {};
  84.     /*des*/                    ~BENCH() {};
  85.  
  86.     void                        add( SOME_RUNNER* runner )
  87.     {
  88.         runner_list.push_back( runner );
  89.     }
  90.  
  91.     void                        run()
  92.     {
  93.         printf( "< %d bits > %d trials", sizeof( size_t ) * CHAR_BIT, LOOP_COUNT );
  94.         puts( "" );
  95.         puts( "-------------------------------------------------------------" );
  96.         puts( "|  CHECKER      | Function  name      |   minimum  clocks   |" );
  97.         puts( "-------------------------------------------------------------" );
  98.         i64u    min = -1;
  99.         i64u    max = 0;
  100.         size_t  min_index = 0;
  101.         size_t  max_index = 0;
  102.         for( size_t test_case = 0; test_case < runner_list.size(); ++test_case )
  103.         {
  104.             runner_list[test_case]->init();
  105.             for( size_t test_count = 0; test_count < LOOP_COUNT; ++ test_count )
  106.                 runner_list[test_case]->check();
  107.             puts( runner_list[test_case]->report() );
  108.             if( min > runner_list[test_case]->elapsed_clocks() )
  109.             {
  110.                 min_index = test_case;
  111.                 min = runner_list[test_case]->elapsed_clocks();
  112.             }
  113.             if( max < runner_list[test_case]->elapsed_clocks() )
  114.             {
  115.                 max_index = test_case;
  116.                 max = runner_list[test_case]->elapsed_clocks();
  117.             }
  118.         }
  119.         puts( "-------------------------------------------------------------" );
  120.         printf( "Winner is %s  ( %.2f times faster than looser )",
  121.             runner_list[min_index]->name(),
  122.             float( runner_list[max_index]->elapsed_clocks() ) /
  123.             runner_list[min_index]->elapsed_clocks() );
  124.         puts( "" );
  125.     }
  126. };
  127. //---------------------------------------------------------------------------
  128.  
  129. #define DEFINE_FUNCTION(return_type, function, ...) \
  130.     (SOME_RUNNER*)new RUNNER<return_type>( std::bind(function, __VA_ARGS__), #function )
  131.  
  132. //---------------------------------------------------------------------------
  133.  
  134. #include <functional>
  135. template< typename RET_TYPE >
  136. class                           RUNNER  : public    SOME_RUNNER
  137. {
  138. public:
  139.     /*con*/                     RUNNER( std::function< RET_TYPE() > function,
  140.         const char* function_name )
  141.         : test( function ), SOME_RUNNER( function_name ) {}
  142.     void                        run()
  143.     {
  144.         sum += (i64u)test();
  145.     }
  146.     std::function< RET_TYPE() > test;
  147. };
  148.  
  149. template< >
  150. class                           RUNNER< void > : public    SOME_RUNNER
  151. {
  152. public:
  153.     /*con*/                     RUNNER( std::function< void() > function,
  154.         const char* function_name )
  155.         : test( function ), SOME_RUNNER( function_name ) {}
  156.     void                        run()
  157.     {
  158.         sum++;
  159.         test();
  160.     }
  161.     std::function< void() >     test;
  162. };
  163. //---------------------------------------------------------------------------
  164.  
  165. size_t  strlen_boost( const char* s );
  166. size_t  strlen_hybrid( const char* s );
  167.  
  168. int main()
  169. {
  170.     #define     STRING_LENGTH           1000000
  171.  
  172.     char*       test_string = new char[STRING_LENGTH + 1];
  173.     for( int i = 0; i < STRING_LENGTH; ++i )
  174.     {
  175.         test_string[i] = rand() % 127 + 1;
  176. //        test_string[i] = rand() % 255 + 1;
  177.     }
  178.     test_string[STRING_LENGTH] = 0;
  179.  
  180.     BENCH< 100 > bench;
  181.     bench.add( DEFINE_FUNCTION( size_t, strlen,           test_string ) );
  182.     bench.add( DEFINE_FUNCTION( size_t, strlen_boost,     test_string ) );
  183.     bench.add( DEFINE_FUNCTION( size_t, strlen_hybrid,    test_string ) );
  184.     bench.run();
  185.  
  186.     getchar();
  187.     return 0;
  188. }
  189.  
  190. // Codesafer ----------------------------------------------------------------
  191.  
  192. typedef size_t  step_t;
  193.  
  194. inline  step_t  has_zero_7( const step_t n )
  195. {
  196.     const   step_t  finder = (step_t)0x0101010101010101ULL;
  197.     const   step_t  masker = (step_t)0x8080808080808080ULL;
  198.     return  ( n - finder ) & masker;
  199. }
  200.  
  201. inline  step_t  has_zero_8( const step_t n )
  202. {
  203.     return  has_zero_7( n ) & ~n;
  204. }
  205.  
  206. const   char*   where_zero( const char* s )
  207. {
  208.     size_t  i;
  209.     if( ( i = 0, !s[0] ) ||
  210.         ( i = 1, !s[1] ) ||
  211.         ( i = 2, !s[2] ) ||
  212.         ( sizeof( step_t ) == 8 && (
  213.             ( i = 3, !s[3] ) ||
  214.             ( i = 4, !s[4] ) ||
  215.             ( i = 5, !s[5] ) ||
  216.             ( i = 6, !s[6] ) ) ) )
  217.         return s + i;
  218.     return s + ( sizeof( step_t ) - 1 );
  219. }
  220.  
  221. size_t  strlen_7( const char* s )
  222. {
  223.     if( has_zero_7( *(step_t*)s ) ) return  where_zero( s ) - s;
  224.  
  225.     step_t* w = (step_t*)( (size_t)s & ~size_t( sizeof( step_t ) - 1 ) ) + 1;
  226.     while( 1 )
  227.     {
  228.         if( has_zero_7( w[0] ) ) return  where_zero( (char*)( w ) ) - s;
  229.         if( has_zero_7( w[1] ) ) return  where_zero( (char*)( w + 1 ) ) - s;
  230.         if( has_zero_7( w[2] ) ) return  where_zero( (char*)( w + 2 ) ) - s;
  231.         if( has_zero_7( w[3] ) ) return  where_zero( (char*)( w + 3 ) ) - s;
  232.         if( sizeof( step_t ) == 4 )
  233.         {
  234.             if( has_zero_7( w[4] ) ) return  where_zero( (char*)( w + 4 ) ) - s;
  235.             if( has_zero_7( w[5] ) ) return  where_zero( (char*)( w + 5 ) ) - s;
  236.             if( has_zero_7( w[6] ) ) return  where_zero( (char*)( w + 6 ) ) - s;
  237.             if( has_zero_7( w[7] ) ) return  where_zero( (char*)( w + 7 ) ) - s;
  238.         }
  239.         w += sizeof( 0LL ) + sizeof( 0L ) - sizeof( step_t );
  240.     }
  241. }
  242.  
  243. size_t  strlen_boost( const char* s )
  244. {
  245.     if( has_zero_8( *(step_t*)s ) ) return  where_zero( s ) - s;
  246.  
  247.     step_t* w = (step_t*)( (size_t)s & ~size_t( sizeof( step_t ) - 1 ) ) + 1;
  248.     while( 1 )
  249.     {
  250.         if( has_zero_8( w[0] ) ) return  where_zero( (char*)( w ) ) - s;
  251.         if( has_zero_8( w[1] ) ) return  where_zero( (char*)( w + 1 ) ) - s;
  252.         if( has_zero_8( w[2] ) ) return  where_zero( (char*)( w + 2 ) ) - s;
  253.         if( has_zero_8( w[3] ) ) return  where_zero( (char*)( w + 3 ) ) - s;
  254.         if( sizeof( step_t ) == 4 )
  255.         {
  256.             if( has_zero_8( w[4] ) ) return  where_zero( (char*)( w + 4 ) ) - s;
  257.             if( has_zero_8( w[5] ) ) return  where_zero( (char*)( w + 5 ) ) - s;
  258.             if( has_zero_8( w[6] ) ) return  where_zero( (char*)( w + 6 ) ) - s;
  259.             if( has_zero_8( w[7] ) ) return  where_zero( (char*)( w + 7 ) ) - s;
  260.         }
  261.         w += sizeof( 0LL ) + sizeof( 0L ) - sizeof( step_t );
  262.     }
  263. }
  264.  
  265. size_t  strlen_hybrid( const char* s )
  266. {
  267.     const   size_t  len = strlen_7( s );
  268.     return  len + strlen_boost( s + len );
  269. }
  270. //---------------------------------------------------------------------------
  271.  
Success #stdin #stdout 0.14s 4452KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
< 32 bits > 100 trials
-------------------------------------------------------------
|  CHECKER      | Function  name      |   minimum  clocks   |
-------------------------------------------------------------
[      100000000] strlen                       1337167 clocks
[      100000000] strlen_boost                  652715 clocks
[      100000000] strlen_hybrid                 476025 clocks
-------------------------------------------------------------
Winner is strlen_hybrid  ( 2.81 times faster than looser )
https://ideone.com/CXpmnA
benchmark
language:
C++14 (gcc 8.3)
created:
10 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!