Why Python Is Slow: Looking Under the Hood

Why, oh, why does CPython bother keeping refcounts for small integers? Sure, it lets you make pretty graphs with [sys.getrefcount(i) for i in range(1000)]... but that's an extra memory read and write on every instruction that uses an integer. I can only imagine that not only are these extra instructions, but they're extra instructions that kill pipelining, if the interpreter needed to do "a = 1; b = 1; c = 1" for instance. Maybe they found that the branch needed to not bother refcounting for small integers was even slower? Does anyone know if that was ever tried?

CyberDildonics• 12 years ago

Does that also imply that a small integer is created on the heap? I would think the heap allocation would be the huge performance killer.

plikan132• 12 years ago

Python is not going to call malloc(..) for every single object that you create. It will allocate a block of same-sized objects and maintain a linked list of free slots.

dalke3• 12 years ago

What you propose sounds like it would be a pure headache for all code which otherwise expects a uniform memory API.

Consider a C extension which takes an object and appends it to a list. If small integers did not have a refcount then that extension would have to have special code, like "if object is not a small integer, then increment the reference count".

btown2• 12 years ago

I hadn't considered that extensions which needed direct memory access would need access to these objects. But it's a solvable problem. The proposal might read as follows:

"Objects with IDs between 0 and 2055, inclusive, are considered unreleasable. The Python runtime shall initialize the refcount of these objects to 1 when they are first used, and shall make no guarantee that the refcount on such objects accurately reflects the true number of references to that object. Native extensions may increase and decrease the refcount on these objects as if they were normal objects; if those extensions are well-behaved, then the refcount should never decrease below 1. However, native extensions that can statically reason about whether an object is likely to be unreleasable, may benefit in performance by checking for whether objects passed to their functions are indeed unreleasable, and refraining from modifying or checking their refcount in such cases."

kazinator• 12 years ago

I have experience turning a Lisp dialect with refcounted integers into supporting non-refcounted integers, identified by a type tag field in the "value cell" type.

If small integers did not have a refcount then that extension would have to have special code, like "if object is not a small integer, then increment the reference count".

Easily implemented in one place in the "increment_refcount(obj)" inline function:

    // roughly speaking
    if (is_heap_pointer(obj))
      obj->refcount++;

where "is_heap_pointer(obj)" is an inlined bitmask check like

    (((unsigned int) obj) & TAG_MASK) == TAG_PTR)

If TAG_PTR is zero bits, then a value which satisifes is_heap_pointer can be dereferenced straight.

In a garbage collection implementation, you don't have refcounts, but the garbage collector's "mark object" function does the same check:

   if (!is_heap_pointer(obj))
     return;  // don't try to mark non-heap things

   switch (type(obj)) {
   case TYPE_CONS_CELL
      mark_obj(obj->cons.car);
      mark_obj(obj->cons.cdr);
      break;
   // ...
   }

Another thing is that you provide an API to the extension writers, which abstracts the use of objects. For instance, you can give them a function that can be called like this:

   value n = number(42);
   value z = number(INT_MAX);

The first case might construct an unboxed value because the integer is small enough. But perhaps the second returns a bignum because INT_MAX requires 32 bits, wheres unboxed integers only go up to 30 bits.

So in the first case you get an object with no refcount, whereas in the second you get an object with a refcount of 1. The extension code is written such that it doesn't care.

_wmd3• 12 years ago

There is no such thing as "small integers" in CPython, only PyObjects, of which PyInt_Type and PyLong_Type are implementations. You can't special case integers without changing every C interface that accepts an object, and special casing every piece of code too (i.e. several hundred million lines of 3rd party extension modules, NumPy, lxml, ...). The trade-off is 1 extra machine word per integer (adding to the 2 + heap/alignment slack already present), or 1 conditional branch per object access everywhere.

This isn't so bad on memory either, since Python keeps a static cache of integers that are reused on every int constructor call. Also allowing for slack, I wouldn't be surprised if the machine word came for free.

j_baker2• 12 years ago

When the GP talks about "small integers", I'm assuming he's talking about numbers between -5 and 256, which are cached ahead of time. They're never going to be garbage collected, so refcounting is largely unnecessary.

j_baker2• 12 years ago

