[scala-tools] Compiler books

[Erkki Lindpere-2]

Can anyone recommend a good book or online resource on compilers that
would help understand the Scala compiler?

I want to create a plug-in that does vector math optimizations*, but
I've never studied compilers and many things in the compiler seem really
foreign to me.

* I think scalar replacement is what it's called -- given the type
Vector2(x: Float, y: Float) { /* operations */ }, I want to replace
1) local variables:
  val v = new Vector2(1f, 2f)  -->  val v$x = 1f; val v$y = 2f
2) any operations on Vectors with operations on Floats
3) any escaping vectors with new Vector2(v$x, v$y) -- most of the time
they will not escape

Or should I just wait until JIT can do this better? :)

Erkki

[Miles Sabin]

On Sun, Jun 28, 2009 at 11:26 PM, Erkki Lindpere<erkki@...> wrote:
> * I think scalar replacement is what it's called -- given the type
> Vector2(x: Float, y: Float) { /* operations */ }, I want to replace
> 1) local variables:
>  val v = new Vector2(1f, 2f)  -->  val v$x = 1f; val v$y = 2f
> 2) any operations on Vectors with operations on Floats
> 3) any escaping vectors with new Vector2(v$x, v$y) -- most of the time they
> will not escape
>
> Or should I just wait until JIT can do this better? :)

Before trying to do this by hand, have you tried the
-XX:+DoEscapeAnalysis option of recent Sun JVMs?

Cheers,


Miles

--
Miles Sabin
tel: [phone]
skype:  milessabin
http://www.chuusai.com/
http://twitter.com/milessabin

[Erkki Lindpere-2]

Yes. It helps (~15% overall improvement), but not as much as manual
scalar replacement in source code has helped.

Erkki

Miles Sabin wrote:

> On Sun, Jun 28, 2009 at 11:26 PM, Erkki Lindpere<erkki@...> wrote:
>  
>> * I think scalar replacement is what it's called -- given the type
>> Vector2(x: Float, y: Float) { /* operations */ }, I want to replace
>> 1) local variables:
>>  val v = new Vector2(1f, 2f)  -->  val v$x = 1f; val v$y = 2f
>> 2) any operations on Vectors with operations on Floats
>> 3) any escaping vectors with new Vector2(v$x, v$y) -- most of the time they
>> will not escape
>>
>> Or should I just wait until JIT can do this better? :)
>>    
>
> Before trying to do this by hand, have you tried the
> -XX:+DoEscapeAnalysis option of recent Sun JVMs?
>
> Cheers,
>
>
> Miles
>
>  

[Erkki Lindpere-2]

Also, I'm counting Vector2 allocations (in a companion object field) and
turning on -XX:+DoEscapeAnalysis does not remove a single allocation.
The Vector2 class actually looks something like this:

case class Vector2(x: Float, y: Float) {
  def +(a: Float) = Vector2(x + a, y + a)
  def -(a: Float) = Vector2(x - a, y - a)
  def *(a: Float) = Vector2(x * a, y * a)
  def /(a: Float) = Vector2(x / a, y / a)
  // rest of operations
}

I also tried making the class, it's methods and fields final but that
didn't change anything either. Scala's -optimize and -Yinline also had
no effect on performance (with relevant methods marked @inline final).

Erkki

Erkki Lindpere wrote:

> Yes. It helps (~15% overall improvement), but not as much as manual
> scalar replacement in source code has helped.
>
> Erkki
>
> Miles Sabin wrote:
>> On Sun, Jun 28, 2009 at 11:26 PM, Erkki Lindpere<erkki@...> wrote:
>>  
>>> * I think scalar replacement is what it's called -- given the type
>>> Vector2(x: Float, y: Float) { /* operations */ }, I want to replace
>>> 1) local variables:
>>>  val v = new Vector2(1f, 2f)  -->  val v$x = 1f; val v$y = 2f
>>> 2) any operations on Vectors with operations on Floats
>>> 3) any escaping vectors with new Vector2(v$x, v$y) -- most of the
>>> time they
>>> will not escape
>>>
>>> Or should I just wait until JIT can do this better? :)
>>>    
>>
>> Before trying to do this by hand, have you tried the
>> -XX:+DoEscapeAnalysis option of recent Sun JVMs?
>>
>> Cheers,
>>
>>
>> Miles
>>
>>  
>

[Miles Sabin]

On Sun, Jun 28, 2009 at 11:54 PM, Erkki Lindpere<erkki@...> wrote:
> Also, I'm counting Vector2 allocations (in a companion object field) and
> turning on -XX:+DoEscapeAnalysis does not remove a single allocation.

As in you have the ctor increment a companion object field?
-XX:+DoEscapeAnalysis shouldn't have any effect on that count whether
it manages to inline objects into the stack or not.

Cheers,


Miles

--
Miles Sabin
tel: [phone]
skype:  milessabin
http://www.chuusai.com/
http://twitter.com/milessabin

[Erkki Lindpere-2]

