[jerven]

If you look at modern JIT compilers such as Truffle-Ruby, then yes it will change algorithms. e.g. changing sort algorithms depending on data size. if the data is small enough it will do a bubblesort on registers, when its big it will do TimSort on heap data etc...[1]

[1]: http://chrisseaton.com/rubytruffle/small-data-structures/

[coldtea]

This example is about the compiler changing between (existing) internal versions of sorting algorithms for language data structures.

Not about changing what algorithms the user coded.

[danielbarla]

Exactly, that's two completely different things. It's akin to a compiler using the famous "switch statement becomes if-else chain if less than 7 items, otherwise lookup table".

The parent posts are referring to macro-level optimisations, where large changes to how a system works are implemented, in order to get massive gains in performance. Picking out the essence of the larger implementation would be a difficult task for a compiler, but more importantly it wouldn't have enough information about the context of the application to make optimisation decisions. Things like: do we need to read from that file each time we need this piece information, or is it a once-off that can be cached? Unless this contextual information is expressed somehow (and it basically never is), only the programmer will be able to make the change.

[jerven]

    def clamp(num, min, max)
      [min, num, max].sort[1]
    end

being turned into

    def  clamp(num, min, max)
       if (num < min)
       {
         if (num < max) 
             return num; 
         else 
             return max;
       }

       if (min < max)
         return min;
      else return max;
   end

Seems to me to be algorithm rewriting. As is superword optimization and partial evaluation. All things that Truffle-Ruby + Graal do today.

[danielbarla]

Sure, and at this level, I would also argue that compilers are as good as humans at optimisation (likely better than almost all, actually). These arguments were constantly going on in the 80s and 90s, where (assembly-enthusiast) people vehemently argued that machines (C compilers) will never optimise things as well as humans. While the argument still exists in some form today, it's certainly died down a lot.

That said, in my own limited experience, everyday optimisation problems tend to exist at a much higher level, on the high-level approach or "what are we doing" level. Perhaps these are "obvious" to some, or below the level of discussion here. But essentially, a compiler can optimise away endlessly at a piece of code, but will never beat code that shouldn't exist in the first place. My comment above was that a compiler has insufficient information to make decisions about what's truly wasteful or useless.

As an example, no compiler today will come up with a Courgette update [1] by itself. And the day it does, I think we can pack up our bags and go home (hopefully in a nice, comfy retirement kind of way).

[1] https://www.chromium.org/developers/design-documents/softwar...

[wolfgke]

> These arguments were constantly going on in the 80s and 90s, where (assembly-enthusiast) people vehemently argued that machines (C compilers) will never optimise things as well as humans.

I still argue this way. But these kinds of optimizations are tedious and time-intensive (thus costly). Also dependent on the architecture, i.e. when some extensions (say new SIMD instructions) are added to the instruction set, the compiler sometimes is able to use them automatically (though typically in a very sub-optimal way), while hand-optimized assembly code has to be rewritten (costly). Also if you port your program to a new CPU architecture (say Intel -> ARM or ARM-A32 -> ARM-A64) hardly anything can be reused. Finally tight hand-optimized code tends to be much harder to add features to than more high-level code (say, C code).

So I believe these vehemently arguing people are right (and have always been). But this does not contradict the fact that in many cases a very suboptimal code generated by the (say C) compiler is often fast enough and C is much more economical to use.

[jerven]

I agree with this, reading it I feel once again the limitations of written communication forms.

However, the top level discussion is about is it worth using an optimizing compiler. Or in my example is it worth using TruffleRuby instead of MRI. I would argue yes because that optimizing compiler gets you 10x more perf per cpu.

[openasocket]

I mean that's basically constant folding on steroids, in this case taking advantage of the fact it knows the array has three elements, and that we only care about entry 1. Which is impressive, really impressive, but it is fundamentally limited. This approach won't ever be able to take your bubble sort implementation and turn it into a quick sort or merge sort. In general I don't think this sort of optimization will lead to asymptotic improvements in runtime, excluding certain edge cases.

Which isn't to say these optimizations aren't important and can lead to very real improvements in speed, I just wouldn't consider it algorithm rewriting in the strictest sense.

[AstralStorm]

The only way to automatically replace nontrivial algorithms safely to provide a formal proof of each one then do a library match.