Questions tagged [program-optimization]

Questions about how to optimise a program's performance, both manually and automatically, e.g. in compilers.

Filter by
Sorted by
Tagged with
22
votes
4answers
1k views

Automated optimization of 0-1 matrix vector multiplication

Question: Is there established procedure or theory for generating code that efficiently applies a matrix-vector multiplication, when the matrix is dense and filled with only zeros and ones? Ideally, ...
20
votes
1answer
1k views

Do fully optimizing compilers for terminating programs exist?

In Andrew W. Appel's book, Modern Compiler Implementation in ML, he says under chapter 17 that Computability theory shows that it will always be possible to invent new optimizing transformations and ...
19
votes
12answers
9k views

Data structure or algorithm for quickly finding differences between strings

I have an array of 100,000 strings, all of length $k$. I want to compare each string to every other string to see if any two strings differ by 1 character. Right now, as I add each string to the ...
16
votes
2answers
3k views

Why is static-single assignment preferred over continuation passing style in many industry-used compilers?

According to the Wikipedia page on static-single assignment (SSA), SSA is used by large and well-known projects such as LLVM, GCC, MSVC, Mono, Dalvik, SpiderMonkey, and V8 while the page on projects ...
14
votes
2answers
616 views

What property of cons allows elimination of tail recursion modulo cons?

I'm familiar with the idea of basic tail recursion elimination, where functions that return the direct result of a call to themselves can be rewritten as iterative loops. ...
11
votes
5answers
633 views

Why is the OS design able to reduce power consumption?

I have read that OSes like Android and iOS are somehow optimised to improve battery life. My understanding is that a CPU executes a certain number of operations in a certain time, so I would think ...
10
votes
1answer
714 views

Micro-optimisation for edit distance computation: is it valid?

On Wikipedia, an implementation for the bottom-up dynamic programming scheme for the edit distance is given. It does not follow the definition completely; inner cells are computed thus: ...
9
votes
3answers
650 views

Equivalence of data-flow analysis, abstract interpretation and type inference?

@Babou's answer to a recent question reminds me that at one time I think I read a paper about the equivalence (in terms both of the facts that can be inferred or proved and the time complexity of ...
8
votes
1answer
436 views

Data Flow Analysis with exceptions

Data flow analysis work over a control flow graph. When a language under consideration supports exceptions, control flow graph can explode. What are the standard techniques for dealing with this ...
8
votes
0answers
183 views

Optimizing order of graph reduction to minimize memory usage

Having extracted the data-flow in some rather large programs as directed, acyclic graphs, I'd now like to optimize the order of evaluation to minimze the maximum amount of memory used. That is, given ...
7
votes
3answers
285 views

Are compilers able to detect alternating accesses to arrays and interleave them in memory?

Is it possible to design a compiler which optimizes a loop in which arrays are accessed in alternate fashion? For example like this: ...
7
votes
1answer
284 views

Reference request: optimizing procedures on lists in dynamic languages by performing safety checks in advance

For my science fair project, I implemented an optimization to Python's sort routine. The idea is to move the safety checks that have to be carried out during each comparison, e.g. type checks and ...
7
votes
1answer
443 views

When is it useful to split critical edges?

Some compilers have utility functions that split critical edges in the control flow graph. I assume that this is not done as an optimization in itself, but rather to simplify other analyses and ...
6
votes
3answers
4k views

Constant folding vs. Constant propogation

What is the difference between constant folding and constant propogation? They both seem to do the same thing, instead of saving constants into stack or evaluating a full arithmetic expression, they ...
6
votes
1answer
595 views

generating pi using Machin like formula

Back in 2002, using this arctan formula for pi discoverd by Stoemer: $$ \pi = 176 \arctan(1/57) + 28 \arctan(1/239) - 48 \arctan(1/682) \\ + 96 \arctan(1/12943)$$ and I assume using this ...
5
votes
2answers
255 views

is the problem of parallelising any program, NP-complete?

