brnstnd@kramden.acf.nyu.edu (Dan Bernstein) (09/24/90)
In article <PCG.90Sep23181145@teachc.cs.aber.ac.uk> pcg@cs.aber.ac.uk (Piercarlo Grandi) writes: > Maybe Rubin is a bit rough in expression, but I think that he is trying > to say that he would dearly love to have extensible compilers, I'd like to focus on this point. Upward extensibility through macros and functions is pretty well understood. Its syntax may not be as well understood, but that's not a serious problem. What would it take to make a realistic language downward-extensible? For example, many computers have a way to multiply 32 bits by 32 bits and get each word of the 64-bit result, even if they don't have 64-bit types. How can I take advantage of this in a program? The simplest answer is to settle on a standard way of escaping to the lowest levels of the machine. C has asm(), for example. But this isn't enough. I have to explicitly define a compile-time symbol to choose between the assembler version and the slower, high-level version. I have to learn a new language and write a new routine for every computer where I want a speedup. And if the compiler learns some new optimization tricks or the CPU is upgraded, my ``fast'' code may be worthless. It isn't hard to solve the last problem. The language just needs some construct to say ``compile either this code or that code, whichever you think will come out faster.'' I may want to reorganize the flow of my program if one alternative is better, so the language should also define a compile-time symbol for me saying which alternative it picked. This also solves the first problem. What's tricky is the second problem. How can downward extensions be portable? A sufficiently weird hardware operation may not have any sensible language equivalent, but most of the time it will. So the problem reduces to teaching the compiler to recognize *something* in the langauge that takes advantage of any given instruction. Then programmers use the ``compile this or that'' form mentioned above; the more forms they use, the better chance they'll have of matching the hardware on any given computer. And their programs will still be portable. Comments? ---Dan
Chris.Holt@newcastle.ac.uk (Chris Holt) (09/24/90)
In article <28750:Sep2402:58:2290@kramden.acf.nyu.edu> brnstnd@kramden.acf.nyu.edu (Dan Bernstein) writes: > >I'd like to focus on this point. Upward extensibility through macros and >functions is pretty well understood. Its syntax may not be as well >understood, but that's not a serious problem. What would it take to make >a realistic language downward-extensible? You'd want the components of an abstract machine model to be described in the high-level notation, with an obvious, efficient implementation (e.g. RegisterA := RegisterB + RegisterC would be implemented as a single low-level instruction); and you'd want parameters of the abstract machine to be constants in the environment (e.g. TimeForAddition would return 12 nanoseconds, or whatever). Then, each of the operations might be implemented on each of the machines, either directly or as sequences of other operations; and the conditionals would be in terms of If TimeForAddition(AbstractStackMachine) < TimeForAddition(AbstractVectorMachine) Then Push(Pop1+Pop2) Else VectorR1 := VectorR2 + VectorR3. This obviously isn't quite right, and there would have to be relationships defined among the abstract machines; but I think this approach might be the sort of thing you're looking for. [Clearly, when the compiler can figure out which branch is to be taken, only the code for that branch need be generated.] ----------------------------------------------------------------------------- Chris.Holt@newcastle.ac.uk Computing Lab, U of Newcastle upon Tyne, UK ----------------------------------------------------------------------------- "What two ideas are more inseparable than Beer and Virtual Reality?"
brnstnd@kramden.acf.nyu.edu (Dan Bernstein) (09/26/90)
In article <1990Sep24.160705.21113@newcastle.ac.uk> Chris.Holt@newcastle.ac.uk (Chris Holt) writes: > In article <28750:Sep2402:58:2290@kramden.acf.nyu.edu> > brnstnd@kramden.acf.nyu.edu (Dan Bernstein) writes: > >I'd like to focus on this point. Upward extensibility through macros and > >functions is pretty well understood. Its syntax may not be as well > >understood, but that's not a serious problem. What would it take to make > >a realistic language downward-extensible? > You'd want the components of an abstract machine model to be described > in the high-level notation, with an obvious, efficient implementation Not necessarily. I'm trying to get at the lower levels, not at the abstract levels. Your TimeFor*(*Machine) idea is interesting, but it wouldn't be portable, would be painful to use if there are lots of machines, may not have a fixed answer (times depend on context), and doesn't have a good semantic match with compiler-choose-one-of-these. Rather than this abstract discussion, let's examine a concrete example. Someone just asked in comp.lang.c how to count the number of bits in a 32-bit integer. Most people would use a table of 256 or 65536 values and shift appropriately. But one person pointed out that count-the-bits is a single instruction on at least one machine. How, without making any preparations in the language specification beforehand, could we let the programmer extend the language downwards to take advantage of this instruction? If a compiler worked along the lines of my previous article, it would have *some* construct that it would recognize as count-the-bits. Say it understands { unsigned long i; for (i = j;i;i >>= 1) count += (i & 1); } as count = count-the-bits(j). The documentation would point this out, of course. Now the programmer wants to use this without losing portability. I envision a solution like this: quickpick fast(define builtin_bitcount 0) count = bitcounts[j & 65535] + bitcounts[(j >> 16) % 65535]; fast(define builtin_bitcount 1) unsigned long i; for(i = j;i;i >>= 1) count += (i & 1); endquickpick If the compiler recognized the second construct, it would define builtin_bitcount as 1 and use that code. If not, it would probably choose the first construct. The bitcounts table would be defined if builtin_bitcount was set. In any case, the code is perfectly portable. ---Dan
Chris.Holt@newcastle.ac.uk (Chris Holt) (09/27/90)
In article <9363:Sep2521:41:1290@kramden.acf.nyu.edu> brnstnd@kramden.acf.nyu.edu (Dan Bernstein) writes: >Rather than this abstract discussion, let's examine a concrete example. >Someone just asked in comp.lang.c how to count the number of bits in a >32-bit integer. Most people would use a table of 256 or 65536 values and >shift appropriately. But one person pointed out that count-the-bits is a >single instruction on at least one machine. > >How, without making any preparations in the language specification >beforehand, could we let the programmer extend the language downwards to >take advantage of this instruction? It seems as though you want the basic ideas of object-oriented programming, in that instructions/operations/functions should have formal specifications, libraries of objects are accessed in terms of these specifications, and when there are alternative possibilities, they can be selected without human intervention whenever possible. In this case, count-the-bits could be specified as something like output = sum(bit-to-int over int-to-array-of-bits(input)) where the basic functions of sum, over, and type conversions can be easily remembered. The trouble with actually implementing an algorithm, and hoping for the compiler to optimize, is that there are so many ways of doing it. This is (IMHO) why libraries haven't taken off yet, especially with regard to imperative languages. As soon as a library has say 10K elements in it, nobody knows how to find anything any more. Machines come in a tremendous variety of flavours, and new ones are being built every day; so unless you go to specifications, I think the compiler is going to have a *lot* of trouble matching up pieces of code to instructions. >If a compiler worked along the lines of my previous article, it would >have *some* construct that it would recognize as count-the-bits. Say it >understands { unsigned long i; for (i = j;i;i >>= 1) count += (i & 1); } >as count = count-the-bits(j). The documentation would point this out, of >course. If the compiler is to be portable, it's going to have to remember an awful lot. E.g. on a DAP, if the number is stored across an array of processors (back when they had bit processors), you'd want a different algorithm; on a Cray, you'd want a different one again. >Now the programmer wants to use this without losing portability. I >envision a solution like this: > > quickpick > fast(define builtin_bitcount 0) > count = bitcounts[j & 65535] + bitcounts[(j >> 16) % 65535]; > fast(define builtin_bitcount 1) > unsigned long i; > for(i = j;i;i >>= 1) count += (i & 1); > endquickpick I'm just claiming that there are so many alternative algorithms that you'd end up with say a hundred alternatives, and that this would happen all over the place. I'd see it as more likely that the programmer interacts with the compiler/environment by specifying what should be done at a given point; the c/e either says it doesn't know how to do that, or yes it does. If the latter, fine; trust it to optimize; if it doesn't, break it down into substeps that the c/e might recognize. There is the minor problem that this hasn't been implemented yet. :-) ----------------------------------------------------------------------------- Chris.Holt@newcastle.ac.uk Computing Lab, U of Newcastle upon Tyne, UK ----------------------------------------------------------------------------- "What two ideas are more inseparable than Beer and Virtual Reality?"
brnstnd@kramden.acf.nyu.edu (Dan Bernstein) (09/27/90)
In article <1990Sep26.191602.6195@newcastle.ac.uk> Chris.Holt@newcastle.ac.uk (Chris Holt) writes: > It seems as though you want the basic ideas of object-oriented > programming, It seems as though I'm missing the definition of ``object-oriented,'' which is used as a catchphrase for the much better-defined ideas of modularity, portability, reusability, and extensibility. > In this case, count-the-bits could be specified as something like > output = sum(bit-to-int over int-to-array-of-bits(input)) But how do you propose to give the compiler a fighting chance to optimize this? Rather, to let the programmer give the compiler that chance? > If the compiler is to be portable, it's going to have to remember > an awful lot. The compiler won't be portable, because it has to be custom-tailored to recognize (e.g.) how to use a count-the-bits instruction. > > quickpick > > fast(define builtin_bitcount 0) > > count = bitcounts[j & 65535] + bitcounts[(j >> 16) % 65535]; > > fast(define builtin_bitcount 1) > > unsigned long i; > > for(i = j;i;i >>= 1) count += (i & 1); > > endquickpick > I'm just claiming that there are so many alternative algorithms > that you'd end up with say a hundred alternatives, and that > this would happen all over the place. I don't think so! It really is true that 50/80/90% of a program's time is spent in 50/20/10% of its code, and that the same holds recursively inside each bottleneck. Programs won't balloon just because you're simultaneously optimizing for a Sun and a Convex. Also, I doubt there are a hundred sensible alternatives for any short section of code. ---Dan
Chris.Holt@newcastle.ac.uk (Chris Holt) (09/27/90)
In article <18281:Sep2702:57:1090@kramden.acf.nyu.edu> brnstnd@kramden.acf.nyu.edu (Dan Bernstein) writes: >In article <1990Sep26.191602.6195@newcastle.ac.uk> Chris.Holt@newcastle.ac.uk (Chris Holt) writes: >> It seems as though you want the basic ideas of object-oriented >> programming, > >It seems as though I'm missing the definition of ``object-oriented,'' >which is used as a catchphrase for the much better-defined ideas of >modularity, portability, reusability, and extensibility. Sorry, I was using my own private definition ( :-) of an object as a structure perhaps containing code and data, with a well-defined formal interface. However, I think you do want all the buzzwords above, so it doesn't matter very much. >> In this case, count-the-bits could be specified as something like >> output = sum(bit-to-int over int-to-array-of-bits(input)) > >But how do you propose to give the compiler a fighting chance to >optimize this? Rather, to let the programmer give the compiler that >chance? What I think I'm trying to say is that the compiler will in general have a better chance of recognizing specifications than algorithms, when we start getting into the use of large libraries of alternative code fragments. >> If the compiler is to be portable, it's going to have to remember >> an awful lot. > >The compiler won't be portable, because it has to be custom-tailored to >recognize (e.g.) how to use a count-the-bits instruction. I'd rather have a portable compiler that has information about a variety of machines; then it is given as one of its inputs the parameters that describe the given machine. Custom-tailoring is expensive (not that the alternative is cheap). > ... It really is true that 50/80/90% of a program's time >is spent in 50/20/10% of its code, and that the same holds recursively >inside each bottleneck. Programs won't balloon just because you're >simultaneously optimizing for a Sun and a Convex. Also, I doubt there >are a hundred sensible alternatives for any short section of code. I think the variety in machine architectures is not going to be reduced for a while. It's not just a Sun and a Convex, it's also a hypercube, a shared memory multiprocessor, a vector machine, a DAP, a transputer network, etc. [I don't remember what a Convex looks like, sorry.] After all, the attempts at defining abstract assemblers like JANUS, to solve the nxm problem for compilers, tended to get into trouble just because there were so many different machine models around. ----------------------------------------------------------------------------- Chris.Holt@newcastle.ac.uk Computing Lab, U of Newcastle upon Tyne, UK ----------------------------------------------------------------------------- "What two ideas are more inseparable than Beer and Virtual Reality?"
seanf@sco.COM (Sean Fagan) (09/28/90)
In article <9363:Sep2521:41:1290@kramden.acf.nyu.edu> brnstnd@kramden.acf.nyu.edu (Dan Bernstein) writes: > quickpick > fast(define builtin_bitcount 0) > count = bitcounts[j & 65535] + bitcounts[(j >> 16) % 65535]; > fast(define builtin_bitcount 1) > unsigned long i; > for(i = j;i;i >>= 1) count += (i & 1); > endquickpick Ugh. Are you then going to standardize *everything*? (N.B. The machines mentioned that had the bit-counting were, I suspect, the CDC Cyber and Cray machines, which have a Pop Count instruction.) The Elxsi has an instruction for passing a message (up to 836 bytes, I think) to a "port", which is usually another process (yet need not be). Are you going to straddle your "language" with the semantics of this instruction, simply because someone may find it useful? Some of the highly-specialized graphics processors have instructions to rotate three-dimensional polygons in memory; yet most of them have vastly to slightly different semantics; are you going to straddle the "language" with the semantics of *all* of them? Now, all that said: C has the #ifdef route, which is close to what you want. (The compiler won't automatically know that it can do the popcount, for example, but it's easy enough to add conditional expressions to check for which machine you're on.) Combine this with inline functions and assembly a la gcc, and it's hard to get any better *and* portable. -- -----------------+ Sean Eric Fagan | "Never knock on Death's door: ring the bell and seanf@sco.COM | run away! Death really hates that!" uunet!sco!seanf | -- Dr. Mike Stratford (Matt Frewer, "Doctor, Doctor") (408) 458-1422 | Any opinions expressed are my own, not my employers'.
brnstnd@kramden.acf.nyu.edu (Dan Bernstein) (09/28/90)
In article <7935@scolex.sco.COM> seanf (Sean Fagan) writes: > In article <9363:Sep2521:41:1290@kramden.acf.nyu.edu> brnstnd@kramden.acf.nyu.edu (Dan Bernstein) writes: > > quickpick > > fast(define builtin_bitcount 0) > > count = bitcounts[j & 65535] + bitcounts[(j >> 16) % 65535]; > > fast(define builtin_bitcount 1) > > unsigned long i; > > for(i = j;i;i >>= 1) count += (i & 1); > > endquickpick > Ugh. Are you then going to standardize *everything*? What are you talking about? The only thing added to the language is the quickpick control structure. All I'm doing is letting the programmer give the compiler a much better chance to optimize a section of code. > The Elxsi has an instruction for passing a message (up to 836 bytes, I > think) to a "port", which is usually another process (yet need not be). Are > you going to straddle your "language" with the semantics of this > instruction, simply because someone may find it useful? Of course not! What would be the point of that? The compiler should be able to use the instruction if at all possible, but nothing in the language changes. What we're trying to do here is let a language be downward-extensible without losing portability at all. > Now, all that said: C has the #ifdef route, which is close to what you > want. No, it isn't, for the several reasons I explained in the first article of this thread. ifdefs are clumsy to define, and they guarantee that your program will run poorly when the hardware changes under your nose. They require that someone who wants to install the software on a new machine figure out each one of your ridiculously many ifdefs. That is not the portable downward extensibility that we want. ---Dan
seanf@sco.COM (Sean Fagan) (09/30/90)
In article <29047:Sep2816:51:1290@kramden.acf.nyu.edu> brnstnd@kramden.acf.nyu.edu (Dan Bernstein) writes: >> Ugh. Are you then going to standardize *everything*? > >What are you talking about? The only thing added to the language is the >quickpick control structure. All I'm doing is letting the programmer >give the compiler a much better chance to optimize a section of code. Uhm... where are you going to define the names that are used? Or is the compiler supposed to go through your "worst-case" one, analyze it, and see which instruction matches it most closely? If it could do that already, you wouldn't need to bother with your "quickpick" thingy. If the "names" are going to be "standardized" (which is what I was referring to), you're going to have a real mess on your hands, which is why I went into the example about the elxsi et al. >No, it isn't, for the several reasons I explained in the first article >of this thread. ifdefs are clumsy to define, and they guarantee that >your program will run poorly when the hardware changes under your nose. So will your method. You would have to recompile. If you do something like: #ifdef BIT_COUNT_IN_HARDWARE __builtin_bitcount (whatever); #else whatever #endif what is the difference between *that*, and your method? Other than niggling little details? >They require that someone who wants to install the software on a new >machine figure out each one of your ridiculously many ifdefs. That is >not the portable downward extensibility that we want. Your method requires lots of things, too. Generally, though, the person who builds the compiler would figure them out, not necessarily the installer. For example, in <stdlib.h> (or something like <stdext.h>, I guess), with the correct defines for the machine. No more difficult than installing a libc. For most people, that is. Maybe not you. -- -----------------+ Sean Eric Fagan | "Never knock on Death's door: ring the bell and seanf@sco.COM | run away! Death really hates that!" uunet!sco!seanf | -- Dr. Mike Stratford (Matt Frewer, "Doctor, Doctor") (408) 458-1422 | Any opinions expressed are my own, not my employers'.
stephen@estragon.uchicago.edu (Stephen P Spackman) (10/01/90)
IMHO, the best way of making a language "downward-extensible" is not to touvch the language at all. Instead, you add to the compiler's transformation-strategy library (we're talking about a fairly radical compiler here) a note to the effect that this piece of code you want to go fast is equivalent to this other piece of code - if you're being careful you also provide a formal proof, and if not you just give your initials and the date :-). Then the compiler can, if the optimisation level is low, compile just what you wrote; if the optimisation level is high, it compiles both options in parallel until it has reached a point where one clearly dominates the other under the current regime (space/time/resource availability and so forth). We already trust the compiler to do much of our optimisation. Making that compiler smarter, possibly interactively, is what we want to do next. Maybe we can even give up on our source languages being a priori implementable by now - ditching everything but the specs. stephen p spackman stephen@estragon.uchicago.edu 312.702.3982
brnstnd@kramden.acf.nyu.edu (Dan Bernstein) (10/02/90)
In article <7950@scolex.sco.COM> seanf (Sean Fagan) writes: > In article <29047:Sep2816:51:1290@kramden.acf.nyu.edu> brnstnd@kramden.acf.nyu.edu (Dan Bernstein) writes: > >> Ugh. Are you then going to standardize *everything*? > >What are you talking about? The only thing added to the language is the > >quickpick control structure. All I'm doing is letting the programmer > >give the compiler a much better chance to optimize a section of code. > Uhm... where are you going to define the names that are used? What names are you talking about? The language is not extended by the compiler. > Or is the > compiler supposed to go through your "worst-case" one, analyze it, and see > which instruction matches it most closely? If it could do that already, you > wouldn't need to bother with your "quickpick" thingy. Huh? The compiler already converts any given sequence of code into machine instructions as well as it knows how. quickpick just lets the programmer give the compiler several alternatives. There's no way to do this currently. > If the "names" are going to be "standardized" (which is what I was referring > to), you're going to have a real mess on your hands, which is why I went > into the example about the elxsi et al. Agreed, that would be a real mess, like the current ifdef situation. See my first quickpick example. > >No, it isn't, for the several reasons I explained in the first article > >of this thread. ifdefs are clumsy to define, and they guarantee that > >your program will run poorly when the hardware changes under your nose. > So will your method. You would have to recompile. Yes, I'm aware of that; programs are almost always recompiled for new hardware. The point is that you don't need the original programmer slobbering over each new chip to figure out whether it's faster with algorithm X or algorithm Y. You let the compiler do the job for you. > If you do something like: > #ifdef BIT_COUNT_IN_HARDWARE > __builtin_bitcount (whatever); > #else > whatever > #endif > what is the difference between *that*, and your method? Other than niggling > little details? Namespace problems! Lack of portability! Decentralized language extensions! The difficulty of defining every single ifdef on every single machine! Don't you realize that this is a problem? > >They require that someone who wants to install the software on a new > >machine figure out each one of your ridiculously many ifdefs. That is > >not the portable downward extensibility that we want. > Your method requires lots of things, too. Generally, though, the person who > builds the compiler would figure them out, not necessarily the installer. > For example, in <stdlib.h> (or something like <stdext.h>, I guess), with the > correct defines for the machine. No more difficult than installing a libc. > For most people, that is. Maybe not you. At the risk of being overrepetitively redundantly redundant: Think about managing the namespace. How do you plan to tell all the compiler writers around the world what symbols they should define? Do you plan to fix a single set and let this form of optimization stagnate? Do you want namespace anarchy? Will you hold an annual seance to resolve these problems? What will you do when the number of symbols balloons? Do you seriously believe that each vendor is going to define a thousand other symbols saying ``no, I don't support that other vendor's optimizations'' when only ten or twenty optimizations are relevant locally? The current C situation makes it annoyingly difficult to write portable, efficient code. For most people, that is. Maybe not you. Maybe you think that it's reasonable for each package to define a new set of symbols for the installer to suffer through. I don't. ---Dan
brnstnd@kramden.acf.nyu.edu (Dan Bernstein) (10/02/90)
In article <STEPHEN.90Sep30235402@estragon.uchicago.edu> stephen@estragon.uchicago.edu (Stephen P Spackman) writes: > IMHO, the best way of making a language "downward-extensible" is not > to touvch the language at all. Instead, you add to the compiler's > transformation-strategy library (we're talking about a fairly radical > compiler here) a note to the effect that this piece of code you want > to go fast is equivalent to this other piece of code I agree. I just think it's more flexible to put those transformations into the code than to force a single transformation structure on all future compilers and separate the efficient code from the code proper. It's also possible to implement on today's compilers. ---Dan
lgm@cbnewsc.att.com (lawrence.g.mayka) (10/02/90)
In article <18718:Oct120:03:0090@kramden.acf.nyu.edu>, brnstnd@kramden.acf.nyu.edu (Dan Bernstein) writes: > At the risk of being overrepetitively redundantly redundant: Think about > managing the namespace. How do you plan to tell all the compiler writers > around the world what symbols they should define? Do you plan to fix a > single set and let this form of optimization stagnate? Do you want > namespace anarchy? Will you hold an annual seance to resolve these > problems? What will you do when the number of symbols balloons? Do you > seriously believe that each vendor is going to define a thousand other > symbols saying ``no, I don't support that other vendor's optimizations'' > when only ten or twenty optimizations are relevant locally? Each vendor can supply new and useful language/library extensions - definitions of new functions, datatypes, etc. - in a namespace (e.g., a package in Common Lisp) distinct from the "common" one (the one containing all those symbols already standardized). A programmer who wishes to use such definitions can refer to them in their original package (e.g., as VENDOR:FUNC), or for convenience import them into her/his own "working" package. The programmer must of course supply her/his own definition of the symbol when porting code to a less capable platform. Eventually, if enough programmers find the definition useful, most of the leading vendors will incorporate it into their systems. At this point, the definition may be added to the language/library standard. The specific example of counting the number of 1-bits in an integer is standardized as LOGCOUNT in Common Lisp. Lawrence G. Mayka AT&T Bell Laboratories lgm@iexist.att.com Standard disclaimer.
seanf@sco.COM (Sean Fagan) (10/03/90)
In article <18718:Oct120:03:0090@kramden.acf.nyu.edu> brnstnd@kramden.acf.nyu.edu (Dan Bernstein) writes: >Agreed, that would be a real mess, like the current ifdef situation. See >my first quickpick example. Hmm. Hold on. I just reread your original article, and read this one. I think I almost understand what you're trying to say. You want things such that someone can describe an algorithm, in more or less generic terms, as well as a "better" replacement algorithm, and have the compiler automagically replace it? Ok. *That* I understand (why didn't you say that?). I am not certain of this, but I think there has been some success in that area. If this *is* what you mean, then comp.compilers would be a good place to (briefly) continue the discussion, since that's where those types hang out. -- -----------------+ Sean Eric Fagan | "Never knock on Death's door: ring the bell and seanf@sco.COM | run away! Death really hates that!" uunet!sco!seanf | -- Dr. Mike Stratford (Matt Frewer, "Doctor, Doctor") (408) 458-1422 | Any opinions expressed are my own, not my employers'.
pardo@cs.washington.edu (David Keppel) (10/03/90)
>brnstnd@kramden.acf.nyu.edu (Dan Bernstein) writes: >>[A mess, like the #ifdef situation; see quickpick example.] In article <7976@scolex.sco.COM> seanf (Sean Fagan) writes: >[You want a generic algorithm description and a better replacement, > and have the compiler automagically select the implementation?] >[I think there's been some success in that area.] I can immagine two cases: * Anything on the list of approved alternatives is a valid substitution. You write `binsearch (...)' and the compiler uses rule-based description quicksort any other magic way (provided it has the right type signature). Selection is done based on the name of the operation invoked (e.g., `binsearch'). * The compiler is supposed to pattern match an algorithm and select a replacement from a list. The first is easy. The second is hard. ;-D on ( Leftward extensible political compilers ) Pardo -- pardo@cs.washington.edu {rutgers,cornell,ucsd,ubc-cs,tektronix}!uw-beaver!june!pardo
nevin@igloo.scum.com (Nevin Liber) (10/03/90)
In article <STEPHEN.90Sep30235402@estragon.uchicago.edu> stephen@estragon.uchicago.edu (Stephen P Spackman) writes: >We already trust the compiler to do much of our optimisation. Making >that compiler smarter, possibly interactively, is what we want to do >next. I definitely agree with you that the solution to this problem is to make our compilers smarter. However, I'm not quite sure that making them interactive is going to help. It assumes that the person who is compiling (and this person is not necessarily the author) a given program knows what is more optimal. I doubt that the majority of people who compile or build software have the time to learn the code and machine architectures well enough to make informed decisions about optimisations. Also, interactive compiling would probably take 5-10 times longer than batch compiling (just a guess; if someone knows of some real research done in this area, please post the results), and requires that someone devote a lot of time to a relatively boring job. Just some thoughts, -- NEVIN ":-)" LIBER nevin@igloo.scum.com or ..!gargoyle!igloo!nevin (708) 831-FLYS California, here I come! Public Service Announcement: Say NO to Rugs!
seanf@sco.COM (Sean Fagan) (10/04/90)
In article <13224@june.cs.washington.edu> pardo@june.cs.washington.edu (David Keppel) writes: >* The compiler is supposed to pattern match an algorithm and > select a replacement from a list. > >The first is easy. The second is hard. Yep. That's what makes it so *fun*! (Note that, as far as I'm concerned, doing that for the general case will go a long way towards implementing true AI. At which point, you can probably start just handing specs to your "compiler," and letting it chug out a solution. Scary, isn't it? 8-)) -- -----------------+ Sean Eric Fagan | "Never knock on Death's door: ring the bell and seanf@sco.COM | run away! Death really hates that!" uunet!sco!seanf | -- Dr. Mike Stratford (Matt Frewer, "Doctor, Doctor") (408) 458-1422 | Any opinions expressed are my own, not my employers'.
pardo@cs.washington.edu (David Keppel) (10/07/90)
>stephen@estragon.uchicago.edu (Stephen P Spackman) writes: >>We already trust the compiler to do much of our optimisation. Making >>that compiler smarter, possibly interactively, is what we want to do >>next. In article <2873@igloo.scum.com> nevin@igloo.UUCP (Nevin Liber) writes: >[But does the person really know the ideal mapping to each machine?] I think the goal is that the compiler discovers ``Boy, I could move this common subexpression out of the loop if I only knew that it wasn't an alias for this thing over here'' and then queries the user to see if that is indeed the case (presumably the user says ``yes'' or ``no'' in a way that the compiler won't ask again next time). >[But won't that slow compilation?] Only the phase with optimization turned on, and only when you have it in ``query'' mode. >[Interactive might be 5-10 times slower -- any real results?] How fast can you type a response ?-) ;-D on ( Amortize compiler costs? Nah, depreciate! ) Pardo -- pardo@cs.washington.edu {rutgers,cornell,ucsd,ubc-cs,tektronix}!uw-beaver!june!pardo
brnstnd@kramden.acf.nyu.edu (Dan Bernstein) (10/08/90)
In article <1990Oct2.024511.10082@cbnewsc.att.com> lgm@cbnewsc.att.com (lawrence.g.mayka) writes: > Each vendor can supply new and useful language/library extensions - > definitions of new functions, datatypes, etc. - in a namespace (e.g., > a package in Common Lisp) distinct from the "common" one (the one > containing all those symbols already standardized). Well, okay, but that doesn't help the programmer who's trying to write portable code. Some extensions, like vector processing, won't be standardized for a very, very long time. Does that mean the programmer shouldn't be able to write code that will take advantage of vectors when they're around? Does it mean that all such code must be unportable? ---Dan
brnstnd@kramden.acf.nyu.edu (Dan Bernstein) (10/08/90)
In article <7976@scolex.sco.COM> seanf (Sean Fagan) writes: > You want things such that someone can describe an algorithm, in more or less > generic terms, as well as a "better" replacement algorithm, and have the > compiler automagically replace it? Right. But both algorithms will be fully generic, and fully portable. The compiler will make its best guess, or take the first choice if it has no idea. > I am not certain of this, but I think there has been some success in that > area. If this *is* what you mean, then comp.compilers would be a good place > to (briefly) continue the discussion, since that's where those types hang > out. Well, it is a language issue, insofar as the language has to provide quickpick (or something like it) in the first place. ---Dan
brnstnd@kramden.acf.nyu.edu (Dan Bernstein) (10/08/90)
In article <13224@june.cs.washington.edu> pardo@june.cs.washington.edu (David Keppel) writes: > * Anything on the list of approved alternatives is a valid > substitution. You write `binsearch (...)' and the compiler > uses > rule-based description > quicksort > any other magic way No; that's exactly what I'm objecting to. I don't want to lose portability just because I'm letting the compiler see several idioms for the same computation. I also don't want to force every recipient of the code to define binsearch or any other symbol just so they can compile. You write out all the choices, explicitly, and the compiler hopes to recognize one of them as something it can really optimize. ---Dan
gl8f@astsun9.astro.Virginia.EDU (Greg Lindahl) (10/08/90)
In article <899:Oct800:50:3590@kramden.acf.nyu.edu> brnstnd@kramden.acf.nyu.edu (Dan Bernstein) writes: >Well, okay, but that doesn't help the programmer who's trying to write >portable code. Some extensions, like vector processing, won't be >standardized for a very, very long time. Does that mean the programmer >shouldn't be able to write code that will take advantage of vectors when >they're around? Does it mean that all such code must be unportable? That's funny, the FORTRAN community wrote standards for vector processing quite a while ago. You have the BLAS libraries, you have the future F9X, and oddly enough Cray seems to have little trouble writing a compiler which totally vectorizes my hydrodynamics code which is written in portable fortran. Perhaps what you want is already available: pick a library interface, write portable versions, and develop machine-specific versions as you go along. Smart compilers can inline routines so it will even be efficient. And it's certainly portable. -- "Restraint, hell. I'm just too fucking busy." -- Bill Wisner
seanf@sco.COM (Sean Fagan) (10/10/90)
In article <975:Oct800:52:3590@kramden.acf.nyu.edu> brnstnd@kramden.acf.nyu.edu (Dan Bernstein) writes: >Well, it is a language issue, insofar as the language has to provide >quickpick (or something like it) in the first place. No, it doesn't. It *can*, but it doesn't need to. The compiler can take a look at code sections, and decide whether or not it should replace the code with completely different algorithms. See "The SuperOptimizer" for some reality. -- -----------------+ Sean Eric Fagan | "Never knock on Death's door: ring the bell and seanf@sco.COM | run away! Death really hates that!" uunet!sco!seanf | -- Dr. Mike Stratford (Matt Frewer, "Doctor, Doctor") (408) 458-1422 | Any opinions expressed are my own, not my employers'.
brnstnd@kramden.acf.nyu.edu (Dan Bernstein) (10/18/90)
In article <1990Oct8.034201.2631@murdoch.acc.Virginia.EDU> gl8f@astsun9.astro.Virginia.EDU (Greg Lindahl) writes: > That's funny, the FORTRAN community wrote standards for vector > processing quite a while ago. You have the BLAS libraries, you have > the future F9X, and oddly enough Cray seems to have little trouble > writing a compiler which totally vectorizes my hydrodynamics code > which is written in portable fortran. Same for Convex---but since each compiler vendor gives the programmer a different way to indicate vectorization, the efficiency itself isn't portable. You're right, though, that vectorization is a bad example. But the argument still makes sense. ``Some extensions, like very fast pythagorean sums, won't be standardized for a very, very long time. Does that mean the programmer shouldn't be able to write code that will take advantage of pythagorean sums when they're around? Does it mean that all such code must be unportable?'' ---Dan
gl8f@astsun.astro.Virginia.EDU (Greg Lindahl) (10/19/90)
In article <13549:Oct1800:31:5490@kramden.acf.nyu.edu> brnstnd@kramden.acf.nyu.edu (Dan Bernstein) writes: >> the future F9X, and oddly enough Cray seems to have little trouble >> writing a compiler which totally vectorizes my hydrodynamics code >> which is written in portable fortran. > >Same for Convex---but since each compiler vendor gives the programmer a >different way to indicate vectorization, the efficiency itself isn't >portable. My code doesn't need any vetorization directives. The efficiency is portable. >But the argument still makes sense. ``Some extensions, like very fast >pythagorean sums, won't be standardized for a very, very long time. >Does that mean the programmer shouldn't be able to write code that will >take advantage of pythagorean sums when they're around? Does it mean >that all such code must be unportable?'' This is how programmers were doing it many years ago: 1) Write a library interface for the sum. 2) Code a portable routine. 3) If necessary, write efficient machine-specific version. This gives you portable code. -- "Restraint, hell. I'm just too fucking busy." -- Bill Wisner