How much power should programmers have?

True or False?

Programmers should not be required or allowed to specify any choice of algorithm or representation when a clearly better choice having equivalent results can be found by analysis, profiling, and consultation of a large knowledge base.

Compilers should for example treat any code describing a bubblesort, once detected, as a call to a better sorting algorithm. If this requires extensive analysis to figure out exactly how to map the bubblesort onto the better sort, then damnit that analysis ought to be done!

The minimal "compiling" tests used by most compilers are only enough to find the most simple and obvious optimizations and bugs. Working through the whole knowledge base may take weeks of time on all of your company's thousand servers, so it should be a background task that runs continuously.

Automated agents distributed with the IDE should participate in a distributed network to gather and share knowledge about code equivalents and optimizations as they are discovered. If any pattern of code existing in the local codebase is proven semantically equivalent to some class of more efficient implementations, by any agent anywhere in the world, then the news ought to come to the local agent via the network, so that next time, and every subsequent time, that local code gets compiled, the compiler will know that it should be compiled as though it were one of those more efficient implementations.

Likewise, any analysis technique which can, statically or dynamically, detect unambiguous bugs (such as 'malloc' being called while a call frame for a destructor is on the stack in C++, or detecting race conditions in threaded code, or detecting a side effecting function used in an "assert", etc) should, once discovered, be distributed over the network and, on receipt and periodically thereafter, run against the local codebase. These tests ought to be running continuously, in round-robin style, in the background whenever any workstation has the IDE or the headless agent running, and the work ought to be shared out to all IDE's and agents accessing the same codebase so as to minimize the total time to complete testing of the whole codebase in its current version.

These tests and optimizations should remain in the knowledgebase until a later test subsumes their functionality, or until expired by local policy or size limits on the local knowledgebase. If expiry becomes common, then they should be redistributed at intervals.

The Daily WTF should be triaged as a source of outrageous examples of wrong or wasteful programming practices, and 'proper' implementations for each correct but horribly-inefficient or wasteful example found there ought to be part of the knowledge base. Likewise, anything there which is clearly a bug no matter what the circumstances, ought to be part of the knowledge base and if static tests can be devised to detect similar bugs, they ought to be.

Is this an extreme position? I think it is, but I also believe it has merit. Why not do this?

Ray

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

Why not do this?

Why not do this?

Because the slope between 'obviously wrong' and 'apparently wrong, but...' is subtle and slippery. An algorithm chosen today may be incorrect for the current codebase/userbase/data flow, but will be way better once the rest of it is done/we get the users we expect/release day comes and we're swamped.

That's a fairly obvious example though. I would argue that the majority of design decisions aren't Daily WTF issues, but trade-offs that are impossible to either measure or evaluate due to changes over time, incomplete data, or simple guesses.

Tools should err away from false positives in cases like these.

Why not do this?

Because the slope between 'obviously wrong' and 'apparently wrong, but...' is subtle and slippery.

And at its bottom, beyond one dev application's worth of bug reports and fixes where the tool was finding false equivalences, lies a better understanding of algorithmic analysis and the knowledge of how to use this capability well. Full steam ahead.

An algorithm chosen today may be incorrect for the current codebase/userbase/data flow, but will be way better once the rest of it is done/we get the users we expect/release day comes and we're swamped.

Conversely, an algorithm which is correct for the current application may be horribly inefficient under the constraints and load of a vastly increased userbase, when currently-unconsidered features are added in a future release, or when the code is reused in a different project. Either way, ongoing analysis, iterative profiling, and bisimulation should reveal the mismatch and savings to be had by substitution, and the better algorithm (whatever it is for the application) should be used, regardless of what the source code says.

.... the majority of design decisions are ... trade-offs that are impossible to either measure or evaluate due to changes over time, incomplete data, or simple guesses.

It's my contention that these trade-offs *are* possible to measure. The programmer may not be able to figure it out when s/he's writing the code. But the profiler can measure the application's performance under different compilations and interpretations and pick the best one. Why should programmers have to do this iteratively and at risk of accidentally introducing new bugs, when the process can be automated?

Tools should err away from false positives in cases like these.

