inline function call

[Riko Wichmann]

Re: inline function call

Peter Hansen wrote:[color=blue]
>
> Seeing what others have achieved is always educational to the ignorant,
> so I learned something. ;-)[/color]

Would have been even more educating, if I had my original code still at
hand for comparison, which unfortunately I didn't. But all the
improvements come from following the advises given in the URL I posted
earlier already:

http://wiki.python.org/moin/PythonSpeed/PerformanceTips

Cheers,

Riko

[Christopher Subich]

Re: inline function call

Diez B. Roggisch wrote:[color=blue]
> No. That is simply impossible in python as well as in java where functions
> are always virtual, meaning they are looked up at runtime. Because you'd
> never know _which_ code to insert of all the different foo()-methods that
> might be around there.[/color]

Not quite "simply impossible" -- inlining function/method calls could
indeed be an optimization done (eventually) by PyPy or another
Psyco-like optimizer. In this case, function inlining is just something
that You Can Do if you dynamically determine that the function is a
constant object.

Since it is an optimization that makes an assumption about the constancy
of an object, this wouldn't hold true in the general case; an
interpreter which makes that dynamic optimization would need some degree
if checks to make sure that the assumption remains valid.

So it's not technically impossible, at least in the majority of cases
where functions are neither modified nor rebound, no current python
interpreter makes that assumption.

[Bengt Richter]

Re: inline function call

On Thu, 05 Jan 2006 08:47:37 +1100, Steven D'Aprano <steve@REMOVETH IScyber.com.au> wrote:
[color=blue]
>On Wed, 04 Jan 2006 13:18:32 +0100, Riko Wichmann wrote:
>[color=green]
>> hi everyone,
>>
>> I'm googeling since some time, but can't find an answer - maybe because
>> the answer is 'No!'.
>>
>> Can I call a function in python inline, so that the python byte compiler
>> does actually call the function, but sort of inserts it where the inline
>> call is made? Therefore avoiding the function all overhead.[/color]
>
>The closest thing to that is the following:
>
>
># original version:
>
>for i in xrange(100000):
> myObject.someth ing.foo() # three name space lookups every loop
>
>
># inline version:
>
># original version:
>
>foo = myObject.someth ing.foo
>for i in xrange(100000):
> foo() # one name space lookup every loop
>[/color]
But that isn't in-lining, that's hoisting some expression-evaluation
out of a loop on the assumption that the expression has constant value
and no side effects. That's good optimization, but it isn't in-lining.
Inlining is putting code to accomplish what foo does in place of the foo call.
E.g. if under simple conditions and assumptions you in-lined

def foo(x,y):return 2*x+y+1
in
a = 3*foo(b,c)

the code would be

a = 3*(2*b+c+1)

This could be achieved by a custom import function that would capture the AST
and e.g. recognize a declaration like __inline__ = foo, bar followed by defs
of foo and bar, and extracting that from the AST and modifying the rest of the
AST wherever foo and bar calls occur, and generating suitable substitutions of
suitable AST subtrees generated from the ASTs of the foo and bar ASTs and rules
for renaming and guaranteeing safe temporary names etc. The modified AST would
then pass through the rest of the process to compilation and execution for the
creation of a module. You just wouldn't be able to plain old import to do the
importing (unless you had the custom import hooked in, and assumed that sources
without __inline__ = ... statements would not occur unintended.

Without hooking, usage might look like

import inliner
mymod = inliner.__impor t__('mymod') # side effect to mymod.pyc and sys.modules

and then you could expect calls to designated and defined inline functions in mymod.py
to have been inlined in the code of mymod.

I've been meaning to do a proof of concept, but I've hinted at these things before,
and no one seems much interested. And besides it's really a distraction from more radical
stuff I'd like to try ;-)

Regards,
Bengt Richter

[Michael Spencer]

Re: inline function call

Bengt Richter wrote:
....[color=blue]
>
> This could be achieved by a custom import function that would capture the AST
> and e.g. recognize a declaration like __inline__ = foo, bar followed by defs
> of foo and bar, and extracting that from the AST and modifying the rest of the
> AST wherever foo and bar calls occur, and generating suitable substitutions of
> suitable AST subtrees generated from the ASTs of the foo and bar ASTs and rules
> for renaming and guaranteeing safe temporary names etc. The modified AST would
> then pass through the rest of the process to compilation and execution for the
> creation of a module.[/color]

I've thought about a similar approach, but I suspect that pure AST
transformations (i.e., source-code inlining) would work only in a few special
cases. General inlining would require, I guess:

* Munging the names of the in-lined local function variables, e.g., prepending
them with the name of the inlined function, and perhaps a sequence number
* Inserting a set of assignments to replicate the parameter-passing
* Replacing the return statement (there would have to be only one) with another
assignment

In order for the assignment operations to take place in an expression list, the
modifications would have to happen at the byte-code level. It may be possible
to modify compiler.pycode gen.ModuleCodeG enerator to do most of the work. Or
perhaps the new pypy compiler might be more amenable to experimenting - I
haven't looked at it.
[color=blue]
>
> I've been meaning to do a proof of concept, but I've hinted at these things before,
> and no one seems much interested. And besides it's really a distraction from more radical
> stuff I'd like to try ;-)
>
> Regards,
> Bengt Richter[/color]

Might be fun to try

Michael

[Xavier Morel]

Re: inline function call

Peter Hansen wrote:[color=blue]
> Riko, any chance you could post the final code and a bit more detail on
> exactly how much Psyco contributed to the speedup? The former would be
> educational for all of us, while I'm personally very curious about the
> latter because my limited attempts to use Psyco in the past have
> resulted in speedups on the order of only 20% or so. (I blame my
> particular application, not Psyco per se, but I'd be happy to see a
> real-world case where Psyco gave a much bigger boost.)
>
> Thanks,
> -Peter
>[/color]

Someone I know created an application to compute Markus Lyapunov
fractals (aka heavy mathematical computations) (he pretty much did it to
learn Python).

Last time I checked, his code ran in roughly 3 minutes (179s) on my box
(Athlon64/3000+) without psyco and 46 seconds with psyco enabled under
Windows 2000.

Someone else got respectively 2mn34s and 13s (without and with psyco) on
a Linux box with an Athlon XP 2600+ (same frequency as my 3200+ btw, 2GHz).

My tests show a 74% speedup, and the Linux test shows a 91% speedup.

In any case, the gain is significant because the actual code is very
short (less than 200 lines, and the algorithm itself fits in under 50
lines) and is called very often (from my notes, the main function is
called 160000 times during the computation of the fractal)