Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c++ > #14173 > unrolled thread

Writing efficient normal distribution function (for learning purposes).

Back to article view | Back to comp.lang.c++

Contents

  Writing efficient normal distribution function (for learning purposes). Luca Cerone <luca.cerone@gmail.com> - 2012-02-17 07:41 -0800
    Re: Writing efficient normal distribution function (for learning purposes). "Asger Joergensen" <Junk@Asger-P.dk> - 2012-02-17 16:45 +0000
      Re: Writing efficient normal distribution function (for learning purposes). lucacerone <luca.cerone@gmail.com> - 2012-02-17 09:36 -0800
        Re: Writing efficient normal distribution function (for learning purposes). "Asger Joergensen" <Junk@Asger-P.dk> - 2012-02-17 17:50 +0000
          Re: Writing efficient normal distribution function (for learning purposes). lucacerone <luca.cerone@gmail.com> - 2012-02-19 01:59 -0800
            Re: Writing efficient normal distribution function (for learning purposes). lucacerone <luca.cerone@gmail.com> - 2012-02-19 02:49 -0800
              Re: Writing efficient normal distribution function (for learning purposes). "Asger Joergensen" <Junk@Asger-P.dk> - 2012-02-19 11:53 +0000
              Re: Writing efficient normal distribution function (for learning purposes). Miles Bader <miles@gnu.org> - 2012-02-19 23:09 +0900
                Re: Writing efficient normal distribution function (for learning purposes). Joshua Maurice <joshuamaurice@gmail.com> - 2012-02-19 13:34 -0800
                  Re: Writing efficient normal distribution function (for learning purposes). Marc <marc.glisse@gmail.com> - 2012-02-19 22:10 +0000
                    Re: Writing efficient normal distribution function (for learning purposes). Miles Bader <miles@gnu.org> - 2012-02-20 09:14 +0900
                    Re: Writing efficient normal distribution function (for learning purposes). Juha Nieminen <nospam@thanks.invalid> - 2012-02-20 10:24 +0000
                      Re: Writing efficient normal distribution function (for learning purposes). Miles Bader <miles@gnu.org> - 2012-02-20 19:57 +0900
                      Re: Writing efficient normal distribution function (for learning purposes). Dombo <dombo@disposable.invalid> - 2012-02-20 21:07 +0100
                        Re: Writing efficient normal distribution function (for learning purposes). Juha Nieminen <nospam@thanks.invalid> - 2012-02-21 08:41 +0000
                          Re: Writing efficient normal distribution function (for learning purposes). 88888 Dihedral <dihedral88888@googlemail.com> - 2012-02-21 01:10 -0800
                  Re: Writing efficient normal distribution function (for learning purposes). Miles Bader <miles@gnu.org> - 2012-02-20 09:04 +0900
                Re: Writing efficient normal distribution function (for learning purposes). lucacerone <luca.cerone@gmail.com> - 2012-02-20 02:26 -0800
      Re: Writing efficient normal distribution function (for learning purposes). Juha Nieminen <nospam@thanks.invalid> - 2012-02-17 20:42 +0000
        Re: Writing efficient normal distribution function (for learning purposes). "Asger Joergensen" <Junk@Asger-P.dk> - 2012-02-17 22:20 +0000
    Re: Writing efficient normal distribution function (for learning purposes). Juha Nieminen <nospam@thanks.invalid> - 2012-02-17 20:52 +0000
    Re: Writing efficient normal distribution function (for learning purposes). Victor Bazarov <v.bazarov@comcast.invalid> - 2012-02-17 15:57 -0500
    Re: Writing efficient normal distribution function (for learning purposes). Joshua Maurice <joshuamaurice@gmail.com> - 2012-02-17 15:01 -0800
      Re: Writing efficient normal distribution function (for learning purposes). Victor Bazarov <v.bazarov@comcast.invalid> - 2012-02-18 08:44 -0500
        Re: Writing efficient normal distribution function (for learning purposes). Paavo Helde <myfirstname@osa.pri.ee> - 2012-02-18 09:20 -0600
    Re: Writing efficient normal distribution function (for learning purposes). Paavo Helde <myfirstname@osa.pri.ee> - 2012-02-18 09:36 -0600
      Re: Writing efficient normal distribution function (for learning purposes). glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2012-02-18 20:19 +0000
        Re: Writing efficient normal distribution function (for learning purposes). Miles Bader <miles@gnu.org> - 2012-02-19 10:32 +0900
    Re: Writing efficient normal distribution function (for learning purposes). lucacerone <luca.cerone@gmail.com> - 2012-02-20 02:36 -0800
    Re: Writing efficient normal distribution function (for learning purposes). gwowen <gwowen@gmail.com> - 2012-02-20 06:48 -0800
      Re: Writing efficient normal distribution function (for learning purposes). lucacerone <luca.cerone@gmail.com> - 2012-02-21 04:32 -0800

