bpendlet@esunix.UUCP (Bob Pendleton) (10/07/88)
From article <1988Sep29.192410.246@utzoo.uucp>, by henry@utzoo.uucp (Henry Spencer): > > Right. In other words, what we have done is to redefine the semantics > of C to allow *NULL. Thus guaranteeing that all programs with this flag > in the UIF will be at a serious performance disadvantage on machines > that don't allow *NULL. The semantics of *NULL are inherently and > incurably machine-dependent, and any "universal" intermediate format > file which specifies them is machine-dependent. I thought the semantics of *NULL were implementation dependent. Note, I did not say machine specific. There is a difference. I was trying to show how implementation specific decisions can be passed on in a portable way and be made to work, even on machines where they don't make sense. The idea is, after all, to provide portability. Efficiency is, of course, a critical issue. If no one cared how long something takes, computer development would never have started. Take a look in the "Proceedings of the SIGPLAN '84 Symposium on Compiler Construction" entitled "A Portable Optimizing Compiler for Modula-2" page 310, by Michael L. Powell, who was at the time at DECWRL. I've included some relevant quotations from the paper. "3.3 Optimizing Checks "Runtime checks are often disabled in production programs because they "cost so much. For example, the P-code translator, written in Berkely "Pascal, runs 3 times slower when runtime checks are enabled. By "optimizing runtime checking, its benefits can be obtained at a "fraction of the usual cost. "The runtime checks performed by the compiler include checking variant "tags, subranges, subscripts, and pointers. The pointer check catches "not only bad addresses, but also pointers to objects that have been "disposed. Checks are entered into the expression tree like any other "expressions, appearing to be unary operators. These expressions are "often common subexpressions or loop invariants. Such expressions are "also eligible for loop induction, which could replace a subscript "check in a loop by checks of the lower and upper bounds of the loop "index. The following table is made from information contained in two tables in the paper. The compilers being used are Berkeley Pascal (pc), the Berkely Unix C compiler, the DEC VMS C compiler, and the Powell Modula-2 compiler. All times are in VAX 11/780 cpu seconds. Opt Check All Opt Program Berkeley UNIX DEC DEC DEC name Pascal C C Mod-2 mod-2 perm 2.7 2.6 2.5 2.0 2.4 Towers 2.8 2.6 2.7 1.9 2.6 Queens 1.6 1.0 0.7 0.9 1.3 Intmm 2.2 1.7 0.8 0.8 1.1 Mm 2.7 2.2 1.3 0.9 1.2 Puzzle 12.9 12.4 4.9 4.1 6.5 Quick 1.7 1.2 0.8 0.8 1.2 Bubble 3.0 1.7 1.0 1.0 1.9 Tree 6.4 6.2 3.4 1.9 2.2 FFT 4.8 4.1 2.6 1.6 2.0 The first 3 columns give execution times with all available optimization turned on. The 4th column gives execution times for code generated with all optimizations turned on and all checking turned off. The 5th column gives execution times with all optimizations turned on and all runtime checking turned on. Comparing columns 4 and 5 we see that runtime checking can increase runtime by as much as %50 for this Modula-2 compiler. But, with checking turned on it generates code that is as much as twice as fast as code compiled with the Berkeley C compiler. Notice that the compiler is doing a lot more than just checking pointers for equality to NULL. This table certainly shows the cost of full runtime checking. I hope the Berkeley C compiler has been improved during the last 4 years. I'd hate to think we were worrying about the cost of runtime checks when just using a good compiler can get you back 4 or 5 times what you loose to run time checks. Going on to the topic of a Machine Independed Intermediate Language, the paper has this to say: "Our P-code is a dialect of the P-code originally developed for Pascal "compilers [Nori et al. 73]. P-code looks like machine language for a "hypothetical stack machine and has been used successfully for "portable compilers. For example, the Model programming language "[Johnson and "Morris 76], which generates P-code, runs on the Cray-1, "DEC VAX, Zilog Z8000, and Motorola MX68000 computers. The principle "features that distinguish this version of P-code from others are "support for multiple classes of memory and specification of types and "bit sizes on all operations. ... "The P-code translator is a one-pass compiler of P-code into VAX code. "It performs the compilation by doing a static interpretation of the "P-code. ... I've used this technique myself. It works very nicely. I first saw it described in the BCPL porting guide, which I read in ~75, I don't know when it was written. It is an old and well understood technique. "Although P-code is machine independent, the P-code translator is "inherently machine dependent. Decisions of what registers and "instructions to use to implement a particular P-code operation are "left entirely to it. However, many of the strategies span a wide class "of computers, in particular, register-oriented ones. thus the global "structure of the P-code translator and many of its strategies are "common to all the implemenations, adding a degree of machine "independence. I hope that the existence proofs that others have posted, plus this information convinces you that the concepts behind MIILs have been known, and in use for many years, that MIILs can be used as part of an optimizing compiler system, and that there need not be any performance loss as a result of using one. > How does the target machine's translator know whether it can do the > arithmetic that the program wants? This cannot be stated in the UIF > unless the compiler can figure it out. It can't simply be based on the > compiler's host, because then a program which *doesn't* require the full > range of the host's arithmetic (think of a 32-bit host and a 16-bit > target, and a program which is careful not to depend on 32-bit numbers) > again takes a massive efficiency hit for no good reason. > > It is a property of the *program*, not the host it is compiled on, whether > it requires 32-bit arithmetic, the ability to dereference NULL pointers, > etc. It is difficult to deduce these things from the program, unfortunately. > Modifying the program is not the answer, because there is a massive payoff > for being able to use this technology on existing programs. Accepting the > efficiency hits is not the answer, because there is another massive payoff > for not losing efficiency. Yes, it is a property of the program. But, if the language doesn't allow you to declare the actual size of the data you are doing arithmetic on, if the language doesn't define the semantics of pointer operations, then where am I going to get the information needed to make these decisions? We could have compiler options that let you tell the compiler things you can say in the language. We could forced to compile by saying something like: cc -short=16 -long=32 -catch_null to define the size of the arithmetic and how to handle dereferencing null pointers. Or, the compiler can get it from the host the program is compiled on. Or, we can modify the definition of the langauge so that the size of an int and what it means to dereference NULL are explicitly stated. Or, we could use pragmas to supply the information. No matter what mechanism is used, the information must be provided if a program is to have any chance of being automagically portable from one machine to another. You mention the case of a program that has been designed so that it can be run efficiently on a machine with small ints (say 16 bits). If the program is developed on a machine with large ints (say 32 bits), how does the programmer really know if it will work using small ints without testing it on a machine with small ints? The only practical way that I can think of is to use a compiler that allows you to tell it how big an int is and that generates runtime checks to make sure that small int semantics are enforced. Testing capabilities of this sort would allow you to safely put the contstraint that ints must be >= 16 bits long into the MIIL for the program. The same thing goes for the *NULL problem. Test with runtime checks for references to *NULL. Then you can put the assertion that NULL is not derefrenced into the MIIL. Personally, I'd keep the runtime checks. Midnight calls from customers are bad enough, but having the program die without even printing a message that will help me get the customer running again are awful. > ... Much good stuff deleted > efficiency loss for the sake of correctness, but that is not the way the > market thinks, and trying to re-educate the market is a really good way > to go broke (if you are trying to do it for profit) or to be laughed at I can't resist. Look at who I work for and tell me I don't already know. :-) If that doesn't make any sense to you, look up Evans & Sutherland in "Fundamentals of Interactive Computer Graphics" by Foley and Van Dam. Especially the stuff about the PS300. Of course I could also tell you about the commercial success (I think 20 copies were sold) of my FORTH compiler that "fixed" everything I didn't like about FORTH. > When I talk about the idea not being > "practical", I don't mean it is technically ridiculous, I mean that it > WON'T SELL -- people will not adopt it, so proposing it is pointless. It will sell if you push it hard enough. If the alternative is having to include IBM-PC/MS-DOS compatiblity as part of every machine you make, then I think the computer manufacturers will work very hard to make something like this sell. Consider; a new machine won't sell without a large existing base of applications. And, software developers can't afford to develop for machines that don't have a large installed base. A standard MIIL allows hardware vendors to compete on a price/performance basis and provides software vendors with a huge installed base of possible customers. So a software distribution standard looks like a win for hardware vendors, software vendors, and end users. A win win win situation isn't going to be passed up. Consider how hard it was to get people to stop laughing at the idea of an operating system written in a high level language only 10 years ago. The technology development that made that practical didn't stop. -- Bob Pendleton, speaking only for myself. An average hammer is better for driving nails than a superior wrench. When your only tool is a hammer, everything start looking like a nail. UUCP Address: decwrl!esunix!bpendlet or utah-cs!esunix!bpendlet
henry@utzoo.uucp (Henry Spencer) (10/11/88)
In article <997@esunix.UUCP> bpendlet@esunix.UUCP (Bob Pendleton) writes: >You mention the case of a program that has been designed so that it >can be run efficiently on a machine with small ints (say 16 bits). If >the program is developed on a machine with large ints (say 32 bits), >how does the programmer really know if it will work using small ints >without testing it on a machine with small ints? ... Competent programming by people who understand portability. We know this works, we do it. -- The meek can have the Earth; | Henry Spencer at U of Toronto Zoology the rest of us have other plans.|uunet!attcan!utzoo!henry henry@zoo.toronto.edu
chip@ateng.ateng.com (Chip Salzenberg) (10/14/88)
According to henry@utzoo.uucp (Henry Spencer): >In article <997@esunix.UUCP> bpendlet@esunix.UUCP (Bob Pendleton) writes: >>If the program is developed on a machine with large ints (say 32 bits), >>how does the programmer really know if it will work using small ints >>without testing it on a machine with small ints? ... > >Competent programming by people who understand portability. We know >this works, we do it. Just a confirmation and a testimonial here. C News Alpha runs just fine on a '286, thanks much to Messrs. Spencer and Collyer. -- Chip Salzenberg <chip@ateng.com> or <uunet!ateng!chip> A T Engineering Me? Speak for my company? Surely you jest! Beware of programmers carrying screwdrivers.
henry@utzoo.uucp (Henry Spencer) (10/16/88)
In article <1988Oct13.202604.22464@ateng.ateng.com> chip@ateng.ateng.com (Chip Salzenberg) writes: >Just a confirmation and a testimonial here. C News Alpha runs just fine >on a '286, thanks much to Messrs. Spencer and Collyer. Dept of Minor Nits: Collyer and Spencer. Geoff did all the hard stuff. -- The meek can have the Earth; | Henry Spencer at U of Toronto Zoology the rest of us have other plans.|uunet!attcan!utzoo!henry henry@zoo.toronto.edu
hermit@shockeye.UUCP (Mark Buda) (10/22/88)
In article <1988Oct13.202604.22464@ateng.ateng.com> chip@ateng.ateng.com (Chip Salzenberg) writes: |According to henry@utzoo.uucp (Henry Spencer): |>In article <997@esunix.UUCP> bpendlet@esunix.UUCP (Bob Pendleton) writes: |>>If the program is developed on a machine with large ints (say 32 bits), |>>how does the programmer really know if it will work using small ints |>>without testing it on a machine with small ints? ... |> |>Competent programming by people who understand portability. We know |>this works, we do it. | |Just a confirmation and a testimonial here. C News Alpha runs just fine |on a '286, thanks much to Messrs. Spencer and Collyer. GNU CC, however, doesn't. I expected more from them... sniff... -- Mark Buda / Smart UUCP: hermit@shockeye.uucp / Phone(work):(717)299-5189 Dumb UUCP: ...{rutgers,ihnp4,cbosgd}!bpa!vu-vlsi!devon!shockeye!hermit Entropy will get you in the end. "A little suction does wonders." - Gary Collins
ken@gatech.edu (Ken Seefried III) (10/24/88)
In article <222@shockeye.UUCP> hermit@shockeye.UUCP (Mark Buda) writes: >|Just a confirmation and a testimonial here. C News Alpha runs just fine >|on a '286, thanks much to Messrs. Spencer and Collyer. > >GNU CC, however, doesn't. I expected more from them... sniff... >-- I'll be kind and simply call this kind of talk silly. The 80286 is an amazingly stupid design. the GNU group made some assumptions (most of them pretty reasonable) when the built gcc and its ilk. One of the biggies was 32-bits implimented in a semi-reasonable way. The 80286 is niether 32-bits nor reasonably implimented. Since the target audience for 'gcc' was 680x0, 32x32, etc. based, and the rest of the world is moving that direction, and they wanted to produce a high quality compiler, these requirments make a whole lot of sense. I cannot believe the unmitigated gall of some people ( 'I expected more...' ). 'gcc' will not run on the PDP-11/2 in my closet, nor will it run on the old Z80-CP/M machine that I use for a terminal, but then it was never ment to, so I tend not to bitch and moan. Moral: if you want to run real software, get real hardware... Oh, and please don't whine that its all that you can afford. I know that story inside and out (being a student, and having saved a whole bunch of pennies for my computer). >Mark Buda / Smart UUCP: hermit@shockeye.uucp / Phone(work):(717)299-5189 ...ken
hermit@shockeye.UUCP (Mark Buda) (10/27/88)
In article <17536@gatech.edu> ken@gatech.UUCP (Ken Seefried iii) writes: #In article <222@shockeye.UUCP> hermit@shockeye.UUCP (Mark Buda) writes: #>|Just a confirmation and a testimonial here. C News Alpha runs just fine #>|on a '286, thanks much to Messrs. Spencer and Collyer. #> #>GNU CC, however, doesn't. I expected more from them... sniff... #>-- # #I'll be kind and simply call this kind of talk silly. The 80286 is an #amazingly stupid design. I agree wholeheartedly. The only semi-reasonable processor in the family is the 80386, and that's pretty bad too. #the GNU group made some assumptions (most of them pretty reasonable) #when the built gcc and its ilk. One of the biggies was 32-bits implemented #in a semi-reasonable way. The 80286 is niether 32-bits nor reasonably #implemented. Since the target audience for 'gcc' was 680x0, 32x32, etc. #based, and the rest of the world is moving that direction, and they wanted #to produce a high quality compiler, these requirments make a whole lot of #sense. I think the problem is that I didn't make something clear in my original posting. I don't want to compile *for* the 286. I want to compile for a 386, on a 386, but the compilers I have only understand 8086/286, and I'm damned if I'm going to spend hundreds of dollars for a compiler I'll only use once. #I cannot believe the unmitigated gall of some people ( 'I expected #more...' ). The only thing I object to in GNU CC is the attitude that you can put a pointer in an int or pass '0' for a null pointer where the portable thing is '(char *)0' or NULL. #Moral: if you want to run real software, get real hardware... # #Oh, and please don't whine that its all that you can afford. It's not mine. I'll keep my mouth shut from now on.