Darn straight. Every last change ought to be justified by profiler output and verified by bisimulation. Make no changes unless you're sure they'll help. But we have reached a point where false negatives (ie, not doing this where it really is needed) are just as bad.

Ray

I don't disagree.

But we have reached a point where false negatives (ie, not doing this where it really is needed) are just as bad.

I do not disagree. I have skepticism that (with modern hardware and software engineering maturity) the process could be automated for a wide enough range of problems to be useful, robust enough to provide enough confidence to be adopted, and run in a short enough time so that the results are applicable to current conditions.

It seems like you'd suffer the practical challenges of genetic algorithms to some exponential power as they interact with other inflection points in the program.

I'd love to see a prototype applied to a small real-world scenario.

Fixing optimized broken code

Say you have a complicated function with many cases, but you got some condition near the outside backwards so your function is provably equivalent to 'return false'. The optimizer proves this, and compiles it as 'return false'. Now that that's happened, you're going to have a hard time debugging. You'd at least need a way to turn the optimizations off for debugging, but then your program would might run so slowly that you can't even reach the bug within your lifetime. So you need something even more complicated: a way to find where the bug might be and only un-optimize parts related to that area of code.

Not seeing the problem.

The minute there's a breakpoint in the code, it is no longer functionally equivalent to the substituted 'return false.' So the substitution would not be done for code with a breakpoint inserted.

So as you debug, you'll single-step, one breakpoint at a time, down to the condition that's bypassing all these complicated cases.

We don't need an automated way to figure out where a semantic bug "might" be and un-optimize parts related to that area; we just need to know where the current breakpoint is and not apply transformations that would eliminate the breakpoint.

Ray

a lot of recompiles?

So you're planning to recompile every time a single step in the debugger is taken in order to make sure that code containing the new breakpoint is not optimized away, and then re-run the recompiled program up to the new breakpoint? It sounds like an incredible amount of trouble given the benefits of the system you outline.

Thousands of them, though not for individual breakpoints.

Yes, lots of recompiling. In fact, the default state of the system, day in and day out, week after week, until many days after the last time someone touched the source code, would be recompiling. Every change someone made would kick off a new recompile of that module, usually triggering an abort of an unfinished previous compile. A compilation checking and taking advantage of everything in the knowledge base could take weeks, but because that turnaround is unacceptable to human developers, there still needs to be a less-optimized object code that is produced in a more normal way in seconds to minutes.

And, to put it bluntly, debuggers have never worked well with highly optimized code; feeding the transformed output to the debugger would be dumb.

I had been thinking of a system based on a conventional compiler doing the same kind of rapid compilation and optimization that we see today as the basis for development, debugging, and early testing. But in this system that would just be the 'first-cut' compilation. The 'supercompiler' or 'superoptimizer' would be a background process continuously working on the code repository and keeping a roomful of headless servers busy, not something that the developers interact with and have to wait for.

The kind of system I'm describing is unrealistic for a development cycle where it has to turn around fast enough to keep human developers productive. Discovery of higher-level transformations to apply is a task will take a lot of compute cycles, and it could take literally weeks of server time after a recompile to get through the whole knowledge base. You simply can't have the developer waiting that long to test and debug, so you still have to have a conventional compiler that produces results in realtime. So this would need to be mainly a phase done after and independent from human involvement with the code. That makes it very important to NOT introduce bugs, and necessary to make before-and-after regression tests part of the process.

Actually applying discovered transformations could be a lot faster, and part of the normal compile cycle. But that relies on local caching of the applicable transformations, and could only work on code that has not been modified and hasn't had its requirements modified since the transformations were found applicable.

I wouldn't expect people to be attempting to breakpoint the transformed code. Even with current compilers, debuggers usually insist on what the GCC suite calls -O0 (optimization minimal, make the code behave in the expected way in the debugger) code. That is an additional requirement which transformed code would very definitely not meet, and the changed requirement would invalidate the transformation.

So if an outer condition is mistaken in such a way that a routine always returns false, the routine may be getting reduced to 'return false' -- but for as long as you're breakpointing in that routine or that module, that cached transformation would not be applicable. So the developer would be looking at the conventional -O0 compiler output in the usual way, and the IDE would be inserting breakpoints by directly manipulating that generated -O0 machine code in the usual way.

