Friday, August 24, 2012

Potential Speed Improvements in CPython

There’s a very interesting new group discussing static type checking in Python.  Lots of big names and big brains are there.

The obvious win of static type checking is having robuster code sooner.  Linting is always good.

Less obvious is that the output of a static type checker - the annotated AST - is actually the input for a compiler.  In a sense, shedskin for example is a static type checker too.

You could spit out native code as shedskin does.  However, I see a middle-ground that suites CPython:

Focus only on the analysis of each function, and not a call/reference graph.

For each function, a Static Single Type Assignment (SSTA) filter followed by an escape filter would tell us several things for each SSA:

  1. the variable is passed in so must be boxed on the heap
  2. the variable always escapes so must be boxed on the heap
  3. the variable sometimes escapes, so must be boxed on the heap as it escapes (I believe the CLR has this optimisation but cannot find my source)
  4. the variable is a non-escaping primative so can be on the stack using new VM op-codes to access
  5. the variable is dynamic typed, but not escaping, so the box/tag can go on the stack but value must go on the heap
  6. and so on…

Hopefully, large numbers of local variables could now routinely end up on the stack.  I would anticipate this being a big performance win; certainly worth prototyping.

(Excuses of why I personally don’t have time available on request)

Notes

  1. williamedwardscoder posted this

 ↓ click the "share" button below!