A tool that suggests optimized logic for a piece of code/module/function
in [Unix Programming]
|
From: Andrew Poelstra on 12 Jan 2010 12:42 On 2010-01-12, scattered <still.scattered(a)gmail.com> wrote: > On Jan 12, 11:04�am, acd <acd4use...(a)lycos.de> wrote: >> On 11 Jan., 21:07, karthikbalaguru <karthikbalagur...(a)gmail.com> >> wrote: >> > Hi, >> > There are certain editors that highlight >> > the syntax/color for datatypes/variables >> > or comments etc. >> >> > Similarly, >> > Is there a tool for C language that >> > could suggest an optimized/alternate >> > programming logic for the function that >> > is written ? >> >> > The optimized/alternate logic can be >> > suggested as soon as we finish coding >> > for one function or it can be suggested >> > as soon as the code is compiled/parsed >> > by that tool. >> >> > It will be even more helpful if that tool >> > also provides the cycle counts, cache >> > usage, cache misses and lines of code >> > also. >> >> > It would be better if that tool has an >> > option to enable / disable this feature >> > either through compile time or some >> > other configurations. >> >> > Any ideas ? >> >> > Thx in advans, >> > Karthik Balaguru >> >> Brain? >> >> Seriously, I think this is impossible. >> What I can recommend to you are some good books, including >> (More) Programming Perls >> and >> Hacker's delight. >> >> Andreas- Hide quoted text - >> >> - Show quoted text - > > I don't see why it would be impossible. Optimizing compilers exist and > by using similar techniques it should be possible to write a compiler > that uses C as both the source and target language. How useful this > would be is another question. The resulting code would need to be > humanly readable if the tool would be of any use and the would > probably place severe restrictions on the sorts of optimizations that > can be done. I would be surprised if no work along these lines has > been done. > Indeed, some of what he suggested (loop counting, etc) would be not only very useful, but would be an excellent parsing/analysis learning experience if the OP were to try and implement it himself. And C would be an excellent language for this, because it has so few keywords and such straightforward branch control contructs (function pointers aside).
From: Andrew Poelstra on 12 Jan 2010 16:53 On 2010-01-12, David Schwartz <davids(a)webmaster.com> wrote: > On Jan 12, 9:12�am, scattered <still.scatte...(a)gmail.com> wrote: > >> I don't see why it would be impossible. Optimizing compilers exist and >> by using similar techniques it should be possible to write a compiler >> that uses C as both the source and target language. How useful this >> would be is another question. The resulting code would need to be >> humanly readable if the tool would be of any use and the would >> probably place severe restrictions on the sorts of optimizations that >> can be done. I would be surprised if no work along these lines has >> been done. > > That would be a useless tool, all it would do would be obfuscate. If > the code contains optimizations that can be made by machine, what is > the point of modifying the source code? Let the machine make the > optimizations when the code is compiled and keep the source intact. > > DS The idea would be that it could provide suggestions, not necessarily implement them or even come up with a concrete solution. Even something as simple as highlighting a function as "O(n^3)" would be helpful. Saying something like "this looks like a Bubblesort" and linking to a database (or wiki link) of sorting algorithms would also be nice, even if the machine didn't understand the data structures or nature of the data well enough to help.
From: David Brown on 12 Jan 2010 17:44 Walter Banks wrote: > > scattered wrote: > >> On Jan 12, 11:04 am, acd <acd4use...(a)lycos.de> wrote: >> >>> (More) Programming Perls >>> and >>> Hacker's delight. > > --------------------------------------- > > >> I don't see why it would be impossible. Optimizing compilers exist and >> by using similar techniques it should be possible to write a compiler >> that uses C as both the source and target language. How useful this >> would be is another question. The resulting code would need to be >> humanly readable if the tool would be of any use and the would >> probably place severe restrictions on the sorts of optimizations that >> can be done. I would be surprised if no work along these lines has >> been done. > > Programming Pearls and Hacker's delight are both must haves > even if you are only remotely interested programming algorithms. > > There has been quite a bit of work done in compilers at the > expression level to optimize algorithms and statements > implementing functionally equivalent statements in the > generated code. > > The problem in the bigger scale suggested by the op is the > ability to recognize the larger overview of the programming > objective at the scale of turning a bubble sort into a quick > sort. > > At the statement level recognizing functionality is generally > a simple task. At the function level this a significantly larger > problem. > > The solution may be mostly hard work and processing > cycles. A start may be to catalog common functions > and implementations and create a significant tool > to recognize these functions from source code extracting > out key function parameters and then using these to select > alternative implementations. > > As well as the data base of common functions a significant > piece of expert system software would need to be written > to extract knowledge out of the source. > > Do-able probably. > > Regards, > I think that it is conceivable that such a program could be made to do some re-writing of source code for increased efficiency. In fact, there are already editors that can aid in this - "refactoring" the code. All that is missing is to automatically suggest refactoring moves that could improve the code. Automatically change source code at the algorithmic level, on the other hand, is very much a blue-sky idea. However, I don't think it is the right approach. The /real/ goal is to make it easier for the programmer to write code that ends up as as efficient as possible target code. There are, I think, three things to tackle her. First off, compilers can be better at optimising code. There are certainly some pretty advanced optimisations in good compilers at the moment - but there is more that could be done, especially in cases when code and data space is tight. I can certainly think of optimisations that I believe would be feasible in compilers, but are (to my knowledge) not used today. And I am certain that Walter could think of many more. Secondly, rather than trying to write compliers that try to guess what C code is trying to do, it would be better to develop programming languages that make it easier for the programmer to express exactly what he means. Many current languages are better than C in this regard - for example, languages like Pascal and Ada let you declare types that are ranges of integers. The compiler doesn't have to fight with C's insistence that everything should be at least a 16-bit int - if the compiler knows it can fit that data into an 8-bit slot, then it can use 8 bits (assuming that gives better code on the target). Some languages like OCAML deduce many declarations automatically based on the usage of a variable - that lets the compiler pick the best type for the job, rather than the programmer. A language that can avoid forcing the programmer to either under-specify or over-specify what he wants would let the compiler do a better job. Thirdly, rather than having a compiler try to guess what algorithm you are trying to implement, it would be better to have more algorithms implemented in the libraries and preferably the language itself in a way that is natural for the programmer. For example, if the language has support for real arrays with functions such as sorting, the programmer can work with an array and let the compiler figure out the best way to implement it. With C, the programmer will either write their own bubble sort, or call qsort - with all its overheads. This is why programs written in interpreted languages such as Python can often be faster than compiled C code for code working with complex data structures, hash tables, sorting, list manipulation, etc., Of course the C code /could/ be faster - but people don't write optimal algorithms in most code. With the libraries and language support in Python, you get very good algorithms for free. mvh., David
From: Rich Webb on 12 Jan 2010 20:23 On Tue, 12 Jan 2010 13:34:11 -0800 (PST), David Schwartz <davids(a)webmaster.com> wrote: >On Jan 12, 9:12�am, scattered <still.scatte...(a)gmail.com> wrote: > >> I don't see why it would be impossible. Optimizing compilers exist and >> by using similar techniques it should be possible to write a compiler >> that uses C as both the source and target language. How useful this >> would be is another question. The resulting code would need to be >> humanly readable if the tool would be of any use and the would >> probably place severe restrictions on the sorts of optimizations that >> can be done. I would be surprised if no work along these lines has >> been done. > >That would be a useless tool, all it would do would be obfuscate. If >the code contains optimizations that can be made by machine, what is >the point of modifying the source code? Let the machine make the >optimizations when the code is compiled and keep the source intact. What he's looking for is not compiler optimizations but optimization of the underlying algorithm. As somebody else mentioned, seeing a bubble sort and deciding that a quick sort would be more appropriate. -- Rich Webb Norfolk, VA
From: Keith Thompson on 12 Jan 2010 20:53
Rich Webb <bbew.ar(a)mapson.nozirev.ten> writes: > On Tue, 12 Jan 2010 13:34:11 -0800 (PST), David Schwartz > <davids(a)webmaster.com> wrote: >>On Jan 12, 9:12 am, scattered <still.scatte...(a)gmail.com> wrote: >>> I don't see why it would be impossible. Optimizing compilers exist and >>> by using similar techniques it should be possible to write a compiler >>> that uses C as both the source and target language. How useful this >>> would be is another question. The resulting code would need to be >>> humanly readable if the tool would be of any use and the would >>> probably place severe restrictions on the sorts of optimizations that >>> can be done. I would be surprised if no work along these lines has >>> been done. >> >>That would be a useless tool, all it would do would be obfuscate. If >>the code contains optimizations that can be made by machine, what is >>the point of modifying the source code? Let the machine make the >>optimizations when the code is compiled and keep the source intact. > > What he's looking for is not compiler optimizations but optimization of > the underlying algorithm. As somebody else mentioned, seeing a bubble > sort and deciding that a quick sort would be more appropriate. Of course, that particular example is not terribly useful in practice, since it's easy enough to just not write a bubble sort in the first place. But it's a good as an example because it's easy to understand. -- Keith Thompson (The_Other_Keith) kst-u(a)mib.org <http://www.ghoti.net/~kst> Nokia "We must do something. This is something. Therefore, we must do this." -- Antony Jay and Jonathan Lynn, "Yes Minister" |