Zeit messen

Hallo,
http://www.c-plusplus.net/ubb/cgi-bin/ultimatebb.cgi?ubb=get_topic&f=8&t=002606
und
http://www.c-plusplus.net/ubb/cgi-bin/ultimatebb.cgi?ubb=get_topic&f=15&t=002946&p=1
http://www.c-plusplus.net/ubb/cgi-bin/ultimatebb.cgi?ubb=get_topic&f=15&t=002946&p=2
MfG Lem

PaRu

ich habe das gleiche problem wie der ingo(algorithmen auf geschwindigkeit testen). das mit dem time unter linux find ich nicht so doll und die links zu den alten beiträgen gibt es nicht mehr. wie bekomme ich denn millisekunden vom computer?
Gruß Patrick

volkard

zum testen nehme man rdtsc.
also was plattformabhängiges. ist aber net soo schlimm, weils für linux und win fast gleich ist und nur nen intel drunter braucht.

um genau zu messen, sorge man dafür, daß alles fein im gecached ist und daß keine anderen prozesse zuschlagen. wie macht man das? die anderen prozesse erstmal dranlassen mit Sleep(0) (mal davon ausgehen, daß kein anderer dran will, hab ich fein meine zeitscheibe resetted) unter win und für linux wirds auch was feines geben und oft messen. am besten, man mißt so lange, bis die messergebnisse nicht mehr kleiner werden. kleine zwischentiefs macht man weg durch die forderung, daß 1000 messungen oder so kein besserer wert mehr kommt. so kommste auf auch bei langen sachen, die mehrere hundert takte brauchen auf den takt genau raus.

hier ist recht aktueller messcode von mir:

#include <iostream>
#include <ctime>
#include <windows.h>
using namespace std;

int wpc45sec(int offset,int max)
{
    //443.7156
    int a=offset,b=max;
    if(a<b)
    {
        int tmp=a;
        a=b;
        b=tmp;
    }
    while(b)
    {
        int tmp=a%b;
        a=b;
        b=tmp;
    }
    return a==1;
}

int wpc45(int offset,int max);

#pragma warning(disable:4035)
inline __int64 rdtsc()
{
    __asm rdtsc;
}

int __cdecl main()
{
    {
        cout<<"test\n";
        srand(time(0));
        for(int offset=1;offset<=100;++offset)
        {
            cout<<offset<<"     \r";
            for(int max=1;max<=100;++max)
            {
                int r1=wpc45sec(offset,max);
                int r2=wpc45(offset,max);
                if(r1!=r2)
                {
                    cout<<endl<<"Fehler!"<<endl;
                    __asm int 3;
                    wpc45(offset,max);
                    return 1;
                }
            }
        }
    }
    {
        cout<<"messung\n";
        int r;
        double mintime=1e100;
        int const TODOSTART=1000;
        int todo=TODOSTART;
        while(todo>0)
        {
            srand(0);
            Sleep(0);
            __int64 start=rdtsc();
            for(int i=0;i<10000;++i)
            {
                int offset=rand()*3+rand()+1;
                int max=(rand()*2^rand())+1;
//              cout<<offset<<' '<<max<<"     \r";
                r+=wpc45(offset,max);
            }
            __int64 stop=rdtsc();
            double time=(stop-start)/10000.0;
            if(time<mintime)
            {
                todo=TODOSTART;
                mintime=time;
                cout<<mintime<<"     "<<endl;
            }
            --todo;
        }

        cout<<r<<'\r';
        cout<<mintime<<endl;
    }
    return 0;
}

(in dem code mess ich immer 10000 durchläufe auf einmal, weil ich nen durchscnittlichen wert haben will, damit ich nicht die funktion nur für bestimmte eingaben optimiere.)
für borland siehts aus wie für den msvc, den ich verwende. für linux hab ich meine inline-funktion leider verschlampt.

für sortiersachen isses außerdem hilfreich, durch so ein ähnliches prog sich ne ganze wertetabelle zu machen mit den laufzeiten für 10 bis 10000 elemente und für verschiedene implementierungen und sich dann bidchen von den graphen zeigen zu lassen. so kriegt man ein hübsches gefühl dafür, in welchen problemgrößen welche tricks gut sind.

edit:
mal in OS.i von den ACE-Wrappers geguckt. sieht nach sowas aus:

inline long long rdtsc()
{
  long long now;
  // Read the high-res tick counter directly into memory variable "now".
  // The A constraint signifies a 64-bit int.
  asm volatile ("rdtsc" : "=A" (now) : : "memory");
  return now;
}

[ Dieser Beitrag wurde am 25.03.2003 um 13:28 Uhr von volkard editiert. ]

Gerard

