[Cython] Visitors and speed issues

[Dag Sverre Seljebotn]

Gary Furnish wrote:
> Efficiency does matter to Sage though, and an O(1) overhead is very
> far from negligible.  Cython uses real C vtables, so there are
> absolutely no dict-based lookups involved with cdef class
> polymorphism.  -Infinity to any proposal that makes code slower.

This is interesting; if there's a real-world, noticeable speed penalty 
to dict-based visitors then I agree they should be made vtable-based 
instead. I'd like to discuss it a bit more first though:

Just to have more data I benchmarked this on my own computer; 10^7 
visitor lookups were done in a loop. Doing everything as typed as 
possible (all arguments typed, all classes and methods cdef-ed) it took 
1.7 seconds, while using a full-blown dict-lookup (with 100 items in the 
dict) it took 8.4 seconds.

Assuming an "average" file has 10 000 nodes syntax tree nodes in it, and 
that there will be 40 visitors passing through the tree in a 
compilation, that gives ~0,07 seconds for typed and ~0,34 seconds for 
dict-based, ie a difference in 0,27 seconds per file. So on 100 files 
that is half a minute wasted.

I don't know if that is much or little, how long does Cython spend on 
compiling 100 files of 10 000 nodes today?

So far all is well. However, the problem is that Cython code is not 
using cdef classes, nor typing the method arguments! Nor will "cdef 
class" be likely to hit the source, because even if we'd like to be able 
to compile it, it is a must that it can use the Python interpreter in 
order to compile Cython with Cython (we don't want to bother with having 
a bootstrapping chain for Cython I think...).

So in order to cash out on this one must first make Python code produce 
cdef classes with typed method signatures. Of course full-blown 
inference of this is not needed, decorator support (or some comment 
format support, if we want it compilable in Python 2.3) could be used 
instead.

Thoughts?

(BTW, when I said O(1) I was referring to class construction, which 
happens once per invocation of Cython, not dict lookups (in this context 
I consider dict lookups as giving an "O(n) penalty", since there would 
be a constant number of them per node, and the number of nodes is 
proportional to input file size). If the invocation time of Cython is a 
problem then one better just have Cython compile many files in one 
process session, the Python interpreter starts up relatively slowly 
anyway...)


-- 
Dag Sverre