Of course, I should have thought of this: the optimizer mustn't remove
side effects. Anyway, even with escape analysis turned on, I'm still
getting bigger improvements from manually inlining (doing scalar
replacement on) the vector operations.

Miles Sabin wrote:

> On Sun, Jun 28, 2009 at 11:54 PM, Erkki Lindpere<erkki@...> wrote:
>  
>> Also, I'm counting Vector2 allocations (in a companion object field) and
>> turning on -XX:+DoEscapeAnalysis does not remove a single allocation.
>>    
>
> As in you have the ctor increment a companion object field?
> -XX:+DoEscapeAnalysis shouldn't have any effect on that count whether
> it manages to inline objects into the stack or not.
>
> Cheers,
>
>
> Miles
>
>  

[Daniel Spiewak]

I can give you some general compiler book suggestions.  None of these will specifically help you with Scala, but they should give you a decent idea of what needs to happen in any good compiler:

• The Purple Dragon book (http://www.amazon.com/Compilers-Principles-Techniques-Tools-2nd/dp/0321486811/ref=sr_1_1?ie=UTF8&s=books&qid=1246239528&sr=8-1).  This is really the book for compiler architecture and implementation.  If you can understand the material in this book, you should be able to figure out 90% of what happens in Scala's compiler.
  
• Programming Language Pragmatics (http://www.amazon.com/Programming-Language-Pragmatics-Third-Michael/dp/0123745144/ref=sr_1_1?ie=UTF8&s=books&qid=1246239596&sr=1-1).  Not strictly a compilers text, but I like it anyway.  It does a better job of laying out the basics of compilers than the dragon book, but doesn't get into anywhere near as much depth.
• Types and Programming Languages (http://www.amazon.com/Types-Programming-Languages-Benjamin-Pierce/dp/0262162091/ref=sr_1_1?ie=UTF8&s=books&qid=1246239654&sr=1-1).  Very, very good introduction to type theory.  This should help with that remaining 10%.
  

You might also look around for papers on parsing techniques, just because they're that cool.  :-)  Scala has a hand-written parser which I believe uses recursive-descent, but I haven't looked closely enough to be sure.  For what you're doing, you shouldn't have to change anything in the syntactic analysis, but it's still worth knowing at least generally what's going on in that arena.

Daniel

On Sun, Jun 28, 2009 at 5:26 PM, Erkki Lindpere <erkki@...> wrote:

Can anyone recommend a good book or online resource on compilers that would help understand the Scala compiler?

I want to create a plug-in that does vector math optimizations*, but I've never studied compilers and many things in the compiler seem really foreign to me.

* I think scalar replacement is what it's called -- given the type Vector2(x: Float, y: Float) { /* operations */ }, I want to replace
1) local variables:
 val v = new Vector2(1f, 2f)  -->  val v$x = 1f; val v$y = 2f
2) any operations on Vectors with operations on Floats
3) any escaping vectors with new Vector2(v$x, v$y) -- most of the time they will not escape

Or should I just wait until JIT can do this better? :)

Erkki

[Tony Sloane]

On 29/06/2009, at 8:26 AM, Erkki Lindpere wrote:

> Can anyone recommend a good book or online resource on compilers  
> that would help understand the Scala compiler?

For a good introduction that is easy to read but also covers quite a  
bit of depth, I can recommend Modern Compiler Design by Grune et al. (http://www.cs.vu.nl/~dick/MCD.html 
).

cheers,
Tony

[Erkki Lindpere-2]

Thanks for the suggestions! I'll order some of these books.

However, while they arrive, could someone give me a hint how to do
scalar replacement in a transformer:

// Given this method
def compute(v1: Vector2) = { val v2 = v1 + 2f; v2 }
// I want it to transform it to this
def compute(v1: Vector2) = {
  val v2$x = v1.x + 2f
  val v2$y = v2.y + 2f
  Vector2(v2$x, v2$y)
}
// Nevermind that in this particular case there is no performance
improvement

In a transformer if I match on ValDef(...) I can do the replacement, but
what should I return?
I must return a single tree, but I have two trees that need to replace
the first one.

Maybe I should do this with a different method, not with the tree
transformer class?
Or perhaps I should create a new tree subtype that is eliminated in a
next phase?

Sorry if these are dumb questions :)

Erkki

Erkki Lindpere wrote:

> Can anyone recommend a good book or online resource on compilers that
> would help understand the Scala compiler?
>
> I want to create a plug-in that does vector math optimizations*, but
> I've never studied compilers and many things in the compiler seem
> really foreign to me.
>
> * I think scalar replacement is what it's called -- given the type
> Vector2(x: Float, y: Float) { /* operations */ }, I want to replace
> 1) local variables:
>  val v = new Vector2(1f, 2f)  -->  val v$x = 1f; val v$y = 2f
> 2) any operations on Vectors with operations on Floats
> 3) any escaping vectors with new Vector2(v$x, v$y) -- most of the time
> they will not escape
>
> Or should I just wait until JIT can do this better? :)
>
> Erkki
>