Once he fixes the outer condition, recompiles, debugs, and satisfies himself that it's working correctly, the background compiler has time to work on it again. It could be days or weeks before the reanalysis/reoptimization is complete, and the process would have to start over if any *other* changes were made to that routine. Meanwhile the background compiler might produce and check in new versions of the object code (or transformation cache file) for that module, daily or hourly, as it finds new applicable transformations.

Presumably after the fix it won't find any excuse to replace the routine with 'return false'.

Ray

well argued

Now what you're proposing makes a lot more sense to me. Thank you for taking the time to explain.

Matters are rarely so open and shut

One of the classic WTFs is having a hundred variables with slightly different names instead of an array, yet this is just manual loop unrolling, a transformation that current compilers often perform, if rather more cautiously.

Similarly, the tradeoff between lower algorithmic complexity and a smaller constant factor often depends on things outside the purview of the current module, or even the current program. If several million arrays of size 10 or less are to be sorted in the course of a computation, a small-constant-factor O(N^2) algorithm may be a win. In situations such as sorting diacritical mark classes for Unicode normalization, where the maximum normal size of the array is about 4 and the modal size is 1, a fully unrolled sort algorithm is probably the Right Thing.

Debugging such unreasonably smart code will of course be impossible, unless it is decompiled, in which case any bugs will probably vanish.

