The Orctimizer: An optimizer for high-level concurrent programs#

Modern languages have made huge strides to alleviate the difficulties of managing concurrency. These languages provide facilities such as cooperative concurrent programming support (often called asynchronous programming) and futures. However, in most cases the programmer needs to choose when to apply these tools and when not to based on performance and semantics. This forces two intermixed programming styles: concurrent (often future-based) and traditional sequential.

The Orctimizer optimizes the concurrency in the program to eliminate unnecessary futures and other concurrency constructs. It is implemented as an optimization phase in a compiler. This allows the programmer to use futures anywhere they may be needed, and rely on the compiler to eliminate futures that are not needed based on its analysis of the program. The optimizations in this paper are applicable to many languages with futures, such as JavaScript, but are particularly applicable to language with implicit future creation and forcing.

A prototype implementation of the Orctimizer is available on the Orctimizer branch of the Orc git repository. There is a discussion of Orctimizer design choices and optimizations and analyses in OrctimizerDesignDocumentation.

Backend#

The current backend for the Orctimizer compiler stack is Porc. However, future work on the backend may avoid Porc and replace it with a direct Truffle-based interpreter of Orctimizer code. We could also consider writing a Truffle interpreter for Porc; however, a Truffle-based Orctimizer interpreter is likely to be able to speculatively modify itself better.

Truffle#

Truffle has many advantages. For instance, it automatically supports profile-based specialization and even function cloning when profiles do not match.

However, Truffle may not have fully mature thread support. This could result in problems with multiple threads executing the same code and perhaps degrade performance when different threads result in different profiles or the like. Truffle is at least thread-safe, so the concurrency of Orc will not be a correctness problem.

Older notes on this subject#

Adrian wrote some early notes on this subject that are saved in CompileToJvm. They may provide inspiration or perspective.

Plan#

The plan for the Orctimizer and refinement paper.

  • Develop Orctimizer type system
  • Write motivation (MCU, JavaScript)
  • Write prose description of Orctimizer
  • Implement Porc C/JavaScript backend for MCU/Web motivation
  • Implement Orctimizer with as good a Porc backend as I can
  • Measure secondary metrics
  • Compare performance with itself
  • Compare performance with Scala
  • Write evaluation section
  • Define exactly what I need to prove
  • Write correctness section
  • Write high-level manual proof sketches
  • Build Coq framework for proving refinements
  • Prove Orctimizer refinements
  • Write paper which shows the Orctimizater as an intermediate language for translating pervasively concurrent code for mostly sequential execution.
    • Introduction/Motivation. Novelty.
    • Pervasively concurrent programming for modern day problems.
    • Eliminating pervasive concurrency automatically.
    • Correctness and refinement.
    • Performance evaluation (secondary metrics and actual performance).
    • Related work.
    • Conclusion.

Deadline: Nov 15 (PLDI paper due)

Schedule#

Task [1] Start date [2] Finish date [2] People
Draft Orctimizer long-form paper Tue, Jun 21 Fri, Jul 8 Arthur
PLDI paper due Tue, Nov 15 Tue, Nov 15
PLDI rebuttal period Thu, Jan 26, 2017 Sat, Jan 28, 2017 Arthur
PLDI author notification Mon, Feb 13, 2017 Mon, Feb 13, 2017
CONCUR abstract due (approx.) Apr 11, 2017 Apr 11, 2017
CONCUR paper due (approx.) Apr 18, 2017 Apr 18, 2017

[#1] While sorting by date works, there is no way to return to the original order other than reloading the page.

[#2] When editing make sure that every cell in the date columns is a date (in some format, it's pretty flexible) or sorting will be lexical. The current convention is that header rows should have the earliest start date from their children and the latest end date that requires active work (other than going to the conference. The idea is that we will be able to pretty much forget about it other than the conference itself.

Add new attachment

Only authorized users are allowed to upload new attachments.
« This page (revision-9) was last changed on 28-Mar-2017 14:32 by Arthur Peters