20120915, 17:35  #1 
Just call me Henry
"David"
Sep 2007
Cambridge (GMT/BST)
2×5×587 Posts 
Program optimization
I while back I came across http://critticall.com/
This program optimizes code by making random changes, checking whether they work and their speed. Would this sort of approach work with optimizing assembler? Currently a compiler outputs a particular version for each type of cpu but there are potentially more optimizations that can be done for a particular system. Experimentation would surely give better results. 
20120915, 18:50  #2  
Basketry That Evening!
"Bunslow the Bold"
Jun 2011
40<A<43 89<O<88
3·29·83 Posts 
Quote:


20120915, 18:54  #3 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
9434_{10} Posts 
It would have been funny, if it wasn't so sad to watch...

20120915, 18:59  #4 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
9434_{10} Posts 
Here's how Critticall would solve the following problem.
One of the lights in the bathroom just went out. Solve it. <...a few hours later...> All walls are drilled in random places, the toilet is taken off and broken to pieces, all the fuses are blown by shorts, the water pipes were disconnected (but not shut)... you get the idea. The light is still off. _______________ (Genetic algorithms were around for more than a decade. I do agree that there are some problems for them. I've exaggerated a little bit with this example.) Last fiddled with by Batalov on 20120915 at 19:05 
20120915, 20:01  #5 
"Richard B. Woods"
Aug 2002
Wisconsin USA
2^{2}×3×641 Posts 
The basic problem is that the random genetic evolution algorithm needs 4 billion years to work properly.

20120916, 03:05  #6  
Aug 2006
3^{2}·5·7·19 Posts 
Quote:


20120922, 07:25  #7  
May 2008
Worcester, United Kingdom
20E_{16} Posts 
Quote:
The code is first designed and it is then analysed and annotated with information that specifies how far each individual instruction can be moved relative to the others around it without changing the final answer (using knowledge of the target microarchitecture). The code is then run in a simulator that tests the different instruction orders to find the order that gives the highest speed. 

20120922, 07:41  #8  
Undefined
"The unspeakable one"
Jun 2006
My evil lair
6,143 Posts 
The problem I foresee here is:
Quote:
The modern CPUs are very complex things. There are both internal and external states and conditions that occur under real application usage that a simulator cannot hope to duplicate, or even model closely. Also with the sheer number of movable instruction in any nontrivial program I suspect that finding the optimal order is a rather hard problem. Is there a travelling salesman in the house? 

20120922, 08:16  #9  
May 2008
Worcester, United Kingdom
2·263 Posts 
Quote:


20120922, 08:59  #10  
Undefined
"The unspeakable one"
Jun 2006
My evil lair
6,143 Posts 
Quote:
Quote:
Quote:


20120922, 09:41  #11  
May 2008
Worcester, United Kingdom
2·263 Posts 
Quote:
Nobody pretends that any of this is perfect  it doesn't have to be. The overall speed improvements are both measurable and significant. 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
gcc optimization/intrinsics  R.D. Silverman  Factoring  12  20150915 08:51 
Possible optimization for GIMPS  alpertron  Math  3  20120813 16:08 
NFS Optimization  R.D. Silverman  Factoring  91  20100124 20:48 
Program Optimization for dual processor machines  Altrus  Software  4  20050926 15:19 
ASM Optimization  Cyclamen Persicum  Hardware  4  20040526 07:51 