Why don't all languages have the same efficiency?

Question

I just finished my compilers course. One of the topics discussed was ways to make compilers more efficient. For example: tail recursion, inlining procedures, strength reduction, removing dead code, constant propagation. Considering that the main reason why C is more efficient than Python is because it doesn't have dynamic types and a garbage collector. These disadvantages can be removed during the optimization phase when the actual machine code is generated. So why, at the end of the day, is a language like C is more efficient than Python?

Answer 1

Machine code doesn't magically make type checking irrelevant. The thing with many varieties of machine code is that they have no inherent understanding of types. But that doesn't mean you can't build a type system onto them by using your own conventions.

As a trivial example, you could decide that every value is 16 bits. The first 8 bits represents the type, and the second 8 bits represents the actual value. Now you've got something you can check at runtime to verify you're not adding a horse to your latitude. Here's c=b+c in pseudo-assembly:

  enter               // function entry
  loadw [ax], bx      // load 16 bits at [ax] into bx
  loadw [ax+2], cx    // load 16 bits at [ax+2] into cx
  cmp   bl, cl        // compare the low bytes of bx and cx
  jne   ERROR         // if ^ is not equal, jump to ERROR
  addb  bh, ch        // add the high bytes of bx and cx, store in ch
  storw cx, [ax+2]    // store cx back in memory
  ret                 // return to caller
ERROR:
  // Handle error, print warning, throw exception, etc

That's an example of the instructions a dynamically-typed language may compile down to (in this case, an actually pretty fragile language; consider that even if b and c are the same type, addition might be an outright nonsensical operation to perform on them. e.g GUID+GUID=huh?). Here's what a statically-typed language may do:

  enter               // function entry
  loadb [ax], bh      // load 8 bits at [ax] into bh
  loadb [ax+1], ch    // load 8 bits at [ax+1] into ch
  addb  bh, ch        // add bh and ch, store in ch
  storb ch, [ax+1]    // store ch back in memory
  ret                 // return to caller

Notice that there's no cmp, jne, or error handling. Why? Because a statically-typed language can prove, without running the program, that an invalid pair of types will never enter that section of code. Therefore, it can safely elide the checking code. And since it doesn't check the extra type metadata, it can leave that out, too, hence why it's only loading and storing 8 bit bytes instead of 16 bit words.

Similarly, machine code doesn't magically clean up your garbage for you. If you're using a garbage collector, it doesn't just disappear when compiling, it gets translated to the target language along with the rest of your program.

But do note that a garbage collector is not necessarily less efficient than alternatives. malloc() is not necessarily deterministic.

Answer 2

Considering that the main reason why C would be more efficient than Python is because it doesn't have dynamic types and a garbage collector, all of those disadvantages will be removed after actual machine code is generated.

Not exactly. Whether you're interpreting, running from a parse tree or intermediate byte code or compiled machine code, a Python program still has to behave like a Python program. That means it comes with all of Python's baggage.

Consider this function and some code that calls it:

def add(a, b):
    return a + b

print add(3, 2)
print add("Three", "Two")
print add("Five", 9)         # This will throw an exception.

Python, being dynamically-typed, can't make any assumptions about the types of a and b when something calls add(). Internally, the first call isn't simple invocation of a function with a pair of integer constants. Those constants actually have little tags tied to them that say "this is an integer". Inside the function, something has to look at what's on the left side of the + operator, read the type off the tag, check to see if that operator is defined for that type and hand the operator both expressions. The operator then has to look at them and decide whether or not the second argument is compatible with the first before trying to produce a result. The second and third calls work exactly the same way, except that it's the string type. The third ends up trying to hand the string type an integer for the right-hand operand, the string type decides it can't add it and throws an exception.

That's an awful lot of decision making that has to be repeated every time something calls add().

Compilers for statically-typed languages actually go through much the same process, but knowing the types ahead of time, they can do all of the analysis once and generate nice, compact object code. Adding two registers eats up a cycle or two. The example in 8bittree's answer takes up a lot more and only does type safety. Expand it to figure out what bit of code needs to be called in the face of being handed an arbitrary type and it gets even longer.