konnte es nicht lassen und habs in eine klasse gepackt

#ifndef STOP_WATCH_H_DIM
#define STOP_WATCH_H_DIM

#include <iostream>
#include <windows.h>

namespace dim
{
    class stop_watch
    {
    public:
        typedef __int64 int64_t;

        stop_watch()
        {
            reset();
        }

        void reset()
        {
            Sleep( 0 );
            starttime_ = ticks();
        }

        int64_t time() const
        {
            return ticks() - starttime_;
        }

    private:

        int64_t ticks() const
        {
            #pragma warning(disable:4035)
            __asm rdtsc;
            #pragma warning(default:4035)
        }

    private:
        int64_t starttime_;
    };

    class average
    {
    public:
        typedef stop_watch::int64_t int64_t;

        average(unsigned int n)
            :   sum_( 0 ),
                count_( 0 ),
                n_( n )
        {
        }

        bool need_more_values() const
        {
            return n_ != 0;
        }

        average & operator+= (stop_watch & sw)
        {
            sum_ += sw.time();
            ++count_;
            if(n_)
                --n_;
            return *this;
        }

        int64_t value() const
        {
            return sum_ / count_;
        }

    private:
        int64_t             sum_;
        unsigned int        count_;
        unsigned int        n_;
    };

    std::ostream & operator<< (std::ostream & os, const stop_watch & sw)
    {
        return os << sw.time();
    }

    std::ostream & operator<< (std::ostream & os, const average & av)
    {
        return os << av.value();
    }

}//end of namespace dim

#endif

und hier ein bsp

#include <iostream>
#include "stop_watch.h"
using namespace dim;
using namespace std;

int main()
{

    dim::average    av( 10000 );
    dim::stop_watch sw;

    int i = 99999;
    int c = 0;
    do
    {
        sw.reset();

        do
        {
            if(k & 0x1)
                ++c;
            k >>= 1;
        }while(k);

        av += sw;
    }while(av.need_more_values());

    cout << av << endl;
}

[ Dieser Beitrag wurde am 26.03.2003 um 04:30 Uhr von Dimah editiert. ]

Gerard

und noch eine kleine verbesserung

#include <iostream>
#include "StopWatch.h"
using namespace dim;
using namespace std;

    class foo
    {
    public:
        foo(int n)
            :   av_( n )
        {
        }

        operator bool()
        {
            av_ += sw_;
            sw_.reset();
            return av_.need_more_values();
        }

        average     av_;
        stop_watch  sw_;
    };

int main()
{
    int i = 99999;
    int c = 0;
    foo f( 10000 );
    do
    {

        int k = i;
        do
        {
            if(k & 0x1)
                ++c;
            k >>= 1;
        }while(k);

    }while(f);
    cout << c << endl;
    cout << f.av_.value() << endl;
}

japro

warum ist clock() eigentlich so unpräzise? ich meine es gibt doch diese konstanten (weiss jetzt grad nimmer wie sie genau geheissen haben) die die ticks per second und so angeben und ich bin mir sicher das der standard nicht vorschreibt clock müsse eine schlechte auflösung haben....
jedenfalls aufm gcc isses so unpräzise. aber das würde doch nicht so viel kosten da mal eben schnell das ganze betribssystemspezifisch neu zu machen... ist ja nur eine funktion die man ändern muss...

zum rdtsc:
Intel raet davor noch ein cpuid zu machen um die sequenzielle ausfuerung zu erzwingen. ansonsten kann es zu fehlmessungen kommen.

GetTicks() etc. sind ungenau,da es passieren kann daß der Thread in dem die Algorithmen laufen vom BS zugunsten eines anderen höher priorisierten verdrängt wird. Unter Win gibt es eine Fkt. GetThreadTimes() die genau das berücksichtigt. Evtl. gibt es eine ähnliche Fkt. unter Linux

Gerard

Original erstellt von <b7f7>:
zum rdtsc:
Intel raet davor noch ein cpuid zu machen um die sequenzielle ausfuerung zu erzwingen. ansonsten kann es zu fehlmessungen kommen.

dazu habe ich das gefunden http://cedar.intel.com/software/idap/media/pdf/rdtscpm1.pdf

4.2 Pentium Processors and Pentium with MMXTM Technology
Processors
All of the rules and code samples described in section 4.1 also apply to the Pentium Processor and Pentium with
MMXTM Technology Processor. The only difference is, the CPUID instruction is not necessary for serialization.
Thus, all calls to CPUID can be omitted from the code samples. Leaving the calls to CPUID in will not make the
code incorrect, only slower.

true but:
ab PII gibt es soetwas wie out of order execution also auf allen heute gebrauchlichen Chips in der intelwelt