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;
}
Apr 7 '08
48  2138 
In article <fe************ *************** *******@q1g2000 prf.googlegroup s.com>,
<is*********@gm ail.comwrote:
>Setting the "-O2 -funroll-loops" flags, I compiled my program
again . Using the optimization flags made my program 1 sec faster.
The program compiled without these optimization flags took 72 secs to
run. I used MinGW to compile my program.
Can changing the function to macro definition make things faster? I
know that calling a function itself but without executing its body
takes tiny time. Suppose it would take 10e-5 secs per call. Calling
it 1,000,000 would take 10 secs.
Elsewhere you said that there are a million calls, and that the number
of elements is less than 5,000. 72 seconds sound like a long time for
that - about 10 billion floating point operations - on a modern
computer. I used the program below to test it on my Mac (which uses
gcc). It takes about 23 seconds wth no optimisation, and about 5.7
seconds with -O or -O2; -funroll-loops doesn't make much difference.
If you're using a current machine, I would reconsider your conclusion
that it's the floating point calculation loop that is taking all the
time.
#include <stdio.h>
#include <stdlib.h>
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;
}
int main(int argc, char **argv)
{
int size = atoi(argv[1]);
int rep = atoi(argv[2]);
double *a = malloc(size * sizeof(*a));
double *b = malloc(size * sizeof(*b));
int i;
double res;
for(i=0; i<size; i++)
{
a[i] = random();
b[i] = random();
}
for(i=0; i<rep; i++)
res += foo(a, b, size);
printf("res=%g\ n", res);
return 0;
}
-- Richard
--
:wq is*********@gma il.com wrote:
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.
[...]
Then a[] and b[] should probably be arrays of unsigned char,
encoding the a's and b's as four and five times their nominal
values, respectively. You compute the sum of products as before
(but using an integer sum), and then divide the total by 20.0
before returning it. This might produce speed gains on two
fronts: first, integer multiplications and additions are faster
than F-P operations on many machines, and second, fetching one-
eighth (probably) as much data from memory will save time on
many machines.
Still, I think your first step should be to turn up the
optimization level on your compiler; it seems you've been using
no optimization at all. If that's not enough (or maybe even
if it *is* enough), try some of the higher-level algorithmic
suggestions various people have mentioned: arrange to call
foo() less often, or on shorter vectors, or both.
-- Er*********@sun .com
On Apr 8, 10:42 am, rich...@cogsci. ed.ac.uk (Richard Tobin) wrote:
In article <fe039dce-a422-4dff-9bed-d070e59dc...@q1 g2000prf.google groups.com>,
<istillsh...@gm ail.comwrote:
Setting the "-O2 -funroll-loops" flags, I compiled my program
again . Using the optimization flags made my program 1 sec faster.
The program compiled without these optimization flags took 72 secs to
run. I used MinGW to compile my program.
Can changing the function to macro definition make things faster? I
know that calling a function itself but without executing its body
takes tiny time. Suppose it would take 10e-5 secs per call. Calling
it 1,000,000 would take 10 secs.
Elsewhere you said that there are a million calls, and that the number
of elements is less than 5,000. 72 seconds sound like a long time for
that - about 10 billion floating point operations - on a modern
computer. I used the program below to test it on my Mac (which uses
gcc). It takes about 23 seconds wth no optimisation, and about 5.7
seconds with -O or -O2; -funroll-loops doesn't make much difference.
If you're using a current machine, I would reconsider your conclusion
that it's the floating point calculation loop that is taking all the
time.
#include <stdio.h>
#include <stdlib.h>
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;
}
int main(int argc, char **argv)
{
int size = atoi(argv[1]);
int rep = atoi(argv[2]);
double *a = malloc(size * sizeof(*a));
double *b = malloc(size * sizeof(*b));
int i;
double res;
for(i=0; i<size; i++)
{
a[i] = random();
b[i] = random();
}
for(i=0; i<rep; i++)
res += foo(a, b, size);
printf("res=%g\ n", res);
return 0;
}
-- Richard
--
:wq
Thanks. The foo I posted previously was a simplified version of my
real foo. The real foo function, which
is computes a function's value and its first derivative given x, is
below. The foo function is defined as
\sum_{i=0}^{sz-1} [ log(exp0*f0[i]+exp1*f1[i]+exp2*f2[i]) -
log(exp0*g0[i]+exp1*g1[i]+exp2*g2[i]) ].
typdef struct vector_t {
double *data;
unsigned long *size;
} Vector;
/*
* Computes function value and its first derivative.
* x and df both have size 2.
*/
#define exp0 2.71828
static double foo(Vector *x, Vector *df, double *fip0, double *fip1,
double *fip2,
double *firp0, double *firp1, double *firp2, unsigned long sz)
{
unsigned long i;
register double sum;
register double x0, x1, x2, y0, y1, y2;
register double z1, z2;
register double exp1, exp2;
fip0 = para->prob0;
fip1 = para->prob1;
fip2 = para->prob2;
firp0 = para->prob3;
firp1 = para->prob4;
firp2 = para->prob5;
sum = 0.0;
df->data[0] = 0.0;
df->data[1] = 0.0;
exp1 = exp(x->data[0]);
exp2 = exp(x->data[1]);
for (i = 0; i < sz; i++) {
x0 = exp0*firp0[i];
x1 = exp1*firp1[i];
x2 = exp2*firp2[i];
z1 = x0 + x1 + x2;
y0 = exp0*fip0[i];
y1 = exp1*fip1[i];
y2 = exp2*fip2[i];
z2 = y0 + y1 + y2;
sum += log(z1) - log(z2);
df->data[0] += x1/z1 - y1/z2;
df->data[1] += x2/z1 - y2/z2;
}
return sum;
}
I tried Paul Hsieh's idea. But I got almost the same running time. is*********@gma il.com wrote:
) Thanks. The foo I posted previously was a simplified version of my
) real foo. The real foo function, which
) is computes a function's value and its first derivative given x, is
) below. The foo function is defined as
Ah, so you're asking how to optimize one function, when in fact
the function you want optimized is a *very different* one ?
Jeez.
SaSW, Willem
--
Disclaimer: I am in no way responsible for any of the statements
made in the above text. For all I know I might be
drugged or something..
No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT
On Apr 8, 11:04 am, Eric Sosman <Eric.Sos...@su n.comwrote:
istillsh...@gma il.com wrote:
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.
[...]
Then a[] and b[] should probably be arrays of unsigned char,
encoding the a's and b's as four and five times their nominal
values, respectively. You compute the sum of products as before
(but using an integer sum), and then divide the total by 20.0
before returning it. This might produce speed gains on two
fronts: first, integer multiplications and additions are faster
than F-P operations on many machines, and second, fetching one-
eighth (probably) as much data from memory will save time on
many machines.
Still, I think your first step should be to turn up the
optimization level on your compiler; it seems you've been using
no optimization at all. If that's not enough (or maybe even
if it *is* enough), try some of the higher-level algorithmic
suggestions various people have mentioned: arrange to call
foo() less often, or on shorter vectors, or both.
--
Eric.Sos...@sun .com
Thanks. The foo I posted previously was a simplified version of my
real foo. The real foo function, which computes a function's value
and its first derivative, given x, is shown below. The foo function
is defined as
\sum_{i=0}^{sz-1} [ log(exp0*f0[i]+exp1*f1[i]+exp2*f2[i]) -
log(exp0*g0[i]+exp1*g1[i]+exp2*g2[i]) ].
I tried Paul Hsieh's idea. But I got almost the same running time.
-----------------------------------------------------------------------
typdef struct vector_t {
double *data;
unsigned long *size;
} Vector;
/*
* Computes function value and its first derivative.
* x and df both have size 2.
*/
#define exp0 2.71828
static double foo(Vector *x, Vector *df,
double *f0, double *f1, double *f2,
double *g0, double *g1, double *g2,
unsigned long sz)
{
unsigned long i;
register double sum;
register double x0, x1, x2, y0, y1, y2;
register double z1, z2;
register double exp1, exp2;
f0 = para->prob0;
f1 = para->prob1;
f2 = para->prob2;
g0 = para->prob3;
g1 = para->prob4;
g2 = para->prob5;
sum = 0.0;
df->data[0] = 0.0;
df->data[1] = 0.0;
exp1 = exp(x->data[0]);
exp2 = exp(x->data[1]);
for (i = 0; i < sz; i++) {
x0 = exp0*g0[i];
x1 = exp1*g1[i];
x2 = exp2*g2[i];
z1 = x0 + x1 + x2;
y0 = exp0*f0[i];
y1 = exp1*f1[i];
y2 = exp2*f2[i];
z2 = y0 + y1 + y2;
sum += log(z1) - log(z2);
df->data[0] += x1/z1 - y1/z2;
df->data[1] += x2/z1 - y2/z2;
}
return sum;
}
On Apr 8, 11:51 am, Willem <wil...@stack.n lwrote:
istillsh...@gma il.com wrote:
) Thanks. The foo I posted previously was a simplified version of my
) real foo. The real foo function, which
) is computes a function's value and its first derivative given x, is
) below. The foo function is defined as
Ah, so you're asking how to optimize one function, when in fact
the function you want optimized is a *very different* one ?
Jeez.
SaSW, Willem
--
Disclaimer: I am in no way responsible for any of the statements
made in the above text. For all I know I might be
drugged or something..
No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT
I thought the general problem was the same. I did not want to mess
with too many details.
On Apr 8, 10:42 am, rich...@cogsci. ed.ac.uk (Richard Tobin) wrote:
In article <fe039dce-a422-4dff-9bed-d070e59dc...@q1 g2000prf.google groups.com>,
<istillsh...@gm ail.comwrote:
Setting the "-O2 -funroll-loops" flags, I compiled my program
again . Using the optimization flags made my program 1 sec faster.
The program compiled without these optimization flags took 72 secs to
run. I used MinGW to compile my program.
Can changing the function to macro definition make things faster? I
know that calling a function itself but without executing its body
takes tiny time. Suppose it would take 10e-5 secs per call. Calling
it 1,000,000 would take 10 secs.
Elsewhere you said that there are a million calls, and that the number
of elements is less than 5,000. 72 seconds sound like a long time for
that - about 10 billion floating point operations - on a modern
computer. I used the program below to test it on my Mac (which uses
gcc). It takes about 23 seconds wth no optimisation, and about 5.7
seconds with -O or -O2; -funroll-loops doesn't make much difference.
If you're using a current machine, I would reconsider your conclusion
that it's the floating point calculation loop that is taking all the
time.
#include <stdio.h>
#include <stdlib.h>
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;
}
int main(int argc, char **argv)
{
int size = atoi(argv[1]);
int rep = atoi(argv[2]);
double *a = malloc(size * sizeof(*a));
double *b = malloc(size * sizeof(*b));
int i;
double res;
for(i=0; i<size; i++)
{
a[i] = random();
b[i] = random();
}
for(i=0; i<rep; i++)
res += foo(a, b, size);
printf("res=%g\ n", res);
return 0;
}
-- Richard
--
:wq
Thanks. The foo I posted previously was a simplified version of my
real foo. The real foo function, which computes a function's value
and its first derivative, given x, is shown below. The foo function
is defined as
\sum_{i=0}^{sz-1} [ log(exp0*f0[i]+exp1*f1[i]+exp2*f2[i]) -
log(exp0*g0[i]+exp1*g1[i]+exp2*g2[i]) ].
I tried Paul Hsieh's idea. But I got almost the same running time.
-----------------------------------------------------------------------
typdef struct vector_t {
double *data;
unsigned long *size;
} Vector;
/*
* Computes function value and its first derivative.
* x and df both have size 2.
*/
#define exp0 2.71828
static double foo(Vector *x, Vector *df,
double *f0, double *f1, double *f2,
double *g0, double *g1, double *g2,
unsigned long sz)
{
unsigned long i;
register double sum;
register double x0, x1, x2, y0, y1, y2;
register double z1, z2;
register double exp1, exp2;
sum = 0.0;
df->data[0] = 0.0;
df->data[1] = 0.0;
exp1 = exp(x->data[0]);
exp2 = exp(x->data[1]);
for (i = 0; i < sz; i++) {
x0 = exp0*g0[i];
x1 = exp1*g1[i];
x2 = exp2*g2[i];
z1 = x0 + x1 + x2;
y0 = exp0*f0[i];
y1 = exp1*f1[i];
y2 = exp2*f2[i];
z2 = y0 + y1 + y2;
sum += log(z1) - log(z2);
df->data[0] += x1/z1 - y1/z2;
df->data[1] += x2/z1 - y2/z2;
}
return sum;
}
In article <1207667017.624 058@news1nwk>,
Eric Sosman <Er*********@su n.comwrote:
>This might produce speed gains on two
fronts: first, integer multiplications and additions are faster
than F-P operations on many machines,
With exceptions. The MIPS R8000/R10000/R12000 floating point
operations were, if I recall correctly, faster than the
integer operations -- most noticably so for the R8000.
--
"History is a pile of debris" -- Laurie Anderson
On Apr 8, 10:42 am, rich...@cogsci. ed.ac.uk (Richard Tobin) wrote:
In article <fe039dce-a422-4dff-9bed-d070e59dc...@q1 g2000prf.google groups.com>,
<istillsh...@gm ail.comwrote:
Setting the "-O2 -funroll-loops" flags, I compiled my program
again . Using the optimization flags made my program 1 sec faster.
The program compiled without these optimization flags took 72 secs to
run. I used MinGW to compile my program.
Can changing the function to macro definition make things faster? I
know that calling a function itself but without executing its body
takes tiny time. Suppose it would take 10e-5 secs per call. Calling
it 1,000,000 would take 10 secs.
Elsewhere you said that there are a million calls, and that the number
of elements is less than 5,000. 72 seconds sound like a long time for
that - about 10 billion floating point operations - on a modern
computer. I used the program below to test it on my Mac (which uses
gcc). It takes about 23 seconds wth no optimisation, and about 5.7
seconds with -O or -O2; -funroll-loops doesn't make much difference.
If you're using a current machine, I would reconsider your conclusion
that it's the floating point calculation loop that is taking all the
time.
#include <stdio.h>
#include <stdlib.h>
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;
}
int main(int argc, char **argv)
{
int size = atoi(argv[1]);
int rep = atoi(argv[2]);
double *a = malloc(size * sizeof(*a));
double *b = malloc(size * sizeof(*b));
int i;
double res;
for(i=0; i<size; i++)
{
a[i] = random();
b[i] = random();
}
for(i=0; i<rep; i++)
res += foo(a, b, size);
printf("res=%g\ n", res);
return 0;
}
-- Richard
--
:wq
Thanks. The foo I posted previously was a simplified version of my
real foo. The real foo function, which computes a function's value
and its first derivative, given x, is shown below. The foo function
is defined as
\sum_{i=0}^{sz-1} [ log(exp0*f0[i]+exp1*f1[i]+exp2*f2[i]) -
log(exp0*g0[i]+exp1*g1[i]+exp2*g2[i]) ].
I tried Paul Hsieh's idea. But I got almost the same running time.
-----------------------------------------------------------------------
typdef struct vector_t {
double *data;
unsigned long size;
} Vector;
/*
* Computes function value and its first derivative.
* x and df both have size 2.
*/
#define exp0 2.71828
static double foo(Vector *x, Vector *df,
double *f0, double *f1, double *f2,
double *g0, double *g1, double *g2,
unsigned long sz)
{
unsigned long i;
register double sum;
register double x0, x1, x2, y0, y1, y2;
register double z1, z2;
register double exp1, exp2;
sum = 0.0;
df->data[0] = 0.0;
df->data[1] = 0.0;
exp1 = exp(x->data[0]);
exp2 = exp(x->data[1]);
for (i = 0; i < sz; i++) {
x0 = exp0*g0[i];
x1 = exp1*g1[i];
x2 = exp2*g2[i];
z1 = x0 + x1 + x2;
y0 = exp0*f0[i];
y1 = exp1*f1[i];
y2 = exp2*f2[i];
z2 = y0 + y1 + y2;
sum += log(z1) - log(z2);
df->data[0] += x1/z1 - y1/z2;
df->data[1] += x2/z1 - y2/z2;
}
return sum;
} This thread has been closed and replies have been disabled. Please start a new discussion. Similar topics | |
by: Kamilche |
last post by:
I have a routine that I really need, but it slows down processing
significantly. Can you spot any ineffeciencies in the code?
This code makes a critical function of mine run about 7x slower than
using a prebuilt format string. For maximum flexibility, it would be
best to calculate the format string using this method, so I'd dearly
love to keep it.
def fmtstring(args):
delim = '\0'
|
by: Brent Patroch |
last post by:
Hello,
Novice here, I am doing bulk emails using CDO, connection to a smtp
server at another location. I am trying to streamline my script, or
through it out and start over to make it faster.
I know that I am doing something wrong and that messages should be
sending much faster. Any help appreciated:
Set objConfig = Server.CreateObject("CDO.Configuration")
|
by: ajikoe |
last post by:
def f(x,y):
return math.sin(x*y) + 8 * x
I have code like this:
def main():
n = 2000
a = zeros((n,n), Float)
xcoor = arange(0,1,1/float(n))
ycoor = arange(0,1,1/float(n))
|
by: pkilambi |
last post by:
I wrote this function which does the following:
after readling lines from file.It splits and finds the word occurences
through a hash table...for some reason this is quite slow..can some one
help me make it faster...
f = open(filename)
lines = f.readlines()
def create_words(lines):
cnt = 0
spl_set = '+'
for content in lines:
|
by: Scott Emick |
last post by:
I am using the following to compute distances between two lat/long
coordinates for a store locator - (VB .NET 2003)
it seems to take a long time to iterate through like 100-150 locations -
about 10-15 seconds...I want to make the code faster. I changed it to be
multi-threaded, and it doesn't really make it any faster. The bottleneck
seems to be with the math computations.
Any ideas like changing my data types or other ideas etc would...
| | |
by: Extremest |
last post by:
I know there are ways to make this a lot faster. Any
newsreader does this in seconds. I don't know how they do
it and I am very new to c#. If anyone knows a faster way
please let me know. All I am doing is quering the db for
all the headers for a certain group and then going through
them to find all the parts of each post. I only want ones
that are complete. Meaning all segments for that one file
posted are there.
using System;
|
by: vunet.us |
last post by:
Is there a suggestion I can make this code run faster:
if(document.getElementById("1")){ doOne(); }
if(document.getElementById("2")){ doTwo(); }
....................
if(document.getElementById("n")){ doN(); }
It is a simplified version above. There is a large number of these
repetitive actions. So I wanted to change them for:
|
by: Simply_Red |
last post by:
Hi,
is there a way to make this function faster???
struct Points {
double X;
double Y;
};
|
by: Steve Bergman |
last post by:
I'm involved in a discussion thread in which it has been stated that:
"""
Anything written in a language that is 20x slower (Perl, Python,
PHP) than C/C++ should be instantly rejected by users on those grounds
alone.
"""
I've challenged someone to beat the snippet of code below in C, C++,
or assembler, for reading in one million pairs of random floats and
|
by: Hystou |
last post by:
Most computers default to English, but sometimes we require a different language, especially when relocating. Forgot to request a specific language before your computer shipped? No problem! You can effortlessly switch the default language on Windows 10 without reinstalling. I'll walk you through it.
First, let's disable language synchronization. With a Microsoft account, language settings sync across devices. To prevent any complications,...
|
by: Oralloy |
last post by:
Hello folks,
I am unable to find appropriate documentation on the type promotion of bit-fields when using the generalised comparison operator "<=>".
The problem is that using the GNU compilers, it seems that the internal comparison operator "<=>" tries to promote arguments from unsigned to signed.
This is as boiled down as I can make it.
Here is my compilation command:
g++-12 -std=c++20 -Wnarrowing bit_field.cpp
Here is the code in...
| | |
by: Hystou |
last post by:
Overview:
Windows 11 and 10 have less user interface control over operating system update behaviour than previous versions of Windows. In Windows 11 and 10, there is no way to turn off the Windows Update option using the Control Panel or Settings app; it automatically checks for updates and installs any it finds, whether you like it or not. For most users, this new feature is actually very convenient. If you want to control the update process,...
|
by: isladogs |
last post by:
The next Access Europe User Group meeting will be on Wednesday 1 May 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM).
In this session, we are pleased to welcome a new presenter, Adolph Dupré who will be discussing some powerful techniques for using class modules.
He will explain when you may want to use classes instead of User Defined Types (UDT). For example, to manage the data in unbound forms.
Adolph will...
|
by: conductexam |
last post by:
I have .net C# application in which I am extracting data from word file and save it in database particularly. To store word all data as it is I am converting the whole word file firstly in HTML and then checking html paragraph one by one.
At the time of converting from word file to html my equations which are in the word document file was convert into image.
Globals.ThisAddIn.Application.ActiveDocument.Select();...
|
by: TSSRALBI |
last post by:
Hello
I'm a network technician in training and I need your help.
I am currently learning how to create and manage the different types of VPNs and I have a question about LAN-to-LAN VPNs.
The last exercise I practiced was to create a LAN-to-LAN VPN between two Pfsense firewalls, by using IPSEC protocols.
I succeeded, with both firewalls in the same network. But I'm wondering if it's possible to do the same thing, with 2 Pfsense firewalls...
|
by: adsilva |
last post by:
A Windows Forms form does not have the event Unload, like VB6. What one acts like?
|
by: 6302768590 |
last post by:
Hai team
i want code for transfer the data from one system to another through IP address by using C# our system has to for every 5mins then we have to update the data what the data is updated we have to send another system
| | |
by: bsmnconsultancy |
last post by:
In today's digital era, a well-designed website is crucial for businesses looking to succeed. Whether you're a small business owner or a large corporation in Toronto, having a strong online presence can significantly impact your brand's success. BSMN Consultancy, a leader in Website Development in Toronto offers valuable insights into creating effective websites that not only look great but also perform exceptionally well. In this comprehensive...
| |
