 |
Compiler
Papers
Books
Generated Code
Optimization
Parallelization
Parallel
Tools
Grammars
Papers
Interesting papers on programming languages (under
construction)
Books
Good books on compiler construction:
- Modern Compiler Design, Grune, Bal, Jacobs,
Langendoen
- Advanced Compiler Design Implementation, Steven S.
Muchnick
- High Performance Compilers for Parallel Computing, Michael
Wolfe
- Modern Compiler Implementation in Java Andrew W.
Appel
.. and on programming language design in general:
- Programming Language Design Concepts, David A. Watt
Generated Code
To debunk some myth about sneaky Java optimizations by saving
some checks in a loop and instead catch the out-of-bound exception
of the array that is iterated over to end the loop: It does not
work - not on any tested compiler. I checked Sun's Hotspot on Linux
(version 1.4.2 and 1.5.0), on Solaris 8 (version 1.2.2), on Mac OS
X (version 1.4.2) and gcj on
Linux (version 3.3), on Mac OS X (version 4.0.1). The compilers all
succeed in removing the unnecessary 2nd check in the straight
forward implementation; this makes the exception-driven loop even
slower as the exception itself takes some extra time.
Here is the code so you can check for yourself:
public class Test {
static int[] k;
static int size = 10000000;
public static void main( String args[] ) {
long time_r = 0;
long time_e = 0;
for( int i = 0; i < 100; i++ ) {
time_r += reasonable();
k = null; //avoid out of memory exception
time_e += exception();
k = null; //avoid out of memory exception
}
System.out.println( "reasonable: " + time_r/100 );
System.out.println( "exception: " + time_e/100 );
}
public static long reasonable() {
int i[] = new int[size];
int j = 0;
long time = System.currentTimeMillis();
for( j = 0; j < i.length; j++ ) {
i[j] = j;
}
time = System.currentTimeMillis() - time;
k = i; //avoid removal of loop by compiler optimizations
return time;
}
public static long exception() {
int i[] = new int[size];
int j = 0;
long time = System.currentTimeMillis();
try {
while( true ) {
i[j++] = j;
}
} catch( Exception e ) {}
time = System.currentTimeMillis() - time;
k = i; //avoid removal of loop by compiler optimizations
return time;
}
}
This C language example shows, that your compiler uses some kind
of intermediate language. At least with gcc (3.3, 4.0) this code snippet produces
identical binaries for each define (A, B, C, D). Of course everyone
familiar with the Church-Turing
Thesis shouldn't be too surprised... ;)
#include <stdio.h>
int main( char* args[] ) {
#ifdef A
while(1) {
printf( "hello" );
}
#elif B
do {
printf( "hello" );
} while(1);
#elif C
mark:
printf( "hello" );
goto mark;
#elif D
for(;;) {
printf( "hello" );
}
#endif
return 0;
}
Optimization
Some links about compiler optimizations (under
construction)
Parallelization
Parallel
Though not a parallelizing compiler, there are
parallel compilers, too:
- The LLVM compiler
infrastructure, a compiler framework centered around an advanced
intermediate language definition
- flex, very well
done scanner generator (flex
doc)
- bison, yacc
compatible parser generator (bison
doc)
- treecc, a tool
to create abstract syntax trees (integrates with yacc/bison).
(treecc
docs)
- byacc, the BSD
version of yacc
- byaccj, extended
BSD yacc that can e. g. generate Java code
- lemon, the parser
generator in use by sqlite
- Java Cup,
Java LALR parser generator
- JLex,
scanner generator for use with Java
-
gcc frontend howto, create your very own gcc frontend
Grammars
|
 |