18 votes
Accepted

What is the name of this type of program optimization where two loops operating over common data are combined into a single loop?

It's called "loop fusion". It's often more efficient, in the sense of doing more work per loop iteration and sometimes (as you say) other advantages. On the other hand, the fused loop in ...
Pseudonym's user avatar
  • 22k
17 votes
Accepted

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

I imagine many compiler implementers for typical imperative languages simply weren't that familiar with CPS and CPS-based compilation techniques. In the functional programming community both CPS and ...
Derek Elkins left SE's user avatar
15 votes
Accepted

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

While GCC likely uses ad-hoc rules, you can derive them in the following way. I'll use pow to illustrate since you're foo is so ...
Derek Elkins left SE's user avatar
15 votes

Data structure or algorithm for quickly finding differences between strings

My solution is similar to j_random_hacker's but uses only a single hash set. I would create a hash set of strings. For each string in the input, add to the set $k$ strings. In each of these strings ...
Simon Prins's user avatar
12 votes
Accepted

Data structure or algorithm for quickly finding differences between strings

It's possible to achieve $O(nk \log k)$ worst-case running time. Let's start simple. If you care about an easy to implement solution that will be efficient on many inputs, but not all, here is a ...
D.W.'s user avatar
  • 158k
10 votes
Accepted

Data Flow Analysis with exceptions

Ignoring exceptions is unsound. Example: let g = { raise E; } let f = { x := interesting_stuff(); g(); x := 0; } When analyzing ...
Gilles 'SO- stop being evil''s user avatar
9 votes

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

I’m going to beat around the bush for a while, but there is a point. Semigroups The answer is, the associative property of the binary reduction operation. That’s pretty abstract, but multiplication ...
Davislor's user avatar
  • 1,241
9 votes
Accepted

What formal representation is commonly used to describe compiler optimizations?

There are many compilers, which compile widely different kinds of languages which serve widely different purposes. For example, a database language will have very different optimizations than an array-...
cody's user avatar
  • 8,154
9 votes
Accepted

Constant folding vs. Constant propogation

Based on these two websites: http://www.compileroptimizations.com/category/constant_folding.htm and http://www.compileroptimizations.com/category/constant_propagation.htm The difference is that ...
nikolaevra's user avatar
7 votes
Accepted

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

I'm not aware of anything exactly like this, but there are some things that are arguably related. For specifically sorting this is related to the Schwartzian transform, though with a very different ...
Derek Elkins left SE's user avatar
7 votes
Accepted

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

Data flow analysis and type inference are specific instances of abstract interpretation. Data flow analysis and abstract interpretation look similar since they are both about computing a fix point. ...
zpavlinovic's user avatar
  • 1,644
7 votes
Accepted

Is writing a compiler for a compact language easier?

In almost every case, the more compact languages like APL will be harder write a compiler for: On the front end (parser), in the worst case, you have a ton bunch of special cases for your symbols in ...
Joey Eremondi's user avatar
7 votes

Data structure or algorithm for quickly finding differences between strings

I would make $k$ hashtables $H_1, \dots, H_k$, each of which has a $(k-1)$-length string as the key and a list of numbers (string IDs) as the value. The hashtable $H_i$ will contain all strings ...
j_random_hacker's user avatar
7 votes

Does strong typing contribute to better performance optimization by compiler?

I think your friend somewhat presents a false dichotomy. I will just give one example: when it first came out, the Self VM was one of the fastest dynamic language implementations. In fact, the ...
Jörg W Mittag's user avatar
6 votes

Is it possible to submit every March Madness bracket?

The rate-limiting factor is the cost of submitting each of those $2^{63}$ combinations. Since submitting a combination probably requires (at minimum) opening a network connection and sending the ...
D.W.'s user avatar
  • 158k
6 votes

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

A good place to learn about these three approaches and how the relate is the book Principles of Program Analysis by Nielson, Nielson and Hankin. I don't think it's correct to say that data-flow ...
Martin Berger's user avatar
5 votes

When is it useful to split critical edges?

An easy google search shows in Muchnick, Advanced Compiler Design & Implementation, Section 13.3 Partial-Redundancy Elimination, pp 407-408: A key point in the algorithm is that it can be much ...
cody's user avatar
  • 8,154
5 votes

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

I consider them as basically the same. They just had initially different goals and were coined by different computer science factions. Data flow analysis comes from the compiler engineering faction, ...
lambdapower's user avatar
5 votes

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

It is not clear what exactly you want of that compiler, so let me explore several possibilities. Optimize the parallelism This is impossible. Optimizing even sequential runtime is not computable, ...
Raphael's user avatar
  • 72.3k
5 votes

Why is it so difficult to eliminate dead loops?

The conceptual problem here is that dead code elimination is not computable. That is, we know that there is no algorithm that can remove all instances of dead code. Of course, tools can be created ...
Raphael's user avatar
  • 72.3k
4 votes
Accepted

Can loops like this one be algorithmically transformed into multiplication

The name for this optimization seems to be induction variable elimination, there are some nice slides explaining the idea here.
cody's user avatar
  • 8,154
4 votes

Functional programming with branches that have no order?

Here's the problem: You always need some way to resolve ambiguity when there are overlapping clauses There is no easy syntactic way to ensure that clauses don't overlap. So, if you can think of a ...
Joey Eremondi's user avatar
4 votes
Accepted

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

Assuming f(0) and f(1) are integers, find which powers of two and of five are factors of f(0) and f(1). The powers in f(n) can be calculated like a Fibonacci sequence and the number of trailing zeroes ...
gnasher729's user avatar
  • 29.4k
3 votes

Identify similar functions

The problem is not decidable (by reduction from the Halting problem), so there is no perfect algorithm that always terminates and always gives the correct answer. Therefore, you'll need to make some ...
D.W.'s user avatar
  • 158k
3 votes

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

Challenge #1: Imperative code You've shown code that is in a nicely functional form. But in many languages, in many cases, the code won't be in that nice form. Imagine if instead of ...
D.W.'s user avatar
  • 158k
3 votes
Accepted

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

$\mathsf{3LIN}$ is the following problem: Given a set of linear equations of the form $x_i \oplus x_j \oplus x_k = b$, where $1 \leq i,j,k \leq n$ and $b$ is a bit, find an assignment for the bits $...
Yuval Filmus's user avatar
3 votes

Big-O Notation and Calculus?

an algorithm linear according to Big-O notation reduces the size of the problem by a constant amount at each step I don't think that's really true. It seems to me that all you're doing here is ...
David Richerby's user avatar
3 votes

What is the difference between speculative execution & branch prediction?

“Branch prediction” will predict whether a particular branch is taken or not. The prediction can be right or wrong; whoever designs the hardware for it will want the prediction to be correct as often ...
gnasher729's user avatar
  • 29.4k
2 votes

Functional programming with branches that have no order?

If you restrict yourself to using constructors of datatypes, the compiler knows what can happen during pattern matching. For instance, assume your integer type is defined by this: ...
Raphael's user avatar
  • 72.3k

Only top scored, non community-wiki answers of a minimum length are eligible