Python also keeps refcounts for other objects that shouldn't be garbage collected such as None, True, and False. The reason being to prevent having certain objects that need to be refcounted and certain objects that don't. Otherwise, C code would be littered with if statements like the below:

    if (number < -5 || number > 256) {
      decrement_refcount(number);
    }

Pxtl• 12 years ago

To be fair, you'd expect that to live in decrement_refcount.

ggchappell5• 12 years ago

2. Python is interpreted rather than compiled.

Can we stop saying things like this? Virtually all Python is compiled, as part of the interpretation process.

There is a valid point here, of course. The point is that the top Python compilers do not compile to native code. So say that.

Words have meanings. Use them correctly. <grumble, grumble>

bunderbunder• 12 years ago

Might want to start by asking the core Python community. Check out the first sentence on wiki.python.org.

Nowadays it's the norm for interpreted languages to be JIT-compiled. They still universally call themselves interpreted languages because the jitter is an implementation detail, and the use of one does nothing to negate the characteristics they're trying to advertise when describing themselves as interpreted languages.

Think of it this way: Can I take a text file containing source code in the language and execute it anywhere that has a special program for executing files written in that language (commonly known as an interpreter)? Or do I have to manually perform an intermediate step of converting the program to some binary representation using a special program for doing that (commonly known as a compiler), and then execute the output that program produces?

lispm4• 12 years ago

There are several compiler-only Lisp implementations which can execute source from text. Nobody there would call them interpreter because of that. In Lisp we call them interpreter, when the implementation traverses the source code during execution. If it compiles the source to some byte-code or machine code, we call in Compiler.

The incremental nature of a compiler, then does not make it that we would call it an Interpreter. We would call it an incremental compiler. That's a compiler, which can compile all expression, regardless of the size of the expression, not just 'whole programs'.

jeffreyrogers• 12 years ago

There are three primary methods of running code: interpretation, compilation to object code, and running on a VM/JIT. Obviously python is interpreted by any meaningful definition of interpretation and thus it is not compiled in the typically sense of the word (at least not in the implementation everyone uses).

The reason human language is so expressive is because we can leave out a lot of context and formalism that is required in mathematics and programming languages because the listener/reader will be able to infer it. It's pedantic to expect a writer to hedge against every possible interpretation, when their focus should be on communicating clearly in the first place.

andreyf• 12 years ago

FWIW, wikipedia says "The main Python implementation, named CPython, [...] compiles Python programs into intermediate bytecode, which is executed by the virtual machine." I'm not sure why people call Python's VM an interpreter, but it's definitely interpreting byte code, not the source directly.

This is very different from Perl, where a line of code isn't parseable until you know the values of the variables, e.g.

    whatever / 25 ; # / ; die "this dies!";

ggchappell5• 12 years ago

It's pedantic to expect a writer to hedge against every possible interpretation, when their focus should be on communicating clearly in the first place.

Our discipline (computer programming) is, perhaps more than any other, one in which precision of meaning is of paramount importance. I expect people to hedge. Especially when it's easy: "Python is not usually compiled to native code."

In any case, since Python is virtually always compiled, saying it's not is simply false. That's hardly clear communication, I think.

Obviously python is interpreted by any meaningful definition of interpretation ....

Now, here I'm not sure what you mean. You've already distinguished interpretation from Just-In-Time compilation to Virtual Machine code. Since the latter is pretty much always what happens with Python, would you then say that Python is not interepreted? (Serious question!)

Me, I don't have a problem with these concepts overlapping (and I don't see why many people do). Python is interpreted. The usual mechanism for this is JIT compilation to virtual-machine code, which is then -- in the case of CPython -- interpreted as-is. In contrast, something like "C" is traditionally Ahead-Of-Time (AOT) compiled to native code. Interpreted: no. Compiled: yes. And then there are languages whose interpreters do not involve a compilation step -- although they are becoming rare.

slashnull3• 12 years ago

Short answer: because it doesn't JIT

ludamad• 12 years ago

That's a lossy short answer. LuaJIT with JIT turned off still runs circles around CPython.

trynumber9• 12 years ago

Even normal Lua is fast compared to Python, if the shootout games are any bit accurate.

http://benchmarksgame.alioth.debian.org/u64/benchmark.php?te...

slashnull3• 12 years ago

True.

So, with element of answer 1) ruled out as Lua is also dynamic, and 2) ruled out by your evidence, remains

3. Python's object model can lead to inefficient memory access

philippeback2• 12 years ago

