Tuesday, January 5, 2010

Optimize python functions by marking certain promises about its behavior : Python

promise: bytecode optimisation using staticness assertions.

This is a module for applying some simple optimizations to function bytecode. By promising that a function doesn't do certain things at run-time, it's possible to apply optimizations that are not legal in the general case.

Reddit Comments: Optimize python functions by marking certain promises about its behavior : Python: "
I gave a talk on this at our local users group a few weeks ago, the slides are online if anyone's interested:



The above presentation is really nice - great, simple example of the power of this technique.

I was thinking along these lines. Having code where we specify two "speeds":

(1) flexibility/expressiveness/global-mutability/side-effects-happen-globally-immediately are important (at cost to throughput and low-latency)

i.e. dispatch on pattern matching ASTs on global mutable list of patterns, global mutable generic functions, global mutable generic methods

Allow global mutable objects in general. All mutable state is handled like distributed-revision-control & write-on-change, with all communication going through a key-hole (enforcing low latency by throttling large data transfers) as asynchronous messaging as transactions (and building transactions).

Side effects are GO!  Allow global state to change, allow outside communication, all happening ASAP, might pre-calculate while waiting for reply, but wait to the bitter end for reply none-the-less.

(2) throughput and low-latency (performance) are important (at cost to flexibility/expressiveness/global-mutability) - no side effects (all "side-effect messages" are stored, to be returned as a group when function returns, maybe each "side-effect message" is paired with a continuation)

A simple directed acyclic graphImage via Wikipedia
i.e. dispatch on low level bytecode (think: LLVM), preferred data structures are immutable and have the "shape" of directed acyclic graph (possibly a much more restricted form of directed acyclic graph, where each node has an immutable index, and parent indexes are always less than child indexes), the limited explicitly mutable state is local to OS-thread or green-thread.  No traditional asynchronous side-effects allowed.

And there are speeds in the middle, by being explicit about what you are relaxing and what you are constraining. Typically, you expect to pay a "compiling" cost to get down to the low level bytecode - again, by being explicit, if you are doing a lot of this "compiling", you can improve by being explicit about what you are relaxing and what you are constraining.

Low-latency (ability to best react to asynchronous signals) will always be preferred over throughput. If you want to put throughput over low-latency, you have to explicitly say so, with the knowledge that you have very little influence over that isolated code (isolated so able to make no compromise in throughput)


Hey, cool.  People are trying "Promise" out on code in the wild.  Here is creator Ryan Kelly explaining how to make use of the bytecode improvements:


1. Ryan Kelly left...
2010.01.05 Tue 4:25 pm :: http://www.rfk.id.au/
Matt, thanks for taking the time to put this together. The optimizations applied by promise are certainly not in the same league as something like psyco - they have to be quite well targeted to have any measurable effect.
Some clarifications: promising a function pure() doesn't optimise that function at all, but it can speed up things that call that function by inlining its bytecode at the call site. To get this to work, you have to use constant() to promise that references to the pure function won't change. Example:

..def calculate(a,b):
......return a + 2*b
..def aggregate(pairs):

In this scenario, the bytecode for "calculate" will be inlined directly into the "aggregate" function and will save the overhead of many function calls.
By far the biggest speedup that can currently be obtained using promise is inlining pure functions that get called in a loop.
Reblog this post [with Zemanta]

No comments: