Avatar billede Druesukker Nybegynder
20. januar 2012 - 17:00 Der er 13 kommentarer og
1 løsning

Lille compiler

Hey...
Jeg er ved at læse en bog der handler om at lave compilers og interpreters.
Source koden der følger med bogen er skrevet i java, jeg har dog valgt at lave det i C++, bl.a. for at blive bedre til C++.

Min C++ kode er næsten en-til-en med java koden og jeg arbejder derfor næsten hele tiden med pointers til objekter (i stedet for referencer). Indtil videre har jeg lavet begyndelsen til en lexical analyser (scanner).

Den følgende metode laver de nye tokens. (Bliver kaldt en gang for hvert bogstav i kildekoden som skal compiles):

Token *PascalScanner::extractToken()
{
  if(currentChar()== EOF)
      return new EofToken(source);  // last token
  else
      return  new Token(source);    // normal token
}

Jeg skulle da lige prøve at teste køretiden af min C++ udgave mod Java udgaven som fulgte med bogen.

Det viser sig dog at Java udgaven er i stand til at læse en kildekode på 1,000,000 linjer og lave 38,000,000 Tokens på 1.5 sek.

Min C++  udgave(compilet med g++ -O2) kan lige snige sig ned på at bruge 6 sek.

Hvordan kan det lade sig gøre at Java udgaven er så meget hurtigere, taget i betragtning at koden næsten er en-til-en.

I øjeblikket bruger jeg kun den sidste token af alle dem som bliver konstrueret.
Min C++ udgave bruger over 2 GB RAM når den læser en kildekode på 1,000,000 linjer. Og java udgaven bruger ikke særligt meget.

(1)
- Er det muligt at JVM er i stand til at forudse dette og måske genbruge hukommelse i stedet for at lave et helt nyt objekt?
- Er det mig som har skrevet et elendigt C++ program?
- Eller ?

Dette er dog ikke mit eneste spørgsmål. Jeg ville lige prøve at lave et lille program som skulle finde fib(45) hvor:
fib(n) = fib(n - 1) + fib(n - 2).

Jeg skrev programmet i 6 forskellige programmeringssprog:
C++    ca.: 9 sek.
C      ca.: 6 sek.
jwasm  ca.: 18 sek.
gas asm ca.: 18 sek.
D      ca.: 18 sek.
Java    ca.: 4 sek.

Nu er der da først noget galt.
Min assembly kode er 3 gange langsommere end min C kode.
Og det er ikke fordi jeg er en dårlig asm programmør.

Jeg kan måske forstå hvis Java er hurtigere end de native compiled sprog. Måske fordi JVM finder et mønster i koden og dermed kan optimere mens programmet kører.

(2)
Men: C/C++ vs asm wtf?
Avatar billede arne_v Ekspert
20. januar 2012 - 17:22 #1
Jeg tror muligvis at du er en daarlig assembler programmoer.

En ting er at skrive assembler osm virker og er mulig at vedligeholde - noget helt andet er at skrive hurtigst mulig assembler.

Med moderne super pipelinede CPU'er skal instruktionerne arrangeres meget "grimt" for at koere optimalt.

Men du kan jo proeve at lade C++ compileren gemme assembler kode og kigge paa den!
Avatar billede arne_v Ekspert
20. januar 2012 - 17:24 #2
Det at C++ bruger meget mnere memory end Java antyder ret kraftigt at du mangler at faa deallokeret noget memory i din C++ version.

Saa du skal nok igang med at java memory leaks.
Avatar billede arne_v Ekspert
20. januar 2012 - 17:28 #3
"Java er alt for langsomt i forhold til C/C++" er en myte som har overlevet fra engang midt i 1990'erne.

Men i de fleste tilfaelde boer du med lidt fiflen med C/C++ koden kunne lave den 0-10% hurtigere end Java.

For din compiler kan det vaere memory forbruget som ogsaa paavirker CPU forbruget.

Det kan ogsaa vaere et streng problem. C char[] og C++ STL string er lidt addons til sprogene mens Java String er mere indbygget (og JVM laver mig bekendt special cases for optimering af String). Saa det sker at Java er hurtigere naar det drejer sig om strenge.
Avatar billede arne_v Ekspert
20. januar 2012 - 17:29 #4
Hvis din compiler understoetter -O4 eller -O6 kunne du proeve dette.
Avatar billede Druesukker Nybegynder
20. januar 2012 - 19:25 #5
Tak for svarene...

Ja, du har ret i at asm skal stilles meget grimt op når man skal optimere det. Det er impornerende hvad compilere kan gøre ved ens kode.

C udgaven ser sådan her ud (den klarer fib(45) på 6 sek med optimering):
unsigned fib(unsigned num)
{
  if(num == 0) return 0;
  else if(num == 1) return 1;
  return fib(num - 1) + fib(num - 2);
}

Jeg fik min egen asm udgave ned på 11 sek (det er ulæseligt nu):
fib:
  test    DWORD PTR [esp + 4], 0FFFFFFFEh
  jnz L0                  ; if zero then arg <= 1
  mov eax, [esp + 4]
  ret   
