[C] Integer calculation langzamer dan floating point?

[Pete]

Voor school moesten we een klein scriptje schrijven om dingen te timen. Nu hadden we daar geen problemen mee, maar hetgeen wat we hebben getimed vonden we een beetje vreemd.

Script:

C:

#include<stdio.h>
#include<sys/time.h>
#include<stdlib.h>

#define LOOPS           100000000

void sum_integer(){
        int sum=0, k=1, m=1;
        int i;
        for(i=1; i<=LOOPS; i++){
                m = k * k;
                sum = sum + m / k;
        }
}

void sum_float(){
        float sum=0, k=1, m=1;
        int i;
        for(i=1; i<=LOOPS; i++){
                m = k * k;
                sum = sum + m / k;
        }
}

void sum_double(){
        double sum=0, k=1, m=1;
        int i;
        for(i=1; i<=LOOPS; i++){
                m = k * k;
                sum = sum + m / k;
        }
}
long giveMiliseconds(struct timeval *tm1, struct timeval *tm2){
        long segundos = tm2->tv_sec - tm1->tv_sec;
        long micros = tm2->tv_usec - tm1->tv_usec;

        if(micros < 0){
                segundos-=1;
                micros+=1000000;
        }

        micros = (long) ((float)micros /1000);

        return segundos*1000 + micros;

}

int main(void){
        struct timeval tm1, tm2;
        struct timezone tz1, tz2;

        gettimeofday(&tm1, &tz1);
        sum_integer();
        gettimeofday(&tm2, &tz2);
        printf("INTEGERS: %ld (ms)\n",giveMiliseconds(&tm1, &tm2));

        gettimeofday(&tm1, &tz1);
        sum_float();
        gettimeofday(&tm2, &tz2);
        printf("FLOATS: %ld (ms)\n",giveMiliseconds(&tm1, &tm2));

        gettimeofday(&tm1, &tz1);
        sum_double();
        gettimeofday(&tm2, &tz2);
        printf("DOUBLES: %ld (ms)\n",giveMiliseconds(&tm1, &tm2));

}

Output mijzelf (gcc, amd turion 64, 32 bit Ubuntu)

INTEGERS: 3158 (ms)
FLOATS: 826 (ms)
DOUBLES: 870 (ms)

Output collega PowerPC (Mac OS X)

INTEGERS: 2719 (ms)
FLOATS: 3953 (ms)
DOUBLES: 3884 (ms)

Hoe kan dit verschil? Normaal zijn integeroperaties toch altijd sneller dan floating-point? Wie kan mij vertellen hoe het kan dat bij mij integeroperaties bijna 4x zolang duren?

[pentersje]

Iemand?? Ik wil dat zelf ook graag weten!
Sowieso vind ik die score verrasend. Ik dacht dat de AMD CPU sneller zou zijn met Floating points dan een PowerPC CPU.

[scorpie]

pentersje schreef op zaterdag 06 oktober 2007 @ 14:56:
Iemand?? Ik wil dat zelf ook graag weten!
Sowieso vind ik die score verrasend. Ik dacht dat de AMD CPU sneller zou zijn met Floating points dan een PowerPC CPU.

Dat is ie toch ook?

[Verwijderd]

pentersje schreef op zaterdag 06 oktober 2007 @ 14:56:
Iemand?? Ik wil dat zelf ook graag weten!
Sowieso vind ik die score verrasend. Ik dacht dat de AMD CPU sneller zou zijn met Floating points dan een PowerPC CPU.

Die AMD is ook sneller Kijk maar eens goed, het gaat om tijden, dus degene met de minste tijd is sneller

[Marcj]

Waarschijnlijk omdat je gcc de boel aan het optimaliseren is. Aangezien je helemaal niets met de sum doet.. Maar waarom hij wel de floats optimaliseerd, maar de ints niet is mij ook een raadsel. Probeer voor de grap dit maar eens:

C++:

#include <iostream>

#define LOOPS           1000000000 

int sum_integer() {
    int sum = 0, k = 1, m = 1;
    for (long i = 0; i < LOOPS; i++) {
        m = k * k;
        sum += m / k;
    }
    return sum;
}

