Julia: compiler performance

[JeffBezanson]

This is a tracking issue for work on speeding up the compiler itself. Between LLVM 3.7 and the upcoming jb/functions we have significant slowdowns. Dealing with this is becoming quite urgent. All phases of the system could use improvement.

Front end

• Options for improving flisp performance
  
  
  
  • Try using Gambit-C again
  
  
  • Write an flisp bytecode-to-llvm compiler (can be a static compiler)
  
  
  • Hand compile the front end code to C
  
  

• Clean up lowering passes (julia-syntax.scm). Probably at least 2-3 of them can be combined or removed. (#14997)

  IR

• AST representation needs to be more compact and include better debug info #15609, #14949, #15583

  • Eliminate jl_compress_ast
• More efficient Slot representation (#15951)

• (Maybe) make GenSym/SSAVal assignments implicit, i.e. just statement indexes

  Type inference

• Use workqueue instead of recursion #15300

• More efficient lookup structure for cached inferred trees #15779
• Don't keep as many trees around (e.g. ones too big to be inlined) (#15970)
• Method-cache-style widening before invoking recursive inference, to cut down workload
• Fewer specializations
• Const lattice element (#15785)
• combine tfunc and specializations arrays (#15918)

• allow type inf to always allocate new LambdaInfos to avoid copies in both specializations and method cache

  Other

• Use generated functions less

• There is sometimes a regression due to #15934 believed to be largely fixed

  Codegen

• Run more things in an interpreter, avoiding codegen entirely (#15855)

• Codegen time might be slightly super-linear in total amount of code (see https://github.com/JuliaLang/julia/pull/14845#issuecomment-176579441) #15632
• Quadratic jit debug info registration (#14846) gdb bug, not Julia
• Add -O0 option
• Run fewer optimization passes (basically just mem2reg), e.g. on code with poor type information
• When 2 specializations of a function have the same LLVM IR, reuse the native code
• Use less memory (#14626)
• Improvements inside LLVM
• calling convention for constant functions that fully avoids codegen (#16837)

Some specific issues:

• #6685 Slow compilation with many comprehensions
• #14113 AST representation with many constants
• #14556 egal bottleneck

[Keno]

When 2 specializations of a function have the same LLVM IR, reuse the native code

I've been thinking about this. We could try hashing the IR code, but we'd have to do some work to avoid spurious differences due to naming things, etc., e.g. we could name all functions after a hash of their IR. Of course this'll also seriously complicate backtraces/debug info.

[JeffBezanson]

this'll also seriously complicate backtraces/debug info

Would this be mitigated if we started by only considering different specializations of the exact same method? I imagine we could do a reasonably quick experiment to see if this might be profitable.

[Keno]

Would this be mitigated if we started by only considering different specializations of the exact same method? I imagine we could do a reasonably quick experiment to see if this might be profitable.

Yes for backtraces, no for debug info, but I think it might be fixable.

[StefanKarpinski]

The approach I had contemplated was replacing actual debug info with some sort of template values and then when you get a cache hit, use the previously generated code but with the debug info "template" filled in. Not sure how well that could be made to work though.

[Keno]

I think the biggest problem is to know which of the specializations you're in while walking the stack. You could potentially do it by looking at the local variables of the parent frame and the trying to figure out which one would have had to have been called.

[StefanKarpinski]

What I'm was describing would result in different specialized versions (with different debug info), but would reuse the generated code, so it would save time but not memory. Of course, that's not as good as using the _same_ generated code, but that seems much harder.

[Keno]

Ah, I understand

[ViralBShah]

Wasn't gambit a bit buggy when we first tried it in the very early days? I guess it should be easy to try it out and run PkgEvaluator.

[ViralBShah]

An flisp to llvm bytecode compiler could also be a great JSOC project. We need to announce JSOC soon too.

[StefanKarpinski]

I think that compiler performance is a little too important to hang our hopes on a JSoC project.

[ViralBShah]

Of course we wouldn't hang our hopes on it, but there is no harm in mentioning it as a potential candidate project - in case we don't get around to doing it.

[felipenoris]

Is there any update on which solution will be given to improve flisp performance?

[timholy]

Check out https://github.com/JuliaLang/julia/pulls?q=is%3Apr+author%3AJeffBezanson+is%3Aclosed for some of Jeff's PRs which have already implemented some of the solutions.

[andreasnoack]

On my laptop, generic_matmatmul! takes 0.5 seconds to compile on 0.5 and 0.3 seconds on 0.3 (and 0.4). Even though the function is ~200 lines, it seems too slow in general and is probably one the main time consumers in the linear algebra tests.

It might be related to #16434 and, therefore, we should probably also look into the effects of splitting up the function. It might be much faster to compile six smaller versions.

[JeffBezanson]

With a quick look, a significant amount of compile time for generic_matmatmul! is in alloc_elim_pass.

[JeffBezanson]

Still to go here: #16837

[JeffBezanson]

There's also an especially bad case in #17137 we should fix.

[PallHaraldsson]

"Try using Gambit-C again", "Scheme" wasn't obvious (well I guess implied by flisp..):

https://en.wikipedia.org/wiki/Gambit_(scheme_implementation)

Is FemtoLisp on the way out? If/when this works? I see recent issues on a REPL for it..

[ViralBShah]

@PallHaraldsson This is just adding noise by asking such questions here. Best to do it on julia-users.

[vtjnash]

Doesn't seem to be anything left on this list worth doing / tracking with a meta issue.