Pharo 3's results (JIT enabled VM)

[(1 to: 100000000) sum] timeToRun 0:00:00:07.335

http://pharo.org

Version 4 with new VM due in 2015.

Will perform much much better as with the range used, we need to use LargeIntegers as the 32 bit VM must promote to LargeInteger objects. With the 64bit VM, all fits in.

masklinn6• 12 years ago

    > pypy -mtimeit 'sum(xrange(1, 100000001))'
    10 loops, best of 3: 153 msec per loop

however the context of TFA is scientific computing, hence pypy being ignored/dismissed

philippeback2• 12 years ago

We can do it this was if needed.

http://clementbera.wordpress.com/2013/06/19/optimizing-pharo...

Skunkleton• 12 years ago

Another reason python is slower than other languages is that abstraction adds significant overhead which most implementations cannot optimize away. See here:

http://blog.reverberate.org/2014/10/the-overhead-of-abstract...

coolsunglasses2• 12 years ago

The overhead of abstraction...unless you're using Haskell where typeclass instances get specialized, so you can abstract without slowing things down.

haberman9• 12 years ago

The article is not suggesting that abstraction inherently has overhead in all languages. Rather it is exploring the difference between languages where abstractions can be essentially free (in terms of runtime overhead), and languages/implementations where abstraction has a noticeable cost.

tome• 12 years ago

Let's not overstate the case. There's still plenty of abstraction which is tricky or impossible for GHC to optimize. But yes, with static analysis comes the possibility of nice optimizations.

pnathan2• 12 years ago

Heh, Python is slow: in order to write fast Python, you have to write in C and conform to the FFI.

I vastly prefer to use tools which don't come misshapen out of the box, personally.

the_real_bto• 12 years ago

Different tools for different jobs. Being able to develop code quickly is a huge win that Python delivers. Sometimes that makes Python the right tool, e.g. Youtube. Other times slow execution speed makes it the wrong choice.

[0] http://www.gooli.org/blog/youtube-runs-on-python/

pnathan2• 12 years ago

other tools also deliver code quickly. that's an evasion of the criticism.

tjradcliffe• 12 years ago

A related question is: why is Perl so fast?

Quite a few years ago I wrote a little Runge-Kutta solver in Perl for some simulation work. It seemed like a good idea at the time. The equations of motion had to be integrated over a very long time, and it could take hours for a single run (still much faster than the Monte Carlo it was being used to do a sanity-check on). I re-wrote everything in C++, and picked up less than a factor of two in speed.

So it isn't that "Python is interpreted" that is the problem, because "Perl is interpreted" in exactly the same way. It really does seem to come down to the Python object model. Perl's scalar types have vastly less overhead, so much so that you can actually do reasonably efficient numerical computation in it.

I abandoned Perl for Python shortly thereafter because once I got over the "oh my god it's full of whitespace" thing Python was just more fun to code in, but the speed that Perl provided is something I've definitely missed, and it was a real awakening to the notion that interpreted languages don't have to be slow. The striking thing was that unlike Java (say) where it can be fast but you generally have to think about it, I was getting fast Perl without even really trying.

tenfingers• 12 years ago

Also had the same experiences. Perl is relatively fast and memory compact compared to other modern scripting languages.

Perl also has PDL (http://pdl.perl.org/), which is very similar in scope to numpy, but predates it by several years.

dagw3• 12 years ago

predates it by several years

If you want to get technical, Numpy is a continuation of Numeric which in turn pre-dates pdl.

haberman9• 12 years ago

I'm not sure your results are typical.

In microbenchmarks, Perl is 2-125x slower than C++: http://benchmarksgame.alioth.debian.org/u32/benchmark.php?te...

And Java is quite a bit faster than Perl too: http://benchmarksgame.alioth.debian.org/u32/benchmark.php?te...

Perl isn't really that fast. It's faster than Python in most cases, but gets beat by Lua pretty consistently: http://benchmarksgame.alioth.debian.org/u32/benchmark.php?te...

hyperbovine• 12 years ago

I'm not sure microbenchmarks are typical.

cleaver2• 12 years ago

For a general-purpose problem, Perl won't be particularly fast. For a Perl-type problem (scanning and parsing big files), Perl is very fast.

Doing a Perl-type problem in a general-purpose language would be considerably slower. However, Python or others will perform much better in the "can I read my own code six months later" benchmark.

Igglyboo3• 12 years ago

If you're doing numerical computation Numpy will be extremely fast. Most of it is a thin layer over C code so you get the best of both worlds(unless you're the Numpy maintainers).

