[Cython] Visitors and speed issues

[Robert Bradshaw]

On May 12, 2008, at 1:43 AM, Dag Sverre Seljebotn wrote:

> 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.

I am very surprised that the results are so close--I'm getting a 14x  
speedup for cdef vs. def methods in my tests.

> 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?

My hope is that Cython will have an option intelligently turn some  
classes/methods into cdef classes/cpdef methods without forcing the  
user to be explicit (as part of making it a good Python compiler).

> (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
> _______________________________________________
> Cython-dev mailing list
> Cython-dev at codespeak.net
> http://codespeak.net/mailman/listinfo/cython-dev