Re: C++ FAQ

In article <6a10abb9-928d-4a7e-a7cd-
e422b8a2880e@f30g2000vbf.googlegroups.com>, duggar@alum.mit.edu
says...

[ ... ]


Sure:

#include <iostream>
#include <vector>
#include <time.h>

struct noshow {
    mutable unsigned int x_, y_;
    noshow() : x_(0), y_(0) {}
    void operator()(int x, int y) const {
        x_ += x;
        y_ += y;
    }
    friend std::ostream &operator<<(std::ostream &os, noshow const
&n) {
        return os << n.x_ << " " << n.y_ <<"\n";
    }
};

template < class F >
inline void circle_octant ( int r, F &f )
{
    int x = r;
    int y = 0;
    int e = -r / 2 ;
    if ( r & 1 ) { --e; goto odd ; }
even :
    f(x,y) ;
    if ( y >= x ) return ;
    e += y++ ;
    if ( e >= 0 ) e -= --x ;
odd :
    f(x,y) ;
    if ( y >= x ) return ;
    e += ++y ;
    if ( e >= 0 ) e -= --x ;
    goto even ;
}

template <class F>
inline void circle_octant2(int r, F &f) {
    int x = r;
    int y = 0;
    int odd = r&1;
    int e = (-r/2)-odd;
    do {
        f(x,y);
        e += y++ + odd;
        if (e >= 0)
            e -= --x;
        odd ^= 1;
    } while (y < x);
    f(x,y);
}

int main() {
    int const max_radius = 1024;
    int const min_radius = 8;
    int const limit = 1000;

    noshow noshow1, noshow2;
    clock_t time1=0, time2=0;

    for (int radius=min_radius; radius<max_radius; ++radius) {
        clock_t start1 = clock();
        for (int i=0; i<limit; ++i)
            circle_octant(radius, noshow1);
        clock_t stop1 = clock();
        time1 += stop1 - start1;

        clock_t start2 = clock();
        for (int i=0; i<limit; ++i)
            circle_octant2(radius, noshow2);
        clock_t stop2 = clock();
        time2 += stop2-start2;
    }

    std::cout << noshow1 << noshow2;
    std::cout << "Time1: " << time1 << "\n";
    std::cout << "Time2: " << time2 << "\n";

    return 0;
}

Here are the results with MS VC++ 9, AMD 5200+:

2600493312 3726143080
2600493312 3726143080
Time1: 1365
Time2: 1135
2600493312 3726143080
2600493312 3726143080
Time1: 1261
Time2: 1207
2600493312 3726143080
2600493312 3726143080
Time1: 1285
Time2: 1183

Here are the results with Comeau, AMD 5200+:

D:\c\source>aout
2600493312 3726143080
2600493312 3726143080
Time1: 1374
Time2: 969

D:\c\source>aout
2600493312 3726143080
2600493312 3726143080
Time1: 1200
Time2: 1112

D:\c\source>aout
2600493312 3726143080
2600493312 3726143080
Time1: 1283
Time2: 1029

Here are the results with gcc, AMD 5200+:

Administrator@fc2 /cygdrive/d/c/source
$ ./circle1
2600493312 3726143080
2600493312 3726143080
Time1: 1283
Time2: 1170

Administrator@fc2 /cygdrive/d/c/source
$ ./circle1
2600493312 3726143080
2600493312 3726143080
Time1: 1370
Time2: 1083

Administrator@fc2 /cygdrive/d/c/source
$ ./circle1
2600493312 3726143080
2600493312 3726143080
Time1: 1315
Time2: 1138

