fork(1) download
copy 
  1. #if _MSC_VER
  2. #pragma warning(disable: 4996)  // _CRT_SECURE_NO_WARNINGS
  3. #include <intrin.h>
  4. #else
  5. #include <x86intrin.h>
  6. #endif
  7.  
  8. #include <iostream>
  9. #include <stdio.h>              // printf
  10. #include <string.h>             // memcmp
  11. #define min_( a, b )            ( (a) < (b) ? (a) : (b) )
  12.  
  13. //------------------------------+---------------------------------------------------------------
  14.  
  15. #ifndef SYS_BITS
  16. #define CHAR_BITS               8
  17. #define SYS_BYTES               sizeof( std::size_t )
  18. #define SYS_BITS                ( SYS_BYTES * CHAR_BITS )
  19. #endif
  20.  
  21. //------------------------------+---------------------------------------------------------------
  22.  
  23. using   ON_RUN      =           void( & )( void* );
  24. using   ON_PREPARE  =           void( & )( void* );
  25. using   ON_COMPARE  =           bool( & )( void*, void*, std::size_t );
  26.  
  27. //------------------------------+---------------------------------------------------------------
  28. //  BENCH 에 의해서만 접근되기 때문에 모든 멤버가 private ( class default ) 입니다
  29. class                           RUNNER
  30. {
  31. friend  class                   BENCH;
  32.     const   char*               name;
  33.     unsigned long long          elapsed;
  34.     const   ON_RUN              on_run;
  35.     void*                       result;
  36.  
  37.                                 RUNNER( const char* name, ON_RUN&& on_run, void* result )
  38.     :   name( name )
  39.     ,   on_run( on_run )
  40.     ,   elapsed( -1 )
  41.     ,   result( result )
  42.     {
  43.     }
  44.  
  45.     void                        run()
  46.     {
  47.         auto    begin   = __rdtsc();
  48.         on_run( result );
  49.         elapsed         = min_( elapsed, __rdtsc() - begin );
  50.     }
  51. };
  52. ///-----------------------------+---------------------------------------------------------------
  53.  
  54. #include <vector>
  55.  
  56. class                           BENCH
  57. {
  58. private:
  59.     const   char*               title;
  60.     std::vector< RUNNER* >      runners;
  61.     ON_PREPARE                  on_prepare;
  62.     ON_COMPARE                  on_compare;
  63.     void*                       answer;
  64.     std::size_t                 answer_size;
  65.     const   unsigned int        trial;
  66.  
  67. public:
  68.                                 BENCH( const char* title, const int trial,
  69.                                        ON_PREPARE&& prepare, ON_COMPARE&& compare
  70.     )
  71.     :   title( title )
  72.     ,   trial( trial )
  73.     ,   on_prepare( prepare )
  74.     ,   on_compare( compare )
  75.     {
  76.     };
  77.                                ~BENCH()
  78.     {
  79.         for( auto runner : runners )
  80.             delete[] runner;
  81.         runners.clear();
  82.     }
  83.  
  84.     auto                        record( unsigned int index ) const
  85.     {
  86.         return  runners[ index ]->elapsed;
  87.     }
  88.  
  89.     auto                        runner_count() const
  90.     {
  91.         return  runners.size();
  92.     }
  93.  
  94.     void                        solution( ON_RUN&& correct_function,
  95.                                           void* result, const std::size_t bytes )
  96.     {
  97.         answer      = result;
  98.         answer_size = bytes;
  99.         on_prepare( result );
  100.         correct_function( result );
  101.     }
  102.  
  103.     template< typename T >
  104.     void                        solution( ON_RUN&& correct_function,
  105.                                           T& result, const std::size_t bytes )
  106.     {
  107.         solution( correct_function, &result, bytes );
  108.     }
  109.  
  110.     void                        add( const char* name, ON_RUN&& on_run, void* result )
  111.     {
  112.         runners.emplace_back( new RUNNER( name, on_run, result ) );
  113.     }
  114.  
  115.     template< typename T >
  116.     void                        add( const char* name, ON_RUN&& on_run, T& result )
  117.     {
  118.         add( name, on_run, &result );
  119.     }
  120.  
  121.     void                        run() const
  122.     {
  123.         if( runners.empty() )
  124.             return;
  125.  
  126.         printf( "\n   < %d bits %d trial >    %s\n", (int)SYS_BITS, trial, title );
  127.         puts( "   ----------------+---------------------------------+-----------------------" );
  128.         puts( "   |    CHECKER    |          function name          |    minimum clocks    |" );
  129.         puts( "   ----------------+---------------------------------+-----------------------" );
  130.  
  131.         unsigned long long  min_clocks = -1;
  132.         unsigned long long  max_clocks = 0;
  133.         RUNNER* min_runner = runners[ 0 ];
  134.         RUNNER* max_runner = runners[ 0 ];
  135.  
  136.         for( const  auto    runner : runners )
  137.         {
  138.             int     pass_count = 0;
  139.             for( unsigned int i = 0; i < trial; ++i )
  140.             {
  141.                 on_prepare( runner->result );
  142.                 runner->run();
  143.                 pass_count += on_compare( runner->result, answer, answer_size );
  144.             }
  145.  
  146.             if( min_clocks > runner->elapsed )
  147.             {
  148.                 min_runner = runner;
  149.                 min_clocks = runner->elapsed;
  150.             }
  151.             if( max_clocks < runner->elapsed )
  152.             {
  153.                 max_runner = runner;
  154.                 max_clocks = runner->elapsed;
  155.             }
  156.  
  157.             char    temp[ 14 ];
  158.             if( trial == pass_count )
  159.                 sprintf( temp, "       PASSED" );
  160.             else
  161.                 sprintf( temp, "FAILED%7d", trial - pass_count );
  162.  
  163.             printf( "   [ %s ] %32s %15llu clocks\n", temp, runner->name, runner->elapsed );
  164.         }
  165.         puts( "   --------------------------------------------------------------------------" );
  166.         printf( "   Winner is %s  ( %.2f times faster )\n\n",
  167.                 min_runner->name, float( max_clocks ) / min_clocks );
  168.     }
  169. };
  170.  
  171. #define FUN( function_name )    #function_name, function_name
  172.  
  173. //==============================================================================================
  174. //------------------------------+---------------------------------------------------------------
  175.  
  176. using   SOURCE = char;
  177. using   RESULT = char;
  178.  
  179. SOURCE  src[ 1<<20 ];
  180.  
  181. constexpr   std::size_t SIZE = sizeof src / sizeof *src;
  182.  
  183. RESULT  dst0[ SIZE ], dst1[ SIZE ], dst2[ SIZE ], dst3[ SIZE ];
  184.  
  185. //------------------------------+---------------------------------------------------------------
  186. //  테스트전에 불려질 초기화 함수
  187. void    prepare( void* result )
  188. {
  189. 	for( auto& v : src )
  190. 		v = 'a';
  191. 	src[ sizeof src - 1 ] = 0;
  192. //    memcpy( result, src, sizeof src );
  193. }
  194. //  테스트후에 불려질 점검 함수
  195. bool    compare( void* result, void* answer, std::size_t bytes )
  196. {
  197.     return  *(int*)result == *(int*)answer;
  198. //    return  memcmp( result, answer, bytes ) == 0;
  199. }
  200. //------------------------------+---------------------------------------------------------------
  201. //  테스트할 함수들
  202.  
  203. namespace	cose_new
  204. {
  205.  
  206. constexpr       std::size_t  finder = ( std::size_t )0x0101010101010101ULL;
  207. constexpr       std::size_t  masker = ( std::size_t )0x8080808080808080ULL;
  208.  
  209. constexpr       std::size_t  has_zero_7bit( const std::size_t n )
  210. {
  211.     return  ( n - finder ) & masker;
  212. }
  213.  
  214. constexpr       std::size_t  has_zero_8bit( const std::size_t n )
  215. {
  216.     return  has_zero_7bit( n ) & ~n;
  217. }
  218.  
  219. inline	auto    where_zero( const std::size_t* w )
  220. {
  221. 	auto*   p = (const char*)w;
  222. 	while( *p++ );
  223.     return  p - 1;
  224. }
  225.  
  226. template< int bits >
  227. auto            strend_bit( const char* s )
  228. {
  229.     const int  step     = sizeof finder == 4 ? 8 : 4;
  230.     const auto has_zero = bits == 7 ? has_zero_7bit : has_zero_8bit;
  231.  
  232.     if( has_zero( *(std::size_t*)s ) )
  233.         return  where_zero( (std::size_t*)s );
  234.  
  235.     auto    w = (std::size_t*)( (std::size_t)s & ~std::size_t( sizeof finder - 1 ) ) + 1;
  236.  
  237.     while( 1 )
  238.     {
  239.         if( has_zero( w[ 0 ] ) ) return  where_zero( w     );
  240.         if( has_zero( w[ 1 ] ) ) return  where_zero( w + 1 );
  241.         if( has_zero( w[ 2 ] ) ) return  where_zero( w + 2 );
  242.         if( has_zero( w[ 3 ] ) ) return  where_zero( w + 3 );
  243.         if( sizeof finder == 4 )
  244.         {
  245.         if( has_zero( w[ 4 ] ) ) return  where_zero( w + 4 );
  246.         if( has_zero( w[ 5 ] ) ) return  where_zero( w + 5 );
  247.         if( has_zero( w[ 6 ] ) ) return  where_zero( w + 6 );
  248.         if( has_zero( w[ 7 ] ) ) return  where_zero( w + 7 );
  249.         }
  250.         w += step;
  251.     }
  252. }
  253.  
  254. auto            strlen_fast( const char* s )
  255. {
  256.     return  strend_bit< 8 >( strend_bit< 7 >( s ) ) - s;
  257. }
  258.  
  259. void            run( void* dst )
  260. {
  261. 	*(int*)dst = strlen_fast( src );
  262. }
  263.  
  264. }
  265.  
  266. void	        run( void* dst )
  267. {
  268. 	*(int*)dst = strlen( src );
  269. }
  270. //------------------------------+---------------------------------------------------------------
  271.  
  272. int main()
  273. {
  274.     BENCH bench( "strlen", 1000, prepare, compare );
  275.     bench.solution( run, dst0, sizeof dst0 );
  276.  
  277.     bench.add( FUN( run ), dst1 );
  278.     bench.add( FUN( cose_new::run  ), dst2 );
  279.  
  280.     bench.run();
  281.  
  282.     getchar();
  283.     return  0;
  284. }
Success #stdin #stdout 0.88s 20360KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
   < 64 bits 1000 trial >    strlen
   ----------------+---------------------------------+-----------------------
   |    CHECKER    |          function name          |    minimum clocks    |
   ----------------+---------------------------------+-----------------------
   [        PASSED ]                              run          453531 clocks
   [        PASSED ]                    cose_new::run          114437 clocks
   --------------------------------------------------------------------------
   Winner is cose_new::run  ( 3.96 times faster )
https://ideone.com/xyGEKr
strlen bench
language:
C++14 (gcc 8.3)
created:
9 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!