Survival of the fittest

[Dieter Maurer]

Dennis Lee Bieber <wlfraed at ix.netcom.com> writes on Thu, 28 Sep 2006 23:57:51 GMT:
> On 28 Sep 2006 22:48:21 +0200, Dieter Maurer <dieter at handshake.de>
> declaimed the following in comp.lang.python:
> 
> > We learn: a C/C++ implementation can in some cases be drastically
> > more efficient than a Python one.
> >
> 	Did we?
> 
> 	When did someone build a C/C++ compiler that generates bytecodes for
> the Python virtual machine interpreter?
> 
> 	What I've learned from this tale is that a C/C++ implementation --
> compiling to native hardware opcodes -- can run faster than an
> implementation compiled to interpreted Python bytecodes... No idea as to
> "efficiency" of the implementations themselves <G>

I would be really surprised if an optimizing compiler (e.g. a just
in time compiler) would have found the optimations I implemented.

You may look at the two implementations: They are
"IncrementalSearch" (Python) and "IncrementalSearch2" (C), respectively, on

  <http://www.dieter.handshake.de/pyprojects/zope>


The Python implementation worked with arbitrary trees,
the C implementation needs quite different code for integer trees
and and for arbitrary trees and only for integer trees, it can
gain the two orders of magnitude in speed.

The optimizing compiler would need to recognize that it can
drastically optimize if *ALL* keys in a tree are integer
and would need to efficiently detect for a given tree
that it satisfies this condition.
It would lose immediately, when it tried to verify the
a tree has only integer keys (as this takes linear time while
most operations are sub-linear).


--
Dieter