Human vs Computer

In my post Disruptive Programming Languages, I snared Ian Griffiths into my trap. Ian Griffiths is an .NET author and instructor at DevelopMentor and writes lots of low-level .NET articles on the web. I own his book .NET Windows Forms in a Nutshell. Maybe he’s getting back at me, after I was surrendipitously able to score one up on him on weak delegates in a prior post. Thanks, Ian, for the opportunity to present myself as your peer and pair off my sophomoric ideas against your expericnce and research.

Here’s a simple exercise: How many words can you come up by rearranging the three letters in the word TEA, including TEA? Even though there are six possible words that one can make from rearranging the letters, it’s likely that you will not have found every word. You can also try this for many other words with my WordFinder application, which I’ll post later. A computer can search for and find every instance of a valid word each time without fail. A human may miss some words that he knows as well as some he doesn’t know.

I often think about Mathematica, which I use to solve all kinds of symbolic math problems. The results that I get from this program are better than I can obtain by hand—much faster, often instantaneous, and without errors. It’s a good example of artificial intelligence, where the computer consistently outperforms humans in intelligence task. I also believe that is the ultimate destination of all AI.

When I was speaking about compiler output surpassing human output earlier, I was viewing this as part of a long-run trend. Most compilers don’t utilize logic programming, which is useful for emulating human reasoning, although we might be seeing some of that with the “whole program optimization” feature in C++.

Also, when I talk about compilers, I am speaking rather generally. In some sense, I am comparing a computer-managed process against a human-managed one. When we entrust more and more work to a computer, there may be more overhead initially, but, over time with more optimization and because of the computer’s advantages in speed, the computer-based approach will likely far surpass the manual labor.

I would include .NET garbage collection as a computer-managed process which competes well with C++’s finalistic determinization, a manual process, even though the latter has more domain information. Over time garbage collection will improve from better algorithms and coevolution. Through coevolution, processors have evolved to work better with compilers than with humans. Future architectures will be optimized for garbage collection. (I am reminded of processors that were optimized for Lisp decades ago.)

I believe future languages will be declarative and symbolic. Current control constructs will be replaced by various forms of search, which optimize away to conditionals and loops in the simplest case. Future languages will probably resemble functional and logical languages like Prolog more so than the imperative languages most developers use today. I suspect that our present day of writing low-level control constructs leads us to less sophisticated programs, because programming proceeds at a human pace rather than at a computer’s pace.

I wrote earlier that compilers can currently emit C code that can run faster than handwritten assembly code. Ian responded:

“Not that old chestnut!” This statement is only true for small values of developer capability.

Intel still release hand-crafted performance libraries. The ones I've used (for image processing) still beat the socks off anything produced by a compiler - and we're not talking something that's a few percent faster. These libraries run several times faster than the same algorithms written in C and compiled by the compiler.

Ian states that the statement is true only for small values of developer capability, but that probably still represents an overwhelming majority of developers I imagine—and not just those who are don’t know assembly language. He means you—mainstream developer.

I admit that the current C# and JIT compilers aren’t very good optimizers. The C++ compilers are probably better ones in the Windows platforms, though C/C++ have some difficulties with aliasing because of pointers.

I don’t think the Intel libraries are a good example. The libraries themselves could almost be considered part of compiler. Intel does develop their own optimizing compilers with its finer understanding of their processors, since it doesn’t have access to the commercial compilers of other vendors, which are more platform-agnostic. Intel contributes to these other compilers in the only way it can by providing libraries. The type of code that Intel produces in its performance libraries may very well be handwritten; however, the code is written by chip designers themselves, very likely aided by extensive computer analysis, and probably have undergone lengthy development and testing. Also, these libraries can make additional assumptions that a general compiler cannot. Users are not likely to write equivalent code without the deep level of knowledge that Intel programmers possess.

I also wrote that if the compiler has the same information about a problem as a human, the compiler should theoretically alway be able to produce superior code.

