Superbasic efficiency question

"Joseph Turian" <tu****@gmail.com> wrote in message
news:11**********************@c13g2000cwb.googlegr oups.com...

Aaron,

Performance on the toy code snippet is not informative of anything more
than performance on the toy code snippet.
Please help me resolve my internal struggle.
10 Write the code the most clear, maintable way possible.
20 Run the code under a profiler.
30 Optimize the actual performance bottleneck (as opposed to, say,
imaginary performance bottlenecks).

Optimizing might require significant changes, even major design changes. If
you know from the outset that speed is important, then consider it from the
outset. Toy code snippets can help you determine early on how you'll need to
go about doing certain things.
40 GOTO 20

If you have any problems with 30, get back to the group. Until then,
both you and us are just shooting in the dark.

Jul 22 '05 #3

Gianni Mariani

I'm working on a scientific computing application. I need a class
called Element which is no more than a collection of integers, or
"nodes" and has only on method int getNode(int i).

I would like to implement in the most efficient was possible. So I
summoned up my programming intellect and asked myself: Do I want to
have members such as int a, b, c, d, e or a single member such as int
a[5]. So I wrote the following snippet and compiled it with a -O3 flag:

int main(char *argv[], int argc) {

/*
int a, b, c, d, e;
for (int i = 0; i < 1000000000; i++) {
a = 1;
b = 2;
c = 3;
d = 4;
e = 5;
}

*/
int a[5];
for (int i = 0; i < 1000000000; i++) {
a[0] = 1;
a[1] = 2;
a[2] = 3;
a[3] = 4;
a[4] = 5;
}

return 0;
}

The first (commented out) version ran twice as fast. (For doubles
instead of ints, it was a factor of 4). So the simpleton part of me
thinks that that answers my question. The remaining part tells me that
it is never that simple. Finally, the cynical part of me thinks that it
all doesn't matter and other parts of the program are bound to be far
more time consuming.

It is more than likely that the compiler re-arranged your code

int a, b, c, d, e;
a = 1;
b = 2;
c = 3;
d = 4;
e = 5;
for (int i = 0; i < 1000000000; i++) {
}

Or, perhaps the compiler placed the values in registers.

There is a deeper design question for you.

Are these values really related ? Do you do operations on them in
tandem ? Would you ever think that it might be interesting to write a
template function with a "pointer to member" of one of these values ?

I would go with the 5 separate values if they are truly separate. That
way it will be harder to run into other problems like going past array
bounds or issues with using the wrong index etc.

Anyhow, below is an example where the compiler can't (easily) make the
optimization above. The results are essentially identical with:
gcc version 4.0.0 20050102 (experimental)
#include <ostream>
#include <iostream>

struct X
{
virtual void F() = 0; // hard for compiler to optimize this
};

struct A
{
int a, b, c, d, e;
};

struct B
{
int a[5];
};
struct Av
: A, X
{
Av()
: A()
{
}

virtual void F()
{
a = 1;
b = 2;
c = 3;
d = 4;
e = 5;
}
};

struct Bv
: B, X
{
Bv()
: B()
{
}

virtual void F()
{
a[0] = 1;
a[1] = 2;
a[2] = 3;
a[3] = 4;
a[4] = 5;
a[5] = 6;
}
};

int main( int argc, char ** argv )
{
X * x;
if ( argc >= 2 )
{
std::cout << "Making an A\n";
x = new Av;
}
else
{
std::cout << "Making a B\n";
x = new Bv;
}

for (int i = 0; i < 1000000000; i++)
{
x->F();
}

}
$ g++ -O3 -o ./optimal_array_or_members ./optimal_array_or_members.cpp
$ time ./optimal_array_or_members
Making a B
6.900u 0.000s 0:06.92 99.7% 0+0k 0+0io 216pf+0w
$ time ./optimal_array_or_members d
Making an A
6.770u 0.000s 0:06.78 99.8% 0+0k 0+0io 216pf+0w
$ time ./optimal_array_or_members
Making a B
6.960u 0.010s 0:06.96 100.1% 0+0k 0+0io 216pf+0w
$ time ./optimal_array_or_members s
Making an A
6.920u 0.000s 0:06.92 100.0% 0+0k 0+0io 216pf+0w
$ time ./optimal_array_or_members
Making a B
7.010u 0.000s 0:07.00 100.1% 0+0k 0+0io 216pf+0w
$ time ./optimal_array_or_members s
Making an A
6.950u 0.000s 0:06.95 100.0% 0+0k 0+0io 216pf+0w
$ time ./optimal_array_or_members
Making a B
6.770u 0.000s 0:06.76 100.1% 0+0k 0+0io 216pf+0w
$ time ./optimal_array_or_members s
Making an A
6.850u 0.000s 0:06.84 100.1% 0+0k 0+0io 216pf+0w

