(message (Hello 'Kay)
(you :wrote
n '(8 Dec 2006 12:25:09 -0800))
(
KS> O.K. I agree with what you said about the generic function vs per
KS> object dictionary dispatch.
KS> But do the performance differences vanish when only builtin types and
KS> functions are used to express Python algorithms?
no.
language semantics require python to do dict lookup on each access to some
global function (or builtin) or variable.
i don't have enough time for in-depth analysis, but here's what's it.
suppose we have
def Fib(n):
if n < 2:
return 1
else:
return Fib(n -2) + Fib(n-1)
import dis
dis.dis(Fib)
you will see this:
....
21 LOAD_GLOBAL 1 (Fib)
24 LOAD_FAST 0 (n)
27 LOAD_CONST 2 (1)
30 BINARY_SUBTRACT
31 CALL_FUNCTION 1
34 LOAD_GLOBAL 1 (Fib)
37 LOAD_FAST 0 (n)
40 LOAD_CONST 1 (2)
43 BINARY_SUBTRACT
44 CALL_FUNCTION 1
47 BINARY_ADD
48 RETURN_VALUE
now let's check what is LOAD_GLOBAL in ceval.c (i have Python 2.4.1
sources):
case LOAD_GLOBAL:
w = GETITEM(names, oparg);
if (PyString_CheckExact(w)) {
/* Inline the PyDict_GetItem() calls.
WARNING: this is an extreme speed hack.
Do not try this at home. */
long hash = ((PyStringObject *)w)->ob_shash;
if (hash != -1) {
PyDictObject *d;
d = (PyDictObject *)(f->f_globals);
x = d->ma_lookup(d, w, hash)->me_value;
if (x != NULL) {
Py_INCREF(x);
PUSH(x);
continue;
}
d = (PyDictObject *)(f->f_builtins);
x = d->ma_lookup(d, w, hash)->me_value;
if (x != NULL) {
Py_INCREF(x);
PUSH(x);
continue;
}
goto load_global_error;
}
}
/* This is the un-inlined version of the code above */
x = PyDict_GetItem(f->f_globals, w);
if (x == NULL) {
x = PyDict_GetItem(f->f_builtins, w);
if (x == NULL) {
load_global_error:
format_exc_check_arg(
PyExc_NameError,
GLOBAL_NAME_ERROR_MSG, w);
break;
}
}
Py_INCREF(x);
PUSH(x);
continue;
so we can see PyDict access. moreover, it's inlined, since it's very
performance-critical function.
but even inlined PyDict access is not fast at all. ma_lookup is a long and
hairy function containing the loop.
moreover, we can see that there are two dict lookups -- into globals and
builins.
lookup into a global hash should about order of magnitude slower than simple
table fetch, so here's the root of python's slowness.
how lisp can be faster here? lisp has SYMBOLs and well-defined semantics of
source code parsing.
first source code is processed by reader, that outputs trees of code. each
variable or function name becomes a SYMBOL object. symbols are typically
interned into packages, but they don't need to be looked-up in the packages
in runtime -- in fact, it's not possible at all.
i can read a piece of code and then unintern some symbol from package --
that will not make that code invalid. packages are used mostly by reader.
(also, i can have many symbols with same name, if they are not interned --
and they will be all different objects)
in runtime, lisp has to lookup symbol's function -- but symbol can be
implemented as a structure, and symbol-function can be just it's field
access.
one more thing -- you can see lookup into builins, so they are in dict too!
and you can see that builtins dict is checked only if name is not found in
globals, so builtins are even slower than globals. that's a reason for
performance slowdowns too.
one can say that it's the only way to change builtins in runtime. yes, but
dict lookup is a big price for it (well, if python use symbols, it would be
faster).
in fact, Common Lisp also allows to redefine "built-in" function -- you can
define a symbol with a same name as builtin in some package and use it, it
will "shadow" symbol in the common-lisp package (common-lisp:+). you can
change symbol-function of this symbol in runtime and do whatever you want.
but symbols in common-lisp package are immutable. that makes it possible to
optimize code.
and there's inlining. for example, in fib definition:
(defun fib (n)
(if (< n 2)
1
(+ (fib (- n 2))
(fib (- n 1)))))
CLISP does not even use symbol FIB in function bytecodes -- it notes that
it's a recursive function calls, so instead of normal function call it does
a local jump.
)
(With-best-regards '(Alex Mizrahi) :aka 'killer_storm)
"People who lust for the Feel of keys on their fingertips (c) Inity")
