How to make it faster?

[istillshine]

When I used gprof to see which function consumed most running time, I
identified the following one. sz was less than 5000 on average, but
foo had been called about 1,000,000 times. I have tried using
"register sum = 0.0" and saw some improvement. My question is how to
improve foo further to make it faster.

double foo(double *a, double *b, int sz)
{

double sum = 0.0;
int i;

for (i = 0; i < sz; i++)
sum += a[i]*b[i];

return sum;
}

[istillshine]

istillsh...@gma il.com wrote:

When I used gprof to see which function consumed most running time, I
identified the following one. sz was less than 5000 on average, but
foo had been called about 1,000,000 times. I have tried using
"register sum = 0.0" and saw some improvement. My question is how to
improve foo further to make it faster.

double foo(double *a, double *b, int sz)
{

double sum = 0.0;
int i;

for (i = 0; i < sz; i++)
sum += a[i]*b[i];

return sum;
}

Twice faster would help a lot.

[Malcolm McLean]

<is*********@gm ail.comwrote in message

double foo(double *a, double *b, int sz)
{

double sum = 0.0;
int i;

for (i = 0; i < sz; i++)
sum += a[i]*b[i];

return sum;
}

Make a and b float arrays, and sum a float too. On some architectures that
will give about a 2 * speedup. Of course you'll have to use single precision
throughout the program.
The code is so simple that there is unlikely to be any sort of other
micro-optimisiation you can do. However it may be possible to call foo()
less often by rearranging the algorithm.

--
Free games and programming goodies.
http://www.personal.leeds.ac.uk/~bgy1mm

[Bartc]

<is*********@gm ail.comwrote in message
news:6d******** *************** ***********@k10 g2000prm.google groups.com...

>

istillsh...@gma il.com wrote:

>When I used gprof to see which function consumed most running time, I
identified the following one. sz was less than 5000 on average, but
foo had been called about 1,000,000 times. I have tried using
"register sum = 0.0" and saw some improvement. My question is how to
improve foo further to make it faster.

double foo(double *a, double *b, int sz)
{

double sum = 0.0;
int i;

for (i = 0; i < sz; i++)
sum += a[i]*b[i];

return sum;
}

Twice faster would help a lot.

Suggestions have already been made for improving the loop.

Reducing the calls from 1000000 will help a lot more, for that the overall
strategy needs to be looked at.

Then there's the data: does sz need to be that high? Is there anything
special about the a and b data (like mostly zeros or ones)?

How accurate does the sum have to be? If a,b change slowly, perhaps sum only
every other pair (then double the result)?

Have you thought about using integers (fixed point)? This might need a
global change.

--
Bart

[Eric Sosman]

is*********@gma il.com wrote:

When I used gprof to see which function consumed most running time, I
identified the following one. sz was less than 5000 on average, but
foo had been called about 1,000,000 times. I have tried using
"register sum = 0.0" and saw some improvement. My question is how to
improve foo further to make it faster.

double foo(double *a, double *b, int sz)
{

double sum = 0.0;
int i;

for (i = 0; i < sz; i++)
sum += a[i]*b[i];

return sum;
}

With very old compilers you might get some improvement
by "unrolling" the loop, but most compilers have been able
to do that on their own for the past couple decades. As
Willem suggests, examine the generated code to see whether
the loop is unrolled already -- if it isn't, do so manually,
but it probably will have been.

Similarly, you could try rearrangements like

double foo(double *a, double *b, int sz) {
double sum = 0.0;
while (--sz >= 0)
sum += *a++ * *b++;
return sum;
}

.... but compilers have been doing *that* for even longer
than they've been unrolling loops. Adding `register' to
the declarations of a,b,sz and possibly sum might help,
but again: today's compilers are unlikely to overlook that
sort of optimization.

The big payoff -- or potential payoff, because it might
not be feasible -- would come not from making foo() faster,
but from calling it less often. You mention a million
calls to compute dot-products of 5000-place vectors; are
all those ten billion numbers really independent? If one
pair is very similar to the next except perhaps for a small
number of elements, maybe you could just make adjustments
to the original dot-product instead of recomputing the whole
thing from scratch:

double dot = foo(a, b, sz);
/* Make a change in the k'th place: */
dot -= a[k] * b[k];
a[k] = newa;
b[k] = newb;
dot += a[k] * b[k];

If you do this a million times you'll need to worry about
the propagation of small errors; consider using something
like Kahan's summation formula (GIYF) for the adjustments.
(You might also use Kahan's formula for the original sum;
it's slower, but that might not be an issue if you can get
a substantial reduction in foo() calls.)

Or maybe there are many changes to a[] and b[] between
foo() calls, but they tend to be clustered. In that case
you might decompose both arrays into 100 or so segments,
calculate the sum of each, make the changes, and then
recalculate only the segments that changed. Taken to the
extreme, this suggests turning the paired vectors into
trees, with the a[i],b[i] at the leaves, the pairwise sums
one level up, the four-way sums a level higher still, and
so on until the grand total is at the root: Changing the
k'th pair of numbers would then need only about thirteen
additions for a 5000-element pair. (You could do the
same thing with higher-degree trees, too.)

