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 1 of 2  [1] 2  Next page →

#14173 — Writing efficient normal distribution function (for learning purposes).

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).

Thank you very much to all of you!
Luca

[toc] | [next] | [standalone]

#14179

Hi Luca

If You can live with fixed precision You code will run much faster if You use 
int's or __int64's and then multiply /devide as much as You need to get Your the
precision You need.

Best regards
Asger-P

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

#14183

Hi Asger-P, thanks for your reply.
Let me understand if I've understood.. by fixed precision you mean having
number with a fixed number of digits? If so, yes I can live with it
as far as I have 8 exact decimal points.

> If You can live with fixed precision You code will run much faster if You use 
> int's or __int64's and then multiply /devide as much as You need to get Your the
> precision You need.

I'm sorry but I don't understand you. How would you suggest to use ints?
What type is it __int64?

Thanks a lot for you help in any case,
Luca

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

#14185

Hi lucacerone

lucacerone wrote:

> Hi Asger-P, thanks for your reply.
> Let me understand if I've understood.. by fixed precision you mean having
> number with a fixed number of digits? If so, yes I can live with it
> as far as I have 8 exact decimal points.

int64_t val = DoubleVal * 100000000;

do the rest of the work with the int and then You divide by the same number
when You need the result.
 
> > If You can live with fixed precision You code will run much faster if You use 
> > int's or __int64's and then multiply /devide as much as You need to get Your the
> > precision You need.
> 
> I'm sorry but I don't understand you. How would you suggest to use ints?
> What type is it __int64?

64 bit integer my borland compiler like __int64, but I think int64_t is the
cross compiler way to write it.

I'm not into math so I don't know if You can use this method for Your project.

I do a lot of gradient graphics, so when I calculate color steps i use this
method and it is a lot faster then using floating point values like float and 
double.

Best regards
Asger-P

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

#14269

Hi Asger,
this solution is not feasible for me unfortunately because the function I want to approximate is nonlinear. Thanks a lot in any case for the advice.

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

#14271

First of all, thank you all for your advices.
Many issues have been arisen, so I try to answer to them in this post.

For the performance I have evaluated them evaluating vectors made of 1000 points, for one hundred thousand times. So I think it is a reliable measurement.

As for the compiler optimization, I'm using g++ (GNU compiler) on a Ubuntu machine. The way I compile the code is simply:

g++ -c -o mylib.o mylib.cpp
g++ -c -o main.o main.cpp
g++ -o executableneme main.o mylib.o

I have absolutely no idea on how to optimize compilation...

Amongst the other suggestions I think I've read to substitute pow(x,2) with x*x. I'll certainly do that.
Also, it is true that in the vector version of the function certain calculations can be made only once. I'll change that as well.

Victor suggested to use pointers rather than indexing
I have to be honest, while studying C++ I haven't arrived to the
pointers chapter yet, that's why I haven't used them... and that's why I haven't fully understood your answer.
Also I don't understand why accessing with pointers might be faster than direct indexing.

I'm sorry if I'm asking easy question, I really am a novice and need to learn a lot :)

Cheers, Luca

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

#14274

Hi lucacerone

lucacerone wrote:

> Victor suggested to use pointers rather than indexing
> I have to be honest, while studying C++ I haven't arrived to the
> pointers chapter yet, that's why I haven't used them... and that's why I haven't 
> fully understood your answer.
 

Have a look in this thread in this NG:
Re: loop optimization    01.19.01

> Also I don't understand why accessing with pointers might be faster than direct 
> indexing.

When You say direct indexing I don't think there is much, if any, difference, 
when it is a single array, but when You have [][] or [][][] there start to be 
a difference, but it all depends on the compiler and various little things.
If You use vector and its indexing there is a 30% difference, at least when
compiled with my CodeGear 2009 compiler, I don't know about gcc, but You can
easily test it Your self, You can use the example from the thread i mentioned
above.
P.s. Do remember that most of the time the indexing is a very little part of 
the time used, in very many cases You will not be able to see the difference
in the total picture.


> I'm sorry if I'm asking easy question, I really am a novice and need to learn a lot :)

No problem in, we all learn more by communicating, reading is good, 
but communicating is better, thats my opinion.

Best regards
Asger-P

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

#14279

lucacerone <luca.cerone@gmail.com> writes:
> As for the compiler optimization, I'm using g++ (GNU compiler) on a
> Ubuntu machine. The way I compile the code is simply:
>
> g++ -c -o mylib.o mylib.cpp
> g++ -c -o main.o main.cpp
> g++ -o executableneme main.o mylib.o
>
> I have absolutely no idea on how to optimize compilation...

