Geeks With Blogs

News
Charles Young
The vexed question of language performance came up a couple of times at the ORF conference last month.   I have long suspected that the Rete community has accidently stumbled across an answer to our climate change problems.   All the heat energy ever needed by the population of this planet could probably be generated by getting a bunch of Rete rules engine techies in a room and setting them free to debate comparative engine performance for the rest of time.   Lots of hot air, but hopefully not as much CO2 compared to burning fossil fuels.
The issues at the conference were, in part, about the theoretical performance possible in programmes written in different languages.   Can rules engines written in Java (I will also include C# as a representative .NET language) ultimately compete with engines written in C?   Is C (and perhaps C++) inherently the more performant technology?   For my part I remain ruthlessly agnostic on this vexed question.   Here is why.
Let me try to explain my arguments with some degree of formalism.   Let’s hypothesise that, for any programme P, there exists an optimal implementation, Po, such that no implementation of P provides greater performance than Po.   If p represents performance (higher is better), we can state this hypothesis as:
p(Po) ≥ p(Pn)
where Pn ∈ {P1, P2, ...}
where {P1, P2, ...} is the set of all possible implementations of the programme P.
This is a very questionable hypothesis.   How do we measure or determine optimal performance?   What if optimal performance is not an attribute of P alone, but, more plausibly, of the combination of P with given hardware, operating system and run-time environment. Much also depends on the compiler technology we use to compile P, and therefore on our choice of language.    We might also ask how we can define P in a way that allows comparison. If two very different implementations of P exist that provide the same outputs for the same inputs, are they implementations of the same programme?   We could argue that for ever.   I will, however, assume that they are for the sake of the following argument, even though I am aware of many reasonable objections.
We will brush aside all these reasonable objections for the moment, and assume simply that for a give P, Po exists.   My first question is this:
1.       For a given programming language, L, is it theoretically possible to implement Po? 
  •  Java or C#?   Probably not.   We don’t have full control over native code generation, and we have to live within the confines of the run-time environment.   At best, we may hope to approximate to Po.   We can represent the set of all possible Java and C# implementations of P as {LJavaP1, LJavaP2, ...} or {LC#P1, LC#P2, ...}.
  •   C? Probably.   C provides a huge amount of control over the emitted code.
  •  Assembly Language? Yes.   If it can’t be done in assembly language, it can’t be done (we will ignore issues over the use of special chipsets, etc.).
Based on the above, it certainly appears reasonable to consider that C is the faster language when compared to Java or C#.   However, consider my next question:

2.       For a given P, can we determine Po beyond any doubt?  

On what practical basis can we determine that a given codebase represents Po, and not simply a member of {LP1, LP2, ...}?   For a very small, very simple programme, running on a given platform in a given environment, it may prove possible to formulate some formal proof of Po.   For a programme of any size or complexity, this will rapidly become a practical impossibility as we start to factor in all the many variables that influence performance.  I suggest that this is probably NP-Hard.
Where P exhibits any complexity then whatever language we choose we are only ever likely to implement a member of {LP1, LP2, ...}.   We simply won’t be able to determine Po, let alone work out if we have achieved it.   Think about it.   How much real-world code have you written where you can truly state, hand on heart, that you know for sure that it cannot be optimised further.
My third question is similar to the last.

3.       For a given P, can we determine LPo beyond any doubt? 

...where LPo is the most optimal implementation of P possible in L.

If it is a practical impossibility, in all but the most trivial cases, to determine Po, then for similar reasons it is probably impossible to determine LPo for a given language.    The same general reasoning applies.
My final question is this:

4.        Can we assert with certainty that it will always be possible to maintain the following relationship:

p(Po) – p(LCPn) < p(Po) – p(LJavaPn)

...where a clause in the form of p(Po) – p(LPn) represents the difference in performance between Po and LPn.  

In natural English, this assertion states that we can always find a way to approximate more closely to a theoretical optimal implementation in C than we can in Java.   If we can answer ‘true’, then C is, beyond doubt, faster than Java. If we can answer ‘false’ then the situation is less clear.   Java may sometimes be as fast as or faster than C.   If you are a .Net developer, substitute C# for Java.
Some believe this assertion is true. Others believe it is false.  I contend that question 4 is pointless.
On the basis of the answer to question 2 we cannot practically determine Po, and hence it is not possible to determine a value of p(Po) – p(LPn)  with any certainty.   This would not matter if we could determine a value of LPo for each language.   If we could do this we could implement each LPo and then apply a comparative performance test.   However, on the basis of the answer to question 3, this is also likely to prove a practical impossibility in all but the most trivial cases.   We cannot, therefore, determine if LPn = LPo. Hence, we cannot know if we have implemented LPo and cannot therefore apply the comparative performance test.   We have no hope of determining if the assertion in question 4 is either true or false. There is no practical way to answer the question.
Let’s say you compare a C rule engine with a Java engine and determine that the C engine is faster.   You cannot know for sure if someday a new version of the Java engine may be released that will perform faster than the C engine.   If that happens, you can’t be sure that later on a new version of the C engine will be released that performs faster than the Java engine.   You can never be sure that you have reached the level of optimal implementation in terms either of a given language or of a theoretical Po.    So stating that ‘C is faster than Java/C#’ on the basis of these comparisons is a pointless exercise in futility. You can claim what you want.   It’s just a matter of personal belief.    I therefore conclude that the C vs. Java/C# performance question cannot be resolved in any absolute sense.
Now, there is still an obvious problem with the argument.   I have repeatedly stated that the argument holds only if P is non-trivial.   If we can determine Po and LPo for a very small, very simple P (e.g., a programme that outputs “Hello World” to stdIO and then terminates), then why can’t we simply compare performance for implementations of our simple P and prove, or disprove, the assertion in question 4?
Clearly, this reasoning does not work.   The assertion in question 4, when properly formulated, is stated in regard to the set of all possible implementations of P that we might create, which is unbounded for Turing machines, although ultimately bounded for real-world computing devices.   In reality, we would have to prove that p(Po) – p(LCPn) < p(Po) – p(LJavaPn) holds, or does not hold, for every possible P.
Putting this is plain English, even if we can prove that C is faster than Java for our simple “Hello World” programme, we cannot reasonably infer from this that C is faster than Java in any general or absolute sense.
This highlights the fundamental problem with micro-benchmarks.   If you carefully select a constrained set of simple programmes, you may be able to show that one language allows you to approximate more closely to, or even achieve, Po compared to another language for programmes in that set.   However, you haven’t proved the assertion for all possible programmes.   Hence, micro-benchmarking cannot resolve the C vs. Java/C# performance question.   The best you can hope for is that by selecting lots of varied micro-benchmarks which test a wide variety of different facets under a broad range of conditions, you can build a convincing body of evidence that suggests that one language is more likely to provide better performance than another in most scenarios.   Another approach is to use complex benchmarks.   If done well, this is really not that different to using a large and varied number of micro-benchmarks.   You can, at best, form a general picture of how performant a technology is compared to another, but you can never be certain of your results.
There are all kinds of claims out there about which language is faster.   People have strong beliefs both ways.   One thing I am convinced of.   They don’t know what they think they know.   Not for certain.
Reality Check
One obvious objection to my arguments above arises naturally when you extend the comparison to certain other languages.   Take a dynamically-typed language, for example.   Surely it reasonable to conclude that C is faster than, say, Ruby or Python.   If that is the case, then it appears that the argument I make cannot be applied generally, and must be suspect.
For my part, I think the argument broadly holds, but needs qualification.   Let’s consider three observations about today’s dynamic languages:
  • There is a straightforward and convincing reason why the mechanisms behind dynamically-typed language result in slower performance in most scenarios.   The type system is a fundamental part of a language and touches virtually every aspect of that language. Dynamically-typing is defined by the performance of type checking at run-time rather than compile-time.   The performance of any non-trivial P will be affected adversely by this type-checking.
  • There appears to be a near-universal consensus that C is faster than dynamically-typed languages (I’m sure someone somewhere disagrees).
  • Available benchmark results provide clear evidence that C does indeed appear faster than, say, Ruby or Python.
Given the above, a general statement that ‘C is faster than Ruby’ seems reasonable.   It is not that the arguments I made above are invalid, but simply that certain well-understood aspects of dynamic-typing lead us to a non-controversial and universally accepted conclusion in this respect.
None of the three observations above hold true for Java or .NET.   Let’s take them in turn.
  • Over time, several commentators and computer scientists have offered explanations of why C is faster or slower than Java or .NET.   Any one of these arguments may appear plausible when read in isolation.   However, taken together, an entirely contradictory picture emerges.
  • There is near-universal lack of consensus about this issue with strong opinions on both sides of the argument.
  • Available benchmark results, when taken together and interpreted reasonably, paint a very uncertain and mixed picture.
In this context, I believe the argument I have outlined above not only holds, but provides the most realistic approach to handling the question of comparative performance between non-trivial codebases written in different languages.

 

Posted on Friday, November 13, 2009 5:50 PM | Back to top


Comments on this post: C or Java/.NET. Which is fastest? Does anyone know?

No comments posted yet.
Your comment:
 (will show your gravatar)


Copyright © Charles Young | Powered by: GeeksWithBlogs.net