debacle• 12 years ago

Because it was written to do (certain) things very fast.

vacri• 12 years ago

"oh my god it's full of whitespace"

When I write in python, this always triggers my mental slogan "python, the language which makes 'nothing' important".

This is said with a trace of irony, as my most fluent language is bash scripting :)

coldtea• 12 years ago

related question is: why is Perl so fast?

Easy answer: it's not. On most benchmarks it's on par with Python, PHP, Ruby, etc, some are faster on one, others on some other test.

once I got over the "oh my god it's full of whitespace" thing

What full of whitespace? Python has as much (or as little) whitespace as normally intended Perl, Ruby, C, etc.

What it has that they don't have is significant whitespace.

jules• 12 years ago

If you only got a 2x speedup there is something wrong. A more usual number for Perl is about 100x slower than C++ for numerical code. Perl isn't very different than Python in this regard. e.g. on the shootout on the n-body benchmark, Perl is about as fast as Python, and 125x slower than C++.

baudehlo• 12 years ago

It's sad that this question hasn't actually even been answered yet.

Some things perl does under the hood to be fast are that integers are (mostly) actually integers under the hood. Arrays are actually arrays under the hood (a fact that makes perl's DBI very fast). And more importantly it has had decades of people trying to make it faster without changing the (sometimes crazy) semantics of the language.

But of course languages with JITs a have massively overtaken it in the performance stakes (PyPy, LuaJIT, and JavaScript). Mostly I think this is a result of lack of funding and huge company spending. Just look at what Facebook have managed to do with PHP.

Htsthbjig• 12 years ago

"why is Perl so fast?"

Is not. We tested our own code in Perl for doing some text processing in our company.

The result was 89 times slower than our c code, which is not so slow compared with other options, but is slow.

We use a lot of c++ and python, but always for managing encapsulated low level code.

With anything that has to compute intensely, like audio, video or 3d work, the differences are way over 3000 times slower. That is: the computer working for a second or for an hour.

Java is not fast, it has never been. It is not its "forte". You could decide to use java or any high level languages based on its merits, but being fast is not one of them.

It is a good idea to learn assembly and disassembly with the debugger before using high level languages. It gives you the knowledge of what computers are really doing under the hood.

stinos• 12 years ago

I re-wrote everything in C++, and picked up less than a factor of two in speed.

Don't think it has been mentioned in the other comments, but this could also be a performance problem with your C++ code - possibly in combination with doing something Perl is good at

hackersf• 12 years ago

Python's GC is a conservative collector as opposed to Java's precise collector => terrible GC compaction.

TheLoneWolfling• 12 years ago

Is it just me who sees a large chunk of these as flaws in the Python implementation as opposed to the Python language?

Dynamic typing can often be optimized at the compilation stage - and yes, Python has a compilation stage - this particular example is basic type inference, for example. Even more complex examples can be optimized by emitting specialized versions for the types that the compiler can see it will be called with. Effectively emitting specialized versions of specific nodes in the control flow graph.

dagw3• 12 years ago

Is it just me who sees a large chunk of these as flaws in the Python implementation as opposed to the Python language?

There are a number of design decision in python language that makes it inherently hard to write a fast python implementation.

Animats• 12 years ago

Ah, the right answer!

There are lots of languages where variables are dynamically typed that can be compiled and optimized with a JIT compiler. In Python, though, any code can mess with any data, using "setattr". You can find all the variables in another module and mess with them at run time, using their names as strings. At compile time, the compiler can't detect that's going to happen.

This is sometimes called the Guido von Rossum Memorial Boat Anchor.

So Python implementations usually have to assume the worst case. Google's attempt at a faster, compatible Python, "Unladen Swallow", was an embarrassing failure. PyPy manages to get past that, but at a huge cost in JIT compiler complexity. After 12 years of work, PyPy is finally shipping stable versions and starting to get some use. It's been all uphill for the PyPy developers, though.

It's kind of sad. Python never achieved its full potential because of the speed problem. Google ended up developing Go because Python was too slow.

masklinn6• 12 years ago

He said "a large number of" though, not "all".

shanemhansen2• 12 years ago

You are technically correct. A Sufficiently Smart Compiler(TM) could theoretically optimize python code.

However certain language features can be inherently difficult to optimize. Most of it's over my head, but headius has written some great articles as part of his experience of implementing ruby on the jvm. http://blog.headius.com/2012/09/avoiding-hash-lookups-in-rub...

scott_s2• 12 years ago

Even if you're already familiar with all of the main reasons that answer the question (that is, you're already familiar with how a VM works), read the Just for fun: a few "never use these" hacks. I mean, wow. That's the kind of nastiness I normally associate with C's free-for-all memory model.

