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

[Alf P. Steinbach]

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

// 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!)

 

[Ian Collins]

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

[/QUOTE]

[QUOTE]

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!

 

[Alf P. Steinbach]

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

[/QUOTE]

[QUOTE]

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:

#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):

#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]

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