[Psyco-devel] Important oversight in psyco_call_psyco [edited]

[Christian T. <ti...@st...>]

[this post had a few typos, here the correction]

While optimizing the snot out of generators, by calling them (now! 
Finally!) directly from psyco-compiled code, I stumbled suddenly over 
this huge chest of gold:

Whenever psyco compiles a function that calls a sub-function, it 
compiles that sub-function as well. This continues to the recursion 
limit of typically 10. In practice, that is in most cases everything  seen.

So far, so good. But here is the catch 22:

===> These compilations get never recorded, anywhere!

Consider a set of 5 functions f1..f5, where every function f[i] calls 
f[i+1] for i < 5. f1 compiles once. f2 compiles twice. f3 complies 4 
times, f4 8 times, and f5 16 times.

This sums up to 31 compilations for n = 5, 63 for n = 6, 1023 for n = 
10, or in general n**2-1.

And what happens if every f[i] calls f[i+1] three times for i < 5?

Compilations = 1 + 3 + 9 + 27 + 81 = 121. For n = 6 it is 364. For n = 
10 we get 9841.

In general, we get c**n/(n-1) calls for n functions calling their sub- 
functions c times.

So this is in fact polynomial behavior, and without doubt a huge win  to 
avoid. Of course, re-compiles do happen for every argument type 
pattern, but this will be only once.

cheers - chris