slashnull3• 12 years ago

With the nuance that C forces you to deal with those never use these hacks in order to do anything non-trivial.

I can't see why anyone would go and mess with CPython's internals like that in production code. Other than for nefarious purposes, I guess.

mahouse• 12 years ago

I don't understand why is it compared to C, when it can be compared to Perl or PHP, which are also dynamically typed, interpreted, etc, but much faster.

masklinn6• 12 years ago

1. Because TFA is about scientific computing

2. And in that context (and most others), the difference between Perl, PHP and CPython is basically non-existent, you might get 2x on one bench, half on the other

slantedview2• 12 years ago

"it's slow"

"just write a C extension"

"but then why use Python?"

nightcracker• 12 years ago

Because 90% of the runtime is spent in 10% of the code.

bch2• 12 years ago

Because beautiful control structures and a REPL ?

pjmlp3• 12 years ago

There are many languages that offer that alongside an AOT compiler to native code.

slantedview2• 12 years ago

I'm not sure that these are compelling reasons to use Python, given the alternatives.

Squeezing performance out of Python often involves dropping down to C. This isn't the case with the competition.

AlexeyBrin• 12 years ago

    "it's slow"
    "just write a C extension"
    "but then why use Python?"

Because you typically need to write a C extension for like 2% or your code, while you could keep the remaining 98% in an easier to write (and more compact) language.

bsder• 12 years ago

Because the C extension you need has probably already been written.

This is the same kind of network effect that drove Perl usage for some many years. CPAN had it. Even if I didn't want to use Perl, CPAN was overwhelmingly compelling.

Python has since taken on that mantle.

mikkom• 12 years ago

Almost all these points apply to javascript as well. Javascript, however, is not really slow anymore.

http://benchmarksgame.alioth.debian.org/u64/benchmark.php?te...

jlebar• 12 years ago

Almost all these points apply to javascript as well.

Sort of.

The article talks about why CPython, an implementation of the Python language, is slow. You're right that a naive implementation of Javascript would have many of the same problems, and indeed many of the first implementations of JS did have these problems. But due to heated competition, Mozilla, Google, Apple, and Microsoft have invested a huge amount of top-quality engineer-years into optimizing their implementations of JS.

Implementations of Python, in contrast -- and CPython in particular -- have not received the same sort of love.

I largely agree with the notion that the speed of modern JS engines serves as an existence proof that Python could be similarly fast.

anentropic• 12 years ago

that's what PyPy is http://speed.pypy.org/

jerf• 12 years ago

"Javascript, however, is not really slow anymore."

What's easy to lose track of under the steady stream of headlines about this microbenchmark going 5x faster and that microbenchmark going 10x faster and this one microbenchmark being "faster than C" is that Javascript is still a fairly slow language, though. Flick that to compare Javascript vs. C: http://benchmarksgame.alioth.debian.org/u64/benchmark.php?te...

It has come a long way. It is, of course, still usable for many things. But it is still an interpreted language, and my guess is that we've basically plateaued on performance for Javascript, and it's important to remember that it isn't as "fast as C" in any useful sense of the term. And for that matter, to get even that performance out of JS seems to require you to write a very specialized subset of JS that will tickle the optimizers correctly. In practice I suspect you will get even worse deltas over C, which, for all of its many failure modes, does make it often easier to do the fast thing than the slow thing, usually regardless of the correctness of either of them.

(That's why we have asm.js, after all. You can't have both of "Javascript is as fast as C" and "asm.js is several times faster than Javascript", because the composition of both statements is absurd.)

madengr• 12 years ago

Please forgive my ignorance, but why can't Python just be compiled into assembly like C? The compiler should be able sift through the code and see that "x=1" is an integer, or converts to a float when "x=x+1.0".

