merits of Lisp vs Python

[Alex Mizrahi]

(message (Hello 'Kay)
(you :wrote  :on '(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")