Re: What can we optimize (was Re: Schwartzian transforms)
Dan Sugalski wrote: At 02:52 PM 3/29/2001 -0800, Russ Allbery wrote: James Mastros [EMAIL PROTECTED] writes: Ahh, bingo. That's what a number of people (inculding me) are suggesting -- a :functional / :pure / :stateless / :somthingelseIdontrecall attribute attachable to a sub. The experience from gcc, which has a similar attribute, is that such an attribute will be fairly rarely used and that most of your gains will come from managing to teach the compiler to figure out that information for itself. I'm hoping to have this stage of optimization in perl. Dan define non-MY to mean, dynamic or lexical from outside of the function, so, non-my relative to the function. obviously_clean(\subX){ # could be defined as: not (any appearance of known-unclean functions) and not (non-MY appears at all) } subs and functions can get flagged clean/unclean fairly quickly then. known-unclean are things like "rand" and any functions that have not been marked "clean" already. The attribute would force a non-obviously clean subroutine to be treated as clean, and memoized, unless use-less-memory is in effect. It would allow for some pretty subtle abuses.
Re: What can we optimize (was Re: Schwartzian transforms)
On Wed, Mar 28, 2001 at 03:41:42PM -0800, Hong Zhang wrote: Are we over-optimizing? The Perl is just an interpreter language. Who really needs this kind of optimization for Perl? Even C does not provide this feature. Umm, art thou sure? C can optimize better then we currently do many times, because it doesn't have to worry about side-efects as often because it doesn't have the concept of ties/overriden operators. (It does, and we do, have to worry about aliasing, but that is somthing of a smaller problem.) Just because C doesn't memonize, doesn't mean we shouldn't have that optimization available to us. So many other optimizations that are doable in C aren't in perl. Though Pascal/Ada have distinctions like function/procedure, it does not make them any faster than C. Umm, I don't know Ada, but in Pascal, the only difference is that one returns a value and the other does not (IE like void vs. nonvoid functions in C, or sub vs. function in VB). Just given its ugly name, I hate to see it in the core language. If people really want to optimize Perl, they can write a native compiler for Perl with advanced garbage collector, just like Scheme or Strongtalk compiler? We want to make it as fast as reasonably possible. Writing a native compiler might not be _reasonably_ possible. And an advanced GC will almost certianly be part of perl6; they're orthogonal issues. -=- James Mastros -- The most beautiful thing we can experience is the mysterious. It is the source of all true art and science. He to whom this emotion is a stranger, who can no longer pause to wonder and stand wrapt in awe, is as good as dead. -=- Albert Einstein AIM: theorbtwo homepage: http://www.rtweb.net/theorb/
Re: What can we optimize (was Re: Schwartzian transforms)
On Thu, Mar 29, 2001 at 10:25:06AM -0500, James Mastros wrote: On Wed, Mar 28, 2001 at 03:41:42PM -0800, Hong Zhang wrote: Are we over-optimizing? The Perl is just an interpreter language. Who really needs this kind of optimization for Perl? Even C does not provide this feature. Umm, art thou sure? C can optimize better then we currently do many times, Somewhat tangentially: this reminds me of a message a week ago or so (can't find it anymore in my inbox) which proposed writing C (or C++) code for Perl 6 so that "modern CPU architectures are happy" (no pipeline stalls because of "if"-s, etc.) Hello? This is a very high-level language we are writing, not a DSP core. Optimizing by choosing good algorithms and data structures, yes, microoptimizing, maybe, only after the code works first, and even then we would be following the mirage since CPU architectures do evolve, and in general, for large codebases, the C compilers are much, much, better in optimizing than humans. Yes, a human can sit down and read the databooks and optimize a simple algorithm to hell and back. But megabytes of source code? Get real. -- $jhi++; # http://www.iki.fi/jhi/ # There is this special biologist word we use for 'stable'. # It is 'dead'. -- Jack Cohen
Re: What can we optimize (was Re: Schwartzian transforms)
Jarkko Hietaniemi wrote: ... proposed writing C (or C++) code for Perl 6 so that "modern CPU architectures are happy" (no pipeline stalls because of "if"-s, etc.) ... in general, for large codebases, the C compilers are much, much, better in optimizing than humans. I totally agree. That would just be absurd. We need to keep our priorities straight. We have to live with the fact that perl might scream a little more on one platform than on another. Far better for us to write code that is maintainable for the long haul. Shoot, by the time perl7 comes out, the C compilers will just be that much better (and the hardware that much faster). -- John Porter
Re: What can we optimize (was Re: Schwartzian transforms)
Jarkko Hietaniemi [EMAIL PROTECTED] wrote: Somewhat tangentially: this reminds me of a message a week ago or so (can't find it anymore in my inbox) which proposed writing C (or C++) code for Perl 6 so that "modern CPU architectures are happy" (no pipeline stalls because of "if"-s, etc.) Hello? This is a very high-level language we are writing, not a DSP core. Optimizing by choosing good algorithms and data structures, yes, microoptimizing, maybe, only after the code works first, and even then we would be following the mirage since CPU architectures do evolve, and in general, for large codebases, the C compilers are much, much, better in optimizing than humans. Yes, a human can sit down and read the databooks and optimize a simple algorithm to hell and back. But megabytes of source code? Get real. That may have been me: http://archive.develooper.com/perl6-internals%40perl.org/msg02685.html (PDD for coding conventions) The main thrust of that was whether a PDD on coding conventions should have sections on: * Coding style * Naming conventions * Commenting conventions * Portability guidelines * Performance guidelines Based on your comments above (which I hearily agree with), I guess we can safely dispense with that last entry. Dave M.
Re: What can we optimize (was Re: Schwartzian transforms)
Dave Mitchell wrote: The main thrust of that was whether a PDD on coding conventions should have sections on: ... * Performance guidelines ...I guess we can safely dispense with that last entry. No, performance guidelines are probably still appropriate; but doing hand-coded peephole optimizations is not the Right Thing. As Jarkko, said: Optimizing by choosing good algorithms and data structures, yes -- John Porter
Re: What can we optimize (was Re: Schwartzian transforms)
At 10:25 AM 3/29/2001 -0500, James Mastros wrote: On Wed, Mar 28, 2001 at 03:41:42PM -0800, Hong Zhang wrote: Are we over-optimizing? The Perl is just an interpreter language. Who really needs this kind of optimization for Perl? Even C does not provide this feature. Umm, art thou sure? C can optimize better then we currently do many times, because it doesn't have to worry about side-efects as often because it doesn't have the concept of ties/overriden operators. (It does, and we do, have to worry about aliasing, but that is somthing of a smaller problem.) Aliasing is actually one of the bigger problems with C, or so I'm lead to believe. It gets in the way of a number of optimizations rather badly. (So say some of Compaq's C and Fortran compiler folks, and I have no reason to doubt them. The Fortran compiler often generates faster code than the C compiler for this reason apparently) Just because C doesn't memonize, doesn't mean we shouldn't have that optimization available to us. So many other optimizations that are doable in C aren't in perl. That's not true. Perl's probably more optimizable than C for many things. Though Pascal/Ada have distinctions like function/procedure, it does not make them any faster than C. Umm, I don't know Ada, but in Pascal, the only difference is that one returns a value and the other does not (IE like void vs. nonvoid functions in C, or sub vs. function in VB). Well, functions without return values are mildly faster than functions with return values. No stack and/or register manipulation needed for the return. Dan --"it's like this"--- Dan Sugalski even samurai [EMAIL PROTECTED] have teddy bears and even teddy bears get drunk
Re: What can we optimize (was Re: Schwartzian transforms)
At 03:41 PM 3/28/2001 -0800, Hong Zhang wrote: Are we over-optimizing? The Perl is just an interpreter language. Perl's not just an interpreter language, and hasn't been for a while. (Granted the bytecode compiler's not fully functional, but it does work in some cases) Who really needs this kind of optimization for Perl? I do. Lots of people with web apps do. Pretty much anyone with a large or long-running perl program does. Even C does not provide this feature. C doesn't have the sort of sort function that makes this possible in the first place, nor does it have the sort of data that makes it a reasonable thing to do. Perl does, so some optimization is reasonable. Whether it's a good first spot to optimize is an open question, but it will be a big win for quite a few people. Though Pascal/Ada have distinctions like function/procedure, it does not make them any faster than C. Depends on how the function's written in C. A function that has no meaningful return yet still returns one which gets inevitably thrown away will cost more than one that never returns anything, and there is a tendency to return *something* since you can. Just given its ugly name, I hate to see it in the core language. What, the ST? Why on earth would you think that we'd make much of a big deal over it in the docs? I'd just soon not mention it and just put it in as an optimization and have it be a pleasant performance win. If people really want to optimize Perl, they can write a native compiler for Perl with advanced garbage collector, just like Scheme or Strongtalk compiler? What, as opposed to the interpreter with advanced garbage collector? :) Dan --"it's like this"--- Dan Sugalski even samurai [EMAIL PROTECTED] have teddy bears and even teddy bears get drunk
Re: What can we optimize (was Re: Schwartzian transforms)
On Thu, Mar 29, 2001 at 11:29:16AM -0500, Dan Sugalski wrote: At 05:19 PM 3/29/2001 +0100, Dave Mitchell wrote: Jarkko Hietaniemi [EMAIL PROTECTED] wrote: Somewhat tangentially: this reminds me of a message a week ago or so (can't find it anymore in my inbox) which proposed writing C (or C++) code for Perl 6 so that "modern CPU architectures are happy" (no pipeline stalls because of "if"-s, etc.) Hello? This is a very high-level language we are writing, not a DSP core. Optimizing by choosing good algorithms and data structures, yes, microoptimizing, maybe, only after the code works first, and even then we would be following the mirage since CPU architectures do evolve, and in general, for large codebases, the C compilers are much, much, better in optimizing than humans. Yes, a human can sit down and read the databooks and optimize a simple algorithm to hell and back. But megabytes of source code? Get real. That may have been me: (Sorry if I sounded too blunt, the other stuff in the PDD was fine.) http://archive.develooper.com/perl6-internals%40perl.org/msg02685.html (PDD for coding conventions) The main thrust of that was whether a PDD on coding conventions should have sections on: * Coding style * Naming conventions * Commenting conventions * Portability guidelines * Performance guidelines Based on your comments above (which I hearily agree with), I guess we can safely dispense with that last entry. Don't. Hand-optimizing the C code's pretty silly generally, but there are some reasonable rules of thumb that can gain enough of a performance boost [snip] Yes. Rules of thumb are good, sort of like common lore of how CPUs in general work. I would like to add the overall principle of optimizing for speed first (that is, at the expense of space, e.g. by using wide integer types) (worry about space later, if needed), and avoiding division/modulus. Perhaps the rule #0 would be: measure before you optimize. Concentrate on the hotspots, instead of wasting your time honing some obscure rarely executed code. An additional coding guideline could be: * Extensibility guidelines (This is not the same as 'portability.') One particular detail I've noticed cropping up would be to avoid using char* (or {char*,length}) if it is feasible to later use a SV* (perl5-speak) at the same spot. An example: UTF-8 hash keys in Perl5. The same goes for flag fields: only if you can be fairly certain that the number of flags never exceeds 32, should you use an int. -- $jhi++; # http://www.iki.fi/jhi/ # There is this special biologist word we use for 'stable'. # It is 'dead'. -- Jack Cohen
Re: What can we optimize (was Re: Schwartzian transforms)
Who really needs this kind of optimization for Perl? I do. Lots of people with web apps do. Pretty much anyone with a large or long-running perl program does. I have to say that I agree to disagree. Since it has been so controversal, I just don't think this optimization is a good one. C doesn't have the sort of sort function that makes this possible in the first place, nor does it have the sort of data that makes it a reasonable thing to do. Perl does, so some optimization is reasonable. Whether it's a good first spot to optimize is an open question, but it will be a big win for quite a few people. C has qsort() and bsearch(). Anyway, I will not put it on my optimization list. Though Pascal/Ada have distinctions like function/procedure, it does not make them any faster than C. Depends on how the function's written in C. A function that has no meaningful return yet still returns one which gets inevitably thrown away will cost more than one that never returns anything, and there is a tendency to return *something* since you can. The function in Ada can not have any side effect, i.e. no change to globals. The procedure can have side effect. It gives compilers some more chances for optimizations. For example (pseudo code), function comp(int n, int m) : int; the compiler can safely remember the result of comparison for the same arguments. Hong
Re: What can we optimize (was Re: Schwartzian transforms)
On Thu, Mar 29, 2001 at 10:36:48AM -0800, Hong Zhang wrote: I have to say that I agree to disagree. Since it has been so controversal, I just don't think this optimization is a good one. Hmm, we aren't talking sort() specificly anymore. Look at the subject line. G The function in Ada can not have any side effect, i.e. no change to globals. The procedure can have side effect. It gives compilers some more chances for optimizations. For example (pseudo code), function comp(int n, int m) : int; the compiler can safely remember the result of comparison for the same arguments. Ahh, bingo. That's what a number of people (inculding me) are suggesting -- a :functional / :pure / :stateless / :somthingelseIdontrecall attribute attachable to a sub. -=- James Mastros -- The most beautiful thing we can experience is the mysterious. It is the source of all true art and science. He to whom this emotion is a stranger, who can no longer pause to wonder and stand wrapt in awe, is as good as dead. -=- Albert Einstein AIM: theorbtwo homepage: http://www.rtweb.net/theorb/
Re: What can we optimize (was Re: Schwartzian transforms)
-BEGIN PGP SIGNED MESSAGE- Hash: SHA1 On Thu, 29 Mar 2001 10:36:48 -0800, "Hong Zhang" [EMAIL PROTECTED] wrote: The function in Ada can not have any side effect, i.e. no change to globals. Unless my reading of the Ada 95 standard is wrong, there's nothing that precludes functions having side effects. The only thing an Ada function cannot do is having "out" or "in out" parameters, so it cannot modify its arguments, and even that can be circumvented (as you can pass "in" access parameters). /L/e/k/t/u -BEGIN PGP SIGNATURE- Version: PGPfreeware 6.5.8 for non-commercial use http://www.pgp.com iQA/AwUBOsOiu/4C0a0jUw5YEQKjQwCeP2Aeu6aJsdpP3asvcQDS+dyk2aoAoKS5 2gJ1o0xX1lfa0hXrVff1tPvx =t4je -END PGP SIGNATURE-
Re: What can we optimize (was Re: Schwartzian transforms)
Dan Sugalski [EMAIL PROTECTED] writes: True enough. This is a small subset of general optimizations. For example, this: $i = 0; foreach (1..1000) { $i++; } can be easily optimized to: $i = 1000; and most language implementations with any sort of optimizer will do this. If $i isn't actually used after that point without another assignment it might well be completely optimized away. With perl, though, this does potentially unexpected things if $i is tied. Do we still optimize it away? Do we only do it if we can tell that $i's not tied? Do we force the programmer to explicitly note which variables are potentially tied with the "my Dog $spot" syntax and assume that everything else is fair game? Can we even do that in the face of runtime requires, dos, or evals? (Or does that force a complete reevaluation of the optimized bytecode) How painful would an 'potential' optimization that marked that area in the bytecode/optree/whatever, with something along the lines of the following be? If you get to this point and $i is not tied, and '=' is not overridden for $i's class then $i = 1000 otherwise, do the loop. Of course, it means that the static runtime size is going to increase, but presumably these potential optimizations wouldn't get done in the presence of 'use less qw/space/' -- Piers
Re: What can we optimize (was Re: Schwartzian transforms)
At 10:57 PM 3/29/2001 +0100, Piers Cawley wrote: How painful would an 'potential' optimization that marked that area in the bytecode/optree/whatever, with something along the lines of the following be? If you get to this point and $i is not tied, and '=' is not overridden for $i's class then $i = 1000 otherwise, do the loop. I've considered an "iftied" opcode that would essentially do this. The downside is the extra size of the bytecode as you've mentioned. I'm not sure if the speed boost would be worth it, but it's on my list of things to try. Dan --"it's like this"--- Dan Sugalski even samurai [EMAIL PROTECTED] have teddy bears and even teddy bears get drunk
Re: What can we optimize (was Re: Schwartzian transforms)
Dan Sugalski [EMAIL PROTECTED] writes: Aliasing is actually one of the bigger problems with C, or so I'm lead to believe. It gets in the way of a number of optimizations rather badly. (So say some of Compaq's C and Fortran compiler folks, and I have no reason to doubt them. The Fortran compiler often generates faster code than the C compiler for this reason apparently) Hence the introduction of the restrict keyword in C99 and several of gcc's attribute extensions for marking pure functions to try to get a handle on the problem. *wry grin* Yeah, that's the main thing that gets in the way of optimizing C. -- Russ Allbery ([EMAIL PROTECTED]) http://www.eyrie.org/~eagle/
Re: What can we optimize (was Re: Schwartzian transforms)
James Mastros [EMAIL PROTECTED] writes: Ahh, bingo. That's what a number of people (inculding me) are suggesting -- a :functional / :pure / :stateless / :somthingelseIdontrecall attribute attachable to a sub. The experience from gcc, which has a similar attribute, is that such an attribute will be fairly rarely used and that most of your gains will come from managing to teach the compiler to figure out that information for itself. This will probably be harder in Perl than in C because C can afford to take more time to do global optimization passes. -- Russ Allbery ([EMAIL PROTECTED]) http://www.eyrie.org/~eagle/
Re: What can we optimize (was Re: Schwartzian transforms)
At 02:52 PM 3/29/2001 -0800, Russ Allbery wrote: James Mastros [EMAIL PROTECTED] writes: Ahh, bingo. That's what a number of people (inculding me) are suggesting -- a :functional / :pure / :stateless / :somthingelseIdontrecall attribute attachable to a sub. The experience from gcc, which has a similar attribute, is that such an attribute will be fairly rarely used and that most of your gains will come from managing to teach the compiler to figure out that information for itself. This will probably be harder in Perl than in C because C can afford to take more time to do global optimization passes. I'm hoping to have this stage of optimization in perl. Off by default with a normal parse-and-go run (though certainly enableable if you want), on by default with the bytecode compiler. Dan --"it's like this"--- Dan Sugalski even samurai [EMAIL PROTECTED] have teddy bears and even teddy bears get drunk
Re: What can we optimize (was Re: Schwartzian transforms)
"DS" == Dan Sugalski [EMAIL PROTECTED] writes: This will probably be harder in Perl than in C because C can afford to take more time to do global optimization passes. DS I'm hoping to have this stage of optimization in perl. Off by DS default with a normal parse-and-go run (though certainly DS enableable if you want), on by default with the bytecode compiler. for long running daemon type programs, any extra optimization overhead at startup will be well worth it. this would be a great win if it wrings out a decent amount of speedup. or you could make it only doable for bytecode and then you run that. this shouldn't be an issue with many systems who want that optimization pass. uri -- Uri Guttman - [EMAIL PROTECTED] -- http://www.sysarch.com SYStems ARCHitecture, Software Engineering, Perl, Internet, UNIX Consulting The Perl Books Page --- http://www.sysarch.com/cgi-bin/perl_books The Best Search Engine on the Net -- http://www.northernlight.com
Re: What can we optimize (was Re: Schwartzian transforms)
At 06:22 PM 3/29/2001 -0500, Uri Guttman wrote: "DS" == Dan Sugalski [EMAIL PROTECTED] writes: This will probably be harder in Perl than in C because C can afford to take more time to do global optimization passes. DS I'm hoping to have this stage of optimization in perl. Off by DS default with a normal parse-and-go run (though certainly DS enableable if you want), on by default with the bytecode compiler. for long running daemon type programs, any extra optimization overhead at startup will be well worth it. this would be a great win if it wrings out a decent amount of speedup. or you could make it only doable for bytecode and then you run that. this shouldn't be an issue with many systems who want that optimization pass. There's not much point in making it doable for bytecode but not normal perl runs, as the same engine will be there for both. (Though I suppose the main perl interpreter would be smaller if there wasn't an optimizer in it, but I wouldn't bet it would take up much space) Since I'm going to tend to fire off long-running stuff in perl, I expect it'll be there for the asking. :) Dan --"it's like this"--- Dan Sugalski even samurai [EMAIL PROTECTED] have teddy bears and even teddy bears get drunk
RE: What can we optimize (was Re: Schwartzian transforms)
From: Dan Sugalski [mailto:[EMAIL PROTECTED]] I'm hoping to have this stage of optimization in perl. Off by default with a normal parse-and-go run (though certainly enableable if you want), on by default with the bytecode compiler. Don't forget about run-time information: You could mark candidates for optimisation at compile time then, at run time, if the size of the array is "big" then spend the time to see if you can optimise. I'm not sure how to define "big", but I'm sure that's solvable. Dave.
Re: What can we optimize (was Re: Schwartzian transforms)
On Wed, Mar 28, 2001 at 04:36:58PM -0500, Dan Sugalski wrote: With perl, though, this does potentially unexpected things if $i is tied. Do we still optimize it away? Do we only do it if we can tell that $i's not tied? Yep. And in non-trivial cases, the only way to do that might be for $i to be :simple. Do we force the programmer to explicitly note which variables are potentially tied with the "my Dog $spot" syntax and assume that everything else is fair game? I'd rather see that things that will never be tied or otherwise magic be marked as :simple. Code always works, and will be faster with a little effort. Can we even do that in the face of runtime requires, dos, or evals? (Or does that force a complete reevaluation of the optimized bytecode) It is a catchable error to remove a behavorial restrictor attribute such as :simple or :stateless. So let it be spoken, so let it be done. This isn't any more preverse then the "you can't assign to constants" rule. -=- James Mastros -- The most beautiful thing we can experience is the mysterious. It is the source of all true art and science. He to whom this emotion is a stranger, who can no longer pause to wonder and stand wrapt in awe, is as good as dead. -=- Albert Einstein AIM: theorbtwo homepage: http://www.rtweb.net/theorb/
Re: What can we optimize (was Re: Schwartzian transforms)
On Wed, Mar 28, 2001 at 05:57:30PM -0500, James Mastros wrote: [A bunch of stuff] Oh, and I agree with sombody else on this thread that unless otherwise stated, the sort should always assume statelessness (and thus the ability to cache at will). If it's trivial to see that the sort function isn't stateless (IE it's a named sub that doesn't have the :stateless attribute set), then have an optional warning, because you probably don't want to be using that function, or the function should be marked :stateless. -=- James Mastros -- The most beautiful thing we can experience is the mysterious. It is the source of all true art and science. He to whom this emotion is a stranger, who can no longer pause to wonder and stand wrapt in awe, is as good as dead. -=- Albert Einstein AIM: theorbtwo homepage: http://www.rtweb.net/theorb/