Whatever the situation, I think it unlikely you'll get
a twofold speedup by tweaking foo() itself; stepping back
and looking at the wider problem may have more promise.

--
Er*********@sun .com

[Fei Liu]

is*********@gma il.com wrote:

When I used gprof to see which function consumed most running time, I
identified the following one. sz was less than 5000 on average, but
foo had been called about 1,000,000 times. I have tried using
"register sum = 0.0" and saw some improvement. My question is how to
improve foo further to make it faster.

double foo(double *a, double *b, int sz)
{

double sum = 0.0;
int i;

for (i = 0; i < sz; i++)
sum += a[i]*b[i];

return sum;
}

Nobody has mentioned "loop unrolling"? Intel compilers also support
embedded prefetch directives if your target platform is Intel based.

Fei

[Walter Roberson]

In article <47************ @gmail.com>, Fei Liu <fe*****@gmail. comwrote:

>Nobody has mentioned "loop unrolling"?

Eric, Willem, and I all mentioned loop unrolling, with Eric and I
mentioning it directly under that name and Willem mentioning the
technique without giving it that name.
--
"Eightly percent of the people in the world are fools and the
rest of us are in danger of contamination." -- Walter Matthau

[istillshine]

On Apr 7, 1:39 pm, istillsh...@gma il.com wrote:

When I used gprof to see which function consumed most running time, I
identified the following one. sz was less than 5000 on average, but
foo had been called about 1,000,000 times. I have tried using
"register sum = 0.0" and saw some improvement. My question is how to
improve foo further to make it faster.

double foo(double *a, double *b, int sz)
{

double sum = 0.0;
int i;

for (i = 0; i < sz; i++)
sum += a[i]*b[i];

return sum;

}

Suppose in my application I know that a[i]*b[i] can only take a
limited set of values. For examples, a[i] can only be 0, 0.25, 0.5,
or 0.75; b[i] can only be 0, 0.2, 0.4, 0.6, or 0.8.
I thought I could pre-compute their products and fetch them given
certain a[i] and b[i]. For example,

if (a[i] == 0.25 && b[i] == 0.2)
sum += 0.05;
else if (a[i] == 0.25 && b[i] == 0.4)
sum += 0.1;
....

But this solution made running time longer. I speculated that
conditional statements were more expensive than multiplication.

Do you have any better solution?

[istillshine]

On Apr 7, 1:39 pm, istillsh...@gma il.com wrote:

When I used gprof to see which function consumed most running time, I
identified the following one. sz was less than 5000 on average, but
foo had been called about 1,000,000 times. I have tried using
"register sum = 0.0" and saw some improvement. My question is how to
improve foo further to make it faster.

double foo(double *a, double *b, int sz)
{

double sum = 0.0;
int i;

for (i = 0; i < sz; i++)
sum += a[i]*b[i];

return sum;

}

Suppose in my application I know that a[i]*b[i] can only take a
limited set of values. For example, a[i] can only be 0, 0.25, 0.5, or
0.75; b[i] can only be 0, 0.2, 0.4, 0.6, or 0.8.
I thought I could pre-compute their products and fetch them given
certain a[i] and b[i]. For example,

if (a[i] == 0.25 && b[i] == 0.2)
sum += 0.05;
else if (a[i] == 0.25 && b[i] == 0.4)
sum += 0.1;
....

But the above solution made the running time considerably longer. I
speculated that conditional statements were more expensive than
multiplication.

Are better solutions possible?

[Richard Tobin]

In article <89************ *************** *******@k1g2000 prb.googlegroup s.com>,
<is*********@gm ail.comwrote:

>Suppose in my application I know that a[i]*b[i] can only take a
limited set of values. For example, a[i] can only be 0, 0.25, 0.5, or
0.75; b[i] can only be 0, 0.2, 0.4, 0.6, or 0.8.
I thought I could pre-compute their products and fetch them given
certain a[i] and b[i]. For example,

if (a[i] == 0.25 && b[i] == 0.2)
sum += 0.05;
else if (a[i] == 0.25 && b[i] == 0.4)
sum += 0.1;
...

But the above solution made the running time considerably longer. I
speculated that conditional statements were more expensive than
multiplication .

Yes, that's quite likely. I would expect a modern compiler to generate
good code for a simple loop of multiplications .

If the values are from some small set, perhaps it would be better not
to store them as floating point numbers. Can you use integers instead
by multiplying by a constant?

Or you could store the values as small integers even if they are not
simple multiples, and have a 2-dimensional array in which you look up
the answers.

Or perhaps you could split your problem into multiple threads.

Of course, if your sequence of multiplications is really so huge that
it is important to speed it up, you should also reconsider your
algorithm.

-- Richard
--
:wq