Jul 22 '05 #4

I'm thinking that your getting a silent error on the code. I don't
believe an integer can handle the value 1000000000 in the following:

for (int i = 0; i < 1000000000; i++)

So what's happening is your integer "i" is overflowing and getting set
to an unpredictable value (possibly negative). You might have better
luck using an "unsigned long" or even "std::size_t".

I'm not sure what the standard says, but I think most compilers
implement 32 bit integers. So an "unsigned" int is 0 to 2^32, and the
"signed" int is -2^16 to 2^16. (Subtract or add a 1 where needed).

Check your compiler's docs to see the sizes of the integral data types.
Otherwise, there should be no real difference in performance of the
code with optimizations on. When you measure the time, remember to
record cpu clock cycles instead of time in seconds.
Hope this helps!

Chris J. (aka Sethalicious)

Jul 22 '05 #5

My feeling is that when you try to implement 'getNode', you will find
that the array-based implementation is faster than a switch statement.
You might be able to squeeze out some more performance though with a
variable-based implementation if you templatize 'getNode' on i, and
specialize for values of i. (Presumably there is some more generic code
in your application which makes 'getNodeA', 'getNodeB', etc.,
prohibitive.)

Jul 22 '05 #6

<aa*******@gmail.com> wrote in message
news:11**********************@c13g2000cwb.googlegr oups.com...

[snip]

int main(char *argv[], int argc) {

/*
int a, b, c, d, e;
for (int i = 0; i < 1000000000; i++) {
a = 1;
b = 2;
c = 3;
d = 4;
e = 5;
}

*/
int a[5];
for (int i = 0; i < 1000000000; i++) {
a[0] = 1;
a[1] = 2;
a[2] = 3;
a[3] = 4;
a[4] = 5;
}

return 0;
}

The first (commented out) version ran twice as fast. (For doubles
instead of ints, it was a factor of 4). So the simpleton part of me
thinks that that answers my question. The remaining part tells me that
it is never that simple. Finally, the cynical part of me thinks that it
all doesn't matter and other parts of the program are bound to be far
more time consuming.

The most likely reason for the difference is that the compiler automatically
places arrays in main memory but individual objects in registers when
possible. I don't see how this test helps for your particular problem. You
need your collection to be indexable, so you don't really have the option of
using individual named variables. Although test programs like this can be
useful, you have to determine the reason for the performance difference and
consider whether the results will hold for your program. If the reason is
register use, then the test probably doesn't mean much.

DW

Jul 22 '05 #7

Joseph Turian

Aaron,

Performance on the toy code snippet is not informative of anything more
than performance on the toy code snippet.

Please help me resolve my internal struggle.

Jul 22 '05 #8

My feeling is that when you try to implement 'getNode', you will find
that an array-based implemenation is faster than a switch statement.
OTOH, you might find that templatizing 'getNode' on i, and then
specializing for values of i is faster yet. Presumably, there is some
more generic part of your application that makes 'getNodeA',
'getNodeB', etc., prohibitive. /david

Jul 22 '05 #9

Jul 22 '05 #10

Jul 22 '05 #11

Jul 22 '05 #12

I'm thinking that your getting a silent error on the code. I don't
believe an integer can handle the value 1000000000 in the following:

for (int i = 0; i < 1000000000; i++)

So what's happening is your integer "i" is overflowing and getting set
to an unpredictable value (possibly negative). You might have better
luck using an "unsigned long" or even "std::size_t".