As a start, you should turn on optimization -- the compiler does no
optimization unless you tell it to, and in many cases non-optimized code
is much, _much_ slower.

To turn on optimization, use the "-O" option, optionally followed by a
digit giving the level of optimization; with gcc, the most common choice
is "-O2" which optimizes somewhat more.

You also want to tell it what processor you're using, because by default
it will produce "generic" code that can run on almost any processor in
the same family, but can be significantly slower than code which is
precisely targetted at the processor you're using.  To do this, use the
"-march=..." option; typically you can use "-march=native", which says
"produce code targetted at the processor in this machine."

So i'd suggest:

  g++ -c -o mylib.o -O2 -march=native mylib.cpp
  g++ -c -o main.o -O2 -march=native  main.cpp
  g++ -o executableneme main.o mylib.o

-Miles

-- 
Infancy, n. The period of our lives when, according to Wordsworth, 'Heaven
lies about us.' The world begins lying about us pretty soon afterward.

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

#14297

On Feb 19, 6:09 am, Miles Bader <mi...@gnu.org> wrote:
> So i'd suggest:
>
>   g++ -c -o mylib.o -O2 -march=native mylib.cpp
>   g++ -c -o main.o -O2 -march=native  main.cpp
>   g++ -o executableneme main.o mylib.o

Why no -O3?

http://gcc.gnu.org/onlinedocs/gcc/Optimize-Options.html#Optimize-Options

-O3
    Optimize yet more. -O3 turns on all optimizations specified by -O2
and also turns on the -finline-functions, -funswitch-loops, -
fpredictive-commoning, -fgcse-after-reload, -ftree-vectorize and -fipa-
cp-clone options.


Function inlining is pretty important for C++.

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

#14298

Joshua Maurice  wrote:

> On Feb 19, 6:09 am, Miles Bader <mi...@gnu.org> wrote:
>> So i'd suggest:
>>
>>   g++ -c -o mylib.o -O2 -march=native mylib.cpp
>>   g++ -c -o main.o -O2 -march=native  main.cpp
>>   g++ -o executableneme main.o mylib.o
> 
> Why no -O3?
> 
> http://gcc.gnu.org/onlinedocs/gcc/Optimize-Options.html#Optimize-Options
> 
> -O3
>     Optimize yet more. -O3 turns on all optimizations specified by -O2
> and also turns on the -finline-functions, -funswitch-loops, -
> fpredictive-commoning, -fgcse-after-reload, -ftree-vectorize and -fipa-
> cp-clone options.

It is fairly safe that -O2 will generate better code than -O1 (which
generates better code than -O0). With -O3, things are much less clear.
Sometimes you get better results, but it is still quite common that
-O3 code runs slower than -O2. The generated code is often much larger
(and the compilation takes longer).

> Function inlining is pretty important for C++.

There is already some inlining at -O2 (exactly how much depends on the
version). And -O3 is not always enough to get the useful inlining,
sometimes you need -fprofile-generate/use or -finline-limit=... to
convince gcc.

This is not to say that -O3 should not be tried, of course. And
possibly -ffast-math if the OP is happy with imprecise (aka wrong)
results.

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

#14303

Marc <marc.glisse@gmail.com> writes:
> This is not to say that -O3 should not be tried, of course. And
> possibly -ffast-math if the OP is happy with imprecise (aka wrong)
> results.

... and if "-ffast-math" isn't acceptable itself, it's often still
worth looking at the sub-options which -ffast-math turns on (look in
the gcc manual, it gives a good description of what it does).
"-fno-math-errno" in particular can give some nice speedups by
dropping standards requirements that very few programs actually care
about.

