[orlp]

I am not cynical about the research itself, I am critical of claims such as "new sorting algorithm uncovered", "up to 70% faster", or "first change in a decade". The research is good. The achieved results are massively inflated.

What they achieved: automatically generated good code.

What they claim: automatically generated code that is revolutionary and an improvement on the state of the art.

And as another commenter noted, superoptimizers are also already a thing: https://en.wikipedia.org/wiki/Superoptimization

There's also automatic searching being done on faster sorting networks that actually recently produced better than state of the art sorting networks: https://github.com/bertdobbelaere/SorterHunter

[saiojd]

While I agree that the claims are hyperbolic, I think you are approaching this paper from the point of view of someone who knows a lot about sorting. Because of this, its normal that the claims of these guys who probably don't know much about it are grating for you.

But, at its core, this is really a RL paper. The objective is to see how far a generic approach can work while understanding as little as possible about the actual domain. After AlphaGo exceeded expectations, the question becomes: "What else can RL do, and can it do anything actually useful?", and this paper seems to suggest that it can optimize code pretty well! I'm really not sure they are self-aggrandizing in terms of impact. The impact of an approach like this could potentially be very large (although I'm not saying that it actually is, I don't know enough).

[bloppe]

Sorting is not a niche topic. Anybody who majored in CS (which is a ton of people these days) will read the abstract and most of the paper thinking "Wow, I can't believe they discovered something better than O(N log N)" because that's usually what people mean when they say "better sorting algorithm". What they discovered here is effectively a new compiler optimization. They should present it as such instead of calling it a new sorting algorithm.

But ya, discovering a new compiler optimization automatically is kinda cool.

[saiojd]

I see your point. I just went over the abstract again and I totally agree.

[elcomet]

I hope people majoring in CS will not think that, as they learned that n log n is the theorically best complexity for a sort algorithm. They will rather think that they found an algorithm with better constants in front of n log n.

[Zacharias030]

true that

[recursive]

70% better than O(N log N) is still O(N log N).

[ummonk]

It's 70% better than O(1). The algorithms it found are for sort3, sort4, and sort5, which were poorly optimized in LLVM's libc++.

[pclmulqdq]

It may have also laundered those from open-source code that wanted to optimize sort3, sort4, and sort5.

[qumeric]

Tbh people who majored in CS are supposed to know that it was proven long ago that better than O(N log N) sorting (in general case) is impossible.

[Dylan16807]

> because that's usually what people mean when they say "better sorting algorithm"

Is it really? I've heard of a few "better sorting algorithms" and it's never meant that in my experience.

[cubefox]

When people say "sorting algorithm" they mean something like bubble sort or merge sort.

[rep_movsd]

Anyone who does any basic algorithmic CS stuff would have been exposed to sorting algorithms, their variations, sorting networks and so on.

There are already superoptimizers who use genetic algorithms to find the most optimal code sequence for small easily verifiable tasks. That is also a form of reinforcement learning in a way

[bamboozled]

When one has a big fuck off hammer, everything becomes a nail. Seems to apply to ML too.

[touisteur]

I somehow agree that I'd be far more impressed by something that would find optimal or even just better sorting (or selection) networks for sizes higher than 17 (last time I looked at SOTA).

[orlp]

Please check my edit right as you commented :)

[touisteur]

Oh very, very cool thanks a bunch.

Edit: compiling the hunter code Right Away and hopefully in some weeks I'll have better networks. Selection networks are even harder to find optimizers for, hopefully one can hack this new thing to get some.

[runsWphotons]

how automatically generated was the code that wrote the code