I can't easily cut 'n paste the results from the other computers, but
I also tested on my a couple of Intel-based machines (my kid's Dell,
my Wife's iMac), my Wife's PowerPC G4-based ibook, and (just for
grins), on my wife's Treo and my old iPaq. The latter two required
different UI code (they don't support a command line at all), but the
test code itself remained identical.

As for reconciling your results, given the real facts of the
situation, I see no reason to even attempt to do so. What you tested
was NOT what either of us actually posted!

Since I prefer to have some built-in timing code, so you don't need
profilers and such to get results, I reworked things a bit more to
consolidate the timing code. In the process, I did change the code
from template functions to template functor classes. This seems to
have no effect on speed compared to the code above that uses them
exactly as posted, but makes it a bit simpler to deal with multiple
versions of the drawing code. Since it was easy, I added another of
your attempts along with Francis Glassborrow's code. Along with that,
since you seem to consider it important, I added a bit of code to
mine to deal with r==0:

#include <iostream>
#include <vector>
#include <time.h>

struct noshow {
    mutable unsigned int x_, y_;
    noshow() : x_(0), y_(0) {}
    void operator()(int x, int y) const {
        x_ += x;
        y_ += y;
    }
    friend std::ostream &operator<<(std::ostream &os, noshow const
&n) {
        return os << n.x_ << " " << n.y_ <<"\n";
    }
};

template < class F >
struct circle0 {
    void operator()(int r, F &f )
    {
        int x = r;
        int y = 0;
        int e = -r / 2 ;
        if ( r & 1 ) { --e; goto odd ; }
    even :
        f(x,y) ;
        if ( y >= x ) return ;
        e += y++ ;
        if ( e >= 0 ) e -= --x ;
    odd :
        f(x,y) ;
        if ( y >= x ) return ;
        e += ++y ;
        if ( e >= 0 ) e -= --x ;
        goto even ;
    }
};

template <class F>
struct circle1 {
    void operator()(int r, F &f) {
        if (r==0)
            return;
        int x = r;
        int y = 0;
        int odd = r&1;
        int e = (-r/2)-odd;
        do {
            f(x,y);
            e += y++ + odd;
            if (e >= 0)
                e -= --x;
            odd ^= 1;
        } while (y < x);
        f(x,y);
    }
};

template <class F>
struct circle2 {
    void operator()(int r, F &f)
    {
        int x = r ;
        int y = 0 ;
        bool o = r & 1 ;
        int e = -r / 2 - o ;

        for ( ; ; ) {
            f(x,y) ;
            if ( y >= x ) return ;
            e += y + o ;
            ++y ;
            o = !o ;
            if ( e >= 0 ) e -= --x ;
        }
    }
};

template <class F>
struct circle3 {

    void operator()(int r, F &f) {
        int x = r ;
        int y = 0 ;
        int e = -r / 2 ;
        if(r & 1) {
            --e ;
            f(x,y) ;
            e+= ++y ;
            if ( e >= 0 ) e -= --x ; // required for r == 1
        }
        while (true) {
            f(x,y) ;
            if ( y >= x ) return ;
            e += y++;
            if ( e >= 0 ) e -= --x ;
            f(x,y) ;
            if ( y >= x ) return ;
            e += ++y;
            if ( e >= 0 ) e -= --x ;
        }
    }
};

template <template <class D> class octant, class F>
clock_t timer(octant<F> &o, int radius, int reps, F &f) {
    clock_t start = clock();
    for (int i=0; i<reps; i++)
        o(radius, f);
    clock_t stop = clock();
    return stop - start;
}

int main() {
    int const max_radius = 1024;
    int const min_radius = 8;
    int const limit = 1000;

    noshow noshow1, noshow2, noshow3, noshow4;

    clock_t time1=0, time2=0, time3=0, time4 = 0;

    for (int radius=min_radius; radius<max_radius; ++radius) {
        time1 += timer(circle0<noshow>(), radius, limit, noshow1);
        time2 += timer(circle1<noshow>(), radius, limit, noshow2);
        time3 += timer(circle2<noshow>(), radius, limit, noshow3);
        time4 += timer(circle3<noshow>(), radius, limit, noshow4);
    }

    std::cout << noshow1 << noshow2 << noshow3 << noshow4;
    std::cout << "\nKeith's original:\t" << time1;
    std::cout << "\nJerry's do/while:\t" << time2;
    std::cout << "\nKeith's \"improved\":\t" << time3;
    std::cout << "\nFrancis's while loop:\t" << time4;
    return 0;
}

Strangely, adding the test for r==0 to my code actually makes it run
a bit faster (even though I'm never giving it a radius of 0, so that
branch is never taken -- apparently that test lets the oompiler
simplify some other part of the code, though I haven't looked at the
assembly output to figure out what). In terms of relative speed, this
doesn't make a whole lot of difference though:

c:\c\source>circle1test
2600493312 3726143080
2600493312 3726143080
2600493312 3726143080
2600493312 3726143080

Keith's original: 1120
Jerry's do/while: 961
Keith's "improved": 1159
Francis's while loop: 1196
c:\c\source>circle1test
2600493312 3726143080
2600493312 3726143080
2600493312 3726143080
2600493312 3726143080

Keith's original: 1084
Jerry's do/while: 965
Keith's "improved": 1158
Francis's while loop: 1194
c:\c\source>circle1test
2600493312 3726143080
2600493312 3726143080
2600493312 3726143080
2600493312 3726143080

Keith's original: 1084
Jerry's do/while: 950
Keith's "improved": 1150
Francis's while loop: 1170

Changing the compiler options can change some of the rankings. For
example, if we don't use the SSE2 instruction set, but do use link
time code generation, Francis's code moves up to second place:

c:\c\source>circle1test
2600493312 3726143080
2600493312 3726143080
2600493312 3726143080
2600493312 3726143080

Keith's original: 1161
Jerry's do/while: 938
Keith's "improved": 1198
Francis's while loop: 1007
c:\c\source>circle1test
2600493312 3726143080
2600493312 3726143080
2600493312 3726143080
2600493312 3726143080

Keith's original: 1160
Jerry's do/while: 943
Keith's "improved": 1188
Francis's while loop: 1018
c:\c\source>circle1test
2600493312 3726143080
2600493312 3726143080
2600493312 3726143080
2600493312 3726143080

Keith's original: 1187
Jerry's do/while: 948
Keith's "improved": 1165
Francis's while loop: 1051

I won't bore you more with pages of results from other compilers and
platforms, but the summary is pretty simple: my code is consistently
the fastest. Francis's code is the least consistent, varying all the
way from last place to a close second place.

If we only look at the best set of options for each piece of code, on
each platform, the results are more consistent: my code is the
fastest, Francis's is a close second place, and your two attempts are
nearly tied for last place, though the original is probably slightly
faster than your modified version (the modified version sometimes
wins, but the original wins quite a bit more often).

--
    Later,
    Jerry.

      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated. First time posters: Do this! ]