The Stack Overflow podcast is back! Listen to an interview with our new CEO.

Questions tagged [program-optimization]

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

65 questions
Filter by
Sorted by
Tagged with
28 views

Change the structure from 3SAT to 1in3 3SAT

There is a variable set V = {x1,x2,x3} and clause set C1={x1,x2,-x3} C2={x1,-x1,-x2} C3={-x1,-x2,x3} C4={x2,x3,-x3}. For this structure, no matter each variable is positive or negative, the clause can ...
49 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 ...
70 views

Tree Optimization, Combinatorics, algorithm [closed]

My Partners and me, we are trying to optimize frequency process... I used Java to show our Problem, but the question is about algorithm NOT about Java implementation. Although implementations in java ...
132 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 /...
31 views

Order of Traversal in Bidirectional Dataflow Analysis

Does order of traversing CFG matter in solving bidirectional dataflow problems, from a performance perspective?
72 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 ...
58 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 ...
54 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 ...
103 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 ...
8k 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 ...
346 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 ...
42 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 ...
155 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 ...
51 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 ...
162 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$$ ...
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 ...
152 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 ...
515 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. ...
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? ...
71 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 ...
4k 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 ...
531 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 ...
3k 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 ...
219 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 ...
98 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 ...
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 ...
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 ...
324 views

906 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, ...
115 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: ...
990 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, ...
98 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 ...
289 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 ...