[igouy]

> Except through the backdoor, where language implementors can sometimes tweak libraries to circumvent restrictions.

Which programming language implementations are doing that to your knowledge?

"… Kernels … Toy programs … Synthetic benchmarks … discredited today, usually because the compiler writer and architect can conspire to make the computer appear faster on these stand-in programs than on real applications."

http://benchmarksgame.alioth.debian.org/why-measure-toy-benc...

[rbehrends]

> Which programming language implementations are doing that to your knowledge?

My point here is not that this is being done (I'm generally assuming that language implementors have better things to do than to pollute their standard libraries for a benchmark game); I was making a different point, namely the inability to do algorithmic improvement, and mentioned that possibility for the sake of completeness.

[igouy]

There's been a good deal of play, flex and slop in the interpretation of "use the same algorithm" for some of those tasks.

I think your point is more that "Don't optimize away the work." is antithetical to what we do.

[rbehrends]

All of the benchmark game problems either prescribe using a fixed algorithm or have an obvious optimal asymptotic complexity. The remaining challenge is generally to reduce the constant factor as much as possible.

This is just not what a lot of computationally expensive problems look like in practice. As a simple example, any practical solution for an NP-hard problem will be full of tradeoffs; often you just want something that's good enough and then you get to choose and adjust an algorithm for your particular problem space to find the sweet spot between time complexity and quality of the solution.

The benchmark games also have fairly simple and obvious data structures; most of them just deal with arrays and strings. Real-world problems often require you to make difficult choices about representation (where one is optimal in some situations, another in a different set of situations, but you handle all of them). Example: adjacency matrixes can be represented as bit matrices, integer/float matrices (if edges can have weights), or associate arrays of sets, to name just a few implementation options. Depending on how your graph is structured (sparse vs. dense, connectivity) and what algorithms you require, one or the other can be optimal. Clever choices can make orders of magnitude of difference for performance.

I'll offer you a concrete example: computing the factorial of large numbers basically has three well-known algorithms: (1) naive multiplication, (2) divide-and-conquer, (3) prime decomposition. Each subsequent approach improves performance over its predecessor, but is also increasingly more difficult to implement.

Now, it so happens that this particular problem is well-researched, so you can look it up, but you encounter similar problems all the time where you can't find them on stackoverflow or in the literature. And then you have to consider tradeoffs between the time spent researching better solutions, implementing those better solutions, and the time gained from the increased performance.

[igouy]

You're pushing hard on a wide-open door :-)