20. januar 2012 - 17:00Der 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.
"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.
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?
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).
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.
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.
Synes godt om
Ny brugerNybegynder
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.
