Optimization: const int& ?

[9lives.9lives]

Hello, everyone! I am trying to optimize some code, but I don't think
I'm doing what I think I'm doing. I profiled my code and found that
the overloaded [] operator of my monomial class did
6384690328 calls in 33.67 seconds.

33.67 6384690328 Monomial:perator[](int) const

Since the parameter was an int, I made it const int& since I reasoned
I would be saving a copy of the int parameter to the stack by changing
from a pass-by-value to pass-by-reference. However, when I next ran
the code the overloaded operator made
6384690328 calls in 71.86 seconds.

Changing the from int to const int& actually slowed it down, more than
doubled the speed! I wonder if anyone can tell me why? My reasoning
must be faulty...

Here is the full function declaration:
inline int operator[](const int& i) const
{
assert(0 <= i && i < n);
return exp;
};


exp is an int*.

Any help or comments on how to speed up this simple function would be
most, most appreciated!

Very best regards,
Susan

 

[Kira Yamato]

Hello, everyone! I am trying to optimize some code, but I don't think
I'm doing what I think I'm doing. I profiled my code and found that
the overloaded [] operator of my monomial class did
6384690328 calls in 33.67 seconds.

33.67 6384690328 Monomial:perator[](int) const

Since the parameter was an int, I made it const int& since I reasoned
I would be saving a copy of the int parameter to the stack by changing
from a pass-by-value to pass-by-reference. However, when I next ran
the code the overloaded operator made
6384690328 calls in 71.86 seconds.

Changing the from int to const int& actually slowed it down, more than
doubled the speed! I wonder if anyone can tell me why? My reasoning
must be faulty...

Here is the full function declaration:
inline int operator[](const int& i) const
{
assert(0 <= i && i < n);
return exp;
};


exp is an int*.

Any help or comments on how to speed up this simple function would be
most, most appreciated!

Very best regards,
Susan

The integer probably has the same size as a pointer. So you're not
saving much passing by value vs. passing by reference in this case.

However, when you pass by reference, you're really passing a pointer.
So, when the operator[] function uses it, it has to dereference it to
get the actual value of the integer. So, you're actually increasing
work at runtime.

Just a guess.

 

[Ian Collins]

Hello, everyone! I am trying to optimize some code, but I don't think
I'm doing what I think I'm doing. I profiled my code and found that
the overloaded [] operator of my monomial class did
6384690328 calls in 33.67 seconds.

33.67 6384690328 Monomial:perator[](int) const

Since the parameter was an int, I made it const int& since I reasoned
I would be saving a copy of the int parameter to the stack by changing
from a pass-by-value to pass-by-reference. However, when I next ran
the code the overloaded operator made
6384690328 calls in 71.86 seconds.

Changing the from int to const int& actually slowed it down, more than
doubled the speed! I wonder if anyone can tell me why? My reasoning
must be faulty...

Implementation specific behaviour, but when passing by reference the
code has to take the address of the variable passed. The variable may
well have been in a register which would simply be pushed on the stack.
One some machines, the compiler could place the variable in a register
which can be accessed by the called function without using the stack.

 

[Alf P. Steinbach]

* 9lives.9lives:

Here is the full function declaration:
inline int operator[](const int& i) const
{
assert(0 <= i && i < n);
return exp;
};


exp is an int*.

As others have already remarked, passing by reference usually incurs
some overhead (dereferencing) compared to passing an int by value.

General rule: if the type is built-in, pass by value, but if it is a
class, pass by reference to const.

Libraries such as Boost provide automated choice of the way to pass a
value argument, based on size, but generally the above rule is enough.

Any help or comments on how to speed up this simple function would be
most, most appreciated!

Most likely the code needs to be optimized at a higher level, where this
operator is called.

Whether you're accessing the array sequentially or hither-and-dither can
be significant, because if the array is large, the access pattern
affects the number of cache reloads and (ditto) virtual memory paging.

Try to access the raw memory mostly sequentially, to maximize the
chances of working with cached data, and avoiding virtual memory page
faults (which are very very costly in terms of performance, for a disk
involving mechanical operations instead of pure electronic operations).

Cheers, & hth.,

- Alf

 

[Alf P. Steinbach]

* 9lives.9lives:

Any help or comments on how to speed up this simple function would be
most, most appreciated!

Sorry, forgot:

* Often the best optimization is /algorithmic/, not fiddling with
individual operations! Check out the algorithm used at higher level.


Cheers, & hth.,

- Alf

 

[Gianni Mariani]

Hello, everyone! I am trying to optimize some code, but I don't think
I'm doing what I think I'm doing. I profiled my code and found that
the overloaded [] operator of my monomial class did
6384690328 calls in 33.67 seconds.

33.67 6384690328 Monomial:perator[](int) const

Since the parameter was an int, I made it const int& since I reasoned
I would be saving a copy of the int parameter to the stack by changing
from a pass-by-value to pass-by-reference. However, when I next ran
the code the overloaded operator made
6384690328 calls in 71.86 seconds.

Changing the from int to const int& actually slowed it down, more than
doubled the speed! I wonder if anyone can tell me why? My reasoning
must be faulty...

Here is the full function declaration:
inline int operator[](const int& i) const
{
assert(0 <= i && i < n);
return exp;
};

I'd expect that the compiler's optimizer would produce identical inlined
code. Perhaps it's an optimizer bug ? Do you know what optimization
flags you turned on in your compiler ?

I just tried it with this code below and gcc 3.4.4 and 4.1.1 and it
produces virtually identical code for the tot function.

#include <cassert>

#ifndef REF
typedef int T;
#else
typedef int & T;
#endif

struct X
{
int * exp;
int n;

inline int operator[](const T i) const
{
assert(0 <= i && i < n);
return exp;
};
};


int tot( const X & x )
{

register int totval = 0;

for ( register int i = 0; i < x.n; ++i )
{
totval += x;
}
return totval;
}

 

[Alex Vinokur]

Any help or comments on how to speed up this simple function would be
most, most appreciated!

[snip]

This might be of interest to you.

http://groups.google.com/group/comp.lang.c++.moderated/msg/286f823e49e07e93

http://groups.google.com/group/comp.lang.c++.moderated/browse_frm/thread/d697a8b1c24bca3b