float sum_float() {
    float sum = 0, k = 1, m = 1;
    for (long i = 0; i < LOOPS; i++) {
        m = k * k;
        sum += m / k;
    }
    return sum;
}

double sum_double() {
    double sum = 0, k = 1, m = 1;
    for (long i = 0; i < LOOPS; i++) {
        m = k * k;
        sum += m / k;
    }
    return sum;
}

int main(void) {
    time_t start;

    start = clock();
    int value = sum_integer();
    printf("INTEGERS: %ld (ms) value = %d\n", clock() - start, value);

    start = clock();
    float fvalue = sum_float();
    printf("FLOATS: %ld (ms) value = %e\n", clock() - start, fvalue);

    start = clock();
    double dvalue = sum_double();
    printf("DOUBLES: %ld (ms) value = %e\n", clock() - start, dvalue);
}

Mijn resultaten (op een Athlon X2 4200+)
INTEGERS: 844 (ms) value = 1000000000
FLOATS: 5484 (ms) value = 1.677722e+07
DOUBLES: 5485 (ms) value = 1.000000e+09

Dat lijkt me al een stuk beter Dit is trouwens met "g++ -O5" gecompileerd...

[bobo1on1]

De functies komen eigenlijk neer op deze berekeningen:

C:

m = 1 * 1;
sum = sum + 1 / 1; 

Dit vind ik niet echt een goede benchmark, dan kun je net zo goed sum++; neerzetten, misschien dat de compiler dat er ook van maakt.


Bij mij loopt het veel sneller met

code:

export CHOST="x86_64-pc-linux-gnu"
export CFLAGS="-march=k8 -O3 -pipe -msse3"
export CXXFLAGS="${CFLAGS}"

code:

bob@bob:~/Projects/test/src$ ./test 
INTEGERS: 0 (ms)
FLOATS: 0 (ms)
DOUBLES: 0 (ms)
bob@bob:~/Projects/test/src$

yeah

Marcj schreef op zaterdag 06 oktober 2007 @ 15:04:
Waarschijnlijk omdat je gcc de boel aan het optimaliseren is. Aangezien je helemaal niets met de sum doet.. Maar waarom hij wel de floats optimaliseerd, maar de ints niet is mij ook een raadsel. Probeer voor de grap dit maar eens:

C++:

#include <iostream>
......

Mijn resultaten (op een Athlon X2 4200+)
INTEGERS: 844 (ms) value = 1000000000
FLOATS: 5484 (ms) value = 1.677722e+07
DOUBLES: 5485 (ms) value = 1.000000e+09

Dat lijkt me al een stuk beter Dit is trouwens met "g++ -O5" gecompileerd...

Dat doet bij mij nog niet veel zinnigs (Athlon X2 4000+) :

code:

bob@bob:~/Projects/test2/src$ ./test2 
INTEGERS: 0 (ms) value = 1000000000
FLOATS: 1920000 (ms) value = 1.677722e+07
DOUBLES: 1900000 (ms) value = 1.000000e+09

Wat mij het beste lijkt is eerst een array vullen met random waardes (niet meenemen in de benchmark) en daarmee gaan rekenen in een loop, dan valt er weinig meer te optimaliseren.
UIteraard wel dezelfde waardes gebruiken voor de verschillende types.

[ Voor 90% gewijzigd door bobo1on1 op 06-10-2007 15:27 ]

[PrisonerOfPain]

phsmit schreef op zaterdag 06 oktober 2007 @ 14:43:
Hoe kan dit verschil? Normaal zijn integeroperaties toch altijd sneller dan floating-point? Wie kan mij vertellen hoe het kan dat bij mij integeroperaties bijna 4x zolang duren?

Waarschijnlijk SSE optimalisaties van je compiler, integer operaties worden namelijk pas vanaf SSE2 ondersteund. Verder verschillen float en integer operaties niet zo heel veel meer de laatste tijd.

[ Voor 6% gewijzigd door PrisonerOfPain op 06-10-2007 15:18 ]

[Pete]

Hier de output van MarcJ (duurde even, ik moest g++ nog installeren)