If I'm doing something like counting from 1 to 10 and summing the count, why can't this be compiled to run the same speed as C?

Obviously since it's interpreted, but when I'm done with development, why can't I just run it through a compiler to get fast assembly code?

Way back when, you could get a BASIC compiler to turn your interpreted BASIC code into assembly.

What fundamental am I missing?

timClicks• 12 years ago

I don't know the full story either, but I expect it's because lots of things change during runtime. It's too hard to lock things down.

joe_the_user• 12 years ago

The problem is that an average interpret/compiler is going to be "dumb" in that it assumes that when it starts parsing a python file that all of the features are going to be used.

It provides facilities for all of python abilities regardless of what the program is going to do.

Now, there are subsets of python people have developed that can be compiled and all sorts of other stuff.

Beyond that, I'd just say "all this stuff sounds easy but gets much harder when you actually have to program it".

"Why can't it just know!" is the programmer's lament.

kyllo• 12 years ago

Runtime metaprogramming. In Python you can create new classes and add methods to existing classes at runtime. If you AOT-compile everything to assembly, you have to take away those runtime features, and then it's not Python anymore.

vidarh2• 12 years ago

No, you don't. You "just" need slower fallbacks that does metadata lookup for things that are not statically decidable.

Consider how many people end up implement their own introspectable C object models.

ovis• 12 years ago

I believe that's essentially what Cython allows you to do, by way of C. Since the Cython compiler isn't especially advanced, it requires some hints to get good performance, which is why Cython code is usually typed, structured more like C, etc. But still, it executes on your basic idea.

jimbokun• 12 years ago

What you describe is pretty much what functional languages with strong static typing, like Haskell, Scala, and Ocaml do. Works very well for examples like you gave: "x = 1", "x = x + 1.0". For expressions similar to these, inferring the types (int, float) works very well.

But things get much more complex very fast, and then the compiler requires the programmer to tell it what types things are.

Then there is the approach taken by JavaScript engines like V8. Run the code for a while, see what the types of variables are, then compile a customized, much more efficient version of the code to speed things up. Still need a fallback, though, in case a totally different kind of value gets stuck in a variable than the type at the time the optimized code was generated. Nothing in JavaScript (or Python) prevents a programmer from assigning any kind of value into a variable, though, so the engine must be prepared for the types of variables to change in unexpected ways.

(The reason the state of the art for these techniques is in the JavaScript engines is because the organizations behind the major browsers pour so many resources into making them fast.)

Now, if you can figure out a way to always predict the types of every variable in a JavaScript or Python program without actually running it, pretty much any CS program would be willing to give you a tenured position on their faculty on the spot. :)

barsonme• 12 years ago

If Python had the same amount of time and energy put into it that JavaScript does from Google and Mozilla it'd be willing to bet it'd be a lot faster.

plikan132• 12 years ago

Why can't a C++ compiler optimize away virtual function tables? If a C++ compiler could deduce the exact derived type of all objects at compile time, it could call the correct virtual function statically instead of going through the extra indirection at runtime.

zanny• 12 years ago

If you declare a C++ virtual function final the compiler can avoid the virtual call table for any invocations of that function in the future on that object or any of its derivatives. Of course, you then cannot override it in child classes anymore.

If you declare a virtual function inline, if it is invoked from a well defined object (ie, not through a reference or pointer) you also get a similar effect while still being able to override, except the code is not a static call but is just inlined with that one implementation of the function.

pjmlp3• 12 years ago

It can, but not across dynamic libraries.

You just need to use profile guided optimisation.

vidarh2• 12 years ago

Python is similar in terms of dynamic features to Ruby. I'm actually working on an ahead of time "a static as possible" Ruby compiler.

You certainly can compile languages this dynamic, the problem is that the "simple" way of compiling it doesn't result in very fast code, because you essentially end up mimicking what the interpreters/vms do very closely, and a lot of what ends up being executed will be things like method lookups which are reasonably well optimized in the interpreters.

The problem boils down to the ability to "change the world" at almost any point.

