4

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?

  • 10
    "all of those disadvantages will be removed after actual machine code is generated" - No – 8bittree Aug 3 '17 at 16:54
  • 3
    I'm confused by your last sentence. I read it as "Considering that C is more efficient than Python for all these reasons, why is C more efficient than Python?" – Cort Ammon Aug 3 '17 at 16:55
  • 3
    Language efficiency is an extraordinarily complex topic, and your characterizations oversimplify the issues. In general, I would consider the fact that C tends to be more efficient than other languages is because it maps more closely to the underlying machine. But that is also an oversimplification. – Robert Harvey Aug 3 '17 at 16:56
  • 4
    In general, C tends to be faster than python because the most popular implementations of python are interpreters and the most popular implementations of C are compilers. All other things being equal, compiled language implementations are generally faster than interpreted implementations. But that, too, is an oversimplification. – Robert Harvey Aug 3 '17 at 17:01
  • 6
    So the vastly oversimplified answer to your question "why are languages not the same efficiency" is "because they are designed differently and have different implementations." It's no different than "why would you buy a truck instead of a car?" Because the truck has certain strengths that the car does not. But they'll both get you from point a to point b. – Robert Harvey Aug 3 '17 at 17:04
12

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.

  • 3
    "Adding a horse to your latitude" is an example I'll use for now on when explaining types. Thank you, sir! – T. Sar Aug 3 '17 at 20:17
5

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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.