INTEGERS: 0 (ms) value = 1000000000
FLOATS: 7140000 (ms) value = 1.677722e+07
DOUBLES: 6920000 (ms) value = 1.000000e+09

Integers geen tijd?

Ik heb trwn mijn eigen script even aangepast dat aan het eind van een functie de waarde geprint word. En toen was de output:

100000000
INTEGERS: 3610 (ms)
16777216.000000
FLOATS: 821 (ms)
100000000.000000
DOUBLES: 824 (ms)

Oftewel, ik denk niet dat het de gcc-optimalisatie is.

PrisonerOfPain schreef op zaterdag 06 oktober 2007 @ 15:17:
[...]

Waarschijnlijk SSE optimalisaties van je compiler, integer operaties worden namelijk pas vanaf SSE2 ondersteund. Verder verschillen float en integer operaties niet zo heel veel meer de laatste tijd.

Aha, daar heb ik dus niet zoveel verstand van (van instructiesets enzo). Maar toch denk ik niet dat dat het is. Want:

$ cat /proc/cpuinfo | grep flags
flags           : fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush mmx fxsr sse sse2 syscall nx mmxext fxsr_opt lm 3dnowext 3dnow up pni lahf_lm ts fid vid ttp tm stc

Mijn processor heeft ook gewoon sse2

[bobo1on1]

C:

#include <stdio.h>
#include <sys/time.h>
#include <stdlib.h>
#include <time.h>

#define LOOPS           100000000

int intvalues[LOOPS];
int floatvalues[LOOPS];
int doublevalues[LOOPS];


void fillvalues()
{
    srand((unsigned int)time((time_t *)NULL));
    int i;
    for (i = 0; i < LOOPS; i++)
    {
        intvalues[i] = rand();
        floatvalues[i] = intvalues[i];
        doublevalues[i] = intvalues[i];
    }
}

int sum_integer() {
    int sum = 0;
    long i;
    for (i = 0; i < LOOPS; i++) {
        sum += intvalues[i] * intvalues[LOOPS - i - 1];
    }
    return sum;
}

float sum_float() {
    float sum = 0;
    long i;
    for (i = 0; i < LOOPS; i++) {
        sum += floatvalues[i] * floatvalues[LOOPS - i - 1];
    }
    return sum;
}

double sum_double() {
    double sum = 0;
    long i;
    for (i = 0; i < LOOPS; i++) {
        sum += doublevalues[i] * doublevalues[LOOPS - i - 1];
    }
    return sum;
} 

long giveMiliseconds(struct timeval *tm1, struct timeval *tm2){
        long segundos = tm2->tv_sec - tm1->tv_sec;
        long micros = tm2->tv_usec - tm1->tv_usec;

        if(micros < 0){
                segundos-=1;
                micros+=1000000;
        }

        micros = (long) ((float)micros /1000);

        return segundos*1000 + micros;

}
int main(void){
        struct timeval tm1, tm2;
        struct timezone tz1, tz2;
        int test1;
        float test2;
        double test3;
    
        fillvalues();
    
        gettimeofday(&tm1, &tz1);
        test1 = sum_integer();
        gettimeofday(&tm2, &tz2);
        printf("INTEGERS: %ld (ms)\tValue: %i\n",giveMiliseconds(&tm1, &tm2), test1);

        gettimeofday(&tm1, &tz1);
        test2 = sum_float();
        gettimeofday(&tm2, &tz2);
        printf("FLOATS: %ld (ms)\tValue: %f\n",giveMiliseconds(&tm1, &tm2), test2);

        gettimeofday(&tm1, &tz1);
        test3 = sum_double();
        gettimeofday(&tm2, &tz2);
        printf("DOUBLES: %ld (ms)\tValue: %f\n",giveMiliseconds(&tm1, &tm2), test3);
        
    
        return(0);
}

Als ik dit draai:

code:

bob@bob:~/Projects/test3/src$ ./test3 
INTEGERS: 364 (ms)      Value: 1212783852
FLOATS: 428 (ms)        Value: 3317307539456.000000
DOUBLES: 414 (ms)       Value: 3316927536364.000000

Dat lijkt er al meer op.

Output van ps aux:

code:

