Operator overloading, C++ performance crappiness

[Karl Heinz Buchegger]

Karl Heinz Buchegger wrote:
[snip]

int main()
{
Matrix a(2), b(3), c;
time_t start, end;

start = clock();
for( int j = 0; j < 100000; ++j )
c = a + b;
end = clock();

Are you sure the compiler did not optimize away all of the loop?
After all, neither a nor b nor c are changing.#

Thats what I initially thought also.
But then I tried an experiment: I increased the number
of iterations and with that the time increased. For me
this is evicence enough that the loop is not
optimized away entirely.

 

[Karl Heinz Buchegger]

Thanks. I don't think there is any difference in speed between the
add() method and the overloaded operator though. I think the difference
you are seeing is from already having the output loaded on the second
run.

Then the second run should actually be faster, don't you think.
But in reality quite the contrary is true. The second run through
the loop, using the add() function is slower.

The CPU will optimize away some of the value changes because they
are exactly the same on the second run. If you separate out the two
versions and run two separate instances the timing will be exactly the same.

Just switch the 2 code parts and see if the results are the same.
Hint: They are the same.

 

[Kai-Uwe Bux]

Is there any way to get to the left-hand side of an operator? Consider
the following (this is not meant to be perfect code, just an example of
the problem):

class Matrix
{
public:
int data[1024];

Matrix() {}

Matrix(int value)
{
for (unsigned i = 0; i < sizeof(data)/sizeof(int); i++)
data = value;
}

void add(const Matrix& obj, Matrix* output)
{
for (unsigned i = 0; i < sizeof(data)/sizeof(int); i++)
output->data = data + obj.data;
}

Matrix operator +(const Matrix& obj)
{
Matrix temp; // "unnecessary" creation of temp variable

for (unsigned i = 0; i < sizeof(data)/sizeof(int); i++)
temp.data = data + obj.data;

return temp; // "unnecessary" extra copy of output
}
};

For nice looking syntax you _really_ want to use the operator+ like:
matrix3 = matrix1 + matrix2;

However, that is some 50% slower than the _much_ uglier:
matrix1.add(matrix2, &matrix3);

If only there were a way to get to the left-hand argument of the
operator+ then it could be fast and easy to use. Consider the following
code which is not valid C++ and will not compile for this example:

Matrix as M
operator+(const Matrix& obj)
{
for (unsigned i = 0; i < sizeof(data)/sizeof(int); i++)
M.data = data + obj.data;
}

That would be fast and clean to use. Is there any way to accomplish
this? Otherwise the situation is just ugly and there is no point in
using operator overloading for these types of situations (which really
defeats the purpose of operator overloading in the first place).

I guess somebody else already mentioned expression templates. Here is some
code for experimentation:

unsigned long const rank = 1024;
unsigned long const runs = 12345;

template < typename VectorExprA,
typename VectorExprB >
struct VectorSum {

typedef typename VectorExprA::value_type value_type;

VectorExprA const & a;
VectorExprB const & b;

VectorSum( VectorExprA const & a_,
VectorExprB const & b_ )
: a ( a_ )
, b ( b_ )
{}

value_type operator[] ( unsigned long i ) const {
return( a + b );
}

}; // struct VectorSum<>;

template < typename arithmetic_type,
unsigned long dim >
class Vector {
public:

typedef arithmetic_type value_type;

private:

value_type entry [dim];

public:

Vector ( value_type val = value_type() ) {
for ( unsigned long i = 0; i < dim; ++i ) {
entry = val;
}
}

Vector & operator= ( Vector const & other ) {
for ( unsigned int i = 0; i < dim; ++i ) {
this->entry = other.entry;
}
return( *this );
}

template < typename VectorExpr >
Vector & operator= ( VectorExpr const & expr ) {
for ( unsigned long i = 0; i < dim; ++i ) {
this->entry = expr;
}
return( *this );
}

value_type const & operator[] ( unsigned long i ) const {
return( entry );
}

value_type & operator[] ( unsigned long i ) {
return( entry );
}

void add ( Vector const & other, Vector & result ) const {
for( unsigned int i = 0; i < dim; ++i ) {
result.entry = this->entry + other.entry;
}
}

}; // class Vector<>;

template < typename VectorExprA,
typename VectorExprB >
inline
VectorSum< VectorExprA, VectorExprB > operator+ ( VectorExprA const & a,
VectorExprB const & b ) {
return( VectorSum< VectorExprA, VectorExprB >( a, b ) );
}




#include <iostream>
#include <ctime>
#include <cstdlib>

void test_operator1 ( void ) {
Vector< double, rank > a ( 0 );
Vector< double, rank > b ( 1 );
std::clock_t ticks = std::clock();
{
for ( unsigned int i = 0; i < runs; ++i ) {
a = a + b;
}
}
ticks = std::clock() - ticks;
std::cout << "opp1: a[0] = " << a[0] << " time: " << ticks << '\n';
}

void test_operator2 ( void ) {
Vector< double, rank > a ( 0 );
Vector< double, rank > b ( 1 );
std::clock_t ticks = std::clock();
{
for ( unsigned int i = 0; i < runs; ++i ) {
a = a + b + b;
}
}
ticks = std::clock() - ticks;
std::cout << "opp2: a[0] = " << a[0] << " time: " << ticks << '\n';
}


void test_add1 ( void ) {
Vector< double, rank > a ( 0 );
Vector< double, rank > b ( 1 );
std::clock_t ticks = std::clock();
{
for ( unsigned int i = 0; i < runs; ++i ) {
a.add( b, a );
}
}
ticks = std::clock() - ticks;
std::cout << "add1: a[0] = " << a[0] << " time: " << ticks << '\n';
}

void test_add2 ( void ) {
Vector< double, rank > a ( 0 );
Vector< double, rank > b ( 1 );
std::clock_t ticks = std::clock();
{
for ( unsigned int i = 0; i < runs; ++i ) {
a.add( b, a );
a.add( b, a );
}
}
ticks = std::clock() - ticks;
std::cout << "add2: a[0] = " << a[0] << " time: " << ticks << '\n';
}

int main ( void ) {
std::srand( 24163 );
while ( true ) {
switch ( std::rand() % 4 ) {
case 0 :
test_operator1();
break;
case 1 :
test_operator2();
break;
case 2 :
test_add1();
break;
case 3 :
test_add2();
break;
}
}
}


On my machine (OS: Linux; CPU: intel; CC: g++-4.0.1 all optimization turned
on), opp1 and add1 are essentially equivalent and opp2 beats add2.


Best

Kai-Uwe Bux

 

[Aleksey Loginov]

Yes, I believe that. I've tested on several compilers/systems and all
pretty much give the same result, 'add' is two-three times better. The
difference undoubtedly comes from the fact that the matrix needs to be
copied to and fro.

can you compare result with

#include <iostream>

using namespace std;

const int dim=4;

struct matrix {
int * data;
int size;

explicit matrix () : data (new int[dim]), size (dim) { }

explicit matrix (int value) : data (new int[dim]), size (dim) {
for ( int i=0; i<size; ++i ) data=value;
}

~matrix () { delete [] data; }

matrix (const matrix &);

matrix & operator = (const matrix & x) {
matrix * ptr=const_cast<matrix *>(&x);
delete [] this->data;
this->data=ptr->data;
this->size=ptr->size;
ptr->data=0; ptr->size=0;
return (*this);
}

int & operator [] (int i) { return data; }
const int & operator [] (int i) const { return data; }

};


matrix operator + ( const matrix & x, const matrix & y ) {
matrix temp;

for (int i=0; i<temp.size; ++i) temp=x+y;

return temp;
}

int main () {

matrix a(2);
matrix b(3);
matrix c;

c=a+b;

return 0;
}

 

[Earl Purple]

Jojo wrote:
<snip>

If you really want to add performance you might find pointer arithmetic
is faster than using array access. Thus:

class Matrix
{
public:
enum { numElements = 1024 };

int data[numElements];


Matrix() {}


explicit Matrix(int value)
{
int* begin( data );
int* end( data + numElements );
while ( begin != end )
{
*begin = value;
++begin;
}
}

Matrix& operator+=( const Matrix& rhs )
{
int* begin( data );
int* end( data + numElements );
const int* srcBegin( rhs.data );
while ( begin != end )
{
*begin = *srcBegin;
++begin;
++srcBegin;
}
return *this;
}
}

Matrix operator+( const Matrix& lhs, const Matrix& rhs )
{
Matrix temp( lhs );
return temp += rhs;
}


If you want to do operator+ without copy-construction then

Matrix operator+( const Matrix& lhs, const Matrix& rhs )
{
Matrix temp;
int* destBegin ( temp.data );
const int* src1Begin( lhs.data );
const int* src2Begin( rhs.data );
int* destEnd( destBegin + Matrix::numElements );
while ( destBegin != destEnd )
{
*destBegin = *src1Begin + *src2Begin;
++destBegin;
++src1Begin;
++src2Begin;
}
};

Note, you could also use post-increment on the pointers which appears
to use fewer lines of code but in reality would probably generate the
same assembly code here (with regular pointers) could could generate
more code (using iterators).

(And you can change the use of the word Begin to something like Pos if
you think Begin is a misnomer).

Note: you'll probably find that STL implements its algorithms similar
to how I just did, and you might want to actually use them.

 

[Victor Bazarov]

Yes, I believe that. I've tested on several compilers/systems and all
pretty much give the same result, 'add' is two-three times better. The
difference undoubtedly comes from the fact that the matrix needs to be
copied to and fro.

can you compare result with

[...]

I just went ahead and merged the OP's 'Matrix' code with your 'matrix',
and then ran 5 million loops of additions for one and then for the other.
The results are interesting, implementing crude "move" semantics does
give an advantage:

2 3 5 21804
2 3 5 13142

(the first is for the 'Matrix' additions, the latter is for 'matrix').

I had to adjust your 'dim' to 1024 to match the original code. I did
implement the copy constructor (although some compilers didn't seem to
need it), just in case.

V

 

[Aleksey Loginov]

Jojo wrote:

6703 is for add() method
11484 is for "c = a + b"

Yes, I believe that. I've tested on several compilers/systems and all
pretty much give the same result, 'add' is two-three times better. The
difference undoubtedly comes from the fact that the matrix needs to be
copied to and fro.

can you compare result with

[...]

I just went ahead and merged the OP's 'Matrix' code with your 'matrix',
and then ran 5 million loops of additions for one and then for the other.
The results are interesting, implementing crude "move" semantics does
give an advantage:

2 3 5 21804
2 3 5 13142

(the first is for the 'Matrix' additions, the latter is for 'matrix').

what time for add() method?

I had to adjust your 'dim' to 1024 to match the original code. I did
implement the copy constructor (although some compilers didn't seem to
need it), just in case.

thanks.
can you try this code, please?

#include <iostream>

using namespace std;

const int dim=1024;

struct matrix {
int * data;
int size;

struct matrix_ref {
matrix * ptr;
matrix_ref ( matrix * x ) : ptr (x) { }
matrix * operator -> () { return ptr; }
};

explicit matrix () : data (new int[dim]), size (dim) { }

explicit matrix (int value) : data (new int[dim]), size (dim) {
for ( int i=0; i<size; ++i ) data=value;
}

explicit matrix (const matrix &);

~matrix () { delete [] data; }


matrix (matrix_ref ptr) : data(0), size(0) {
this->reset (ptr);
}

matrix & operator = (matrix & x) {
this->reset (x);
return (*this);
}

matrix & operator = (matrix_ref ptr) {
this->reset (ptr);
return (*this);
}

operator matrix_ref () { return matrix_ref (this); }


void reset ( matrix_ref ptr ) {
delete [] this->data;
this->data=ptr->data;
this->size=ptr->size;
ptr->data=0; ptr->size=0;
}

int & operator [] (int i) { return data; }
const int & operator [] (int i) const { return data; }

};


matrix operator + ( const matrix & x, const matrix & y ) {
matrix temp;

for (int i=0; i<temp.size; ++i) temp=x+y;

return temp;
}

int main () {

matrix a(2);
matrix b(3);
matrix c;

c=a+b;

return 0;
}

 

[Victor Bazarov]

Victor Bazarov wrote:


Jojo wrote:


6703 is for add() method
11484 is for "c = a + b"

Yes, I believe that. I've tested on several compilers/systems and all
pretty much give the same result, 'add' is two-three times better. The
difference undoubtedly comes from the fact that the matrix needs to be
copied to and fro.


can you compare result with

[...]

I just went ahead and merged the OP's 'Matrix' code with your 'matrix',
and then ran 5 million loops of additions for one and then for the other.
The results are interesting, implementing crude "move" semantics does
give an advantage:

2 3 5 21804
2 3 5 13142

(the first is for the 'Matrix' additions, the latter is for 'matrix').

what time for add() method?

Your class 'matrix' doesn't have 'add' method.

I had to adjust your 'dim' to 1024 to match the original code. I did
implement the copy constructor (although some compilers didn't seem to
need it), just in case.

thanks.
can you try this code, please?

[..]

Sorry, I don't have time at this point. Maybe over the weekend if you are
still interested by then.

V

 

[Aleksey Loginov]

here

Yes, I believe that. I've tested on several compilers/systems and all
pretty much give the same result, 'add' is two-three times better. The
difference undoubtedly comes from the fact that the matrix needs to be
copied to and fro.


can you compare result with

[...]

I just went ahead and merged the OP's 'Matrix' code with your 'matrix',
and then ran 5 million loops of additions for one and then for the other.
The results are interesting, implementing crude "move" semantics does
give an advantage:

2 3 5 21804
2 3 5 13142

(the first is for the 'Matrix' additions, the latter is for 'matrix').

what time for add() method?

Your class 'matrix' doesn't have 'add' method.

i thought OP have... no matter.

I had to adjust your 'dim' to 1024 to match the original code. I did
implement the copy constructor (although some compilers didn't seem to
need it), just in case.

thanks.
can you try this code, please?

[..]

Sorry, I don't have time at this point. Maybe over the weekend if you are
still interested by then.

i can wait, it's not a problem.

i work with gcc 3.2, so can't get real results by myself...

 

[Victor Bazarov]

[...]
i work with gcc 3.2, so can't get real results by myself...

Hmm... I didn't know gcc 3.2 was unable to produce real results...

 

[lilburne]

Yes, I believe that. I've tested on several compilers/systems and all
pretty much give the same result, 'add' is two-three times better. The
difference undoubtedly comes from the fact that the matrix needs to be
copied to and fro.

This is the main reason why we discourage operator=() in our codebase,
prefering the add() style of API. We've been bitten by performance hits
like this too often.

 

[Aleksey Loginov]

[...]
i work with gcc 3.2, so can't get real results by myself...

Hmm... I didn't know gcc 3.2 was unable to produce real results...

good compiler, but he is 2 year's old...