10874
Comment:
|
11483
|
Deletions are marked like this. | Additions are marked like this. |
Line 5: | Line 5: |
= Prologue = With the recent improvements in Cython/SageX, many of these suggestions are handled implicitly and give very little benefits for a large drawback in code readability. |
|
Line 11: | Line 15: |
HOWEVER... it is ''hard work'' to make your Pyrex as fast as C. It's very easy to get it wrong, essentially ''because'' Pyrex makes it all look so easy. This purpose of this document is to collect together the experiences of SAGE developers who have learned the hard way. | HOWEVER... it is ''hard work'' to make your Pyrex as fast as C. It's very easy to get it wrong, essentially ''because'' Pyrex makes it all look so easy. This purpose of this document is to collect together the experiences of SAGE developers who have learned the hard way. [''Cython'' does a lot of this hard work for you.] |
Line 259: | Line 263: |
This is also true for pure python. |
|
Line 308: | Line 314: |
''Cython Update'' There is still a slight speed difference, but it is almost negligable. The code automatically detects lists/tuples at runtime and uses the PyXxx_GET_ITEM code if it can. This is much safer to, as calling PyTuple_GET_ITEM on a non-tuple or with bad bounds results in a segfault. (Not to mention easier to read). | |
Line 374: | Line 381: |
* If no exception occurs, overhead is really tiny | * If no exception occurs, overhead is really tiny. |
[ this page is permanently under construction ]
Prologue
With the recent improvements in Cython/SageX, many of these suggestions are handled implicitly and give very little benefits for a large drawback in code readability.
Introduction
This page describes some techniques for writing really fast Pyrex code. It is aimed at SAGE developers who are working on low-level SAGE internals, where performance is absolutely crucial.
Pyrex is a very unusual language. If you write Pyrex as if it were Python, it can end up running more slowly than Python. If you write it like you're writing C, it can run almost as fast as pure C. The amazing thing about Pyrex is that the programmer gets to choose, pretty much line by line, where along the Python-C spectrum they want to work.
HOWEVER... it is hard work to make your Pyrex as fast as C. It's very easy to get it wrong, essentially because Pyrex makes it all look so easy. This purpose of this document is to collect together the experiences of SAGE developers who have learned the hard way. [Cython does a lot of this hard work for you.]
Apart from the stuff on this page, by far the best way to learn how to make Pyrex code faster is to study the C code that Pyrex generates.
How to contribute to this document
Yes, please do! Make sure to follow these guidelines:
When you give an example, make sure to constrast a fast way of doing things with a slow way, especially if the slow way is more obvious. Show both versions of the Pyrex code, and show the generated C code as well, if you think that this is useful to see. (Remove the irrelevant parts of the C code, because it can get pretty verbose :-).)
- Let's keep this scientific: show some evidence of performance (e.g. timing data).
William Stein is writing a chapter for the programming guide: See [http://sage.math.washington.edu/sage/pyrex_guide].
cdef functions vs def functions
A cdef function in Pyrex is basically a C function, so calling it is basically a few lines of assembly language. A def function on the other hand is a Python function, and incurs the following overhead:
- The caller needs to construct a tuple object that holds the arguments.
- The call itself has to go via the Python API.
- The function being called needs to call the Python API to decode the tuple.
Additionally, in most cases:
- The caller has to do a name lookup to find the function. (But you can cache this if you're calling the same function many times.)
All of this overhead is incurred whether you are calling from Python, or from Pyrex, or from Mars.
Example
Here's the Pyrex code:
Performance data:
Pretty striking difference. (And by the way, the second one goes twice as fast again if you declare a void return type.)
Here's the C code for def_func, note the PyArg_ParseTupleAndKeywords API call:
1 static PyObject *__pyx_f_7integer_1X_def_func(PyObject *__pyx_v_self, PyObject *__pyx_args, PyObject *__pyx_kwds) {
2 PyObject *__pyx_r;
3 static char *__pyx_argnames[] = {0};
4 if (!PyArg_ParseTupleAndKeywords(__pyx_args, __pyx_kwds, "", __pyx_argnames)) return 0;
5 Py_INCREF(__pyx_v_self);
6
7 __pyx_r = Py_None; Py_INCREF(Py_None);
8 Py_DECREF(__pyx_v_self);
9 return __pyx_r;
10 }
In contrast, here's the C code for cdef_func:
Now here are the two versions of the loop that actually does the calling. First, call_def_func, with error handling suppressed:
1 for (__pyx_v_i = 0; __pyx_v_i < 10000000; ++__pyx_v_i) {
2 __pyx_1 = PyObject_GetAttr(((PyObject *)__pyx_v_x), __pyx_n_def_func);
3 __pyx_2 = PyTuple_New(0);
4 __pyx_3 = PyObject_CallObject(__pyx_1, __pyx_2);
5 Py_DECREF(__pyx_1); __pyx_1 = 0;
6 Py_DECREF(__pyx_2); __pyx_2 = 0;
7 Py_DECREF(__pyx_3); __pyx_3 = 0;
8 }
Notice it needs to do (a) a name lookup for def_func, (b) construct a tuple, and (c) call the Python API to make the function call.
Here's the much much slicker call_cdef_func version:
python attributes vs cdef attributes
[ todo ]
avoid python name lookups
[ todo ]
- sage.rings.integer.Integer
Type checking
Generally speaking, using isinstance is very slow. It's slow because it needs to cover many cases, and it's slow because it's a Python function. If you are checking for a particular Pyrex-generated type (or indeed any extension type), it's much faster to use the Python API function PyObject_TypeCheck. In fact, PyObject_TypeCheck is a macro, so there isn't even any C function call overhead. The prototype is declared in cdefs.pxi.
Example Pyrex code:
Here's the performance comparison:
(Note: there is also some overhead in the name lookup for isinstance, but in this case it's a fairly small part of the time, about 10% or so.)
Here's the C code for the first loop (error checking suppressed):
1 for (__pyx_v_i = 0; __pyx_v_i < 5000000; ++__pyx_v_i) {
2 __pyx_1 = __Pyx_GetName(__pyx_b, __pyx_n_isinstance);
3 __pyx_2 = PyTuple_New(2);
4 Py_INCREF(__pyx_v_x);
5 PyTuple_SET_ITEM(__pyx_2, 0, __pyx_v_x);
6 Py_INCREF(((PyObject*)__pyx_ptype_7integer_X));
7 PyTuple_SET_ITEM(__pyx_2, 1, ((PyObject*)__pyx_ptype_7integer_X));
8 __pyx_3 = PyObject_CallObject(__pyx_1, __pyx_2);
9 Py_DECREF(__pyx_1); __pyx_1 = 0;
10 Py_DECREF(__pyx_2); __pyx_2 = 0;
11 __pyx_4 = PyObject_IsTrue(__pyx_3);
12 Py_DECREF(__pyx_3); __pyx_3 = 0;
13 if (__pyx_4) {
14 goto __pyx_L4;
15 }
16 __pyx_L4:;
17 }
And here's the much tighter code for the second loop:
"==" vs "is"
"a is b" checks whether a and b are the same objects while "a == b" returns the result of either a.__class__().__richcmp__(a,b,2) or b.__class__().__richcmp__(a,b,2) depending on if a.class() can handle comparison with b.
This gets used quite often to e.g., check if an attribute of a class has been computed already, like this:
If the cached result has not been computed the default value for any cdef class attribute is None. There is only one single None object in Python so it's safe to check for identity rather equality. Consider these timing examples.
Now consider the times these functions take:
So it's way faster to test for identity with None than comparing with None.
This is also true for pure python.
tuple, list, and dict access
Pyrex plays safe when it comes to list, tuple, dict access:
t[0] gets translated to:
1 __pyx_1 = PyInt_FromLong(0);
2
3 if (!__pyx_1) {
4 __pyx_filename = __pyx_f[0];
5 __pyx_lineno = 10;
6 goto __pyx_L1;
7 }
8 __pyx_3 = PyObject_GetItem(__pyx_v_t, __pyx_1);
9
10 if (!__pyx_3) {
11 __pyx_filename = __pyx_f[0];
12 __pyx_lineno = 10;
13 goto __pyx_L1;
14 }
15 Py_DECREF(__pyx_1); __pyx_1 = 0;
16 Py_DECREF(__pyx_3); __pyx_3 = 0;
This is faster:
As it gets translated to:
Cython Update There is still a slight speed difference, but it is almost negligable. The code automatically detects lists/tuples at runtime and uses the PyXxx_GET_ITEM code if it can. This is much safer to, as calling PyTuple_GET_ITEM on a non-tuple or with bad bounds results in a segfault. (Not to mention easier to read).
integer "for" loops
1 from sage.rings.integer_ring import ZZ
2
3 cdef int n
4 n = 3000000
5
6 def test0():
7 cdef int j,k
8 j = 1
9 k = 2
10 for i in range(n):
11 j = k * j**2
12 return j
13
14 def test0a():
15 for i in range(n):
16 pass
17
18 def test1():
19 cdef int j,k
20 j = 1
21 k = 2
22 for i from 0 <= i < n:
23 j = k * j**2
24 return j
25
26 def test1a():
27 for i from 0 <= i < n:
28 pass
29
30 def test2():
31 cdef int i,j,k
32 j = 1
33 k = 2
34 for i from 0 <= i < n:
35 j = k * j**2
36 return j
1 %time s = test0()
2 # CPU time: 1.34 s, Wall time: 3.38 s
3
4 %time s = test0a()
5 # CPU time: 0.93 s, Wall time: 1.99 s
6
7 %time s = test1()
8 # CPU time: 0.61 s, Wall time: 1.26 s
9
10 %time s = test1a()
11 # CPU time: 0.15 s, Wall time: 0.43 s
12
13 %time s = test2()
14 # CPU time: 0.44 s, Wall time: 1.50 s
use void return type when possible
[ todo ]
exception handling is not as bad as you'd think
[ todo ]
- If no exception occurs, overhead is really tiny.
a.__add__(b) is worse than a+b in Pyrex speed-wise
[ todo ] but headline says it all
Offtopic: Malloc Replacements
[:MallocReplacements:Malloc Replacements]