I'm not sure what the standard says, but I think most compilers
implement 32 bit integers. So an "unsigned" int is 0 - 2^32, and the
"signed" int is -2^16 to 2^16. (Subtract or add a 1 where needed).

Check your compiler's docs to see the sizes of the integral data types.
Otherwise, there should be no real difference in performance of the
code with optimizations on. When you measure the time, remember to
record cpu clock cycles instead of time in seconds.
Hope this helps!

Chris J. (aka Sethalicious)

Jul 22 '05 #13

Gianni Mariani

Sethalicious wrote:

I'm thinking that your getting a silent error on the code. I don't
believe an integer can handle the value 1000000000 in the following:

for (int i = 0; i < 1000000000; i++)

So what's happening is your integer "i" is overflowing and getting set
to an unpredictable value (possibly negative). You might have better
luck using an "unsigned long" or even "std::size_t".

Not in this case - 1billion is less that 2^31.
I'm not sure what the standard says, but I think most compilers
implement 32 bit integers. So an "unsigned" int is 0 to 2^32, and the
"signed" int is -2^16 to 2^16. (Subtract or add a 1 where needed).

Think again.

int has a range from - 2^31 to (2^31-1)

Jul 22 '05 #14

Gianni Mariani

da********@warpmail.net wrote:

My feeling is that when you try to implement 'getNode', you will find
that the array-based implementation is faster than a switch statement.
That's true. A pointer to member might be an alternative.
You might be able to squeeze out some more performance though with a
variable-based implementation if you templatize 'getNode' on i, and
specialize for values of i. (Presumably there is some more generic code
in your application which makes 'getNodeA', 'getNodeB', etc.,
prohibitive.)

Templates also take pointer to members.

Jul 22 '05 #15

Jonathan Turkanis

I'm working on a scientific computing application. I need a class
called Element which is no more than a collection of integers, or
"nodes" and has only on method int getNode(int i).

I would like to implement in the most efficient was possible. So I
summoned up my programming intellect and asked myself: Do I want to
have members such as int a, b, c, d, e or a single member such as int
a[5]. So I wrote the following snippet and compiled it with a -O3
flag:

Make sure that Element is well encapsulated so that you can switch easily
between different implementations. Then, take Joseph's advice and don't worry
about which implementation is better until you can do performance measurements
in real-world scenarios.

Jonathan

Jul 22 '05 #16

I'm thinking that your getting a silent error on the code. I don't
believe an integer can handle the value 1000000000 in the following:

for (int i = 0; i < 1000000000; i++)

So what's happening is your integer "i" is overflowing and getting set
to an unpredictable value (possibly negative). You might have better
luck using an "unsigned long" or even "std::size_t".

I'm not sure what the standard says, but I think most compilers
implement 32 bit integers. So an "unsigned" int is 0 - 2^32, and the
"signed" int is -2^16 to 2^16. (Subtract or add a 1 where needed).

Check your compiler's docs to see the sizes of the integral data types.
Otherwise, there should be no real difference in performance of the
code with optimizations on. When you measure the time, remember to
record cpu clock cycles instead of time in seconds.
Hope this helps!

Chris J. (aka Sethalicious)

Jul 22 '05 #17

E. Robert Tisdale

aa*******@gmail.com wrote:

I'm working on a scientific computing application.
I need a class called Element
which is no more than a collection of integers, or "nodes"
and has only on method int getNode(int i). I would like to implement in the most efficient was possible. So I
summoned up my programming intellect and asked myself,
Do I want to have members such as int a, b, c, d and e?
Or a single member such as int a[5]?
So I wrote the following snippet and compiled it with a -O3 flag: cat main.cc #include <iostream>