In these cases (where there

In these cases (where there aren't savings to be had by a transformation) the profiler would not reveal savings to be had by a transformation, so the transformation wouldn't be done. Again, I'm not seeing the problem.

Okay, there would be some ongoing expense in computrons for periodically repeating the profiling, because analysis is *always* going to flag a use of bubblesort as a candidate that needs profiling to justify a transformation (or, in this case, one that doesn't justify a transformation) but that's not an unreasonable cost for use of an algorithm that is flagrantly wrong in 99+ percent of all uses, and needn't be repeated more often than the module containing it is recompiled.

Ray

Programmers should have the power

to choose appropriate tools for the job.

Magic

Your position is quite retro actually. However, there are serious limits to what the compiler can detect and sanely change. Its actually quite crazy to reverse engineer "how" to get "what" to put back in an equivalent and better "how." Why not just start from "what?"

Witness the fall of optimizations papers in our field, while they still exist, they are not pervasive anymore. Instead, we have focused on better abstractions to achieve better performance; e.g., MapReduce vs. magically parallelizing some code. I believe bug checking is headed in the same direction: rather than build tools that can magically verify properties (or at least find probable bugs), we should simply use safer languages and do more testing.

Complexity

It's turtles all the way down. Now the programmer can be sloppy, but all the complexity has moved into your giant distributed analysis knowledge base and how to patch running code. Maybe that's an improvement, but it doesn't seem all that different from what Coverity's doing today, and they're not getting magic results.

Halide

Halide a DSL for image processing which separate the algorithm and the "optimisation recipe"/schedule which could be generated/improved by a compiler (see http://halide-lang.org/ ).

While Halide's performance given in the paper are cool, note that relying on a "magic compiler" has serious drawbacks:
- good luck for debugging
- your performance may vary a lot depending on the compiler versions..

Friendly and open compilers

Part of the motivation here (and in my own work) is that if someone wants to do competitive optimizations for a kernel of non-trivial size, they cannot do it manually. Once you accept automation, I believe an important design point going forward is 1) letting performance specialists extend the compiler and 2) helping algorithm designers iterate over both functional and behavioral specifications.

So, for your two points:

Debugging: separating out the behavioral spec (optimizations) from the functional spec leads to, for functional correctness, relatively trivial semantics. My favorite example here is the SEJITs work where correctness debugging can be done in normal Python. Performance debugging is a different matter, but at least it is now separated and (in my experience), iteration/experimentation time improves.

Performance variability: for the crazy optimizations we put into these systems, good luck doing them by hand for anything beyond a matrix, DSP, etc. library of small kernels. I think it's more of a choice between using these optimizations or not. If you do, the only maintainable way is via automation. A bit of a culture shift is that algorithms will now be implemented as transformations/compilers rather manual kernels, but such coding is becoming normal for parallel hw architects and algorithm designers anyway. I do think there is a performance variability issue, but more due to modern algorithms being finicky across hardware: for example, autotuning outperforms oblivious approaches, but is inherently sensitive.

The best path here, I think,

The best path here, I think, is to design our abstractions so that optimizations are obvious. The problem is analysis, and the solution is to make that easy by construction. Another reasons why optimizations should be automatic is reuse: if code is in an opaque container and you don't want to copy/paste modify, automatic optimizations are our only hope!

Yep!

Clean abstractions and automatic optimizations are essentially what these systems are designed for. They pick functional specification abstractions such that you can more easily reason about and control behavioral abstractions (e.g., parallel, machine, ...), and for similar reasons, the optimizations become tractable.

For example, our new functional specification language is attribute grammars (SSA or local constraints over trees) and the behavioral specification is a sketch of parallel tree traversals to use. Furthermore, we can often easily iterate over new optimizations like new data representations and parallel runtimes by changing code generators rather than the programs. We have done this several times already, and are now looking at a WebCL backend and integrating into Mozilla's Servo browser / Rust lang+runtime. Doing most of this by hand was a non-starter in our first year.

Agree

Abstractions that support optimizations reduce the burden on the compiler (which doesn't need to be especially smart), the users (who can gain useful intuitions about the performance of a system, and thus control performance), and the intermediate developers (who can create libraries, frameworks, metaprograms that optimize in predictable ways).

Of course, for the last one it is important to support optimization orthogonal to abstraction.

Consider the challenges in OO of supporting cross-object optimizations when objects are provided by constructors with possibly cyclic references. Typically, this results in a lot of unnecessary dynamic dispatch because the object classes are statically known, plus a lot of unnecessary allocation time, GC burden, synchronization burden, plus some non-essential uses of state for the cycles.

In 2008 I chose to address that issue for my actors model at the time (this is before I developed RDP), and I developed a composable, structural `construct { ... }` abstraction for creating a group of actors. Cyclic references were handled by an ability to declare an actor name before assigning it (logic variable style, but only within the construction). The construct was also a nice place to add other annotations. With `construct`, I could allocate and GC at level of the whole group of objects, specialize the group to work together, do quite a bit of inlining and dead-code elimination, optimize the synchronization/parallelism (e.g. combine mailboxes where concurrency is not useful), etc. - all without relying on an "intelligent" compiler. (`construct` was also composable). (I could also emit better static warnings or errors.)

Control over performance is rarely contradictory to efficiency.

The problem my team is

The problem my team is working on, which is in the context of a MapReduce systems, is that these optimizations could make significant reductions in IO, the kind that increase performance by N rather than .N. So they are very important...so important that they have to be very reliable and predictable from the programmer's point of view. The idea that a compiler will somehow be good enough to reverse engineer declarative properties from general purpose code is a bit scary in that context!

I think it still makes sense

I think it still makes sense in the context of a mapreduce system. For example, if a programmer tags a point as @incremental, the compiler knows to check point. Likewise, if the incrementality is observable, such as some destructive update, the compiler should reject the functional spec (the update) as incorrect wrt the intended optimization. If the programmer is lucky, it suggests something like adding a copy-on-write optimization.

I've been thinking about a few ways to extend our system to handle high performance graph algorithm optimizations -- the same philosophy seems to apply. Specify the functional algorithm and map down to ideas like duplication and different communication patterns.

There are many

There are many general-purpose optimizations that can make algorithmic level differences. Tail calls are a classic example. But, regardless of whether or not the abstractions are general purpose, I fully agree with a sentiment that optimizations should be stable, robust, reliable, predictable.

Fragile optimization is worse than no optimization. With unpredictable performance, perceptive programmers learn fear of exploratory update.

horrible, ruinous, classist, and other ugly words

You lost me at this point:

Programmers should not be required or allowed

Who are "programmers", in this context, and who and what are these people with such power over them? Can we get clear about the caste hierarchy you are proposing and the socio-economic order you are imagining, since it seems to be central to your question about tool design.

You are led to such odd formulations as:

Compilers should for example treat any code describing a bubblesort, once detected, as a call to a better sorting algorithm.

I'd want to ask which compilers you are talking about and what their use is to understand that "should" but you are already off into so many social engineering assumptions about "programmers" and the authorities over them that it's hard to formulate that question.

Is this an extreme position?

Seems crypto-fascistic to me.

Crypto-fascist

I tried several times to write a response, but couldn't find appropriate words. Thank you for providing a few.

I would love to support developers in programming with partial specifications with hard and soft constraints and rich types, i.e. so they can ask for a sort and say they care about speed or stability. I wouldn't even mind an IDE that provides suggestions, stylistic hints, lint-style warnings, requests for documentation.

I believe programming is a rich, social medium, especially for live programming in open, federated systems - at which point I can no longer locate the fine line between PX and UX. These days we program with a grand canyon between the PX and UX. We throw apps across the gap, and many flop. Why? Live open system programming is just down the road.

Programmers are the baddies here.


At my high school computer center the kids liked to write video game programs. For a while some of the authors of these games included in the programs a list of which other kids were or weren't allowed to play the games. This practice let the game authors feel powerful and important...
--- Computer Science Logo Style, Volume 3, Brian Harvey.

Who are "programmers", in this context, and who and what are these people with such power over them? Can we get clear about the caste hierarchy you are proposing and the socio-economic order you are imagining, since it seems to be central to your question about tool design.

Programmers create the hierarchy - no two ways about it - these general purpose computing machines aren't restricting themselves.


Either we all live in a decent world or nobody does.
--- George Orwell (Eric Arthur Blair)

no worse than not being allowed to make mutations.

Yeah, that was deliberately provocative wording.

But consider the position that programmers should not be allowed to use variables without declaring their type. Or the position of Wirth (in Pascal) that programmers should not be permitted to make constant declarations after variable declarations. Or the position of the developer of Aha! that programmers should not be allowed to use recursion because it is confusing. Or the position of the developers of Haskell that programmers should not be allowed to use mutation. Or the position of the Java design that programmers are not allowed to write free routines (eg, routines which are not methods on some object).

It seems to me that MOST of what we talk about in programming language theory is about what kind of handcuffs the programmer has to wear, or what should be forbidden, in order to take advantage of some type of abstraction or avoid some type of opportunity to become confused.

What I wish to forbid doesn't prevent programmers from writing any darn code they want and seeing the results as though that code had run, so it's actually less constraining than any of the above. What I want to do could be expressed less provocatively as abstracting implementation from performance.

You've seen math papers where people prove something is computable by using a construction which is one of the most horribly non-performant algorithms possible to compute it, because that algorithm is amenable to some very simple proof technique? Actually, bubblesort is a good example of that; you can unambiguously prove progress is being made with every swap and that it does not terminate until the sequence is completely sorted, and that there is a final state of being completely sorted, and that the algorithm halts once that state is reached.

I want programmers to be able to do the same thing; write simple code whose correctness is easy to verify, or build abstractions on top of other abstractions indefinitely without regard to compounding inefficiencies or redundant operations in each abstraction layer, and let something else worry about how to make it run efficiently. What we give up is the power to specify any algorithm worse than some equivalent algorithm the system can find.

Ray

Compilers should for example

Compilers should for example treat any code describing a bubblesort, once detected, as a call to a better sorting algorithm.

What we give up is the power to specify any algorithm worse than some equivalent algorithm the system can find.

The "goodness" of algorithms or implementations is multidimensional. Bubblesort is very nice on nearly-sorted sequences, for example. Or, maybe the code is only called on very short vectors, and I$ is at a premium. I can already imagine all the introsorts of the world compiling to broken code because introsort is "better" than heapsort.

A sufficiently smart compiler, given enough profiling and machine data, may be able to make the right call in such situations. However, these rewrites have huge effects, and I don't want to depend on the compiler to do the right thing. What if rewrites fire when they shouldn't? What if a seemingly trivial modification blocks a key rewrite, now affecting the program's big-O complexity? Really clever compilers have interesting failure modes.

Ends and Means

Your goal is to separate abstraction from performance. Admirable. But the approach you proposed for achieving this goal is horrible.

Constraints like "don't use mutable variables" or "always declare your variables before using them" are simple, predictable, easy to learn and avoid. They aren't handcuffs... more like guard rails on a bridge to keep developers from falling into the Turing tar pit.

What you described in the OP is building an algorithm then being told, "no, this code sucks according to this ancient DailyWTF" or "hah! ignorant human! I found a better algorithm for this just two minutes ago! You're not allowed to express this!" is not analogous. It is not simple, not predictable, and it places a very large burden on both the language developer and the user.

You might want to consider an approach closer to Goguen's BOBJ, where every algorithm is considered an executable specification that can be observed by other algorithms. (You'll need to rebuild such a system from scratch; BOBJ died with Goguen due to lack of any distribution license.)

Edit: I also agree with pkhuong's point. Quality of an algorithm is contextual and multidimensional. Optimizations must be predictable.

Specifications transformed code must meet are good.

First of all, I'll agree with you that 'optimization' is multidimensional. Usually we want speed, but sometimes and for some routines, other constraints are important too. Usually we want something other than bubblesort but if we're really sorting sets of under ten objects it may be okay.

But I think I have to question the idea that such things should remain unstated. If we have facts that affect the search for optimizations, such as "this set has less than ten objects" wouldn't it be better to assert them? That way we'll at least know immediately if they are in fact, true, and we'll know immediately if they stop being true.

And if we have constraints that affect the solution space, such as "this must be done without allocating," shouldn't we state them explicitly anyway to prevent someone from coming along later and fixing our not-really-broken program in a way that may seem "obvious" to someone who isn't familiar with the broader context and doesn't know about the constraint?

I don't have a problem with programmers needing to add assertions and constraints to source code if they need tight control of how the optimizer works. That boils down to saying true things about the problem you're trying to solve. Unlike most optimization techniques, as long as you're trying to solve the same problem, THAT code would remain valid when you move to a different OS, a different hardware, etc. True statements about the problem you're trying to solve *SHOULD* be a feature of any program. In fact that's a valuable refinement of the basic idea.

As for a tiny change affecting the big-O performance of the code because some optimization no longer applies, I'm going to shrug. The big-O performance would certainly be no worse than the performance of the algorithm your code actually expresses. What we have now is the situation where it's also certainly no better, so I'm not seeing the downside.

But there's another side to the performance-changing thing. It's been my experience in real-world programming that sometimes when you have sweated bullets developing a very efficient representation and especially-clever algorithm for something, management at some later time mandates that you add a conceptually "minor" feature which invalidates the whole design and requires a major rewrite using a different set of algorithms which will have strictly worse performance. Further, sometimes they are absolutely right to do so if the feature being added really is key to the way a large group of users want to work.

It would be a resolution devoutly to be wished, and might actually happen sometimes, that such a conceptually minor added feature might actually *be* minor in terms of effort, in a system where optimization searches are automatic. You add some feature in a straightforward way, to code that you wrote in a straightforward way in the first place; the background compiler discovers that some particular set of transformations no longer applies because the problem space has changed; and performance drops, for exactly the same reasons it would have dropped if you had sweated bullets over both the extra-clever optimized algorithm and the reimplementation. I call this a net win for programmer productivity.

Of course this also points up the need for optimization reports. They're a good idea regardless. You have to have feedback if you want to improve something. But aside from that, if performance drops you have to be able to find out why. If you didn't sweat bullets over that extra-clever algorithm you may not know how the output that your program specified is actually being produced. You may not know why it has to be produced in a different and slower way after the change. So you'll need an optimization report that shows what transformations were found to apply before and after the change, and the estimated/measured savings from each transformation, to enable you to make an informed choice.

Ray

Programs are not

Programs are not mathematical specifications for behavior. The behavior, correctness, and the requirements for a program are determined, in practice, by context and iterative refinement. Among those empirical observations is performance. A significant change in efficiency or latency can turn a working program into a broken one.

It is unreasonable to assume the programs are generally static, that we have arbitrary time available to search for optimizations. Where are you accounting for the performance of the search? In many cases - e.g. dynamic programs, scripts, REPLs - one must consider the compilation time to effectively be part of the running time for a program.

Today, performance is typically approximated from operational semantics (a poor approximation of CPU/Cache behavior). However, it is entirely feasible to model costs and cost-constraints in a type-system or in a constructive logic. With some care, this would allow developers to model the optimization search when they want one. And that would be my general recommendation: if I want ad-hoc search for optimizations, I'll model it (probably by sending some code to a compilation service).

Programmers need optimizations they can depend on, ideally which can be achieved in a time relative to the size of the program.

If you're interested in a world where programs may vary between O(N!*N) and O(N*lg(N)) based on the whims of an optimizer, then try it for yourself before imagining it would be reasonable for anyone else.

Wups. Sorry, I think I expressed that in a misleading way.

What you described in the OP is building an algorithm then being told, "no, this code sucks according to this ancient DailyWTF" or "hah! ignorant human! I found a better algorithm for this just two minutes ago! You're not allowed to express this!" is not analogous. It is not simple, not predictable ....

Ah. Apologies for my lack of clarity earlier, but that is a misunderstanding of what I intended. I did not envision a system in which source code would or should be rejected for inefficiency. My goal is that code describing an algorithm to produce some result should be treated as specifying the result but not the algorithm, and that optimizations and transformations very much more aggressive than we now perform should be done. If a compiler can find a better way to produce that result using a different algorithm, then it should do so.

Programmer used bogo-sort (an O(N x N!) sort) and also allocates space every iteration? Yeah, right, don't mess with the source code or reject the program or anything radical like that, but produce an executable that runs in O(N Log(N)) without allocating.

Programmer wrote Fibonacci the easy way using a branching recursion with expected O(exp(N)) running time? Yeah, right, don't bother him about it, but produce an executable that runs in O(N) or less and doesn't allocate stack frames.

Programmer wants to sort lists composed of CONS cells, which his code malloc's individually? Um, fine, whatever, but see if you can't convert big parts of the program, and maybe the whole thing, to a cdr-coded representation so you can use arrays for all the sequences in the executable.

Etc.

I may not actually be sane, but even I wouldn't try to hold programmers or source code to constraints that change every two minutes. I'd rather lick the third rail than incur that much wrath and cause that much frustration.

Ray

Programmer used bogo-sort

Programmer used bogo-sort (an O(N x N!) sort) and also allocates space every iteration? Yeah, right, don't mess with the source code or reject the program or anything radical like that, but produce an executable that runs in O(N Log(N)) without allocating.

The problem is when a later version replaces the bogosort with a smarter algorithm, say, a selection sort. "Things will be much faster now," thinks the programmer. And yet, no, the improved version actually compiles to asymptotically slower code because the (n lg n) transform doesn't match anymore. She stares at the results, thanks coworkers for including mandatory performance tests, wastes the whole day trying to understand what's going on, and rightfully decides that a tool with such a complex performance model isn't fit for productive work.

I think this simply implies

I think this scenario is true, but simply implies that performance and behavioural constraints need to be declared and verified by a language. If you need a polymorphic function specialized for performance reasons, there should exist a language keyword to declare that requirement.

If you expect O(log n) time complexity, it'd be pretty handy to be able to declare that the compiler must check and preserve that property.

Behaviors and Strategies

I think the essence of your idea is that programmers don't specify algorithms. Instead, they specify behaviors along with a (perhaps inefficient) proof those behaviors can be accomplished, coupled together in the form of an algorithm. This is NOT a new idea. The usual trouble with this technique is that algorithms also tend to capture a lot of semantic noise when encoding the behavior, which leads to accidental complexity, e.g. requiring stronger constraints on ordering than the algorithm really needs, or exposing partial failure modes (exceptions, failures, bugs) that are not essential, probably not even desirable. This complexity, caused by over-specification, can hinder many optimizations one might wish to pursue.

A more successful approach has been to formally distinguish the behavior specification (i.e. what must hold true for correct behavior) from a recommended strategy. The algorithm, then, is not the source of ground-truth for observed behavior; it is, instead, a proof that a specification can be fulfilled, and serves as a reference implementation (in case nothing better has been discovered). Alternatively, we can reverse this so we provide the proof then extract the algorithm.

If we constrain against performance properties, make them explicit in the specification or type, then we have a feasible approach to support what you are imagining. Linear types provide a basic way to constrain performance properties - e.g. by requiring developers to statically record and report the performance of each subprogram, no ability to "drop" this information or hide it.

This technique still has its weaknesses because we don't always know what resources we'll care about in a given context. For example, a proof that some sort occurs in finite time and space is not the same as proving it occurs in-place or that it is cache-local. I.e. this technique is still subject to an "expression problem" for discovering appropriate proofs.

Some people, especially Adam Chlipala and William Cook, have explored ways to compose proofs and strategies in a more open or traits-like manner. Cook's work is on Enso, and Chilipala's work was part of his Bedrock effort (the automation of tactics). Joseph Goguen worked on a similar concept from the rewriting community, with BOBJ. Juergen Schmidhuber wants to create a self-optimizing machine based on the concept.

I think, if you wish to pursue your ideas, you should learn what has already been done and try to understand why we aren't using it yet. I think such techniques hold a great deal of promise, but we're still building the tools to build the tools to build the tools. There's a long road ahead, fraught with unshaven yaks.

I think the essence of your

I think the essence of your idea is that programmers don't specify algorithms. Instead, they specify behaviors along with a (perhaps inefficient) proof those behaviors can be accomplished, coupled together in the form of an algorithm.

That's it exactly.

The usual trouble with this technique is that algorithms also tend to capture a lot of semantic noise when encoding the behavior, which leads to accidental complexity, e.g. requiring stronger constraints on ordering than the algorithm really needs, or exposing partial failure modes (exceptions, failures, bugs) that are not essential, probably not even desirable.

Yes. I didn't know that the beautifully appropriate phrases "semantic noise" and "accidental complexity" were in fact terms of art that I could use to find prior work, but I have been muttering exactly those phrases (and also "algorithmic overspecification") myself of late as I try to develop general programming constructs and primitives that minimize them. Minimizing overspecification been the main informing design principle of what I'm calling the "general" library for the Lisp dialect I'm working on.

It turns out that when overspecification is minimized a lot of distinctions I'm accustomed to disappear, and specifying those distinctions is now something I see as a thing actively to be avoided. Instead, the optimizer/profiler should find which implementation to use in which circumstance.

The idea of 'sequence' is independent of whether it is implementated as a list or array. The idea of 'dictionary' is independent of whether it is implemented using trees, arrays, hash tables, environments, objects/records with named fields, etc. The idea of 'text' subsumes both strings and characters (which can also be stated as "characters are just really short strings").

All the sets of operations our supposedly "different" types support are really just interfaces to those very few fundamental ideas, not fundamentally different things. All the different "types" that type theory relies on, are just dictionaries in which some value is keyed by the symbol '$type'.

Thank you for the pointers, although it looks like I'm not going to be able to get anything useful about BOBJ -- all the materials disappeared from the web when Goguen passed away and his webspace was deleted.

Ray

Oh, please, no

To be honest, I think that identifying potentially inefficient algorithms and reporting them to the programmer as (overridable) warnings is a much better idea than silently substituting different `optimized' algorithms. These warnings can go in with the static-analysis warnings, so they don't break regular builds. For a start, this keeps the performance model tractable: I can look at the code and understand how fast it's going to go without worrying about what the hyperintelligent compiler will do next week.

Not being able to predict performance has troublesome security implications. Performance is directly observable through the timing side-channel; there are side-channels too, such as cache behaviour, power consumption, and E-M emission. These side-channels leak information about the operands to algorithms -- operands which properly ought to be kept secret. Algorithms which have good side-channel behaviour often sacrifice some performance. The last thing I want is some overly clever compiler `optimizing' my careful time-invariant elliptic-curve point multiply to reintroduce a trivial timing attack.

Also, this enormous knowledge base of optimizations -- we're going to have to keep a complete history of its evolution. Otherwise we lose reproducibility of builds, and that ain't nice.

Because it is hard

There are good arguments for more aggressive optimizations. But they're difficult to implement. Buzzwords such as "distributed network", "knowledge base" and "agent" are not helpful without specifics.

If someone wanted to work on this, a good start would be to look at JavaScript on slow web pages, recognize linear searches, and convert them to better algorithms. Javascript is widely used by programmers who have no theoretical background, so it's a good place to look for inefficient code. There's probably a commercial market for such a product.

wrong question

Choices of algorithm and data structure almost never matter in practice. When they matter, the sum of human knowledge is tiny.

No compiler in this area is needed. In light of the unobtanium-ish qualities of it.....