That's patently bogus. The human will always be able to do at least as well as the compiler because if all else fails, the human can work through the same set of rules the compiler is using. Indeed, there's an age-old technique for guaranteeing that you do at least as well as the compiler: get the compiler to write your first version for you, tweak what it gives you and always compare against the original when benchmarking. You are guaranteed to do at least as well as the compiler, because if you make any changes that make things worse, you just back them out again.

Here’s why, if a compiler encodes all the rules that a human would apply in optimizing the code and both the human and the computer have the same information, then a compiler can successively apply rules until no more can be applied. Since the application of one rule can affect the subsequent application of another rule, the compiler may have to backtrack to consider alternative reorderings of rules. Assuming the computer has applied all rules, a human could not perform better, because the computer, using the same rules, has already considered any enhancement the human could add.

Because humans built computers, my statement consists of few circularities. Anything produced by a compiler is also indirectly produced by a human. The other circularity that Ian mentions is that a human could modify the output of the compiler to produce better code than the compiler, unless the compiler has already considered all of the human’s enhancements prior to output. If a compiler supports inlined assembly as Visual C++ does, you could also use the same argument in reverse, in which you feed back the human-modified code into the compiler; the resulting code of the compiler will be as good as the human.

Optimized code is notoriously difficult for humans to navigate. Something as simple as reusing a variable for a different purpose in assembly can make code very hard to follow. When modifying optimized code, humans often introduce subtle errors. Many times, an “obvious” improvement to optimized code actually reduces performances.

In many cases, it will not be feasible for a human to reasonably understand the compiler output. Code may be generated as a fully optimized state machine, for example. The output of  a neural network, used in machine vision and speech recognition, or a genetic algorithm is very hard to modify, if either technique was used in compiler.

Processors are also increasingly being designed for compilers and not for humans. I haven't written in assembly since the early 1990s, but I know that one considers not only instruction cycles but a host of new constraints like instruction ordering.

Ian then asserts that my axiom "if the compiler has the same information about a problem as a human" has never been valid.

The compiler doesn't have the same information. There is almost always domain-specific information that can be brought to bear on the problem which cannot be put into source code. (And in any case, compilers still don't make use of all the information that is technically available to them today.)

There are at least two situations where the compiler can extract additional domain information, without the human having to include explicit invariants in the code.

1) Profile-guided optimizations. In this case, the compiler uses information from profile data from an instrumented executable to reorder and optimize code. Profiling provides information to the compiler about how people actually use the product, about which code paths actually get hit often.

2) Whole program optimization. The compiler, in this case, considers the relationships between functions by producing theorems about each function, and then going back to each function and reoptimizing based on those theorems.

These two optimizations can allow a compiler to indirectly deduce doman-specific information. Futhermore, the information obtained can be even more valuable, because the compiler can generate a far greater amount of information, most of which may be nonobvious. These kinds of optimizations also make it difficult for a human to modify code without adversely affecting its performance, because the assumptions that the compiler was able to make are not explicit in the code output.

So your statement is untrue. It's also not really relevant. The important thing is that compilers are good enough. They certainly do a better job in the time they take than a human could do in the same time, so it's all about saving developer time, not machine cycles. Using higher level languages offers a host of benefits, but the quailty of the code is one of the costs, not one of the benefits - we trade quality of code for speed of development.

Of course the other reason it's not all that relevant is that an awful lot of code isn't limited by raw CPU speed. The usual killer is sitting around waiting for stuff to come out of main memory and into the cache. That's something that you can't fix by tweaking the compiled code - you need to address either the data structures or the algorithms or both.

So compiler output really isn't that hot. The key thing is that most of the time it doesn't need to be - it simply has to be good enough.

I agree the bottlenecks today has very little to do with instuction speed. The bottlenecks are memory access and the efficiency of algorithms and data structures used. The compiler may still be able to help with the latter two cases, but more likely it makes more sense for a company to focus on other productivity features. This only strengthens my argument that languages need to get higher-level. I don’t believe that quality of code is necessarily words with higher level languages. You are more likely to write higher quality code in C than in assembly and, also, in C++ than in C.