int main(int argc, char* argv[]) {

if (1 < argc) {
const
size_t n = atoi(argv[1]);
#ifdef INNER
int a[5];
for (size_t j = 0; j < n; ++j) {
a[0] = 1;
a[1] = 2;
a[2] = 3;
a[3] = 4;
a[4] = 5;
}
#else //INNER
int a, b, c, d, e;
for (size_t j = 0; j < n; ++j) {
a = 1;
b = 2;
c = 3;
d = 4;
e = 5;
}
#endif//INNER
}
else {
std::cerr << argv[0] << " <iterations>"
<< std::endl;
}
return 0;
}
g++ --version g++ (GCC) 3.4.1 uname -srmpio Linux 2.6.10-1.9_FC2smp i686 i686 i386 GNU/Linux
g++ -DINNER -Wall -ansi -pedantic -O3 -o main main.cc
time ./main 1000000000 3.362u 0.004s 0:03.36 100.0% 0+0k 0+0io 0pf+0w time ./main 1000000000 3.357u 0.003s 0:03.36 99.7% 0+0k 0+0io 0pf+0w time ./main 1000000000 3.388u 0.003s 0:03.39 99.7% 0+0k 0+0io 0pf+0w time ./main 1000000000 3.388u 0.003s 0:03.39 99.7% 0+0k 0+0io 0pf+0w time ./main 1000000000 3.396u 0.002s 0:03.40 99.7% 0+0k 0+0io 0pf+0w g++ -Wall -ansi -pedantic -O3 -o main main.cc

time ./main 1000000000 3.396u 0.005s 0:03.40 99.7% 0+0k 0+0io 0pf+0w time ./main 1000000000 3.360u 0.003s 0:03.37 99.7% 0+0k 0+0io 0pf+0w time ./main 1000000000 3.371u 0.004s 0:03.37 100.0% 0+0k 0+0io 0pf+0w time ./main 1000000000 3.388u 0.003s 0:03.39 99.7% 0+0k 0+0io 0pf+0w time ./main 1000000000 3.371u 0.003s 0:03.37 100.0% 0+0k 0+0io 0pf+0w
The first (commented out) version ran twice as fast.
Mine doesn't.
(For doubles instead of ints, it was a factor of 4).
So the simpleton part of me thinks that that answers my question.
The remaining part tells me that it is never that simple.
We call that good intuition.
Finally, the [skeptical] part of me thinks that it all doesn't matter
and other parts of the program are bound to be far more time consuming.
Probably correct.
Please help me resolve my internal struggle.

Try upgrading your compiler.

Jul 22 '05 #18

I'm thinking that your getting a silent error on the code. I don't
believe an integer can handle the value 1000000000 in the following:

for (int i = 0; i < 1000000000; i++)

So what's happening is your integer "i" is overflowing and getting set
to an unpredictable value (possibly negative). You might have better
luck using an "unsigned long" or even "std::size_t".

I'm not sure what the standard says, but I think most compilers
implement 32 bit integers. So an "unsigned" int is 0 - 2^32, and the
"signed" int is -2^16 to 2^16. (Subtract or add a 1 where needed).

Check your compiler's docs to see the sizes of the integral data types.
Otherwise, there should be no real difference in performance of the
code with optimizations on. When you measure the time, remember to
record cpu clock cycles instead of time in seconds.
Hope this helps!

Chris J. (aka Sethalicious)

Jul 22 '05 #19

> Think again.

int has a range from - 2^31 to (2^31-1)

Whoops. Totally forgot about 2's complement. :-o I stand corrected!
Thanks!
Chris J. (aka Sethalicious)

Jul 22 '05 #20

Jonathan Burd

Sethalicious wrote:

I'm thinking that your getting a silent error on the code. I don't
believe an integer can handle the value 1000000000 in the following:

for (int i = 0; i < 1000000000; i++)

So what's happening is your integer "i" is overflowing and getting set
to an unpredictable value (possibly negative). You might have better
luck using an "unsigned long" or even "std::size_t".

I'm not sure what the standard says, but I think most compilers
implement 32 bit integers. So an "unsigned" int is 0 - 2^32, and the
"signed" int is -2^16 to 2^16. (Subtract or add a 1 where needed).

Check your compiler's docs to see the sizes of the integral data types.
Otherwise, there should be no real difference in performance of the
code with optimizations on. When you measure the time, remember to
record cpu clock cycles instead of time in seconds.
Hope this helps!

Chris J. (aka Sethalicious)

Duplicate posts? Get Thunderbird and subscribe to this newsgroup
using a decent NG server (news.individual.net is good.)

