16

I assume you are interested in optimisation of runtime. As I've written in my comment, that does not sufficiently specify the goal: does an optimisation reduce runtime on any input, every input, all worst-case inputs or even on average? I will show that all of them are impossible. The proof extends to optimising the length of the program. Recall that the ...


15

Common CPUs that go into smartphones, laptops and even desktop PCs have a variable clock rate. When the scheduler detects that it has idle time, it can reduce the clock rate, and increase it again if there are more processes competing for CPU time. CPUs optimized for battery-powered devices tend to be composed of many functional components that each have ...


15

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 replace one of the letters with a special character, not found in any of the strings. While you add them, check that they are not already in the set. If they are ...


12

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 vaguely defined. Also, foo might best be understood as an instance of last-call optimization with respect to single-assignment variables as the language Oz has and as discussed in Concepts, Techniques, and Models of Computer ...


12

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 simple, pragmatic, easy to implement solution that many suffice in practice for many situations. It does fall back to quadratic running time in the worst case, ...


11

Some work has been done that matches your description. For instance: Compiler-directed array interleaving for reducing energy in multi-bank memories. by Delaluz, V. Design Automation Conference, 2002. Proceedings of ASP-DAC 2002. 7th Asia and South Pacific and the 15th International Conference on VLSI Design. Proceedings. describes a such an optimization.


10

Ignoring exceptions is unsound. Example: let g = { raise E; } let f = { x := interesting_stuff(); g(); x := 0; } When analyzing f, you need to take into account the fact that g raises an exception, otherwise you would incorrectly conclude that x is always 0 on return from f. I don't know that there is a “standard” technique for dealing ...


9

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 CPS-based compilation are very well-known techniques - the latter from Guy Steele's work. Nevertheless, even in the FP community, most compilers don't use CPS-...


9

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-based language like APL. Compilers themselves use several intermediate languages, from the input language, to a de-sugared version of the input language, all ...


8

This is related to an open research question, which is known as the "Online Boolean Matrix-Vector Multiplication (OMv) problem". This problem reads as follows (see [1]): Given a binary $n \times n$ matrix $M$ and $n$ binary column vectors $v_1, \dots, v_n$, we need to compute $M v_i$ before $v_{i+1}$ arrives. Notice that the problem from the question is ...


8

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 is a good example. If x, y and z are some natural numbers (or integers, or rational numbers, or real numbers, or complex numbers, or N×N matrices, or any of a ...


7

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 goal. In the Schwartzian transform, you run through the input applying an expensive function and pairing the input and output together, then sorting on the ...


7

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 your parser, and in the best case, you treat them as generic symbols, in which case you're in the exact same parsing position as a language that has In the back-...


7

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 processed so far but with the character at position $i$ deleted. For example, if $k=6$, then $H_3[ABDEF]$ will contain a list of all strings seen so far that have ...


6

I don't think that the algorithm is flawed. If two strings are matched, we compare first its last two characters (and then recurse). If they are the same, we can match them to get an optimal alignment. For example, consider the strings test and testat. If you don't match the two last ts, than one of the ts remains unmatched, since otherwise your matching ...


5

If it is possible try to exploit banded tridiagonal nature of matrix. Otherwise if the matrix contains only a constant number of distinct values (which surely is being binary), you should try Mailman algorithm (by Edo Liberty, Steven W. Zucker In Yale university technical report #1402): optimized over finite dictionary Common Subexpression Elimination is ...


5

i=0, j=size(ar)-1; while(true) increase i to position of first 1; decrease j to position of first 0; if(i>=j) break; ar[i]=0, ar[j]=1;


5

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 more effective if the critical edges in the flowgraph have been split before the flow analysis is performed. So the notion is useful to increase the efficiency ...


5

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 constant propogation is not saving a variable to the stack, because we know its a constant (like x = 10;) and can simply plug it in everywhere (say if you had an ...


5

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 that recognize some instances of dead code and remove them. Which patterns to look for is a matter of taste and skill of the tool creator; it's better to be ...


4

The algorithm $B$ is described in a mildly sloppy way. You can look at it as a two-step process: Find suitable $P_k$. Run $P_k$. Now, step 1 can be done one program at a time since the set of all programs is recursively enumerable and we assume that a recursive (and total) elegance tester $\mathrm{ET}$ exists. Note that we use $\mathrm{ET}$ as an oracle. ...


4

Generally, reachability analysis is a goal (determine which points in the code are reachable), whereas symbolic execution is a specific algorithmic technique (a tool for analyzing code). You can use symbolic execution for reachability analysis, or for other goals. Conversely, you can use other algorithms for reachability analysis. Classically, symbolic ...


4

This kind of optimization is more difficult than typical data-flow based transformations, because you need to actually change the branching structure of the control flow graph. You need something more than SSA (or something more than the dataflow graph you get from reaching definitions.) That "something" is the control dependence graph (which relies on ...


4

In terms of processor power the main thing the OS can do is to provide APIs that discourage applications from polling. (And also eliminate all polling inside the kernel and device drivers if there was any.) Then the processor can be put into a low power sleep state whenever there is nothing to do. For every device there needs to be a way for the user ...


4

First compilers may (and often will depending on the optimization level) do transformations far more complex than the one you describe. You should not be concerned about the performance implication of the way you express the increment or the division before being sure that you are using a compiler for which it matters. But there are some other implications....


4

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. Data flow analyses typically have finite-height abstract domains which ensures termination. In general, abstract interpretation does not assume such abstract ...


4

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 analysis, abstract interpretation and type inference are the same thing. While there are many similarities, and maybe more than would expect, given that the three ...


4

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 way for the behavior of if to be well defined when there are overlapping clauses, that doesn't depend on the ordering of the clauses, then you can do what you're ...


4

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 combination to a remote server, you can generate combinations a lot faster than you can submit them. Similarly, the cost of storing the submissions is probably ...


4

The name for this optimization seems to be induction variable elimination, there are some nice slides explaining the idea here.


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