L0:            ; arg > 1
  ; no stack frame
  sub esp, 4 
  push DWORD PTR [esp + 8]
  dec DWORD PTR [esp]     
  call fib                ; fib(arg - 1)
  mov [esp + 4], eax
  push DWORD PTR [esp + 12]
  sub DWORD PTR [esp], 2
  call fib                ; fib(arg - 2)
  add eax, [esp + 8]
  add esp, 12              ; rebuild from pushes and sub
  ret   

Mht compileren som jeg skriver i C++, RAM forbruget stammer fra den metode jeg viste i indlæget ( extractToken() ). Den laver 38,000,000 tokens med den .txt fil jeg tester med.

Du har nok ret i at det er det store hukommelses forbrug som gør C++ koden langsom.
I øjeblikket tester jeg min kode med følgende:
token = nextToken();
while(typeid(*token) != typeid(EofToken))
  token = nextToken();

I java koden bruges selvfølgelig isinstance i stedet for. (Den kalder nextToken() 38 mio gange)
Det er klart at JVM ikke vil lade 38,000,000 token pointers hænge.
Og laver derfor garbage collection. Java koden bruger kun omkring 300 MB.

Lige så snart jeg erstater: return new Token; med return t; i ( extractToken() ), hvor t blot er pointer til en Token som er blevet lavet i constructoren.
Så bliver hukommelses forbruget næsten 0 og programmet klarer det på lidt under 1 sek. (Stadig ikke i nærheden af Java).
Gør jeg det samme i Java koden kommer den ned på 0.30 sekund.

Hvorfor tror du Java er så meget hurtigere end de andre sprog?
Avatar billede arne_v Ekspert
20. januar 2012 - 19:42 #6
proev og se hvad compileren outputter for fib
Avatar billede arne_v Ekspert
20. januar 2012 - 19:45 #7
typeid er ogsaa en af de der ting som er kommet til C++ meget sentog jeg har en mistanke om at det ikke er specielt effektivt

Java er foedt med instanceof
Avatar billede arne_v Ekspert
20. januar 2012 - 19:46 #8
hvis Java kan GC'er de tokens, saa bruges de ikke laengere - og saa boer du ogsaa kunne delete dem i C++
Avatar billede Druesukker Nybegynder
20. januar 2012 - 20:29 #9
Jeg har allerede kigget på outputtet for fib.
Vil dog ikke lige bruge tid på at forstå det i dag...

Ja jeg kan sagtens delete de tokens. Jeg skal bare bruge dem når jeg skal til at lave min Parser.
En delete lige efter token objekterne er blevet construeret gør at
hukommelses forbruget er stort set ingen ting. Men programmet er ufatteligt langsomt (6 sek).

Det virker som om at hukommelses allokering og derefter construct af et nyt objekt er mellem 2 og 10 gange hurtigere i Java end C++ (på begge mine OS'er).

Du kan bare skrive et svar næste gang...
Avatar billede arne_v Ekspert
20. januar 2012 - 20:34 #10
Jeg tror mere paa at det er deallokering end allokering hvor Java er hurtig.

Java er meget hurtig til at deallokere en masse smaa objekter med meget kort levetid.

Den deallokerer dem nemlig slet ikke. Naar new generation skal GC'es, saa flytter den de objekter der stadig er i brug op i naeste generation og saa flytter "free pointeren" til starten af new generation heap.
Avatar billede arne_v Ekspert
20. januar 2012 - 20:34 #11
og et svar
Avatar billede Druesukker Nybegynder
20. januar 2012 - 20:57 #12
Det lyder som om det fungerer som brk interrupt på UNIX. Hvilket i så fald også burde gøre allokering hurtigere.
Men hvad ved jeg...

Tak for hjælpen.
Avatar billede Druesukker Nybegynder
20. januar 2012 - 21:46 #13
Jeg prøvede at tilføje Token objekterne til en ArrayList i Java så der ikke kunne laves GC. C++ brugte jeg en vector.

Nu er C++ markant hurtigere. Java kunne ikke allokere hukommelse nok til 38 mio tokens (med -Xmx2560m), på jeg testede med 19 mio i stedet for.

Java klarede det på gennemsnitligt 18 sek. og brugte 1.9 GB.
C++ klarede det på 4 sek. og brugte 1.1 GB.

Java har simpelthen ikke allokeret hukommelse til et objekt som ikke blev brugt til noget.
Avatar billede Druesukker Nybegynder
22. januar 2012 - 12:01 #14
Hvis nogen skulle være interesseret..
Jeg fandt ud af at min C compiler (med optimering) laver om på fib algoritmen, så den altid husker resultatet for det foregående fib(num - 1) i ESI.
Avatar billede Ny bruger Nybegynder

Din løsning...

Tilladte BB-code-tags: [b]fed[/b] [i]kursiv[/i] [u]understreget[/u] Web- og emailadresser omdannes automatisk til links. Der sættes "nofollow" på alle links.

Loading billede Opret Preview
Kategori
Kurser inden for grundlæggende programmering

Log ind eller opret profil

Hov!

For at kunne deltage på Computerworld Eksperten skal du være logget ind.

Det er heldigvis nemt at oprette en bruger: Det tager to minutter og du kan vælge at bruge enten e-mail, Facebook eller Google som login.

Du kan også logge ind via nedenstående tjenester