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

learn more… | top users | synonyms

2
votes
0answers
12 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 ...
3
votes
2answers
51 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
91 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
90 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
85 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: ...
17
votes
4answers
427 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
40 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
77 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 ...
7
votes
2answers
98 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
244 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
156 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 ...
3
votes
2answers
158 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
68 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 ...
3
votes
0answers
108 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
2answers
130 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 ...
1
vote
1answer
289 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 ...
14
votes
1answer
482 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 ...
1
vote
3answers
167 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 ...
3
votes
1answer
3k 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 ...
0
votes
1answer
114 views

Using Loop Dependence analysis for vectorization

How exactly Loop Dependence Analysis helps in vectorization ? Are there any standard rules of safety criterias for parallizing such loops ?
2
votes
1answer
88 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 ...
7
votes
3answers
184 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: ...
5
votes
1answer
111 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 ...
10
votes
1answer
695 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: ...
8
votes
0answers
149 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 ...