USER       PID %CPU %MEM    VSZ   RSS TTY      STAT START   TIME COMMAND
bob      16141  131 39.6 1175540 766760 pts/2  R+   15:45   0:02 ./test3

Hij slurpt wel wat veel geheugen, 39,6% van mijn 2 gb

@hierbeneden: haal eens een nulletje van de LOOPS macro weg.

[ Voor 6% gewijzigd door bobo1on1 op 06-10-2007 15:48 ]

[Pete]

bobo1on1 schreef op zaterdag 06 oktober 2007 @ 15:42:

Dat lijkt er al meer op.

Bij mij niet :

INTEGERS: 7916 (ms)     Value: -1378325916
FLOATS: 1290 (ms)       Value: 184172232704.000000
DOUBLES: 1660 (ms)      Value: 183305267812.000000

[Marcj]

Ik zie het al. De deling is met een integer veel trager dan met een float/double. Dit zal wel komen door de snelle FPU van de Athlon. Ga maar eens alleen vermenigvuldigen, dan is de integer wel sneller.

[Pete]

Marcj schreef op zaterdag 06 oktober 2007 @ 15:57:
Ik zie het al. De deling is met een integer veel trager dan met een float/double. Dit zal wel komen door de snelle FPU van de Athlon. Ga maar eens alleen vermenigvuldigen, dan is de integer wel sneller.

Het script van bobo1on1 bevat ook al geen delingen meer. En zoals je kunt zien duren de integer operaties daar ook stukken langer.

Ho, stop. Ik heb het script even een paar keer meer uitgevoerd en nu zijn ze wel ong gelijk:

peter@ubuntu-laptop-peter:~/Desktop/Operating systems test$ ./testgot2
INTEGERS: 7916 (ms)     Value: -1378325916
FLOATS: 1290 (ms)       Value: 184172232704.000000
DOUBLES: 1660 (ms)      Value: 183305267812.000000
peter@ubuntu-laptop-peter:~/Desktop/Operating systems test$ cp testgot2.c testgot3.c
peter@ubuntu-laptop-peter:~/Desktop/Operating systems test$ nano testgot3.c 
peter@ubuntu-laptop-peter:~/Desktop/Operating systems test$ ./testgot2
INTEGERS: 1282 (ms)     Value: 578230852
FLOATS: 1616 (ms)       Value: -13230940356608.000000
DOUBLES: 1288 (ms)      Value: -13227921040828.000000
peter@ubuntu-laptop-peter:~/Desktop/Operating systems test$ ./testgot2
INTEGERS: 1206 (ms)     Value: 143694422
FLOATS: 1219 (ms)       Value: -10406974193664.000000
DOUBLES: 1213 (ms)      Value: -10406562063786.000000
peter@ubuntu-laptop-peter:~/Desktop/Operating systems test$ ./testgot2
INTEGERS: 2487 (ms)     Value: -685650060
FLOATS: 1690 (ms)       Value: 13197860929536.000000
DOUBLES: 1522 (ms)      Value: 13197748850548.000000

Dan zou het idd aan de delingen liggen. Maar dan vind ik het nog vreemd dat een Floatingpoint deling sneller is dan een integer deling.

[ Voor 60% gewijzigd door Pete op 06-10-2007 16:04 ]

[PrisonerOfPain]

phsmit schreef op zaterdag 06 oktober 2007 @ 15:30:
Mijn processor heeft ook gewoon sse2

Dat geeft niet aan of je compiler ook voor die instructieset optimaliseert; dat heeft namelijk niets met je huidige processor te maken.

[Pete]

PrisonerOfPain schreef op zaterdag 06 oktober 2007 @ 16:25:
[...]


Dat geeft niet aan of je compiler ook voor die instructieset optimaliseert; dat heeft namelijk niets met je huidige processor te maken.

Als ik het dus goed begrijp optimaliseerd gcc niet voor sse2. Waarom gebeurt dat dan niet? Is die functionaliteit niet aanwezig of hebben ze een andere reden om niet voor sse2 te optimaliseren?

[PrisonerOfPain]

phsmit schreef op zaterdag 06 oktober 2007 @ 16:34:
[...]

