How to programmatically test for LINEAR TIME (as opposed to qudratic)?

Discussion in 'C++' started by Alf P. Steinbach, Oct 16, 2013.

  1. I'm totally unfamiliar with programmatic testing of run-time behavior.

    Currently, my Google Test case (? whatever) looks like this, where the
    macro CPPX_U just provides a strongly typed literal (as discussed in my
    "literals" article in the August issue of ACCU Overload mag):

    Code:
    // Linear time concatenations.
    {
    enum { n = 40000 };
    String s4;
    String s5( s4 );        // Addref.
    
    for( int i = 1;  i <= n;  ++i )
    {
    s4 += CPPX_U( "xyz" );
    }
    EXPECT_EQ( n*3, s4.length() );
    
    Timer t1;
    for( int i = 1;  i <= n;  ++i )
    {
    s4 += CPPX_U( "xyz" );
    }
    t1.stop();
    EXPECT_EQ( 2*n*3, s4.length() );
    
    Timer t2;
    for( int i = 1;  i <= n;  ++i )
    {
    s4 += CPPX_U( "xyz" );
    }
    t2.stop();
    EXPECT_EQ( 3*n*3, s4.length() );
    
    double const time_difference = t2.seconds() - t1.seconds();
    double const percent_variation =
    100*(time_difference/t1.seconds());
    EXPECT_TRUE( percent_variation < 20.0 )  // Negative is OK,
    that's "better" than linear.
    << percent_variation << "%: " << t1.seconds() << " " <<
    t2.seconds();
    }
    
    I started out with a max 5% difference criterion and only 10.000
    concatenations, but the resolution of the timer in Windows is only
    milliseconds. So that's one problem, that this is apparently sensitive
    to the number of iterations. Too few for the test machine and result are
    imprecise, too many and the test runs too long (maybe hours).

    Also, I discovered that due to gremlins or something, when I use the
    Visual Studio debugger to "run to cursor" on terminating right brace
    above, then for mysterious reasons more time is used in the t2 loop than
    in the t1 loop. So, it seems sort of unreliable. And even though I now
    get consistent results, 20% leeway feels like it doesn't necessarily
    prove linear time?

    Any thoughts or experience?


    - Alf (in uncharted territory!)
     
    Alf P. Steinbach, Oct 16, 2013
    #1
    1. Advertising

  2. Alf P. Steinbach

    Ian Collins Guest

    Alf P. Steinbach wrote:
    > I'm totally unfamiliar with programmatic testing of run-time behavior.
    >
    > Currently, my Google Test case (? whatever) looks like this, where the
    > macro CPPX_U just provides a strongly typed literal (as discussed in my
    > "literals" article in the August issue of ACCU Overload mag):
    >
    >
    Code:
    [/color]
    
    <snip>
    [color=blue]
    > 
    >
    > I started out with a max 5% difference criterion and only 10.000
    > concatenations, but the resolution of the timer in Windows is only
    > milliseconds. So that's one problem, that this is apparently sensitive
    > to the number of iterations. Too few for the test machine and result are
    > imprecise, too many and the test runs too long (maybe hours).


    This is really a question about operating system timers. On my
    platforms (Solaris and its derivatives) I would use per-process high
    resolution timers (which use a hardware source) for this kind of test.
    Does windows have those?

    > Also, I discovered that due to gremlins or something, when I use the
    > Visual Studio debugger to "run to cursor" on terminating right brace
    > above, then for mysterious reasons more time is used in the t2 loop than
    > in the t1 loop. So, it seems sort of unreliable. And even though I now
    > get consistent results, 20% leeway feels like it doesn't necessarily
    > prove linear time?
    >
    > Any thoughts or experience?


    Don't run timing tests in a debugger!

    --
    Ian Collins
     
    Ian Collins, Oct 16, 2013
    #2
    1. Advertising

  3. On 17.10.2013 00:49, Ian Collins wrote:
    > Alf P. Steinbach wrote:
    >> I'm totally unfamiliar with programmatic testing of run-time behavior.
    >>
    >> Currently, my Google Test case (? whatever) looks like this, where the
    >> macro CPPX_U just provides a strongly typed literal (as discussed in my
    >> "literals" article in the August issue of ACCU Overload mag):
    >>
    >>
    Code:
    [/color]
    >
    > <snip>
    >[color=green]
    >> 
    >>
    >> I started out with a max 5% difference criterion and only 10.000
    >> concatenations, but the resolution of the timer in Windows is only
    >> milliseconds. So that's one problem, that this is apparently sensitive
    >> to the number of iterations. Too few for the test machine and result are
    >> imprecise, too many and the test runs too long (maybe hours).

    >
    > This is really a question about operating system timers. On my
    > platforms (Solaris and its derivatives) I would use per-process high
    > resolution timers (which use a hardware source) for this kind of test.
    > Does windows have those?


    Well, it does, and apparently with somewhat higher resolution than the
    1000 ticks/sec of Visual C++'s std::chrono::high_resolution_clock:

    Code:
    #include <rfc/winapi_wrappers/windows_h.h>
    #include <iostream>     // std::cout, std::cerr, std::endl
    
    void cpp_main()
    {
    LARGE_INTEGER result = {0};
    if( !::QueryPerformanceFrequency( &result ) ) { throw 666; }
    using namespace std;
    cout << result.QuadPart << " ticks/sec" << endl;
    }
    
    #include <rfc/cppx/default_main.hpp>
    
    2435917 ticks/sec

    On this laptop, i.e. about two and half thousand times better. :)

    So, now to write a platform-dependent version of the Timer class.

    For those who just need a timer -- and it's probably very good
    resolution in *nix -- here's the original standard code I used, just
    ad hoc code (ironically, while used in testing not itself tested):


    Code:
    #pragma once
    #include <chrono>
    
    namespace cppx{ namespace instrumentation{
    using std::chrono::high_resolution_clock;
    using std::chrono::duration_cast;
    using std::chrono::nanoseconds;
    
    // Most likely this timer will measure wall clock time, not user
    process time.
    // It depends on the standard library implementation of
    high_resolution_clock.
    
    class Timer
    {
    public:
    typedef high_resolution_clock   Clock;
    typedef Clock::time_point       Time;
    typedef Clock::duration         Duration;
    
    private:
    Time    start_;
    Time    end_;
    bool    is_running_;
    
    public:
    typedef long long   Int64;
    
    auto duration() const
    -> Duration
    { return end_ - start_; }
    
    auto nano_seconds() const
    -> Int64
    { return duration_cast<nanoseconds>( duration() ).count(); }
    
    auto seconds() const
    -> double
    {
    static double const nano = 1e-9;
    return nano*nano_seconds();
    }
    
    void stop()
    {
    end_ = Clock::now();
    is_running_ = false;
    }
    
    void carry_on()     // A.k.a. "continue", which however is a
    C++ keyword.
    {
    start_ = Clock::now() - duration();
    is_running_ = true;
    }
    
    Timer()
    : start_( Clock::now() )
    , end_()
    , is_running_( true )
    {}
    };
    
    } }  // namespace cppx::instrumentation
    

    Cheers, & thanks!,

    - Alf
     
    Alf P. Steinbach, Oct 17, 2013
    #3
  4. On 17.10.2013 00:49, Ian Collins wrote:
    >
    > This is really a question about operating system timers. On my
    > platforms (Solaris and its derivatives) I would use per-process high
    > resolution timers (which use a hardware source) for this kind of test.
    > Does windows have those?


    Apparently with about 2.5 million ticks per second:


    [code header]
    #pragma once
    // Copyright (c) 2013 Alf P. Steinbach

    #include <stdint.h> // uint_least64_t

    namespace cppx{ namespace instrumentation{

    class System_timer
    {
    public:
    enum Time: uint_least64_t {};
    enum Duration: uint_least64_t {};

    private:
    Time start_;
    Time end_;
    bool is_running_;

    static auto current_ticks() -> Time; // System-specific.
    static auto ticks_per_second() -> double; // System-specific.

    static auto nano() -> double { return 1e-9; }

    public:
    auto duration() const
    -> Duration
    { return static_cast<Duration>( end_ - start_ ); }

    auto nano_seconds() const
    -> uint_least64_t
    { return static_cast<uint_least64_t>( seconds()/nano() ); }

    auto seconds() const
    -> double
    { return duration()/ticks_per_second(); }

    void stop()
    {
    end_ = current_ticks();
    is_running_ = false;
    }

    void carry_on() // A.k.a. "continue", which however is a
    C++ keyword.
    {
    start_ = static_cast<Time>( current_ticks() - duration() );
    is_running_ = true;
    }

    System_timer()
    : start_( current_ticks() )
    , end_()
    , is_running_( true )
    {}
    };

    } } // namespace cppx::instrumentation
    [/code]


    [code impl]
    // Coppyright (c) 2013 Alf P. Steinbach.
    #ifndef _WIN32
    # error This implementation file is for Windows OS only.
    #endif
    #include <rfc/cppx/instrumentation/System_timer.h>

    #include <rfc/cppx/core/throwing.h> // cppx::fail
    #include <rfc/winapi_wrappers/windows_h.h>

    namespace cppx{ namespace instrumentation{

    auto System_timer::current_ticks()
    -> System_timer::Time
    {
    LARGE_INTEGER result = {0};
    ::QueryPerformanceCounter( &result )
    || fail( "QueryPerformanceCounter", ::GetLastError() );
    return static_cast<Time>( result.QuadPart );
    }

    auto System_timer::ticks_per_second()
    -> double
    {
    LARGE_INTEGER result = {0};
    ::QueryPerformanceFrequency( &result )
    || fail( "QueryPerformanceFrequency", ::GetLastError() );
    return static_cast<double>( result.QuadPart );
    }

    } } // namespace cppx::instrumentation
    [/code]



    Cheers,

    - Alf
     
    Alf P. Steinbach, Oct 17, 2013
    #4
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. anon
    Replies:
    5
    Views:
    345
    Keith W. McCammon
    May 19, 2004
  2. Chris Berg
    Replies:
    1
    Views:
    534
    Sudsy
    Nov 23, 2003
  3. Ed
    Replies:
    5
    Views:
    529
    Davis
    Oct 30, 2004
  4. Replies:
    1
    Views:
    1,194
    Roedy Green
    Nov 15, 2005
  5. Replies:
    1
    Views:
    129
    Joel VanderWerf
    Mar 6, 2008
Loading...

Share This Page