Consider a program written in a common language such as C. Assume that it does not have any explicit parallel constructs. Then, once it is compiled to an executable program, it will be run serially, ...
5
votes
1answer
136 views

Dataflow framework for global analysis: Why meet, then apply?

In Chapter 9 of the Dragon Book, the authors describe the dataflow framework for global analysis (described also in these slides). In this framework, an analysis is defined by a set of transfer ...
5
votes
0answers
126 views

minimizing computations for evaluating two polynomial simultaneously

I want to evaluate two polynomials $f$ and $g$ simultaneously, on the same input (in a computer program). These polynomial have only coefficients $0, 1, a , b$ and their degree is less than 700. I ...
4
votes
1answer
101 views

What formal representation is commonly used to describe compiler optimizations?

I have devised a compiler optimization that works on any structured language that has arrays assignments array[index] = value and counted loops ...
4
votes
2answers
449 views

Loop-invariant code motion with unsafe operations

There are well-known algorithms LICM, and they work well. Unfortunately, there are certain cases when these optimizations can cause runtime failures with code that was initially correct. Consider the ...
4
votes
1answer
60 views

Is there an algorithm that can find a solution that solves the most number of equations in a linear system of equations?

My apologies if this question makes no sense. I am trying to find an algorithm that can solve a linear system of equations. Unlike most problems like this, this algorithm does not need to find a ...
4
votes
2answers
94 views

Is there a fundamental CS problem in ORMs that leads to N+1?

Many of us are familiar with N+1 problem when working with database queries. The problem was known before ORMs (Object-relational mapping frameworks) came around, but it seems that ORMs exacerbated it....
4
votes
0answers
43 views

Rectangle Packing with Constraints

I am aware that the general rectangle packing problem is NP-hard. I am trying to form an estimate for a version of the problem with constraints. Consider fitting rectangles of smaller size into a ...
4
votes
0answers
43 views

Symbolic Math Systems As Speculative Optimization For Numerical Software?

Has there been published work on hiding symbolic math within numeric software, partitioning parallel processes between speculative symbolic optimization search and numeric evaluations? Real world ...
3
votes
2answers
227 views

Is writing a compiler for a compact language easier?

I am contemplating the project of writing a compiler. I am wondering if, aside from the availability of easy google results, it is easier to write a compiler for a more explicit/verbose language such ...
3
votes
4answers
128 views

Can loops like this one be algorithmically transformed into multiplication

Are there known techniques for converting a loop like the following to an if and a multiplication? ...
3
votes
1answer
966 views

Optimizing NFL draft picks

I have a little problem I have been trying to solve for a hobby after a friend got me interested in fantasy football: given a list of players, positions for those players, projected points, salary, ...
3
votes
1answer
4k views

Using Amdahl's law how do you determine execution time after an improvement?

Speeding up a new floating-point unit by 2 slows down data cache accesses by a factor of 2/3 (or a 1.5 slowdown for data caches). If old FP unit took 20% of program's execution time and data cache ...
3
votes
1answer
38 views

How to best calculate the best possible path with weights

Given a set of nodes, with connections in certain directions (see image), what is the most coins you can collect between the first and last given node. Not all rooms have coins, and we want to output ...
3
votes
1answer
194 views

How to avoid permutations in the n-Queens problem?

EDIT: if you are not familiar with the problem and the solution, it's nicely explained here. I have solved the n-Queens problem as an exercise using backtracking (recursion), but the problem I have ...
3
votes
1answer
624 views

Can you solve 3D Tic Tac Toe with Minimax?

I have implemented a 3d Tic Tac Toe game with AI, where the computer is unbeatable. The only thing is that the board looks like this: _ _ _ _ _ _ _ _ rather ...
3
votes
0answers
52 views

Is there research into associative/commutative optimizations?

While playing around with optimization sets in LLVM, it occurs to me that the order in which optimizations are run matters greatly since, in general, A(B(src)) is ...
3
votes
0answers
157 views

How to compute an optimally cost-effective cache strategy?