Als ik het dus goed begrijp optimaliseerd gcc niet voor sse2. Waarom gebeurt dat dan niet? Is die functionaliteit niet aanwezig of hebben ze een andere reden om niet voor sse2 te optimaliseren?

Daar valt niets nuttigs over te zeggen zonder compiler flags; maar je kunt die optimalisaties handmatig aan of uit zetten (dus of optimaliseren voor SSE of voor SSE2 of voor SSE3 et cetera). Compile je toevallig met -march=athlon-xp of iets wat daar op lijkt? Misschien dat je hier iets wijzer van word.

[Olaf van der Spek]

phsmit schreef op zaterdag 06 oktober 2007 @ 16:34:
Als ik het dus goed begrijp optimaliseerd gcc niet voor sse2. Waarom gebeurt dat dan niet? Is die functionaliteit niet aanwezig of hebben ze een andere reden om niet voor sse2 te optimaliseren?

Waarschijnlijk omdat de code dan niet meer werkt op processors die geen SSE2 ondersteunen.

[MSalters]

Een ander probleem kan registerdruk zijn. Je loop variabele is altijd een integer.

[voodooless]

't loont ook wel degelijk om even met de compilerflags te spelen. Ik heb even bobo1on1 in "[C] Integer calculation langzamer dan fl..." gecompileerd met verschillende flags OSX, GCC 4.0.1

-O5 lijkt hier geen goed idee, met floats is het namelijk meer dan dubbel zo traag:

voodoobook:~/gcctest christiaan$ ./test 
INTEGERS: 214 (ms)      Value: 646840824
FLOATS: 459 (ms)        Value: 798481799184384.000000
DOUBLES: 440 (ms)       Value: 778162821530104.000000

t.o.v -O2:

voodoobook:~/gcctest christiaan$ ./test 
INTEGERS: 206 (ms)      Value: -1839375904
FLOATS: 220 (ms)        Value: -32458289774067712.000000
DOUBLES: 223 (ms)       Value: -43198581039081464.000000

Sorry jongens, een C2D 2.16 kicked ass met zijn 4 MB cache

[RayNbow]

Marcj schreef op zaterdag 06 oktober 2007 @ 15:57:
Ik zie het al. De deling is met een integer veel trager dan met een float/double. Dit zal wel komen door de snelle FPU van de Athlon. Ga maar eens alleen vermenigvuldigen, dan is de integer wel sneller.

phsmit schreef op zaterdag 06 oktober 2007 @ 16:01:
[...]
Dan zou het idd aan de delingen liggen. Maar dan vind ik het nog vreemd dat een Floatingpoint deling sneller is dan een integer deling.

Citaten uit een oude post, RayNbow in "[ASM] x86 vermenigvuldigen (quick)":

quote: http://www.gamedev.net/co.../topic.asp?topic_id=19973

[...]
Actually, fmul is somewhere around 3-5 cycles (same for fadd).

Little summary:

           fmul  fadd   fdiv    (i)mul  (i)div
PPro/PII :  5/2   3/1  17f/36d     4
PIII     :  5/2   3/1  18f/32d     4
Athlon   :  4/1   4/1  16f/20d    4-5    ~40
K6(-2)   :  2/2   2/2              2
Pentium  :  3/1   3/1             11     ~40

fmul and fadd : 5/2 - result after 5 cycles / may start new operation each second cycle
fdiv - delay for float/double

quote: http://www.gamedev.net/co...topic.asp?topic_id=146697

That used to be true on old-skool microprocessors.

At some point, most integer instructions (except for divide and square root) started having a pipeline latency of one cycle, and the difference between bit shifts and multiplies disappeared (except for scheduling constraints). THEN, in a mysterious, un-fathomable decision, Intel decided to make bit shifts SLOWER than multiplies in the Pentium IV. Go figure.

Note that bit masking is still faster than modulo, though, as modulo inherently is a division operation:

fast = foo & 127;
slow = foo % 128;

Let wel, dit is oude informatie...

[Wolfboy]

Als reactie op RayNbow z'n post, hier een lijst van processors met de cpu cycles per instructie: http://www.agner.org/optimize/instruction_tables.pdf