Questions tagged [program-optimization]
Questions about how to optimise a program's performance, both manually and automatically, e.g. in compilers.
0
votes
1answer
69 views
Autocorrect algorithm - How to implement a decent “apostrophe & elision” feature?
shorter version of the original question (as requests in comments)
What is the algorithm to handle missing apostrophe as it is done in auto-correct feature of Android virtual keyboard?
(If it helps /...
1
vote
0answers
28 views
Order of Traversal in Bidirectional Dataflow Analysis
Does order of traversing CFG matter in solving bidirectional dataflow problems, from a performance perspective?
0
votes
1answer
60 views
Any CPUs using value prediction, dynamic instruction reuse?
There is a lot of research about techniques that try to reuse the previous result of an instruction, either memory loads or arithmetic, such as dynamic instruction reuse, value prediction, based on ...
1
vote
1answer
54 views
Optimize sorting matrix entries by row and column
I am writing a routine to store an $M$-by-$N$ sparse matrix in a balanced binary tree. The insertion routine calls a comparison function to determine where a new matrix entry $(i,j)$ should be ...
4
votes
1answer
51 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 ...
0
votes
1answer
87 views
Is the spigot algorithm for $\pi$ useful for computing all the digits of $\pi$?
I'm asking the question here because it's not a purely mathematical question and the answer also depends on how computers work. I think that according to the Wikipedia article Bailey–Borwein–Plouffe ...
17
votes
12answers
7k 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 ...
0
votes
2answers
265 views
Calculate the number of trailing zeros in equation f(n) = f(n-1) * f(n-2) where f(0) and f(1) are any given arbitary numbers
This question is doable if you can calculate the number by multiplying f(n-1) and f(n-2).
Is it possible to do this question if we entirely want to skip ...
4
votes
0answers
41 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
1answer
120 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 ...
2
votes
3answers
47 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 ...
0
votes
1answer
128 views
Is there a poly-time algorithm for expanding out polynomials
so I've been looking around and haven't seen this before. Basically I'm working with a problem in which I need to expand/FOIL out. Something in the form of
$$
z = (x+y)(x-y) \implies x^2+xy-xy+y^2
$$
...
0
votes
0answers
22 views
Non-optimal program, bad choice of language or Low-speed system?
To check some results of an article, I wrote the proposed algorithm from the Coding articles. In the article, some results from the algorithm were obtained. Unfortunately, the performance of my ...
0
votes
0answers
126 views
Why is sequential search of ordered list slower than search of unordered one
I have got assignment to implement set class with linked list, so I first made it with unordered list and time needed to insert million integers is bit less than hour. Then I thought I can get it to ...
13
votes
2answers
459 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.
...
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?
...
2
votes
0answers
69 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 ...
-1
votes
1answer
3k views
How do I calculate the speedup properly?
I am trying to calculate the speedup of this, but I am getting the wrong answer:
Assuming that we have a program where we have two execution phases. One phase takes 1 time unit to execute and can ...
2
votes
1answer
510 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 ...
6
votes
3answers
2k 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 ...
3
votes
2answers
206 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 ...
4
votes
1answer
93 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 ...
1
vote
0answers
27 views
Program Transformation to Disintermediate Isomorphic Representation Transforms
Given two representations of the same abstract data type, any optimal program that incorporates one representation has a corresponding optimal program that incorporates the other.
What is the field ...
13
votes
2answers
2k 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 ...
2
votes
1answer
300 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 ...
1
vote
3answers
328 views
Match dictionary to misspelled word, corner cases
I'm trying to think of corner-cases where I can skip having to linear-search through my dictionary in my problem; For a given word w1, find all matches with the least editing distance from it in the ...
1
vote
1answer
374 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
0answers
1k views
How to use Clarke and Wright saving algorithm to afford heterogeneous fleet?
I want to solve Heterogeneous fleet in vehicle routing problem using the Clarke and Wright saving algorithm. After reading many literature I found two options:
Explicit and early assignment for the ...
6
votes
1answer
449 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 ...
4
votes
1answer
464 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 ...
7
votes
1answer
283 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 ...
2
votes
1answer
588 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 ...
7
votes
1answer
322 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 ...
1
vote
2answers
863 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 ...
3
votes
0answers
48 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 ...
5
votes
1answer
206 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, ...
8
votes
1answer
408 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 ...
4
votes
2answers
86 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....
3
votes
2answers
91 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 ...
5
votes
0answers
123 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 ...
3
votes
1answer
764 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, ...
0
votes
1answer
112 views
What is the name of this code transformation that uses associativity of addition?
I am learning about compiler optimization technique and there is a technique that use associativity of addition to transform code.
For example, consider the following expression:
...
21
votes
4answers
938 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, ...
2
votes
0answers
95 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 ...
2
votes
2answers
261 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 ...
9
votes
3answers
501 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 ...
1
vote
3answers
302 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 ...
11
votes
5answers
488 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 ...
4
votes
2answers
427 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 ...
1
vote
0answers
138 views
Amdahl “validity of the single processor approach”
The following is Figure 1 in Gene M. Amdahl's "Validity of the single processor approach to achieving large scale computing capabilities" (1967) (PDF):
The text describes this as representing the ...
