Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C Programming > A tool that suggests optimized logic for a piece ofcode/module/function

Reply
Thread Tools

A tool that suggests optimized logic for a piece ofcode/module/function

 
 
John Gordon
Guest
Posts: n/a
 
      01-28-2010
In <(E-Mail Removed) inux.net> =?UTF-8?B?QW5kcsOp?= Gillibert <(E-Mail Removed)> writes:

> That's called an "optimizer" and is built into any good C compiler...
> It doesn't even need to suggest a change. It just does it
> internally, without modifying the source code.


The OP was asking for much more than an optimizing compiler.

To give just one example, he wants something which can recognize that
you're using a bubble-sort routine and can automatically rewrite the
source code into a quicksort.

--
John Gordon A is for Amy, who fell down the stairs
http://www.velocityreviews.com/forums/(E-Mail Removed) B is for Basil, assaulted by bears
-- Edward Gorey, "The Gashlycrumb Tinies"

 
Reply With Quote
 
 
 
 
Stefan Ram
Guest
Posts: n/a
 
      01-28-2010
John Gordon <(E-Mail Removed)> writes:
>The OP was asking for much more than an optimizing compiler.
>To give just one example, he wants something which can recognize that
>you're using a bubble-sort routine and can automatically rewrite the
>source code into a quicksort.


When a compiler would do such a thing, why could this
compiler not also be called »an optimizing compiler«?

There is at least one automated optimization technique
capable to do this: It tries all sequences of machine
instructions until it finds one that has the behavior wanted
(or the behavior of a given program).

Of course, this is too slow for real-world programs today,
but I believe it has indeed been used for some small programs.
I just forget the name of this technique.

 
Reply With Quote
 
 
 
 
Keith Thompson
Guest
Posts: n/a
 
      01-28-2010
http://www.velocityreviews.com/forums/(E-Mail Removed)-berlin.de (Stefan Ram) writes:
> John Gordon <(E-Mail Removed)> writes:
>>The OP was asking for much more than an optimizing compiler.
>>To give just one example, he wants something which can recognize that
>>you're using a bubble-sort routine and can automatically rewrite the
>>source code into a quicksort.

>
> When a compiler would do such a thing, why could this
> compiler not also be called Ā»an optimizing compilerĀ«?
>
> There is at least one automated optimization technique
> capable to do this: It tries all sequences of machine
> instructions until it finds one that has the behavior wanted
> (or the behavior of a given program).
>
> Of course, this is too slow for real-world programs today,
> but I believe it has indeed been used for some small programs.
> I just forget the name of this technique.


It's called "superoptimization". I think it's been used to generate
optimal code sequences that can then be hardwired into a compiler (so
the expensive superoptimization occurs during compiler development,
not during each compilation).

--
Keith Thompson (The_Other_Keith) (E-Mail Removed) <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"
 
Reply With Quote
 
Keith Thompson
Guest
Posts: n/a
 
      01-28-2010
John Gordon <(E-Mail Removed)> writes:
> In <(E-Mail Removed) inux.net> =?UTF-8?B?QW5kcsOp?= Gillibert <(E-Mail Removed)> writes:
>
>> That's called an "optimizer" and is built into any good C compiler...
>> It doesn't even need to suggest a change. It just does it
>> internally, without modifying the source code.

>
> The OP was asking for much more than an optimizing compiler.
>
> To give just one example, he wants something which can recognize that
> you're using a bubble-sort routine and can automatically rewrite the
> source code into a quicksort.


So he wants a really clever optimizing compiler.

--
Keith Thompson (The_Other_Keith) (E-Mail Removed) <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"
 
Reply With Quote
 
Walter Banks
Guest
Posts: n/a
 
      01-28-2010


Stefan Ram wrote:

> There is at least one automated optimization technique
> capable to do this: It tries all sequences of machine
> instructions until it finds one that has the behavior wanted
> (or the behavior of a given program).
>
> Of course, this is too slow for real-world programs today,
> but I believe it has indeed been used for some small programs.
> I just forget the name of this technique.


It comes under a number of names "superoptimizer" is one.
There two problems,

1) it as you say it can be slow. A 5 or 6 instruction search
can take up to a day.

2) Anything other than simple examples are surprisingly
hard to write correct execution criterion for.

It is however a technique that be useful for compiler writers
and those interested in coding algorithms.

Regards,


w..
--
Walter Banks
Byte Craft Limited
Tel. (519) 888-6911
http://www.bytecraft.com





 
Reply With Quote
 
Richard Bos
Guest
Posts: n/a
 
      01-31-2010
Keith Thompson <(E-Mail Removed)> wrote:

> John Gordon <(E-Mail Removed)> writes:


> > The OP was asking for much more than an optimizing compiler.
> >
> > To give just one example, he wants something which can recognize that
> > you're using a bubble-sort routine and can automatically rewrite the
> > source code into a quicksort.

>
> So he wants a really clever optimizing compiler.