Page 2 of 2 — ← Prev page 1 [2]

#14195

Luca Cerone <luca.cerone@gmail.com> wrote:
> I'd like to improve my code for speed.

  First of all, are you sure you are compiling with optimizations / in
release mode? A surprisingly common mistake to not to do that.

>  double  val = sqrt(2*M_PI)*csigma;

  A compiler might or might not be able to calculate that "sqrt(2*M_PI)"
at compile time (because compilers oftentimes do not perform floating point
calculations at compile time due to a myriad of reasons; of course it
depends on the compiler and its version). If you want a few clock cycles
off, might be a safer bet to write the value directly.

>  val = val*exp(-pow(px-mu,2)/(2*pow(csigma,2)));    

  Likewise a compiler might or might not be able to optimize a
"pow(x,2)" into "x*x". It may be a safer bet to write it explicitly.
(std::pow is significantly slower than multiplication.)

> vector<double> normdist(const vector<double>& vx,const double& mu,const double& csigma){
>  vector<double> gv(vx.size()) ; //allocates the space for the vector gv.

  How many times is this function called in your program? Are you
measuring its speed by calling this function thousands/millions of
times and seeing how long it takes overall?

  If yes, then there's your major problem. Memory allocation is
(unfortunately) a slow operation in C++ (not really C++'s fault,
but that's another story). You might want to pass the return value
as a reference parameter to the function and have it write there
instead of allocating a new vector each time. Then you can reuse the
same vector object for each call, avoiding the memory allocation
(except for the very first time it's called, of course).

[toc] | [prev] | [next] | [standalone]

#14196

On 2/17/2012 10:41 AM, Luca Cerone wrote:
> Dear all, I'm a beginner in C++ so I'm sorry if my question might seem silly.
> I'm also new to the group so I just say hello to all the people in it.
>
> I've written a function that computes the Normal Distribution, but when comparing the time to create 1000 vectors
> each with 1000 points I've the same performance than using the analogous Matlab built-in function.
> I'd like to improve my code for speed.
> I'm doing this mainly to learn how to write efficient C++ code, so please just don't tell me
> that library X and Y do this faster than my code, but help me understanding why and how to improve
> my code.
>
> I need both a single value and a vector version of this function,
> so this is how I have defined them.
>
> // this is the single point version of the function:
> double normdist(const double&  px,const double&  mu,const double&  csigma){
>    // evaluating the formula taken from http://en.wikipedia.org/wiki/Normal_distribution
>    double  val = sqrt(2*M_PI)*csigma;
>    val = 1/val;
>    val = val*exp(-pow(px-mu,2)/(2*pow(csigma,2)));
>    return val ;

Some compilers are actually good at parsing expressions and converting 
them into efficient machine code.  You could try simply writing

     return exp( -pow(px-mu,2)/2/pow(csigma,2) ) / sqrt(2*M_PI) / csigma;

And now you can see that there are two subexpressions that don't have to 
be calculated on every call.  pow(csigma,2) could be calculated once per 
the entire loop and passed into 'normdist' as a const double&.  The same 
goes for sqrt(2*M_PI), which is just a constant you could define in the 
file scope and just use here.

> }
>
> //this is the vector version. It takes as input a vector of double and gives the vector of corresponding values as output:
>
> vector<double>  normdist(const vector<double>&  vx,const double&  mu,const double&  csigma){
>    vector<double>  gv(vx.size()) ; //allocates the space for the vector gv.
>    for (int i=0 ; i<vx.size() ; i++){

While it might not matter in your particular case, get into the habit of 
not calling any function in your 'for' condition if you know that it's 
not going to change.  I'm yet to see a compiler that knows to eliminate 
it.  Try this:

    for (int i=0, s=vx.size(); i<s; ++i)

>      gv[i]=normdist(vx[i],mu,csigma);
>    }


Most modern compilers are good with indexing, but it's a function call 
for the vector, so you might want to try to eliminate it as well by 
using pointers:

     double* pgv = &gv[0];
     const double* pvx = &vx[0];

     for (...
     {
         *pgv++ = normdist(*pvx++, mu, csigma);
     }

>    return gv ;
> }
>
> As I told I'm a beginner so I guess there is plenty of room for improving the speed and the quality of the code
> (just writing to you I have realized that the initialization of gv might not be optimal, since I create values I don't need).

Good luck!

V
-- 
I do not respond to top-posted replies, please don't ask

[toc] | [prev] | [next] | [standalone]

#14206

On Feb 17, 7:41 am, Luca Cerone <luca.cer...@gmail.com> wrote:
> Dear all, I'm a beginner in C++ so I'm sorry if my question might seem silly.
> I'm also new to the group so I just say hello to all the people in it.
>
> I've written a function that computes the Normal Distribution, but when comparing the time to create 1000 vectors
> each with 1000 points I've the same performance than using the analogous Matlab built-in function.
> I'd like to improve my code for speed.
> I'm doing this mainly to learn how to write efficient C++ code, so please just don't tell me
> that library X and Y do this faster than my code, but help me understanding why and how to improve
> my code.
>
> I need both a single value and a vector version of this function,
> so this is how I have defined them.
>
> // this is the single point version of the function:
> double normdist(const double& px,const double& mu,const double& csigma){
>   // evaluating the formula taken fromhttp://en.wikipedia.org/wiki/Normal_distribution
>   double  val = sqrt(2*M_PI)*csigma;
>   val = 1/val;
>   val = val*exp(-pow(px-mu,2)/(2*pow(csigma,2)));
>   return val ;
>
> }
>
> //this is the vector version. It takes as input a vector of double and gives the vector of corresponding values as output:
>
> vector<double> normdist(const vector<double>& vx,const double& mu,const double& csigma){
>   vector<double> gv(vx.size()) ; //allocates the space for the vector gv.
>   for (int i=0 ; i<vx.size() ; i++){
>     gv[i]=normdist(vx[i],mu,csigma);
>   }
>   return gv ;
>
> }
>
> As I told I'm a beginner so I guess there is plenty of room for improving the speed and the quality of the code
> (just writing to you I have realized that the initialization of gv might not be optimal, since I create values I don't need).
>
> Thank you very much to all of you!
> Luca

Are compiling with all of the proper optimization flags? Are you using
MSVC, and have you disabled checked iterators?

[toc] | [prev] | [next] | [standalone]

#14232

On 2/17/2012 6:01 PM, Joshua Maurice wrote:
> On Feb 17, 7:41 am, Luca Cerone<luca.cer...@gmail.com>  wrote:
>> [..]
>> I've written a function that computes the Normal Distribution, but when comparing the time to create 1000 vectors
>> each with 1000 points I've the same performance than using the analogous Matlab built-in function.
>> [.. code using vector and indexing snipped ..]
>
> Are compiling with all of the proper optimization flags? Are you using
> MSVC, and have you disabled checked iterators?

There seem to be no iterators in that code.

If the code speed is the same as Matlab's, there is probably not much 
hope to significantly improve it.  I doubt that Matlab people release 
their library/application with sub-par performance.

V
-- 
I do not respond to top-posted replies, please don't ask

[toc] | [prev] | [next] | [standalone]

#14233

Victor Bazarov <v.bazarov@comcast.invalid> wrote in
news:jhoa0p$ueu$1@dont-email.me: 

> On 2/17/2012 6:01 PM, Joshua Maurice wrote:
>> On Feb 17, 7:41 am, Luca Cerone<luca.cer...@gmail.com>  wrote:
>>> [..]
>>> I've written a function that computes the Normal Distribution, but
>>> when comparing the time to create 1000 vectors each with 1000 points
>>> I've the same performance than using the analogous Matlab built-in
>>> function. [.. code using vector and indexing snipped ..]
>>
>> Are compiling with all of the proper optimization flags? Are you
>> using MSVC, and have you disabled checked iterators?
> 
> There seem to be no iterators in that code.

MSVC "checked iterators" feature also covers indexing into std::vector, 
which is used in OP-s code. This does not necessarily mean that the 
overhead is significant or even measurable. 

Cheers
Paavo

[toc] | [prev] | [next] | [standalone]

#14235

Luca Cerone <luca.cerone@gmail.com> wrote in
news:5969204.9.1329493277515.JavaMail.geo-discussion-forums@vbnd9: 

> Dear all, I'm a beginner in C++ so I'm sorry if my question might seem
> silly. I'm also new to the group so I just say hello to all the people
> in it. 
> 
> I've written a function that computes the Normal Distribution, but
> when comparing the time to create 1000 vectors each with 1000 points
> I've the same performance than using the analogous Matlab built-in
> function. I'd like to improve my code for speed.
> I'm doing this mainly to learn how to write efficient C++ code, so
> please just don't tell me that library X and Y do this faster than my
> code, but help me understanding why and how to improve my code.
> 
> I need both a single value and a vector version of this function,
> so this is how I have defined them.
> 
> // this is the single point version of the function:
> double normdist(const double& px,const double& mu,const double&
> csigma){ 
>   // evaluating the formula taken from
>   http://en.wikipedia.org/wiki/Normal_distribution double  val =
>   sqrt(2*M_PI)*csigma; val = 1/val; 
>   val = val*exp(-pow(px-mu,2)/(2*pow(csigma,2)));    
>   return val ;
> }
> 
> //this is the vector version. It takes as input a vector of double and
> gives the vector of corresponding values as output: 
> 
> vector<double> normdist(const vector<double>& vx,const double&
> mu,const double& csigma){ 
>   vector<double> gv(vx.size()) ; //allocates the space for the vector
>   gv. for (int i=0 ; i<vx.size() ; i++){
>     gv[i]=normdist(vx[i],mu,csigma);
>   }
>   return gv ;
> }
> 
> As I told I'm a beginner so I guess there is plenty of room for
> improving the speed and the quality of the code (just writing to you I
> have realized that the initialization of gv might not be optimal,
> since I create values I don't need). 


Passing single doubles by reference (e.g. const double& mu) is a 
premature optimization. It is not clear if it makes the code faster or 
slower (a reference may mean introducing an extra pointer variable behind 
the scenes), most probably neither if the compiler is able to inline the 
function, so for simplicity doubles should be passed just by value 
(double mu). 

Returning the whole vector by value may have some negative performance 
impact, depending on compiler and how do you use the result (is it an 
initialization or assignment). Using it for initialization with current 
compiler versions should be OK though. Look up RVO.

pow(x,2) should be replaced by x*x as mentioned by others, it is not 
given that the optimizer is smart enough to do that by itself.

And last, if you think your code could be faster, then the ultimate way 
to actually find out the bottlenecks is to run it under a profiler and 
study the results. Unfortunately, this gives you information only for a 
certain platform, compiler version and compiler settings.

hth
Paavo

[toc] | [prev] | [next] | [standalone]

#14241

Paavo Helde <myfirstname@osa.pri.ee> wrote:

(snip)

> pow(x,2) should be replaced by x*x as mentioned by others, it is not 
> given that the optimizer is smart enough to do that by itself.

I have complained about this before. Fortran compilers have been
known to optimize x**2 for many many years. Being an operator, 
instead of a function, makes it more obvious. 

In addition, there is no pow(double, int) which would help in
optimizing many other cases. 

-- glen

[toc] | [prev] | [next] | [standalone]

#14251

glen herrmannsfeldt <gah@ugcs.caltech.edu> writes:
>> pow(x,2) should be replaced by x*x as mentioned by others, it is not 
>> given that the optimizer is smart enough to do that by itself.
>
> I have complained about this before. Fortran compilers have been
> known to optimize x**2 for many many years. Being an operator, 
> instead of a function, makes it more obvious. 
>
> In addition, there is no pow(double, int) which would help in
> optimizing many other cases. 

All the C++ compilers I've used _do_ optimize "pow(x,2)" to "x*x"...
Not very hard as optimizations go...

-miles

-- 
Saa, shall we dance?  (from a dance-class advertisement)

[toc] | [prev] | [next] | [standalone]

#14317

Thanks to all of you guys, I have had some nice advice from this post!
I do some numerical simulations, but I'm interested in qualitative
rather than quantitative results.
I'd like to know how inaccurate are the results using those math optimization options you were mentioning.

Also, I'd like to know how you would have written those two functions in order to make them faster.
I have restraint to use vectors, nor any specific type. 
I have used vectors because this is what I've read in Stroustrup's book...
I haven't used pointers because I still haven't understood exactly their algebra.
I have passed values by reference to the function because I thought it might be better for memory.

So just to say, I'm trying to learn the various alternative to write function
that are both easy to re-use and fast to evaluate. 
So if you think my version can be entirely rewritten, if you have time can you help me understand how???

Thanks a lot for your help again!!!

P.s. slightly OT, some of you could use some markup in their message..
where can I find a list so that I can use it as well?

[toc] | [prev] | [next] | [standalone]

#14329

On Feb 17, 3:41 pm, Luca Cerone <luca.cer...@gmail.com> wrote:
> Dear all, I'm a beginner in C++ so I'm sorry if my question might seem silly.
> I'm also new to the group so I just say hello to all the people in it.
>
> I've written a function that computes the Normal Distribution, but when comparing the time
> to create 1000 vectors each with 1000 points I've the same performance than using the
> analogous Matlab built-in function.

As an aside, note that what you're calculating is what Matlab calls
normpdf().

It's a reasonable thing to calculate, but unless you're plotting a
curve, its not actually a lot of use.  You're more likely to need to
emulate matlab's randn() [which generates a vector of random values
from a normal distribution] or normcdf() [the cumulative probability
distribution, or "area under the normal curve"].

[toc] | [prev] | [next] | [standalone]

#14368

Hi Gwowen, thanks but I actually want to implement the analogous of normpdf in matlab :)As I said I have no specific tasks to make, just learn how to write efficient cod :)

[toc] | [prev] | [standalone]

Page 2 of 2 — ← Prev page 1 [2]

Back to top | Article view | comp.lang.c++

csiph-web