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?
-
11"all of those disadvantages will be removed after actual machine code is generated" - No– 8bittreeCommented Aug 3, 2017 at 16:54
-
3I'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 AmmonCommented Aug 3, 2017 at 16:55
-
3Language 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 HarveyCommented Aug 3, 2017 at 16:56
-
4In 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 HarveyCommented Aug 3, 2017 at 17:01
-
6So 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 HarveyCommented Aug 3, 2017 at 17:04
2 Answers
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.
-
4"Adding a horse to your latitude" is an example I'll use for now on when explaining types. Thank you, sir!– T. SarCommented Aug 3, 2017 at 20:17
-
Upvoted for the examples in assembly. I think few people develop that intuition. Commented May 30 at 14:30
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.