I am looking for advice in the following optimization problem. I have a website (system) that receives database updates later returned in queries made to the same system. In order to speed up the ...
2
votes
1answer
375 views

Is it possible to submit every March Madness bracket?

A few years ago Warren Buffett started offering $1 billion to anyone who could correctly predict the winner of every game in the NCAA men's basketball tournament. A 64 team (we won't count the first ...
2
votes
2answers
97 views

Functional programming with branches that have no order?

I was wondering if there is any programming style in which the outcome does not depend on the order of statements or groups of statements such as guards. Vaguely, I imagine this would leave room for ...
2
votes
2answers
170 views

Big-O Notation and Calculus?

I was wondering if there are any calculus relationships implicit in Big-O notation. For example, an algorithm linear according to Big-O notation reduces the size of the problem by a constant amount ...
2
votes
1answer
614 views

Why is it so difficult to eliminate dead loops?

I recently came across an issue where my compiler was not able to eliminate some "obviously" dead code - it was a function that returned nothing, with no side effects, and a cursory analysis of the ...
2
votes
2answers
179 views

Chaitin's elegant programs

I need help to understand Chaitin's elegant program proof. An elegant program is the shortest program that produces a given output. Here is the proof: Construct a program $B$ that takes as input a ...
2
votes
2answers
300 views

Second order function formalization

I need to work on a optimizer for a language whose operator are second order functions. They are the well known ones filter, map, reduce, fold, foreach etc. etc. I need to formalize as much as ...
2
votes
1answer
679 views

Difference between symbolic execution and reachability analysis

Now I am confused about symbolic execution (SE) and reachability analysis (RA). As I know, SE uses symbols to execute some code to reach each branch with branch conditions. And RA can be used to find ...
2
votes
3answers
68 views

Automatic softcore configuration based on intermediate representation (IR) compiler output

When compiling a piece of software (with LLVM for exmple), you first transform your code into some kind of intermediate representation (IR code). This IR code needs to be converted to your target ...
2
votes
1answer
127 views

Benefit of Backward Pass at compile time

We collect most of the information about possible compiler optimizations during forward pass. Is it possible to utilize the information collected in forward pass in a backward pass so as to perform ...
2
votes
1answer
804 views

Understanding Amdahl's Law calculation

I have a homework problem: Calculate the overall speedup of a system that spends 40% of its time in calculations with a processor upgrade that provides for 100% greater throughput. Which is a pretty ...
2
votes
0answers
29 views

Compiler optimization which does an SMT-like optimization in software?

Say I had two functions called one after the other: ...
2
votes
0answers
73 views

Lazy evaluation on slow Boolean functions (optimization)

Short-circuit evaluation is a straight forward subject for lazy evaluation on Boolean expressions, I noted that two factors could be useful in ordering Boolean functions to improve run-time. But this ...
2
votes
0answers
99 views

Methods for optimizing short-circuit evaluation for conditions of varying evaluation-cost

I have a bunch of boolean conditions, let's call them A, B, C, D, .... In my code, I need to use these conditions to distinguish between several different possible ...
1
vote
3answers
177 views

Fastest Algo to separate the 0s and 1s [closed]

Suppose, I have an array of length 100. I have 0s at some positions and 1s at some other positions. What is the fastest method by which I can separate the 0s and 1s, so that we get all the 0s at the ...
1
vote
3answers
309 views

Should compilers automatically translate operations into shortcuts?

There are several coding operations that (I suspect) most compilers will change into more efficient operations at the assembly or machine code level. I have several questions about whether or not the ...
1
vote
1answer
375 views

Identify similar functions

I was wondering if there is any technique in order to recognize similar functions behaviour. In particular, suppose that I implement two functions $f$ and $g$ in a certain programming language $P$ and ...
1
vote
2answers
1k views

Best improvements to do to the DPLL SAT algorithm

As part of a college class, I'm asked to improve the performance of a basic DPLL sat solver. I'm already provided a basic, slow working version (essentially the DPLL algorithm; furthermore, to select ...