Similarly, one of the options -ffast-math turns on,
"-funsafe-math-optimizations" (which can often yield good speedups)
actually has useful sub-options itself.  Of these "-fno-trapping-math"
is not problematic for most programs, and can be very useful, as it
allows gcc to speculate expensive operations like division (because it
knows that they can't result in an exception).

[What I do is use "-ffast-math" and then _disable_ the individual
sub-options that I don't want...]

-miles

-- 
Freebooter, n. A conqueror in a small way of business, whose annexations lack
of the sanctifying merit of magnitude.

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

#14313

Marc <marc.glisse@gmail.com> wrote:
> And
> possibly -ffast-math if the OP is happy with imprecise (aka wrong)
> results.

  How are the results imprecise/wrong when using -ffast-math?

  Granted, I don't know every single detail, but I have the impression
that what it does is that it skips some of the most pedantic rules of
IEEE floating point math in favor of faster code. These minute pedantic
rules do not affect the accuracy of the end result in any significant
way (more than what can be expected from floating point values anyways).

  (I do not know if/how it affects situations where undefined results
are produced, such as NaNs or INFs, or in overflow/underflow situations.
In those cases, however, I don't think -ffast-math is going to screw up
your program, unless it uses non-standard code to specifically check for
those situations.)

  Can you provide an example where -ffast-math produces a clearly incorrect
result?

  (Triggering a *bug* in gcc does not count. I have personally reported
one such bug, and it was fixed.)

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

#14319

Juha Nieminen <nospam@thanks.invalid> writes:
>> And
>> possibly -ffast-math if the OP is happy with imprecise (aka wrong)
>> results.
>
>   How are the results imprecise/wrong when using -ffast-math?
>
>   Granted, I don't know every single detail, but I have the impression
> that what it does is that it skips some of the most pedantic rules of
> IEEE floating point math in favor of faster code. These minute pedantic
> rules do not affect the accuracy of the end result in any significant
> way (more than what can be expected from floating point values anyways).

It's not that -ffast-math is bad or anything (I use it happily
myself), but if precise results are important it's a good idea to
check what it does in detail, and make sure things are OK.  One can
always, of course, use -ffast-math, and then _disable_ some of the
finer-grained options it enabled.

For instance: -ffast-math enables -funsafe-math-optimizations, which
enables -freciprocal-math, which: "Allows the reciprocal of a value to
be used instead of dividing by the value if this enables optimizations
... Note that this loses precision and increases the number of flops
operating on the value."

-funsafe-math-optimizations also enables fassociative-math, and
changing the order of operations can affect the precision of the
result in a way that the programmer didn't expect.

-ffast-math also enables -ffinite-math-only, which of course will
cause infinities etc to not be handled as expected.

etc.

-miles

-- 
`There are more things in heaven and earth, Horatio,
 Than are dreamt of in your philosophy.'

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

#14335

Op 20-Feb-12 11:24, Juha Nieminen schreef:
> Marc<marc.glisse@gmail.com>  wrote:
>> And
>> possibly -ffast-math if the OP is happy with imprecise (aka wrong)
>> results.

Floating point math is (almost) always imprecise, whether that means it 
that it wrong depends very much on how precision is needed by the 
application.

>    How are the results imprecise/wrong when using -ffast-math?
>
>    Granted, I don't know every single detail, but I have the impression
> that what it does is that it skips some of the most pedantic rules of
> IEEE floating point math in favor of faster code.

In the old days when the x87 instructions on x86 platforms were used for 
floating point math, you could tell many compilers to keep intermediate 
results in the 80-bit floating point registers (fast), or to always read 
and write intermediate results as 64-bit floating point numbers to 
memory (slow). When using the first option you never really know when an 
operation is performed with 80-bit precision and at what point it gets 
rounded down to 64-bits. With the second option you know that the result 
is always rounded down to 64-bits at every step.

In other words; it is not so much about precision, but more about 
getting consistent results (there is a difference).

Now SSE instructions (which do not have 80-bit registers) are commonly 
used for floating point math on x86 platforms I'm not quite sure how 
this settings would affect floating point math. I believe that the SSE 
instruction do deviate in some aspects from the IEEE 754 standard, so 
some additional code may be needed to fix this for those who care.

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

#14348

Dombo <dombo@disposable.invalid> wrote:
> Now SSE instructions (which do not have 80-bit registers) are commonly 
> used for floating point math on x86 platforms I'm not quite sure how 
> this settings would affect floating point math.

  As someone pointed out, something like this:

    x = a / c;
    y = b / c;

does not (usually) give the *exact* same result as:

    tmp = 1 / c;
    x = a * tmp;
    y = b * tmp;

  The difference will happen in the few least-significant bits of the
mantissa (iow. somewhere around the 15th least-significant digit with
doubles), which is extremely small, but might count in some rare
circumstances.

  The latter, however, is often faster than the former (because floating
point multiplication will usually be something like 1 clock cycle while
division will be a dozen or so).

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

#14351

Juha Nieminen於 2012年2月21日星期二UTC+8下午4時41分14秒寫道：
> Dombo <dombo@disposable.invalid> wrote:
> > Now SSE instructions (which do not have 80-bit registers) are commonly 
> > used for floating point math on x86 platforms I'm not quite sure how 
> > this settings would affect floating point math.
> 
>   As someone pointed out, something like this:
> 
>     x = a / c;
>     y = b / c;
> 
> does not (usually) give the *exact* same result as:
> 
>     tmp = 1 / c;
>     x = a * tmp;
>     y = b * tmp;
> 
>   The difference will happen in the few least-significant bits of the
> mantissa (iow. somewhere around the 15th least-significant digit with
> doubles), which is extremely small, but might count in some rare
> circumstances.
> 
>   The latter, however, is often faster than the former (because floating
> point multiplication will usually be something like 1 clock cycle while
> division will be a dozen or so).



Juha Nieminen於 2012年2月21日星期二UTC+8下午4時41分14秒寫道：
> Dombo <dombo@disposable.invalid> wrote:
> > Now SSE instructions (which do not have 80-bit registers) are commonly 
> > used for floating point math on x86 platforms I'm not quite sure how 
> > this settings would affect floating point math.
> 
>   As someone pointed out, something like this:
> 
>     x = a / c;
>     y = b / c;
> 
> does not (usually) give the *exact* same result as:
> 
>     tmp = 1 / c;

tmp is trucated for finite precision here, 
if err(tmp, tru(1/c)) *a affects the tail bits of a*tmp, 
then the result is different from a/c computed 
by a float or double instruction
 
 
>     x = a * tmp;
>     y = b * tmp;
> 
>   The difference will happen in the few least-significant bits of the
> mantissa (iow. somewhere around the 15th least-significant digit with
> doubles), which is extremely small, but might count in some rare
> circumstances.
> 
>   The latter, however, is often faster than the former (because floating
> point multiplication will usually be something like 1 clock cycle while
> division will be a dozen or so).

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

#14302

Joshua Maurice <joshuamaurice@gmail.com> writes:
>> So i'd suggest:
>>
>>   g++ -c -o mylib.o -O2 -march=native mylib.cpp
>>   g++ -c -o main.o -O2 -march=native  main.cpp
>>   g++ -o executableneme main.o mylib.o
>
> Why no -O3?
>
> http://gcc.gnu.org/onlinedocs/gcc/Optimize-Options.html#Optimize-Options
>
> -O3
>     Optimize yet more. -O3 turns on all optimizations specified by -O2
> and also turns on the -finline-functions, -funswitch-loops, -
> fpredictive-commoning, -fgcse-after-reload, -ftree-vectorize and -fipa-
> cp-clone options.
>
> Function inlining is pretty important for C++.

-O2 does comprehensive inlining as well -- including functions not
 marked "inline" -- using gcc's inlining heuristics, which are quite
 good these days.  [What "-finline-functions" does is act as _every
 function_ were marked "inline" meaning gcc will be more likely to
 inline stuff, even when it doesn't think it's a good idea.]

-O2 is a good default choice if want good optimization, but don't want
to spend a lot of time benchmarking.  -O3 includes optimizations that
may be very expensive at compile-time or may result in excessive code
bloat (and thus can have a negative effect on the icache etc).  -O3
can _sometimes_ help, but it can also sometimes hurt, so it's a good
idea to do some benchmarking to determine which is better.

-Miles

-- 
Cynic, n. A blackguard whose faulty vision sees things as they are, not as
they ought to be. Hence the custom among the Scythians of plucking out a
cynic's eyes to improve his vision.

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

#14315

Thanks Miles, this really improved the speed (doubled it)!
Where can I learn all the tricks I might need about the compiler?

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

#14192

Asger Joergensen <Junk@asger-p.dk> wrote:
> If You can live with fixed precision You code will run much faster if You use 
> int's or __int64's and then multiply /devide as much as You need to get Your the
> precision You need.

  This isn't the early 90's. Processors have got a bit faster at
calculating with floating point values in the meantime.

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

#14202

Hi Juha

Juha Nieminen wrote:

> Asger Joergensen <Junk@asger-p.dk> wrote:
> > If You can live with fixed precision You code will run much faster if You use 
> > int's or __int64's and then multiply /devide as much as You need to get Your the
> > precision You need.
> 
>   This isn't the early 90's. Processors have got a bit faster at
> calculating with floating point values in the meantime.

Not nearly as fast as they can do it with int's though, in my experience.

Best regards
Asger-P

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

Page 1 of 2  [1] 2  Next page →

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

csiph-web