Part I: Compiling is slower, so it's bad

19 Jan 2008


      Part I: Compiling is slower, so it's bad
=========================================
This part will not talk about closures at all, just about the overall  
system archicture of the compiler.
I will write with Math something about Closures, their design and  
performance later.
Before I go into the details, I think I need to clearify one thing:  
from the start, I always saw Squeak in terms
of it's possibilities, never as "what it is now". I think all what  
follows comes from that point of view.
If you see Squeak an artifact that should never be changed, then you  
won't like any of the arguments that
follow. But I am truly convinced that the greatness of Squeak never  
was the artifact, it was always the possibility
it promised.
So.The Compiler is slower to compile code (factor ca. 4). But then,  
this is not that of a problem. Most people
will now think about the slowness of loading code with MC, but that  
has multiple causes, the compiler is not
the slowest thing here... (in 3.9, we managed to speed up code loading  
with MC by a factor of two just by caching
the class category in the "category" variable of the class objec).
Another "problem" of the NewCompiler is that it has far more classes  
then the old one. Horrible for some people,
but interestingly, this makes it far easier to understand than the old  
one...
So, Slower and More Classes. What do we get for that? Of course we  
need some payout. One is that the NewCompiler
is *far* easier to understand. I can explain it to a student in half  
an hour, and the student can hack it.
Slower. The Slowness is caused by two things: 1) Use of SmaCC for  
parsing 2) multi-pass visitor based architecture.
Before explaining (with examples) why both are indeed very nice to  
have, I will in this Part I just do a short overview of the  
architecture.
1) Scanning/Parsing. This is wher the text is analyzed and a tree- 
structure (AST) is build up. The NewCompiler does not
    implement the Scanner/Parser "by hand", but instead it uses a  
Parser-Generator. This is an application that takes a
    description of the Grammar of the language in a fairly  
standardized form (BNF). Then this is compiled using the Parser  
Generator
    to build the Scanner/Parser classes.
    The nice thing about this are three things:
    1) easier to understand and modify (grammar is formulated as a grammer)
    2) less bugs, as the grammar is transformed automatically. This is  
not that important for a simple language is Smalltalk.
    3) Easy to modify, Easy to add a slightly changed / extended  
Smalltalk-like language. (We see examples for that later)
    
    
2) The AST (Abstract Syntax Tree).
    This encodes the syntax as a tree. For a compiler, a very simple  
AST is mostly enough. For the NewCompiler, the AST of
    the Refactoring Browser was used instead. This is an overkill for  
a compiler, but it has some cool aspects:
    1) One AST for the sytem. No duplicated code between the RB and the  
Compiler. Less bugs.
    2) the RB can use the Parser of the Compiler. No problem with  
differences, less duplicated code.
    The nice thing about the RB AST are two things: Visitors and  
Transformations. Visitors are used a lot in the NewCompiler.
    
    
3) Now we have the AST. The AST does not encode any semantics yet,  
e.g. meaning of variables. We know that there is
    Variable "a", but is it a definition or use? Are variables  
shadowing each other?
    This we need to check and add information to all variables. For  
this, we have a Visitor that walks over the AST,
    grows a scope-chain for each block entered, records variable  
definitions, annotated variable uses with the definition
    that it referes to.
4) The annotated AST now can be used to generate Code. The NewCompiler  
uses a very nice small "Squeak Assembler" to emit
    the code. The class for Code Generation is ASTTranslator. Again a  
visitor, walks over the tree and calls IRBuilder to
    emit code.
    Here in ASTTranslator the magic happens for the inlining of if/and/ 
while and so on:
acceptMessageNode: aMessageNode
aMessageNode isInlineIf ifTrue: [^ self emitIfNode: aMessageNode].
    	aMessageNode isInlineIfNil ifTrue: [^ self emitIfNilNode:  
aMessageNode].
    	aMessageNode isInlineAndOr ifTrue: [^ self emitAndOrNode:  
aMessageNode].
    	aMessageNode isInlineWhile ifTrue: [^ self emitWhileNode:  
aMessageNode].
    	aMessageNode isInlineToDo ifTrue: [^ self emitToDoNode: aMessageNode].
    	aMessageNode isInlineCase ifTrue: [^ self emitCaseNode: aMessageNode].
    	^ self emitMessageNode: aMessageNode
Uncomment the line with "isInlineIfNil" --> no compiler generates  
normal message send for ifNil:. Easy.
    		
    
5) The IRBuilder. A symblic assembler for Squeak Bytecode. Here is an  
example of
    a method that compared the first iVar with the argument and  
returns yes or no
ir := RBuilder new
    		numRargs: 2;
    		addTemps: #(self a);		"rcvr, arg"
    		pushTemp: #self;
    		pushInstVar: 1;
    		pushTemp: #a;
    		send: #=;
    		jumpAheadTo: #else if: false;
    		pushLiteral: 'yes';
    		returnTop;
    		jumpAheadTarget: #else;
    		pushLiteral: 'no';
    		returnTop;
    		ir.
    		
    	we can run this method likes this:
    		
    	ir compiledMethod valueWithReceiver: (5@4) arguments: #(5)
As the "ir" suggests, this bytecode assembler does not directly  
generate bytecode,
    but it builds up an Intermediate Representation instead. This is  
nice, as it allows
    the backend to be changed quite easily, so changeing the bytecode  
encoding is easy
    with this kind of architecture. The other thing is that on the IR, we  
can do transformation,
    too. (example later).
The IRBuilder can be used to implement compiler for other  
languages, it's actually very simple
         to do: walk the AST of your language, call method on the  
IRBuilder. (Example later).
6) ByteCodeBuilder now is called by the IRBuilder to emit bytecode and  
build a compiledMethod object.
    This is the only class that encodes the actual bytecode set used.
So, comparing that to the old compiler, it's actually amazing that  
this is just slower by a factor of 4. It's not
a black box compiler, it's a "Compiler Framework" that can be used to  
experiment. Building yout own compiler
is simplified a lot with this framwork.
Part II will show some examples for how we used this compiler  
framework in the past. I will try to write that
later today.
There are some slides that explain all this in some more detail:
http://www.iam.unibe.ch/~denker/talks/07SCGSmalltalk/11Bytecode.pdf
Marcus
--
Marcus Denker  --  denker@iam.unibe.ch
http://www.iam.unibe.ch/~denker

About the new compiler, Part I

Part I: Compiling is slower, so it's bad

Marcus

Part I: Compiling is slower, so it's bad

Marcus

Part I: Compiling is slower, so it's bad