No, he wants a read-my-mind magic optimising compiler. That is a
fundamentally different thing from a merely really clever one.

Richard
 
Reply With Quote
 
Keith Thompson
Guest
Posts: n/a
 
      01-31-2010
(E-Mail Removed) (Richard Bos) writes:
> Keith Thompson <(E-Mail Removed)> wrote:
>> John Gordon <(E-Mail Removed)> writes:
>> > The OP was asking for much more than an optimizing compiler.
>> >
>> > To give just one example, he wants something which can recognize that
>> > you're using a bubble-sort routine and can automatically rewrite the
>> > source code into a quicksort.

>>
>> So he wants a really clever optimizing compiler.

>
> No, he wants a read-my-mind magic optimising compiler. That is a
> fundamentally different thing from a merely really clever one.


I don't think so. It would require some of what one might call
artificial intelligence, but the boundary between AI and merely
clever programming has always been fuzzy.

An optimizer that's able to recognize bubble sort and replace it
with quicksort should be entirely feasible, if it's handled as a
special case. (It's probably not worth doing, since it's easier
for the programmer to just use quicksort in the first place.)

And it wouldn't read the programmer's mind; the whole point is that
the programmer didn't think of using quicksort.

--
Keith Thompson (The_Other_Keith) (E-Mail Removed) <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"
 
Reply With Quote
 
Walter Banks
Guest
Posts: n/a
 
      02-01-2010


Keith Thompson wrote:

> An optimizer that's able to recognize bubble sort and replace it
> with quicksort should be entirely feasible, if it's handled as a
> special case.
>
> And it wouldn't read the programmer's mind; the whole point is that
> the programmer didn't think of using quicksort.


The optimizer difficulty in C is recognizing the bubble sort then
determining that if it were replaced with a quicksort there
would be a benefit.

If a language represented objectives rather than implementations
it would be then possible for the compiler to simply make
choices in the code it generates.

To some extent this happens in C compilers now. For example
when a compiler sees a multiply "*" in source code it makes a
lot of choices when selecting what code to generate. The final
choice is based on data size, multiply by a constant or multiply
to constants (constant folding) and the appropriate code is
generated.

Telling the compiler ins some way what the objective is would
be the first step would be in determining what code should be
included in the application.

Regards,


Walter..

--
Walter Banks
Byte Craft Limited
http://www.bytecraft.com







 
Reply With Quote
 
Richard Tobin
Guest
Posts: n/a
 
      02-01-2010
In article <(E-Mail Removed)>,
Walter Banks <(E-Mail Removed)> wrote:

>Keith Thompson wrote:
>> An optimizer that's able to recognize bubble sort and replace it
>> with quicksort should be entirely feasible, if it's handled as a
>> special case.


It would have to be a bit clever than that. Bubble sort is stable,
and quicksort implementations typically are't. It would have to
either use a stable version of quicksort, or determine that the
difference didn't affect the rest of the program.

Which is another example of this:

>If a language represented objectives rather than implementations
>it would be then possible for the compiler to simply make
>choices in the code it generates.


>To some extent this happens in C compilers now. For example
>when a compiler sees a multiply "*" in source code it makes a
>lot of choices when selecting what code to generate.


And of course one way C does this is by providing the library. Using
qsort() instead of writing a sort algorithm expresses clearly that you
want the data sorted. And it would be better if it provided both
a sort() and a stable-sort(), so you could express whether you
cared.

-- Richard
--
Please remember to mention me / in tapes you leave behind.
 
Reply With Quote
 
Stefan Ram
Guest
Posts: n/a
 
      02-01-2010
(E-Mail Removed) (Richard Tobin) writes:
>It would have to be a bit clever than that. Bubble sort is stable,
>and quicksort implementations typically are't. It would have to
>either use a stable version of quicksort, or determine that the
>difference didn't affect the rest of the program.


What one might want is to provide a list of input-output
pairs and get a generated program to implement a mapping
via a rule that is as simple (small) as possible and then
can be generalized to other inputs as well.

An example of a program to do this is

http://ccsl.mae.cornell.edu/sites/de...09_Schmidt.pdf

. A copy of Eureqa can be downloaded at

http://ccsl.mae.cornell.edu/eureqa_download
http://ccsl.mae.cornell.edu/eureqa

. So, to generate a program to map x to f(x), you would
provide pairs of x and f(x) to Eureqa, and then copy the
formula it gives you into your source code. To »optimize«
another program, let it first generator such pairs and
then feed these pairs to Eureqa.

 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
problem in running a basic code in python 3.3.0 that includes HTML file Satabdi Mukherjee Python 1 04-04-2013 07:48 PM
Download a file piece by piece Patrick Plattes Ruby 2 11-30-2006 07:48 PM
Toshiba suggests end of DVD war is near. Allan DVD Video 1 06-02-2005 01:31 PM
"Google Suggests" and the AJAX .NET Wrapper? Phin ASP .Net 2 06-02-2005 07:43 AM



Advertisments