Secondly, please keep C in c.l.c and C++ in c.l.c++.

A bit can have one of two states (values). A total of 2^1 states.
Range: 0 to 2^1-1.

An octet byte has 8 bits, each bit of which can have one of two
states. A total of 2^8 states. Unsigned Range: 0 to 2^8-1.
Signed range: -2^7 to (2^7-1).

32-bit number:
Unsigned Range: 0 to 2^32-1
Signed range: -2^31 to (2^31-1)
Total numbers: 2^32

% grep "INT_MAX" /mingw/include/limits.h
#define INT_MAX 2147483647
#define INT_MIN (-INT_MAX-1)
#define UINT_MAX 0xffffffff

1000000000
<
2147483647

Regards,
Jonathan.

--
"Women should come with documentation." - Dave

Jul 23 '05 #21

matthias_k

I'm working on a scientific computing application. I need a class
called Element which is no more than a collection of integers, or
"nodes" and has only on method int getNode(int i).

I would like to implement in the most efficient was possible. So I
summoned up my programming intellect and asked myself: Do I want to
have members such as int a, b, c, d, e or a single member such as int
a[5]. So I wrote the following snippet and compiled it with a -O3 flag:

int main(char *argv[], int argc) {

/*
int a, b, c, d, e;
for (int i = 0; i < 1000000000; i++) {
a = 1;
b = 2;
c = 3;
d = 4;
e = 5;
}

*/
int a[5];
for (int i = 0; i < 1000000000; i++) {
a[0] = 1;
a[1] = 2;
a[2] = 3;
a[3] = 4;
a[4] = 5;
}

return 0;
}

The first (commented out) version ran twice as fast. (For doubles
instead of ints, it was a factor of 4). So the simpleton part of me
thinks that that answers my question. The remaining part tells me that
it is never that simple. Finally, the cynical part of me thinks that it
all doesn't matter and other parts of the program are bound to be far
more time consuming.

Please help me resolve my internal struggle.
Many thanks in advance!

Aaron Fude

First of all, your implementation does 1000000000-1 completely
unnecessary steps. You are assigning the same values to the same
variables a billion times. It's most probably that your compiler will
optimize the 999,999,999 unneeded iterations away... So this example
isn't a very good start to check for efficiency.

Second, as far as I can tell, the second version runs slower because you
need to dereference a pointer 5 billion times.

The expression:
a[2] = 3;
is analogous to:
*(a+2) = 3;

That may or may not explain the longer runtime, but it could be a reason.

Regards,
Matthias

Jul 23 '05 #22

Peter Koch Larsen

<aa*******@gmail.com> skrev i en meddelelse
news:11**********************@c13g2000cwb.googlegr oups.com...

I'm working on a scientific computing application. I need a class
called Element which is no more than a collection of integers, or
"nodes" and has only on method int getNode(int i).

I would like to implement in the most efficient was possible. So I
summoned up my programming intellect and asked myself: Do I want to
have members such as int a, b, c, d, e or a single member such as int
a[5]. So I wrote the following snippet and compiled it with a -O3 flag:

int main(char *argv[], int argc) {

/*
int a, b, c, d, e;
for (int i = 0; i < 1000000000; i++) {
a = 1;
b = 2;
c = 3;
d = 4;
e = 5;
}

*/
int a[5];
for (int i = 0; i < 1000000000; i++) {
a[0] = 1;
a[1] = 2;
a[2] = 3;
a[3] = 4;
a[4] = 5;
}

return 0;
}

The first (commented out) version ran twice as fast. (For doubles
instead of ints, it was a factor of 4). So the simpleton part of me
thinks that that answers my question. The remaining part tells me that
it is never that simple. Finally, the cynical part of me thinks that it
all doesn't matter and other parts of the program are bound to be far
more time consuming.

Please help me resolve my internal struggle.
Many thanks in advance!

Aaron Fude

Do not forget to examine the assembly-code, either in the debugger or by
having the compiler produce an assembly-listing. This is to make sure that
you measure what you believe you do.

/Peter

Jul 23 '05 #23

chris

