Date: Mon, 10 Mar 2003 22:38:57 -0800 From: David Schultz <das@FreeBSD.ORG> To: Mark Murray <mark@grondar.org> Cc: Terry Lambert <tlambert2@mindspring.com>, Peter Jeremy <peterjeremy@optushome.com.au>, chat@FreeBSD.ORG Subject: Re: cvs commit: src/lib/libc/i386/string Makefile.inc wcscmp.S Message-ID: <20030311063857.GA4638@HAL9000.homeunix.com> In-Reply-To: <200303102317.h2ANHnIg074715@grimreaper.grondar.org> References: <3E6D17B7.5FDCEAFC@mindspring.com> <200303102317.h2ANHnIg074715@grimreaper.grondar.org>
next in thread | previous in thread | raw e-mail | index | archive | help
Thus spake Mark Murray <mark@grondar.org>: > I _know_ a guru will aways eke out a bit more performance. What I'm > asking is "what shape is the performance/effort curve for _compilers_?" > and I'm leading towards "When, if ever, will compiler optimization > be such that hand coding assembler for system libraries is a waste > of time (on average)?" What I _really_ want to know is how much > optimization is _not_ done, either because its too hard/slow, or > because its too difficult to do. I also want to know how complete > we think our optimization understanding is, ie whether there is > lots of scope for research or we think we know most of the theory > already. If you read the dragon book, Aho and Sethi seem to tell you that all of the world's compiler problems can be solved by throwing theorems at them. But I think that optimization really comes down to a bunch of heuristics, and to the extent to which there are theories, the theories are either impractical (e.g. the algorithm takes exponential time) or not fully general. You can always make a compiler optimize for any *specific* case that you want. For instance, you could train it to recognize a loop that implements ffs(3) and translate that into a single VAX or i386 (?) instruction. But if you wanted it to understand loops that compute log2 or do multiplication by iterated addition, those would just be more special cases. The problem of taking an arbitrary program and finding the most efficient way to compute its result will never be solved (since the halting problem reduces to it), but the heuristics and approximations seem to keep getting better as computers get better. I'm working with some colleagues on a model checking tool for analyzing certain security-relevant aspects of C programs that would have taken too much time and space to be practical a few years ago. Microsoft is using a similar tool to find certain kinds of bugs in Windows. In a few years, general-purpose compilers may be able to adopt similar techniques. To Unsubscribe: send mail to majordomo@FreeBSD.org with "unsubscribe freebsd-chat" in the body of the message
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?20030311063857.GA4638>