compiler optimization tracker

[JeffBezanson]

This is an umbrella issue for compiler and other low-level optimizations. I'm including ones that are already done, to make it more interesting.

compiler:

• static method lookup
• basic inlining
• null check elimination
• function type check elimination
• method lookup hoisting
• function-valued argument inlining (WIP: redesign closures, then generic functions #13412)
• variable type specialization
• varargs allocation elision
• lambda lifting
• native calling convention
• hoist n-d array metadata loads
• hoist 1-d array metadata loads (partial: Add support for @simd  #5355, more via LLVM TBAA)
• hoist access to fields in immutable values (partial: Use tbaa for heap-allocated immutables #8867)
• skip gc frame when possible
• avoid re-boxing non-assigned variables
• unboxed struct layout
• apply tuple lowering: apply(f, t::(T,S)) => f(t[1],t[2])
• apply tuple elision: apply(f, (x,y)) => f(x,y)
• temporary tuple elision
• create and return tuples as structs (elide more tuple allocations #1976, more efficient tuple representation #2496)
• early freeing by dataflow analysis (gc enhancements #261)
• don't pass or store 0-field structs
• rerun type inference after inlining in some cases
• handle more constant conditions in inference (partial: add a lattice element type for constants in inference #15785)
• remove excess temp vars
• pool environments of inner functions
• inline builtins
• better inlining of apply()
• inline invoke() (Performance of invoke #9608)
• inline isdefined() (Optimize isdefined on normal objects in codegen #19334)
• more general inlining
• constant-fold type applications
• direct call methods specialized for non-leaf types
• closure environment specialization
• static keyword argument sorting (WIP static dispatch for kwargs and structural fields #16580)
• compute first field of a new object before allocating, to avoid the unnecessary NULL store to the first slot
• identify types (especially immutable) that are always fully initialized, to avoid undefined checks on their fields (Avoid undefined checks for fields that are always initialized #8827)
• skip gc root for variables with stable values (e.g. vars that only alias arguments)
• avoid redundant loads of single-assigned variables from gc frame
• possibly hoist boxing out of tight loops (might interfere with gc though?)
• faster possibly-undefined variables (optimize undefined variables better #6914)
• constant-propagation and CSE of pure functions (constant-propagation for @pure functions #14324)

RTS:

• compress ASTs
• method hash tables
• more efficient method and cache representation
• gc: 1-bit refcount (gc enhancements #261)
• flatten arrays of tuples
• use realloc in growing arrays (complicated by alignment constraints)
• avoid extra buffer copy in uv_write
• allow scheduler to be a function call, avoiding double task switch to get to next task
• avoid some stack copies in Task; e.g. for tasks that never yield

larger projects:

• bounds check elimination
• cache generated code (suggestions for faster startup #260)
• inlining function arguments
• henchmen unrolling
• better type info for tasks/produce/consume
• SIMD support (SIMD types #2299)

performance-related features:

• inbounds macro (RFC: macros for disabling bounds checks #3268, Provide mechanism for turning off bounds checking #1392)
• bounds check intrinsic
• sizeof intrinsic
• expose llvm select (inlined, eager-evaluated conditional function)
• inline declaration (inline keyword? #1106)
• pure function declaration (Pure function notation #414)
• improve behavior of globals (Type annotations in global scope #964)
• better support for in-place ops (Improvement needed for inplace arithmetics #3424, in-place assignment operator? #249, Functions that produce results in pre-defined outputs #1115, Vectorization Roadmap #16285)

[ViralBShah]

This is a really nice and useful tracker! We should also link these to our release notes.

[timholy]

It's not obvious to me that you gave yourself credit for your awesome recent work in making let faster :-). Presumably it's bundled into something else?

Thanks for this list. Mildly embarrassed by how many of the issues were filed by me, without me being able to do much to fix most of them.

[timholy]

...but here I go again...

In addition to "flatten arrays of tuples" is it at all feasible to "flatten arrays of types with fixed size"? See https://groups.google.com/d/msg/julia-dev/QOZfPkdRQwk/O-DgzNxbQegJ.

[StefanKarpinski]

We did ask for "ungracious demands" from the outset ;-)

[lindahua]

Great stuff! I believe this will take the performance of Julia to a new height when done.

[blakejohnson]

What about the kind of constant folding Stefan mentions in #2741 ?

[IainNZ]

Thinking out loud: how hard would it be to set up something like http://speed.pypy.org/ ?
On the server it seems clear what is required, but do we have a good body of performance tests? If this is something desirable, I'm sure its something the community could pull together without any demands on core developers...

[staticfloat]

@IainNZ; I'm working on that right now. :)

We have a small corpus of performance tests in test/perf2 but I do believe we will need some work to come up with small, self-contained and relevant performance tests. I will open an issue regarding this in the near future, once I have more concrete work done.

[JeffBezanson]

related: 620141b

[malmaud]

I'd be interested in helping out on one of these issues, but I don't want to step on anyone's toes or duplicate effort. Can I get some guidance on which of these issues is in need of manpower?

[staticfloat]

@JeffBezanson Is "bounds check elimination" covered by @inbounds?

[JeffBezanson]

No; ideally there should be some automatic bounds check removal.

[johnmyleswhite]

What level of automaticity do you have in mind? I'd love it if bounds-checking were automatically turned off for loops that look like:

for i in 1:length(x)
    x[i] += 1
end

[JeffBezanson]

Yes, that's the kind of case that can be handled automatically.

[ArchRobison]

By the way, the TBAA support in #5355 partially fixes the ``hoist 1-d array metadata loads'' item. It's partial because bounds checks will stop the hoisting because LLVM can't prove it's legal and profitable to hoist a load up over a branch.

[yuyichao]

@staticfloat Is there any update on having a performance test suite and sth similar to speed.pypy.org. I found it very useful when working on optimizations (in addition to running the current tests to make sure I'm not breaking anything) to have somthing like this to measure the performance gain (or regression in some cases). Would be awesome to have github integration but sth I can run locally is also good enough.

[JeffBezanson]

Running make in test/perf will run our benchmark suite.

[ghost]

@yuyichao: There is also the Julia Speed Center.

Edit: It appears to not have any new updates since June 2014 though, which was around when I last had a look at it.

[ViralBShah]

@staticfloat can shed some light on the history there.

[staticfloat]

Yes, I think @yuyichao was hinting at that when he pinged me. Essentially, I just haven't had time to rewrite speed.julialang.org in something more flexible than the original adaptation from the codespeed project. It's the next big Julia project I will tackle, but unfortunately time for big projects is thin for me at the moment.

[ViralBShah]

Is it fair to tick off SIMD types on this list with tuple overhaul?

[ihnorton]

I think ensuring proper alignment for SIMD is still TODO.
On Apr 23, 2015 9:12 AM, "Viral B. Shah" notifications@github.com wrote:

Is it fair to tick off SIMD types on this list with tuple overhaul?

—
Reply to this email directly or view it on GitHub
#3440 (comment).

[ArchRobison]

My impression is that recent Intel SIMD hardware is much less performance picky about alignment than it used to be, but I have not run experiments.

[simonster]

One bit that is (I think?) still missing is the ability to do vectorized arithmetic on tuples (or something that wraps them) without llvmcall.

[ArchRobison]

The optional (under -O) SLPVectorizer pass used to vectorize tuple arithmetic without any special wrapper. But it is failing to do so.

[pao]

My impression is that recent Intel SIMD hardware is much less performance picky about alignment than it used to be, but I have not run experiments.

And getting good performance out of less-recent hardware shouldn't be ignored if it's reasonable to get.

[ScottPJones]

OK, this is great (thanks for the reference that led me here @timholy) Which boxes that are not checked are already largely in place? Thanks.

[timholy]

I certainly am not qualified to give a whole list, but "more general inlining" and "inline declararation" are presumably largely done (there are still ambitions to introduce inlining as controlled from the call site), and there's already some bounds check elimination and SIMD support.

[vtjnash]

checked off:
better type info for tasks/produce/consume (Channels)
SIMD support (#2299)
more general inlining
inline declaration (#1106)
pure function declaration (#414)

since the basic version of each of these has been implemented

[eschnett]

You may want to add @fastmath code generation.

[vtjnash]

Checked off a few more. We now have all of these, or they are tracked in another existing issues.