I'm working on a scientific computing application. I need a class
called Element which is no more than a collection of integers, or
"nodes" and has only on method int getNode(int i).

I would like to implement in the most efficient was possible. So I
summoned up my programming intellect and asked myself: Do I want to
have members such as int a, b, c, d, e or a single member such as int
a[5]. So I wrote the following snippet and compiled it with a -O3 flag:

int main(char *argv[], int argc) {

/*
int a, b, c, d, e;
for (int i = 0; i < 1000000000; i++) {
a = 1;
b = 2;
c = 3;
d = 4;
e = 5;
}

*/
int a[5];
for (int i = 0; i < 1000000000; i++) {
a[0] = 1;
a[1] = 2;
a[2] = 3;
a[3] = 4;
a[4] = 5;
}

return 0;
}

The first (commented out) version ran twice as fast. (For doubles
instead of ints, it was a factor of 4). So the simpleton part of me
thinks that that answers my question. The remaining part tells me that
it is never that simple. Finally, the cynical part of me thinks that it
all doesn't matter and other parts of the program are bound to be far
more time consuming.

What level of optimisation are you using?

When I use -O2 in the most recent version of gcc, then both of these
programs are compiled away to an empty loop (unfortunatly gcc doesn't
eliminate empty loops as of yet.)

Chris

Jul 23 '05 #24

Lawrence Kirby

On Mon, 24 Jan 2005 12:46:38 +0100, matthias_k wrote:

aa*******@gmail.com wrote:
....

int main(char *argv[], int argc) {

/*
int a, b, c, d, e;
for (int i = 0; i < 1000000000; i++) {
a = 1;
b = 2;
c = 3;
d = 4;
e = 5;
}

*/
int a[5];
for (int i = 0; i < 1000000000; i++) {
a[0] = 1;
a[1] = 2;
a[2] = 3;
a[3] = 4;
a[4] = 5;
}

return 0;
}

The first (commented out) version ran twice as fast. (For doubles
instead of ints, it was a factor of 4). So the simpleton part of me
thinks that that answers my question. The remaining part tells me that
it is never that simple.
Right, there's no point in assigning values to variables if you never use
the value. So even if the compiler generates the sort of code you expect
you are only measuring half of the problem at best.
Finally, the cynical part of me thinks that it
all doesn't matter and other parts of the program are bound to be far
more time consuming.
Probably. Compilers can also be quite good at "optimising" pointless
operations. However it is easier for compilers to track usage of
individual variables than arrays. Your compiler may simply be optimising
the useless code in the first case better than the useless code in the
second. The situation when the values are used could be quite different.
Please help me resolve my internal struggle. Many thanks in advance!
If you need an indexed lookup for the values put them in an array, if
your code accesses the values directly and independently then don't.
Aaron Fude

First of all, your implementation does 1000000000-1 completely
unnecessary steps. You are assigning the same values to the same
variables a billion times. It's most probably that your compiler will
optimize the 999,999,999 unneeded iterations away... So this example
isn't a very good start to check for efficiency.

Although many compiler writers take the view that if you didn't want a
loop you could have written the code without one. So removing a loop
altogether is an optimisation they deliberately choose not to implement.
Second, as far as I can tell, the second version runs slower because you
need to dereference a pointer 5 billion times.

The expression:
a[2] = 3;
is analogous to:
*(a+2) = 3;

That appears to be the case at the source level, but if you think about it
a[2] just represents an int object in memory in much the same way as the
variable name c does. It is entirely possible for the code generated to
access them (i.e. using a constant index like this) to be identical. Or to
put it another way consider

int a;

*&a = 1;

which is very similar to what you are doing with

int a[1];

a[0] = 1;

The use of an array name in a context like this creates an address, so
loosely speaking there is an implicit & in a[0] as well as an implicit *.
However you look at it this is something that a compiler is likely to
generate reasonable code for.
Lawrence

Jul 23 '05 #25

CBFalconer

Sethalicious wrote:

Think again.

int has a range from - 2^31 to (2^31-1)

Whoops. Totally forgot about 2's complement. :-o I stand corrected!