E.g. in Ruby (don't know about Python), you can come back from an eval() call (or load or require) and find that the expression 1 + 1.0 results in the string "two", or will send you an insulting e-mail, because you can even override Fixnum#+.

Now, there's a lot that can be done to infer typing for these types of languages well enough that you can get away with slow-path fallbacks for the rare cases where users does something stupid (like override Fixnum#+) and run faster most of the time, but it's a lot of extra effort.

dragonwriter2• 12 years ago

The compiler should be able sift through the code and see that "x=1" is an integer, or converts to a float when "x=x+1.0".

The short version is "no, it shouldn't".

The longer version is that, viewing Python's runtime class memberships as "types", the type system it would represent is not one for which inference without explicit declarations is generally decidable, so an AOT compiler for unmodified, unrestricted Python that is expected to infer types at runtime simply would not be possible.

You could AOT compile it into C code with a lot of runtime metadata and indirections -- but that would probably have worse performance than the existing interpreter.

Way back when, you could get a BASIC compiler to turn your interpreted BASIC code into assembly.

Well, yeah, BASIC is actually structurally quite close to assembly. Its not a dynamically-typed multiparadigm language like Python.

JoeAltmaier2• 12 years ago

Its hard to be worse than an interpreter. 100X slower than compiled code is typical. Whatever 'metadata and indirection' your C target has, it seems likely to be 10X better than interpreted, easily.

cityhall• 12 years ago

Cython, numba, and other projects do this for a subset of the language, but you lose the metaprogramming that makes things like SQLAlchemy possible. You also have to treat most user objects as hashmaps and constantly look up their fields since members can be added or redefined at any time.

keypusher• 12 years ago

Write a function. It accepts two variables. Add them both together and return the result. What type is returned?

Read input from a file or stdin. Eval that input. What type does it return?

Etc.

rurban• 12 years ago

Unfortunately this blog post is misleading and uninformed. Python and the related other slow dynamic languages perl, php, and ruby are slow not because the dynamic type checks, branches and indirections are costly, but because they are badly written. They are just inefficient and poor interpreters, with bad ops and data structures. In comparison efficient dynamic languages like lisp, scheme, lua or javascript and many others not so well known do exist. Mine, potion, is also in the lua category, and not in the slow PPPR (python, perl, php, ruby) category.

The seminal paper about efficient dynamic interpreters is Ertl's "The Structure and Performance of Efficient Interpreters" http://www.complang.tuwien.ac.at/papers/ertl%26gregg03jilp.p...

The abstract is: "Interpreters designed for high general-purpose performance typically perform a large number of indirect branches (3.2%–13% of all executed instructions in our benchmarks). These branches consume more than half of the run-time in a number of configurations we simulated. We evaluate how accurate various existing and proposed branch prediction schemes are on a number of interpreters, how the mispredictions affect the performance of the interpreters and how two different interpreter implementation techniques perform with various branch predictors. We also suggest various ways in which hardware designers, C compiler writers, and interpreter writers can improve the performance of interpreters."

My own input to this is that the GC, the JIT, the calling convention and esp. the size of the datastructures and ops do matter more, than eliminating the type checks.

enupten• 12 years ago

The numerous Common Lisp implementations out there would agree with you.

mamcx• 12 years ago

Exist a sample I can follow that is made in a imperative language? I'm fluent in python, pascal, C#, obj-c but can survive C if the code is clear...

pjmlp3• 12 years ago

It seems learning about compiler design is not as good as it used to be.

Better learn about the JavaScript framework of the day.

lispm4• 12 years ago

I think the paper is even worse, in that it spreads confusion about what an Interpreter for a programming language actually is, what it does and what it provides.

The paper fails to define the concept of what to call an Interpreter. A bytecode interpreter is entirely different from a Lisp interpreter, which actually runs from source structures. Mixing VMs into the picture makes it only worse.

Part of the reason may be that they don't understand what an Interpreter actually provides and why it is used.

rhgraysonii• 12 years ago

One of my favorite topics lately is Python optimization. A few weeks ago FB put out a release on how they had done fast randomized SVD and in the implementations section they mentinoned using intels kernel math libraries for the BLAS libraries. Largely the result of this is many more functions are F-Contiguous rather than C-contiguous (in linear algebra, fortan obviously wins here). I had done something similar on a much smaller scale about 4 months ago. https://medium.com/@_devbob/from-0-to-warp-speed-b780a2bc36c...

Does anyone else have some good bits or blog entries on these sorts of inner workings and optimizations?

sgt101• 12 years ago

In simple language -> because it's difficult to provide the machine with the information it needs to make decisions about efficiency.

Why Python Is Slow: Looking Under the Hood

Related Stories