I also want to point out that compiler output is not limited to assembly, but also to intermediate languages. In such cases, the benefits of compiler-generated code over human-generated code may be more real in terms of performances, not just in productivity.

By the way, there are five words that can be made from exercise earlier—every combination of letters except AET.

Comments

[keith ray]

Compilers can do better than humans for code generation for RISC processors, because the rules for optimum instruction-scheduling for RISC chips are numerous and arcane, and vary depending on the particular processor. (This chip has gotten simpler, so the compiler has to be more complicated to compensate).

For example, a compiler may insert a NOP instruction immediately after certain other instructions in order to get optimum speed out of the branch-prediction capabilities of a PowerPC processor, but it may make a speed difference only for certain processors like the PowerPC G3 and not for the G5 (or vice versa).

[optionsScalper]

Mr. Moise,

I Love this entry. Here are some non-compiler human-competitive results. To give a simple perspective, these results, as derived by a GP, are better than any human could produce at any time during human history. Essentially, take all of the experts in a discipline, allow them to work on some hard problems, get the best answer. Then hand the problem to a GP Engine (with the same information available to the experts) and get a better answer.

http://www.genetic-programming.com/humancompetitive.html

http://www.genetic-programming.org/gecco2004hc.html

Actually, I noticed that you lost Stephane as a subscriber. I'll take his "subscription" to this blog any day (as long as it doesn't cost me anything). It's a pity that someone should choose such a trivial topic to decide to discontinue a reasonable public discourse.

In the phylogeny of programming languages, we are still in our infancy.

I'm not calling you out, but I need some further information to understand your point.

I'd like to see some math to validate your point. You have a qualitative perspective. Mr. Griffiths appears to have a qualitative perspective as well.

I'm a fan of Mathematica, but it is not Artificial Intelligence at work. Much of what is in the core of the engine is just plain old implementations of mathematics that are in the public domain. The good folks at Wolfram have just found deterministic (or low-order probabilistic) paths for the solutions in their search space. Please refer to this link, for my position, and which I believe, even with your misstatement, further makes your point in the above argument:

http://www.wolfram.com/products/mathematica/technologies/algorithm.html

I'm unaware of any Mathematics package in the public domain that, in the heart of its engine for symbolic regression, symbolic differentiation or symbolic integration, uses a non-deterministic AI methodology. It has not been shown that AI can reduce NP-Complete Graph Problems (or otherwise) into P.

There are instances of the use of Genetic Algorithms in the S-PLUS non-linear optimization package and I'm certain there are others, but not in any core symbology engine to date.

Read my "Down the Rabbit Hole We Go" post for some of the topics that we at JJBR consider. I tend to agree with your position. I just find your arguments in disarray and consequently, not convincing (and I'm not even a proper constructivist).

Regards,

-O

[Wesner Moise]

I tend to view AI as essentially search (broadly speaking).

When I speak of Mathematica as an example of successful AI, I am referring to its ability to manipulate symbols and its large table of rules, not to its use of numerical techniques. The AI is in the infinite evaluation system, the pervasive and sophisticated pattern matching, and the rule transformations occurring at each evaluation step. It's also in the ability to simplify expressions and in the solver, which can work with symbolic expressions and constraints.

There's an old adage that as soon as a problem is solved, it ceases to be called AI.

As for saying compiler output should surpass human output, I did leave open the possibility that a compiler may not be able to fully optimize its output because of time constraints or the intractability of the problem. In those cases, humans may be able produce to a better solution than compiler, if its optimization was terminated earlier.

You clearly have a stronger mathematical background based on your blog. I don't have a master's background, and though I studied applied mathematics, I don't have the formal tools you have and need to rely more on intuition.

[optionsScalper]

Mr. Moise,

wespoints = 0;
1. You did pivot tables. I worked on Wall Street where these things were constantly in use. wespoints += 20;
2. You are an Excel guy. wespoints += 100;
3. You trust your intuition and I think you have a pretty good compass. wespoints += 20;
4. You classify search as AI. wespoint -= 40;

You are one of the few people that I've read who was unafraid to post a regex quiz and then actually identify that the regex is based on the NFA.

I'm subscribed because you are sensible guy. That and you have verbose=on.

-O

[Ian Griffiths]

Hi Wes. I'd be honoured for you to consider me as your peer, so enough with the modesty!

I like the phrase 'finalistic determinization' - it sounds rather apocalyptic! I'm guessing you meant deterministic finalization. I don't think it's really a direct competitor to GC, but that's a different topic from the main one at hand. I just brought it up because I liked the phrase. :)

