E compilers / static analysis

I've been continuing to investigate the performance issues with E, and
I've put some very experimental stuff on a new "static" branch:

http://gitorious.org/~tal-itinnov/repo-roscidus/it-innovation/commits/static

This is not ready for merging, but comments welcome.


I split EExpr.eval(scope) into two steps. EExpr.compile(scope)
transforms the E and returns a CompiledE Thunk, which holds the
transformed E and its scope. Calling the thunk runs the code. e.g.

? def kernelE := e`def double(x) { return 2 * x }`
# value: e`def double {
#            
#            method run(x) {
#                escape __return {
#                    __return.run(2.multiply(x))
#                    null
#                }
#            }
#        }`

? def compiled := kernelE.compile(safeScope)
# value: compiled-e`def double {
#            
#            method run(x) {
#                2.multiply(x)
#            }
#        }`

? def double := compiled()
# value: <double>

? double(4)
# value: 8

This makes it easy to see which optimisations E is actually doing, and
makes it easy to cache the results for speed.

Before, EExpr was doing its own caching (badly). Here's a test case:

def timeit(cb) {
	for x in 0..100 {
		cb()
	}
	def t1 := timer.now()
	for x in 0..10000 {
		cb()
	}
	def t2 := timer.now()
	return t2 - t1
}
def orig := e`require(true)`
for x in 1..4 {
	def ti := timeit(fn { orig.eval(safeScope) } )

	println(`Time: $ti ms`)
}

This takes around 10s using svn trunk's E (with the built-in caching):

Time: 11134 ms
Time: 10690 ms
Time: 10549 ms
Time: 10581 ms

Using the "static" branch's eval/1 (which is just the same but with the
caching *removed*):

Time: 730 ms
Time: 794 ms
Time: 367 ms
Time: 342 ms

And using compile/1 first and then doing eval on that:

Time: 299 ms
Time: 212 ms
Time: 106 ms
Time: 145 ms

I updated ImportLoader to cache CompiledE objects and evaluate them
again each time you import. This fixes the performance problem I
reported previously with <import>, in
http://www.eros-os.org/pipermail/e-lang/2010-February/013443.html

Importing the same file using svn's <import>:

Took: 15354 ms
Took: 15676 ms

Importing using my ELoader (svn trunk):

Took: 464 ms
Took: 495 ms

Using ELoader ("static" branch):

Took: 248 ms
Took: 212 ms

Using the new ImportLoader ("static" branch):

Took: 31 ms
Took: 29 ms


Those are the main changes that improve performance. The static branch
also has some other optimisations. These are sometimes OK in
micro-benchmarks but don't have much effect overall on my main code. I
guess there's some other performance-killer at work, but these might be
useful in the future:

- I pass Scope to BindFramesVisitor (not just ScopeLayout). A comment
said passing ScopeLayout only is to help compilers, but a compiler can't
do any useful optimisations without knowing what some of the values will
be.

- I turn references to final outer slots into LiteralExprs with the
value. e.g. "true", "false" and "null" no longer evaluate
"context.outers(i).get()" each time they're evaluated.

- A CallExpr with a receiver known at compile time turns into a
FastCallExpr with a shortened Script. This doesn't seem to help
performance at all, surprisingly, but it did find three bugs in my code
(untested error paths where I did "Ref.problem(...)" instead of
"Ref.broken(...)".

- SeqExprs have literals removed (except for the last one). If the
removed value isn't null, a warning is printed because code that has no
effect is usually a bug. Currently this won't find many bugs because we
don't expand many constants.

- CallExprs where the receiver is <type> and the value is known are
called at compile time. Guard.coerce(known) is also expanded. This
doesn't help much either, but I think it will be handy for inferring
types later.


-- 
Dr Thomas Leonard
IT Innovation Centre
2 Venture Road
Southampton
Hampshire SO16 7NP

Tel: +44 0 23 8076 0834
Fax: +44 0 23 8076 0833
mailto:tal-v5nx5w6akNyLE8xUarVfuPLx9OUvmyODWmv/[email protected]
http://www.it-innovation.soton.ac.uk