[Erkki Lindpere-2]

Sorry, nevermind, I got it working. Returned Sequence(List(xValDef,
yValDef)) and later "flattened" it in the block where it appeared as a
statement.

Erkki Lindpere wrote:

> Thanks for the suggestions! I'll order some of these books.
>
> However, while they arrive, could someone give me a hint how to do
> scalar replacement in a transformer:
>
> // Given this method
> def compute(v1: Vector2) = { val v2 = v1 + 2f; v2 }
> // I want it to transform it to this
> def compute(v1: Vector2) = {
>  val v2$x = v1.x + 2f
>  val v2$y = v2.y + 2f
>  Vector2(v2$x, v2$y)
> }
> // Nevermind that in this particular case there is no performance
> improvement
>
> In a transformer if I match on ValDef(...) I can do the replacement,
> but what should I return?
> I must return a single tree, but I have two trees that need to replace
> the first one.
>
> Maybe I should do this with a different method, not with the tree
> transformer class?
> Or perhaps I should create a new tree subtype that is eliminated in a
> next phase?
>
> Sorry if these are dumb questions :)
>
> Erkki
>
> Erkki Lindpere wrote:
>> Can anyone recommend a good book or online resource on compilers that
>> would help understand the Scala compiler?
>>
>> I want to create a plug-in that does vector math optimizations*, but
>> I've never studied compilers and many things in the compiler seem
>> really foreign to me.
>>
>> * I think scalar replacement is what it's called -- given the type
>> Vector2(x: Float, y: Float) { /* operations */ }, I want to replace
>> 1) local variables:
>>  val v = new Vector2(1f, 2f)  -->  val v$x = 1f; val v$y = 2f
>> 2) any operations on Vectors with operations on Floats
>> 3) any escaping vectors with new Vector2(v$x, v$y) -- most of the
>> time they will not escape
>>
>> Or should I just wait until JIT can do this better? :)
>>
>> Erkki
>>
>

[Erkki Lindpere-2]

My optimizer is progressing nicely. But I'm stuck with something:
occasionally I cache some expressions in synthetic method-local
variables, and I want to replace other occurences of these
expressions/trees with Ident(varName) of the variable where the tree is
already cached.

I'm trying to use for this purpose an extended HashMap:
    val cache = new collection.mutable.HashMap[Tree, Name] {
      override def elemEquals(key1: Tree, key2: Tree) = key1
equalsStructure key2
      override def elemHashCode(key: Tree) = key.hashCodeStructure
    }

However, it seems that even if the trees I want to replace produce equal
hashCodes with the one cached (using hashCodeStructure), they do not
equal (using equalsStructure). Is this correct? And if so, is there
something else I can use or must I implement my own tree comparison?

Erkki L

Erkki Lindpere wrote:

> I want to create a plug-in that does vector math optimizations*, but
> I've never studied compilers and many things in the compiler seem
> really foreign to me.
>
> * I think scalar replacement is what it's called -- given the type
> Vector2(x: Float, y: Float) { /* operations */ }, I want to replace
> 1) local variables:
>  val v = new Vector2(1f, 2f)  -->  val v$x = 1f; val v$y = 2f
> 2) any operations on Vectors with operations on Floats
> 3) any escaping vectors with new Vector2(v$x, v$y) -- most of the time
> they will not escape
>
> Or should I just wait until JIT can do this better? :)
>
> Erkki
>

[Erkki Lindpere-2]

Sorry, user error :) It works just fine!

Erkki

Erkki Lindpere wrote:

> My optimizer is progressing nicely. But I'm stuck with something:
> occasionally I cache some expressions in synthetic method-local
> variables, and I want to replace other occurences of these
> expressions/trees with Ident(varName) of the variable where the tree
> is already cached.
>
> I'm trying to use for this purpose an extended HashMap:
>    val cache = new collection.mutable.HashMap[Tree, Name] {
>      override def elemEquals(key1: Tree, key2: Tree) = key1
> equalsStructure key2
>      override def elemHashCode(key: Tree) = key.hashCodeStructure
>    }
>
> However, it seems that even if the trees I want to replace produce
> equal hashCodes with the one cached (using hashCodeStructure), they do
> not equal (using equalsStructure). Is this correct? And if so, is
> there something else I can use or must I implement my own tree
> comparison?
>
> Erkki L
>
> Erkki Lindpere wrote:
>> I want to create a plug-in that does vector math optimizations*, but
>> I've never studied compilers and many things in the compiler seem
>> really foreign to me.
>>
>> * I think scalar replacement is what it's called -- given the type
>> Vector2(x: Float, y: Float) { /* operations */ }, I want to replace
>> 1) local variables:
>>  val v = new Vector2(1f, 2f)  -->  val v$x = 1f; val v$y = 2f
>> 2) any operations on Vectors with operations on Floats
>> 3) any escaping vectors with new Vector2(v$x, v$y) -- most of the
>> time they will not escape
>>
>> Or should I just wait until JIT can do this better? :)
>>
>> Erkki
>>
>