On Mathematica, has it ever advanced mathematics by coming up with new theorems in the way that, say, mathematicians do? (And didn't Godel and Turing both have something to say about the limits of automated systems of proof?)

Why do you not think the Intel libraries are a good example? Just because they are part of the toolchain doesn't mean they aren't an important example. They are a library, not part of the compiler. And if part of the library had to be hand coded because the compiler can't do as good a job, doesn't that prove the point that humans can do better than the compilers today? Dismissing the library as irrelevant because it happen to be supplied as part of a toolset that includes the compiler seems to be cheating when we are discussing the quality of compiler code generation.

Just to be clear, I am absolutely not advocating that developers should use assembly language most of the time, even the developers who are good enough to beat the compiler. Steve Gibson seems to advocate that, but I think he's wrong. When it comes to quality of code *as a function of the amount of effort expended by the developer* the compiler beats the the human every time. And perhaps more importantly, on the results:effort ratio, a suitable prepackaged library of reasonable quality beats writing code no matter what language you were going to write the code in.

I'm all in favour of getting the most in return for my efforts, which is why I use high level langauges and libraries whenever I can. Which is most of the time - it has been many years since I had to use assembly language. The extra effort that would be required to hand-code a better solution is typically not worth it these days. IO latency and memory bandwidth are where you tend to take the main hits, and being genuinely constrained by the rate at which instructions are executed is rare, so it's perfectly acceptable to have sub-optimal code gen most of the time.

(Then again, the fact that I no longer work in real time systems is also probably a contributing factor.)

Regarding your specific response to the second paragraph you quoted from me, you are starting from the bogus assumption that the compiler knows all the rules. This is almost always untrue for one simple reason: some of the rules you can bring to bear to optimization are domain-specific. The compiler is always hamstrung because its rules have to work everywhere. I can use rules that take advantage of invariants that will not be visible to the compiler.

At this point, people usually start theorizing about how a compiler with a complete view of the whole program could in principle infer these invariants by analyzing the code, and then go on to use the same techniques as me. (Which is exactly what you do.) But there are two problems here. One is the issue that compiler technology just isn't there yet, so if we're discussing what compilers can achieve in practice, theoretical arguments based on what compilers might conceivably do in the future don't fly. Whole program optimization is a relatively new feature, and is a long way realizing the full potential of this strategy.

The problem second is perhaps more serious: often the compiler can't have total knowledge because of the way code is composed. In the classic C++ compilation model, DLLs and .LIBs put hard barriers in the way of what the compiler can see, because the libraries are compiled in advance of being used. In the .NET model, stuff gets compiled long before the runtime sees the whole world. In theory you could change .NET - in principal the JIT compiler does actually have a complete world view, but again, we're not there yet.

Just let me requote the original statement you made:

"now compilers can currently emit C code that can run faster than handwritten assembly code, because of better optimizations as well as new processors designed toward compiler-generated output"

I stand by my statement that this claim, which is about current technology rather than what might one day be possible, is only true if the handwritten assembly code is of low quality. Maybe the day will come when compilers really can always outshine humans, but today they certainly can't. I suspect they never will.

If you consider a graph showing quality of code output on the X scale, and the graph plotting the distribution of developers able to achieve that quality of assembly code, it's probably fair to say the the compiler is well to the right of the center of the distribution curve. chances are it's in the top 5% of the population. Maybe even the top 1%. And it will continue to go to the right. So there will be a higher and higher proportion of developers unable to beat the compiler. But I don't see it as inevitable that the compiler will eventually exceed every developer's capabilities.

There's another big problem in practice with something like whole program optimization: the vast amount of information available to the compiler turns out to be part of the problem. It cannot possibly explore every possibility because practical concerns like the impending heat death of the universe start to get in the way. Compilers simply cannot consider every possible option in the time available, so they have to prune in order to finish in a useful amount of time. And this selective pruning is often where things go wrong - it's an area where compilers are often weak.

Wes: "Optimized code is notoriously difficult for humans to navigate. Something as simple as reusing a variable for a different purpose in assembly can make code very hard to follow."

Sure, but you wouldn't be writing hand crafted assembly if you didn't really have to, and this is one of the costs of entry. A decade or so ago I wrote a lot of code for embedded systems and device drivers. These were resource-constrained systems, and back then everything was a lot slower anyway. (And I was working in digital video down at the systems layer, where you have very tight realtime constraints, some measured in single digit nanosecond quantities!) If you were using assembly langauge, then the gloves were definitely off. Every sneaky trick in the book was perfectly acceptable.

If you *weren't* doing things like reusing a variable for a different purpose, then you probably have no business writing in assembly langauge anyway. Yes the code is going to be hard to follow, and a pig to maintain because every time you change something you're probably going to have to rewrite vast amounts of code, as it just messed up all your carefully balanced optimizations. But that's just what life is like if you're compelled to squeeze every last drop of performance out. Fortunately, most people don't have to.

You also introduce the idea of feeding human-originated optimzations back into the code through inline asm, and letting the compiler try again from there. Possibly I'm out of date with compiler technology, but inline asm certainly used to be a major headache - it constrained the optimizer rather than helping it because an awful lot of the optimization is done prior to generating machine-specific instructions. There are peephole and scheduling optimizations done after generating target code, but a lot of the important ones are done earlier. By sticking in a lump of asm, you usually end up constraining the possible optimizations earlier in the compile stage.

Keith Ray said:
"Compilers can do better than humans for code generation for RISC processors, because the rules for optimum instruction-scheduling for RISC chips are numerous and arcane"

I've heard that one before too... I've written assembly langauge for embedded systems based on PowerPC, ARM, and a variety of MIPS processors, and assembly language for device drivers on Dec Alpha systems. The argument Keith provides here was put forward back when I was doing this for all those processors. It was demonstrably untrue.

Someone accused me of taking a qualitative approach. Actually I didn't back then. I was strictly quantitative. I would look at the compiler output, time it, and then set about modifying it, and then time it again. If my modified version went faster, I considered this a win. I'm pretty sure that's a quantitative approach. (This is an anecdotal description of course - I don't have figures to hand. But my opinion is based firmly on quantitative observations made over years of practical experience of writing in assembly language.)

