[an error occurred while processing this directive] [an error occurred while processing this directive][an error occurred while processing this directive] [an error occurred while processing this directive] [an error occurred while processing this directive] [an error occurred while processing this directive] (none) [an error occurred while processing this directive] [an error occurred while processing this directive] [an error occurred while processing this directive] [an error occurred while processing this directive] [an error occurred while processing this directive][an error occurred while processing this directive] [an error occurred while processing this directive][an error occurred while processing this directive] [an error occurred while processing this directive][an error occurred while processing this directive] [an error occurred while processing this directive] [an error occurred while processing this directive] [an error occurred while processing this directive] (none) [an error occurred while processing this directive] [an error occurred while processing this directive] [an error occurred while processing this directive][an error occurred while processing this directive]
 
[an error occurred while processing this directive] [an error occurred while processing this directive]
Skåne Sjælland Linux User Group - http://www.sslug.dk Home   Subscribe   Mail Archive   Forum   Calendar   Search
MhonArc Date: [Date Prev] [Date Index] [Date Next]   Thread: [Date Prev] [Thread Index] [Date Next]   MhonArc
 

Re: [PROGRAMMERING] Performance: C contra Ada



On Tue, 02 Mar 2004 17:16:53 +0100, Jakob Oestergaard wrote:

> On Tue, Mar 02, 2004 at 02:40:57PM +0100, Michael Rasmussen wrote:
> ...
>> > Hvis du er interesseret, kan vi godt prøve at analysere nogle konkrete
>> > kodeeksempler.
>> > 
>> Det kunne være spændende. Jeg sidder netop med et underligt problem i
>> C++ contra Java, hvor en trådbaseret løsning af fibonaci både
>> iterativ/rekursiv viser voldsomme udsving performancemæssig i den
>> rekursive tråd - Java er her 20% hurtigere end C++! Mig ikke forstå:-(
> 
> Som udgangspunkt; hvis Java er hurtigere end C++ så har du gjort noget
> forkert    (/me dukker hovedet  ;)

Så så... :)

Faktisk er det et interessant lille problem. Jeg får det samme resultat
på min maskine (PIV 2.0GHz): (Alt tråd halløjet er fjernet, kun den rene 
rekursive algoritme) 

Fib([0..40]):

java: ca 8s   (java -server)
c++: ca 12s

Det er med gcc 3.2, og Sun's jdk 1.4.2. Såvidt jeg husker betyder -server
at hele klassen bliver JIT'et i starten.

Den eneste forklaring jeg umiddelbart kan se er at JIT oversætteren
bruger en anden calling-convention ved funktionskald, som er mere
effektiv. Det kunne være interessant at lave et script der afprøvede
alle permutationer af gcc optimerings flag for at se om de gør nogen
forskel, der er et par stykker der justerer netop hvad der sker ved
funktionskald. 

Som en lille side bemærkning blev jeg lidt skuffet over den højt
besungne JIT oversætter, med alle dens teoretiske muligheder for
dynamiske optimeringer. 

Man kan omskrive den rekursive Fibonacci funktion til en halerekursiv
udgave:

long long doRecTail(const long long  n, long long sum) 
{
  if (n < 2)
    return 1 + sum;
  else {
    long long tmp = doRecTail(n-1,0); 
    return doRecTail(n - 2, tmp + sum);
  }
}

Som pænt bliver oversat til: (gcc -S -O -foptimize-sibling-calls)

...
.L5:
        testl   %esi, %esi
        jg      .L2
        testl   %esi, %esi
        js      .L3
        cmpl    $1, %ebx
        jbe     .L3
.L2:
        pushl   $0
        pushl   $0
        movl    %ebx, %eax
        movl    %esi, %edx
        addl    $-1, %eax
        adcl    $-1, %edx
        pushl   %edx
        pushl   %eax
        call    doRecTail
        addl    $-2, %ebx
        adcl    $-1, %esi
        addl    %eax, -16(%ebp)
        adcl    %edx, -12(%ebp)
        addl    $16, %esp
        jmp     .L5       <<< hop istedet for kald
...

Men Sun's JVM laver ikke denne optimering hvilket man kan overbevise sig
ved at lave en uendelig halerekursiv funktion, hvilket udløser et
stackoverflow.

Men ok, man må give dem at de _er_ hurtigere end C til at beregne
Fibonacci tal :)

Mvh Morten



 
Home   Subscribe   Mail Archive   Index   Calendar   Search

 
 
Questions about the web-pages to <www_admin>. Last modified 2005-08-10, 22:43 CEST [an error occurred while processing this directive]
This page is maintained by [an error occurred while processing this directive]MHonArc [an error occurred while processing this directive] # [an error occurred while processing this directive] *