Computation slow with float than double.

Discussion in 'C Programming' started by Michele Guidolin, Jun 6, 2005.

  1. Hello to everybody.

    I'm doing some benchmark about a red black Gauss Seidel algorithm with 2
    dimensional grid of different size and type, I have some strange result
    when I change the computation from double to float.

    Here are the time of test with different grid SIZE and type:

    SIZE 128 256 512

    float 2.20s 2.76s 7.86s

    double 2.30s 2.47s 2.59s

    As you can see when the grid has a size of 256 node the code with float
    type increase the time drastically.

    What could be the problem? could be the cache? Should the float
    computation always fastest than double?

    Hope to receive an answer as soon as possible,
    Thanks

    Michele Guidolin.
    P.S.

    Here are some more information about the test:

    The code that I'm testing is this and it is the same for the double
    version (the constant are not 0.25f but 0.25).

    ------------- CODE -------------

    float u[SIZE][SIZE];
    float rhs[SIZE][SIZE];

    inline void gs_relax(int i,int j)
    {

    u[j] = ( rhs[j] +
    0.0f * u[j] +
    0.25f* u[i+1][j]+
    0.25f* u[i-1][j]+
    0.25f* u[j+1]+
    0.25f* u[j-1]);
    }

    void gs_step_fusion()
    {
    int i,j;

    /* update the red points:
    */

    for(j=1; j<SIZE-1; j=j+2)
    {
    gs_relax(1,j);
    }
    for(i=2; i<SIZE-1; i++)
    {
    for(j=1+(i+1)%2; j<SIZE-1; j=j+2)
    {
    gs_relax(i,j);
    gs_relax(i-1,j);
    }

    }
    for(j=1; j<SIZE-1; j=j+2)
    {
    gs_relax(SIZE-2,j);
    }

    }
    ---------------CODE--------------

    I'm testing this code on this machine:

    processor : 0
    vendor_id : GenuineIntel
    cpu family : 15
    model : 4
    model name : Intel(R) Pentium(R) 4 CPU 3.20GHz
    stepping : 1
    cpu MHz : 3192.311
    cache size : 1024 KB
    physical id : 0
    siblings : 2
    fdiv_bug : no
    hlt_bug : no
    f00f_bug : no
    coma_bug : no
    fpu : yes
    fpu_exception : yes
    cpuid level : 3
    wp : yes
    flags : fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge
    mca cmov pat pse36 clflush dts acpi mmx fxsr sse sse2 ss ht tm pbe pni
    monitor ds_cpl cid
    bogomips : 6324.22

    with Hyper threading enable on Linux 2.6.8.

    The compiler is gcc 3.4.4 and the flags are:
    CFLAGS = -g -O2 -funroll-loops -msse2 -march=pentium4 -Wall
    Michele Guidolin, Jun 6, 2005
    #1
    1. Advertising

  2. in comp.lang.c i read:

    >I'm doing some benchmark about a red black Gauss Seidel algorithm with 2
    >dimensional grid


    >As you can see when the grid has a size of 256 node the code with float
    >type increase the time drastically.
    >
    >What could be the problem? could be the cache? Should the float
    >computation always fastest than double?


    most likely your system does all floating point computations using a
    precision greater than float, then reduces the result when the value must
    be stored, which happens more often as you increase the size of the table.

    --
    a signature
    those who know me have no need of my name, Jun 6, 2005
    #2
    1. Advertising

  3. Michele Guidolin

    Eric Sosman Guest

    Michele Guidolin wrote:
    > Hello to everybody.
    >
    > I'm doing some benchmark about a red black Gauss Seidel algorithm with 2
    > dimensional grid of different size and type, I have some strange result
    > when I change the computation from double to float.
    >
    > Here are the time of test with different grid SIZE and type:
    >
    > SIZE 128 256 512
    >
    > float 2.20s 2.76s 7.86s
    >
    > double 2.30s 2.47s 2.59s
    >
    > As you can see when the grid has a size of 256 node the code with float
    > type increase the time drastically.


    I see a modest increase at 256 and a huge increase at 512.
    Have there been any transcription errors?

    I also see that the code you didn't show probably accounts
    for the lion's share of the running time, which casts suspicion
    on drawing too many conclusions from a couple of experiments.
    The running time of the posted code should increase (roughly)
    as the square of SIZE, so changing SIZE from 128 to 512 should
    inflate its running time by a factor of (about) sixteen. Yet
    this supposed sixteen-fold increase added only 0.29 seconds to
    the running time for "double;" a straightforward calculation
    (based on data of unknown accuracy, to be sure) suggests that
    the rest of the program accounts for 89% or more of the time
    in that case, and even more in the other two.

    ... and if such a large portion of the total time resides
    "elsewhere," it would be unwise to draw too many conclusions
    until the contributions of "elsewhere" are better characterized,
    or better controlled for (e.g., by repeated experiment and
    statistical analysis).

    > What could be the problem? could be the cache? Should the float
    > computation always fastest than double?


    Cache might be a problem. So might alignment, or other
    competing processes on the machine. If you're reading the
    initial data from a file, perhaps one test paid the penalty of
    actually reading from the disk while the others benefitted from
    the file system's cache. Or maybe the disk is just beginning
    to go sour, and the O/S relocated an entire track of data in
    the middle of one test. Or maybe the phase of the moon wasn't
    propitious.

    Should float always be faster than double? No, the C language
    Standard is silent on matters of speed (which makes the entire
    discussion off-topic here, or at least slightly so). You've shown
    some puzzling data, but you need more data and more analysis to
    draw good conclusions, and the results you eventually get will
    most likely be relevant only to the system you got them on, and
    not to the C language. I'd suggest further experimentation, and
    a change to a newsgroup devoted to your system, where the experts
    on your system's quirks hang out.

    --
    Eric Sosman, Jun 6, 2005
    #3
  4. Michele Guidolin

    CBFalconer Guest

    Michele Guidolin wrote:
    >

    .... snip ...
    >
    > Here are the time of test with different grid SIZE and type:
    >
    > SIZE 128 256 512
    > float 2.20s 2.76s 7.86s
    > double 2.30s 2.47s 2.59s
    >
    > As you can see when the grid has a size of 256 node the code with
    > float type increase the time drastically.
    >
    > What could be the problem? could be the cache? Should the float
    > computation always fastest than double?


    C real computations are always done as doubles by default. When
    you specify floats you are primarily constricting the storage, and
    are causing float->double->float conversions to be done. These are
    eating up the time.

    --
    "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
    CBFalconer, Jun 6, 2005
    #4
  5. Michele Guidolin

    Eric Sosman Guest

    CBFalconer wrote:
    > Michele Guidolin wrote:
    >
    > ... snip ...
    >
    >>Here are the time of test with different grid SIZE and type:
    >>
    >>SIZE 128 256 512
    >>float 2.20s 2.76s 7.86s
    >>double 2.30s 2.47s 2.59s
    >>
    >>As you can see when the grid has a size of 256 node the code with
    >>float type increase the time drastically.
    >>
    >>What could be the problem? could be the cache? Should the float
    >>computation always fastest than double?

    >
    >
    > C real computations are always done as doubles by default. When
    > you specify floats you are primarily constricting the storage, and
    > are causing float->double->float conversions to be done. These are
    > eating up the time.


    That was true in pre-Standard days, but ever since
    C89 the implementation has been allowed to use `float'
    arithmetic when only `float' operands are involved. Not
    all implementations do so (and I don't know whether the
    O.P.'s does), but it's no longer a certainty that the
    conversions are occurring. C99 6.3.1.8 or C89 3.2.1.5;
    I don't have the section number for C90.

    --
    Eric Sosman, Jun 6, 2005
    #5
  6. On Mon, 06 Jun 2005 20:54:56 +0000, CBFalconer wrote:

    > Michele Guidolin wrote:
    >>

    > ... snip ...
    >>
    >> Here are the time of test with different grid SIZE and type:
    >>
    >> SIZE 128 256 512
    >> float 2.20s 2.76s 7.86s
    >> double 2.30s 2.47s 2.59s
    >>
    >> As you can see when the grid has a size of 256 node the code with
    >> float type increase the time drastically.
    >>
    >> What could be the problem? could be the cache? Should the float
    >> computation always fastest than double?

    >
    > C real computations are always done as doubles by default.


    That was true in K&R C, but not in standard C. An implementation CAN
    perform calculations in greater precision than the representation of the
    type but it is not required to.

    > When
    > you specify floats you are primarily constricting the storage, and
    > are causing float->double->float conversions to be done. These are
    > eating up the time.


    Perhaps. But on common architectures it is typically the case that float
    operations are performed using float precision or else loading/saving a
    float sized object in memory to/from a wider register is no more expensing
    than a double sized object in memory.

    Lawrence
    Lawrence Kirby, Jun 6, 2005
    #6
  7. In article <newscache$0viphi$xhe$>,
    Michele Guidolin <"michele dot guidolin at ucd dot ie"> wrote:

    > Hello to everybody.
    >
    > I'm doing some benchmark about a red black Gauss Seidel algorithm with 2
    > dimensional grid of different size and type, I have some strange result
    > when I change the computation from double to float.
    >
    > Here are the time of test with different grid SIZE and type:
    >
    > SIZE 128 256 512
    >
    > float 2.20s 2.76s 7.86s
    >
    > double 2.30s 2.47s 2.59s


    As a rule of thumb: Accessing array elements at a distance that is a
    large power of two is asking for trouble (performance wise).

    Any reason why you choose powers of two? Why not SIZE = 50, 100, 200,
    500?
    Christian Bau, Jun 6, 2005
    #7
  8. Christian Bau wrote:
    >>
    >>SIZE 128 256 512
    >>
    >>float 2.20s 2.76s 7.86s
    >>
    >>double 2.30s 2.47s 2.59s

    >
    >
    > As a rule of thumb: Accessing array elements at a distance that is a
    > large power of two is asking for trouble (performance wise).
    >
    > Any reason why you choose powers of two? Why not SIZE = 50, 100, 200,
    > 500?



    OK! I tried some more test with different SIZE of grid, in the precedent
    message I forgot to say that the number of loop is proportional of SIZE
    of grid, but the different time between two different SIZE shouldn't be
    considerate realy proportonial.

    -------code ----
    ITERATIONS = ((int)(pow(2.0,28.0))/(pow((double)SIZE,2.0)));

    gettimeofday(&submit_time, 0);

    for(iter=0; iter<ITERATIONS; iter++)
    gs_step_fusion();

    gettimeofday(&complete_time, 0);


    -------code -----

    Moreover the time considerer only the loop itself and not other things,
    like data initialization and print of result.

    The new time test are:

    SIZE 100 200 300 400 500 513
    Float 2.17s 2.44s 3.35s 5.82s 8.37s 7.98s
    Double 2.32s 2.34s 2.57s 2.63s 2.63s 2.65s

    When I use a profiler it show me that the 95% of time is on this two
    function:

    for(j=1+(i+1)%2; j<SIZE-1; j=j+2)
    {
    gs_relax(i,j); // 45%
    gs_relax(i-1,j); // 45%
    }

    So I still doesn't understand why the float version is going so slowy.
    Any help?

    Thaks for answer.

    Michele Guidolin
    Michele Guidolin, Jun 7, 2005
    #8
  9. Lawrence Kirby wrote:
    >>Moreover the time considerer only the loop itself and not other things,
    >>like data initialization and print of result.
    >>
    >>The new time test are:
    >>
    >>SIZE 100 200 300 400 500 513
    >>Float 2.17s 2.44s 3.35s 5.82s 8.37s 7.98s
    >>Double 2.32s 2.34s 2.57s 2.63s 2.63s 2.65s
    >>
    >>When I use a profiler it show me that the 95% of time is on this two
    >>function:
    >>
    >> for(j=1+(i+1)%2; j<SIZE-1; j=j+2)

    >
    >
    > What is i? Is this an inner loop?
    >
    >
    >> {
    >> gs_relax(i,j); // 45%
    >> gs_relax(i-1,j); // 45%

    >
    >
    > This suggests that you need to look in gs_relax to see what is happening.
    >
    >
    >> }
    >> }
    >>So I still doesn't understand why the float version is going so slowy.
    >>Any help?

    >
    >
    > You have yet to show any code that accesses float or double data.
    >
    > Lawrence


    The gs_relax simply do a Gauss Seidel red black relaxion.
    I already posted the code in the first message, but I post it again.
    The double version is exactly the same (with the constant 0.25 and not
    0.25f).

    I realy don't understand why the float version is going so slowly whit a
    SIZE > 300. Maybe gcc bug?
    If someone has an idea will be very appreciate.
    Thanks
    Michele.

    ------------- CODE -------------

    float u[SIZE][SIZE];
    float rhs[SIZE][SIZE];

    inline void gs_relax(int i,int j)
    {

    u[j] = ( rhs[j] +
    0.0f * u[j] +
    0.25f* u[i+1][j]+
    0.25f* u[i-1][j]+
    0.25f* u[j+1]+
    0.25f* u[j-1]);
    }

    void gs_step_fusion()
    {
    int i,j;

    /* update the red points:
    */

    for(j=1; j<SIZE-1; j=j+2)
    {
    gs_relax(1,j);
    }
    for(i=2; i<SIZE-1; i++)
    {
    for(j=1+(i+1)%2; j<SIZE-1; j=j+2)
    {
    gs_relax(i,j);
    gs_relax(i-1,j);
    }

    }
    for(j=1; j<SIZE-1; j=j+2)
    {
    gs_relax(SIZE-2,j);
    }

    }
    ---------------CODE--------------
    Michele Guidolin, Jun 7, 2005
    #9
  10. Michele Guidolin

    Tim Prince Guest

    "Michele Guidolin" <"michele dot guidolin at ucd dot ie"> wrote in message
    news:newscache$fsqqhi$o85$...
    > Christian Bau wrote:
    >>>
    >>>SIZE 128 256 512
    >>>
    >>>float 2.20s 2.76s 7.86s
    >>>
    >>>double 2.30s 2.47s 2.59s

    >>
    >>
    >> As a rule of thumb: Accessing array elements at a distance that is a
    >> large power of two is asking for trouble (performance wise).
    >>
    >> Any reason why you choose powers of two? Why not SIZE = 50, 100, 200,
    >> 500?

    >
    >
    > OK! I tried some more test with different SIZE of grid, in the precedent
    > message I forgot to say that the number of loop is proportional of SIZE
    > of grid, but the different time between two different SIZE shouldn't be
    > considerate realy proportonial.
    >
    > -------code ----
    > ITERATIONS = ((int)(pow(2.0,28.0))/(pow((double)SIZE,2.0)));
    >
    > gettimeofday(&submit_time, 0);
    >
    > for(iter=0; iter<ITERATIONS; iter++)
    > gs_step_fusion();
    >
    > gettimeofday(&complete_time, 0);
    >
    >
    > -------code -----
    >
    > Moreover the time considerer only the loop itself and not other things,
    > like data initialization and print of result.
    >
    > The new time test are:
    >
    > SIZE 100 200 300 400 500 513
    > Float 2.17s 2.44s 3.35s 5.82s 8.37s 7.98s
    > Double 2.32s 2.34s 2.57s 2.63s 2.63s 2.65s
    >
    > When I use a profiler it show me that the 95% of time is on this two
    > function:
    >
    > for(j=1+(i+1)%2; j<SIZE-1; j=j+2)
    > {
    > gs_relax(i,j); // 45%
    > gs_relax(i-1,j); // 45%
    > }
    >
    > So I still doesn't understand why the float version is going so slowy.
    > Any help?

    I didn't like to attempt an answer, as I wasn't certain whether your options
    invoke SSE code generation. Several other answers seemed to imply that
    people thought so, but weren't certain. Maybe attacking the problem more
    directly makes it off topic for c.l.c, but I've already seen plenty of
    answers which don't look like pure Standard C information.
    When you divide your grid more finely, are you running into gradual
    underflow? If so, what happens when you invoke abrupt underflow, as
    gcc -O2 -funroll-loops -march=pentium4 -mfpmath=sse -ffast-math
    might do? Most compilers have gradual underflow on as a default, since it
    is required according to IEEE standard, and turn it off either by a specific
    option or as a part of some "fast" package.
    Gradual underflow is quite slow on early P4 steppings, in case you didn't
    believe this question could go far OFF TOPIC.
    Tim Prince, Jun 7, 2005
    #10
  11. On Tue, 07 Jun 2005 11:46:54 +0100, Michele Guidolin wrote:

    > Christian Bau wrote:
    >>>
    >>>SIZE 128 256 512
    >>>
    >>>float 2.20s 2.76s 7.86s
    >>>
    >>>double 2.30s 2.47s 2.59s

    >>
    >>
    >> As a rule of thumb: Accessing array elements at a distance that is a
    >> large power of two is asking for trouble (performance wise).
    >>
    >> Any reason why you choose powers of two? Why not SIZE = 50, 100, 200,
    >> 500?

    >
    >
    > OK! I tried some more test with different SIZE of grid, in the precedent
    > message I forgot to say that the number of loop is proportional of SIZE
    > of grid, but the different time between two different SIZE shouldn't be
    > considerate realy proportonial.
    >
    > -------code ----
    > ITERATIONS = ((int)(pow(2.0,28.0))/(pow((double)SIZE,2.0)));


    It is better to do integer calculations in integer arithmetic if you can.
    Anso consider that C only requires int to be able to represent number in
    the range -32767 to 32767. So you might use something like

    ITERATIONS = (1L << 28) / ((long)SIZE * SIZE);

    > gettimeofday(&submit_time, 0);


    gettimeofday() isn't standard C. You can use the standard clock() function
    to measure CPU time used.

    > for(iter=0; iter<ITERATIONS; iter++)
    > gs_step_fusion();
    >
    > gettimeofday(&complete_time, 0);
    >
    >
    > -------code -----
    >
    > Moreover the time considerer only the loop itself and not other things,
    > like data initialization and print of result.
    >
    > The new time test are:
    >
    > SIZE 100 200 300 400 500 513
    > Float 2.17s 2.44s 3.35s 5.82s 8.37s 7.98s
    > Double 2.32s 2.34s 2.57s 2.63s 2.63s 2.65s
    >
    > When I use a profiler it show me that the 95% of time is on this two
    > function:
    >
    > for(j=1+(i+1)%2; j<SIZE-1; j=j+2)


    What is i? Is this an inner loop?

    > {
    > gs_relax(i,j); // 45%
    > gs_relax(i-1,j); // 45%


    This suggests that you need to look in gs_relax to see what is happening.

    > }
    > }
    > So I still doesn't understand why the float version is going so slowy.
    > Any help?


    You have yet to show any code that accesses float or double data.

    Lawrence
    Lawrence Kirby, Jun 7, 2005
    #11
  12. In article <newscache$r3vqhi$er6$>,
    Michele Guidolin <"michele dot guidolin at ucd dot ie"> wrote:

    > I realy don't understand why the float version is going so slowly whit a
    > SIZE > 300. Maybe gcc bug?


    Is the "double" version at SIZE > 300 slow as well?

    Slowness would be expected when things exceed cache size. 300x300 floats
    would be 360,000 bytes. The "double" version should slow down a bit
    earlier.
    Christian Bau, Jun 7, 2005
    #12
  13. In article <Qjgpe.928$> "Tim Prince" <> writes:
    ....
    > When you divide your grid more finely, are you running into gradual
    > underflow?


    That might very well be the case. In float that happens much earlier than
    in double.

    > If so, what happens when you invoke abrupt underflow, as
    > gcc -O2 -funroll-loops -march=pentium4 -mfpmath=sse -ffast-math
    > might do?


    Another option would be to shift the origin of the coordinate system.

    > Most compilers have gradual underflow on as a default, since it
    > is required according to IEEE standard, and turn it off either by a specific
    > option or as a part of some "fast" package.
    > Gradual underflow is quite slow on early P4 steppings, in case you didn't
    > believe this question could go far OFF TOPIC.


    The main reason is that gradual underflow on most systems is not handled
    by the processor, but by software. And that requires interrupts.
    --
    dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland, +31205924131
    home: bovenover 215, 1025 jn amsterdam, nederland; http://www.cwi.nl/~dik/
    Dik T. Winter, Jun 8, 2005
    #13
  14. Michele Guidolin

    Guest

    Michele Guidolin wrote:
    > Lawrence Kirby wrote:
    > >>Moreover the time considerer only the loop itself and not other things,
    > >>like data initialization and print of result.
    > >>
    > >>The new time test are:
    > >>
    > >>SIZE 100 200 300 400 500 513
    > >>Float 2.17s 2.44s 3.35s 5.82s 8.37s 7.98s
    > >>Double 2.32s 2.34s 2.57s 2.63s 2.63s 2.65s
    > >>
    > >>When I use a profiler it show me that the 95% of time is on this two
    > >>function:
    > >>
    > >> for(j=1+(i+1)%2; j<SIZE-1; j=j+2)

    > >
    > >
    > > What is i? Is this an inner loop?
    > >
    > >
    > >> {
    > >> gs_relax(i,j); // 45%
    > >> gs_relax(i-1,j); // 45%

    > >
    > >
    > > This suggests that you need to look in gs_relax to see what is happening.
    > >
    > >
    > >> }
    > >> }
    > >>So I still doesn't understand why the float version is going so slowy.
    > >>Any help?

    > >
    > >
    > > You have yet to show any code that accesses float or double data.
    > >
    > > Lawrence

    >
    > The gs_relax simply do a Gauss Seidel red black relaxion.
    > I already posted the code in the first message, but I post it again.
    > The double version is exactly the same (with the constant 0.25 and not
    > 0.25f).
    >
    > I realy don't understand why the float version is going so slowly whit a
    > SIZE > 300. Maybe gcc bug?
    > If someone has an idea will be very appreciate.
    > Thanks
    > Michele.
    >
    > ------------- CODE -------------
    >
    > float u[SIZE][SIZE];
    > float rhs[SIZE][SIZE];
    >
    > inline void gs_relax(int i,int j)
    > {
    >
    > u[j] = ( rhs[j] +
    > 0.0f * u[j] +
    > 0.25f* u[i+1][j]+
    > 0.25f* u[i-1][j]+
    > 0.25f* u[j+1]+
    > 0.25f* u[j-1]);
    > }
    >
    > void gs_step_fusion()
    > {
    > int i,j;
    >
    > /* update the red points:
    > */
    >
    > for(j=1; j<SIZE-1; j=j+2)
    > {
    > gs_relax(1,j);
    > }
    > for(i=2; i<SIZE-1; i++)
    > {
    > for(j=1+(i+1)%2; j<SIZE-1; j=j+2)
    > {
    > gs_relax(i,j);
    > gs_relax(i-1,j);
    > }
    >
    > }
    > for(j=1; j<SIZE-1; j=j+2)
    > {
    > gs_relax(SIZE-2,j);
    > }
    >
    > }
    > ---------------CODE--------------


    You may be much better asking this question on a gcc specific group
    such as gnu.gcc.help. It may be an eccentricity of a specific GCC
    version.

    Also, do not test this function using all zeros in the arrays.
    Floating point units often treat zero specially.
    , Jun 8, 2005
    #14
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. JKop
    Replies:
    4
    Views:
    16,514
  2. Sydex
    Replies:
    12
    Views:
    6,489
    Victor Bazarov
    Feb 17, 2005
  3. bd
    Replies:
    0
    Views:
    624
  4. maadhuu

    why is double more efficient than float ?

    maadhuu, Sep 14, 2005, in forum: C Programming
    Replies:
    14
    Views:
    831
    Emmanuel Delahaye
    Sep 17, 2005
  5. Carsten Fuchs
    Replies:
    45
    Views:
    1,540
    James Kanze
    Oct 8, 2009
Loading...

Share This Page