The fact is that compilers would do a lot of stuff that on a superficial analysis looked quite clever - reordering, inserting magic NOPS, and so on, all the stuff Keith mentions. But if you spent just 5 minutes looking at the code, and working out why the compiler had done what it had done, any number of fairly obvious improvements invariably sprang to mind. The typical compiler output would contain elements of brilliance right next to instances of sheer stupidity.

At this point someone usually pipes up and says: "Ah, you *think* the compiler's being stupid, but actually it just understands the CPU instruction scheduling better than you do, and you haven't understood how clever it's really being." So at this point I remind you that I would always time the effect of any changes I made. Usually, when the compiler output looked stupid, it's because it was stupid.

The last time I was writing assembly language on a regular basis I could invariably speed the code up by a factor of 3, and often by a factor of 5. It was this kind of work that left me with a pretty low opinion of the quality of compiler output. It gave me the firm belief that the claim that compilers produced better code than humans is only made by people who'd never made a serious and determined attempt to produce better code than compilers...

Obviously compilers will have improved since then - it's been about 8 years since I was writing such code. I'm sure I couldn't improve by a similar margin today. Possibly it's time I tried again to see how far compilers have come along, although Proebstring's Law suggests that the compilers won't yet have caught up.

[rohit]

hi!
i'm not sure how r u suggesting mathematica as an instance of ai. mathematica has fixed domain and will not learn to improve its solving limit.
i will appreciate your explanation.
rohit