A tool that suggests optimized logic for a piece of code/module/function
in [Embedded]
|
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"
From: Paul Keinanen on 13 Jan 2010 00:40 On Tue, 12 Jan 2010 11:12:18 -0800 (PST), karthikbalaguru <karthikbalaguru79(a)gmail.com> wrote: >On Jan 12, 11:03�pm, Walter Banks <wal...(a)bytecraft.com> wrote: >> The issue is the larger one of function rewriting where >> the problem is larger and less work has been done >> looking for solutions. >> > >It is strange that no much research or >work is done in this area ? Strange !! > >I think, this is one of the most required >tool for efficient software development >in any kind of platform. If the problem on average is badly trained programmers, the obvious solution should be improving the training of programmers. A tool that points out suboptimal constructs etc. might be useful in the training phase, but what is the point of using it in actual program production ?
From: Phil Carmody on 13 Jan 2010 05:27
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. Unless it was only ever a handful of items, in which case an insertion sort might be more appropriate. Know your N (most important when N might be large, of course, but also when it's small). However, anything which brings about the nuking of bubblesort in any context is an improvement. Phil -- Any true emperor never needs to wear clothes. -- Devany on r.a.s.f1 |