Think again. int is only guaranteed -2^15-1 .. 2^15-1. The above
range (-1 at the positive end) is only guaranteed for long int.

--
"If you want to post a followup via groups.google.com, don't use
the broken "Reply" link at the bottom of the article. Click on
"show options" at the top of the article, then click on the
"Reply" at the bottom of the article headers." - Keith Thompson

Jul 23 '05 #26

aaronfude

da********@warpmail.net wrote:

My feeling is that when you try to implement 'getNode', you will find
that an array-based implemenation is faster than a switch statement.
OTOH, you might find that templatizing 'getNode' on i, and then
specializing for values of i is faster yet. Presumably, there is some
more generic part of your application that makes 'getNodeA',
'getNodeB', etc., prohibitive. /david

This is more of an optimization question. Can't the compiler somehow
unwrap and inline the following:

int getNode(int i) {
switch (i) {
case 0: return a;
case 1: return b;
case 3: return c;
//...
}
}

Jul 23 '05 #27

E. Robert Tisdale

aa*******@gmail.com wrote:

This is more of an optimization question.
Can't the compiler somehow unwrap and inline the following:
inline int getNode(int i) {
switch (i) {
case 0: return a;
case 1: return b;
case 3: return c;
//...
}
}

Jul 23 '05 #28

shez

Gianni Mariani wrote:

My feeling is that when you try to implement 'getNode', you will find that the array-based implementation is faster than a switch
statement.
That's true. A pointer to member might be an alternative.

Not really. A decent optimising compiler will implement your switch
statement using a static table. Just do whatever looks best for you
(i.e., most readable).

-shez-

Jul 23 '05 #29

shez wrote:

Gianni Mariani wrote:
My feeling is that when you try to implement 'getNode', you will find that the array-based implementation is faster than a switch

statement.

That's true. A pointer to member might be an alternative.

Not really. A decent optimising compiler will implement your switch
statement using a static table. Just do whatever looks best for you
(i.e., most readable).

-shez-

Meaning that switch and array-based implementations might produce the
same object code? /david

Jul 23 '05 #30

shez

da********@warpmail.net wrote:

Meaning that switch and array-based implementations might produce the
same object code? /david

yes.

Jul 23 '05 #31

Jerry Coffin

da********@warpmail.net wrote:

[ ... ]

You might be able to squeeze out some more performance though with a
variable-based implementation if you templatize 'getNode' on i, and
specialize for values of i.

This might work, but it might easily be considerably slower --
specializing like this will produce a separate piece of code to be
executed for each item that's retrieved. That's not very likely to work
well with the cache, and it won't take very many cache misses for the
net effect on speed to be negative.

--
Later,
Jerry.

The universe is a figment of its own imagination.

Jul 23 '05 #32

Well, it would of course be inlined...

Jul 23 '05 #33

Well, it would of course be inlined...

Jul 23 '05 #34

<da********@warpmail.net> wrote in message
news:11*********************@c13g2000cwb.googlegro ups.com...

Well, it would of course be inlined...

The inlining is the potential problem. You have different code for each
specialized call, so there's more code being executed in total and therefore
greater probability of a cache miss.

DW

Jul 23 '05 #35

This is interesting. I guess you are claiming that loading an array
address, computing the offset of an element, and dereferencing is
potentially cheaper than loading each individual variable since the
array address is more likely to stay in the cache than any one of the
variable values? Why would it be the case that any array element value
is more likely to be cached than a variable value? But if you are
correct, this suggests that having individual 'getNodeA', 'getNodeB',
etc., functions is not a good choice for at least this reason. /david

Jul 23 '05 #36

Jerry Coffin

davidru...@warpmail.net wrote:

This is interesting. I guess you are claiming that loading an array
address, computing the offset of an element, and dereferencing is
potentially cheaper than loading each individual variable since the
array address is more likely to stay in the cache than any one of the
variable values?

What I, at least, was suggesting, was that one piece of code to compute
the effective address, is typically a lot smaller than a million
individual pieces of code, each with a single hard-coded address.

IOW, the concern is with caching the instructions, not the data.

--
Later,
Jerry.

The universe is a figment of its own imagination.

Jul 23 '05 #37