DeepMind AI Develops Efficient Sorting Algorithms

[Tom.G]

https://arstechnica.com/science/202...ps-a-system-that-writes-efficient-algorithms/

 

[.Scott]

https://arstechnica.com/science/202...ps-a-system-that-writes-efficient-algorithms/

Some historical perspective:

In "modern" times, programmers sort using published libraries. But there was a time, just 30+ years ago, when people wrote their own sorts (for example). They were using machines with very limited memory resources and processor power. So, in resource-critical cases, development time was spent identifying ideal solutions - and it was common to go down to the assembly/register level looking for the optimum method to apply for a that particular project.

What "deepmind" has done is to find the most optimal sort solutions for cases where there are a small number of elements to be sorted (2 through 8) and when "optimal" is defined as minimal execution time with ample code memory resources. It's an exercise I performed for element counts of 2 through 6 when I was working out the details of that Zig Zag sort (same example).

But I haven't used my own sort in decades. It rarely makes any sense anymore.

However, there is definitely an advantage to be had with this deepmind result. With modern compiler and linker optimization techniques, a library sort can be created using this result that can select sort code that is as specifically optimized as the code that was hand-selected decades ago. So if you are sorting exactly 7 elements, it will replace your "sort(7,data,comp(&a,&b));" with a more customized "sort_7(data,comp(&a,&b));".
Coding at the Assembly level was once a common optimization practice. A key goal of this kind of optimization is to make assembly as an optimization method completely unnecessary.

 

[Vanadium 50]

I can't possibly be old enough to re,member the times @.Scott is talking about - yet I do.

I "real life" - i.e. when someone is paying you to sort something. (or write a program to sort something) you typically have one of two problems: either the whole thing is unsorted, or it is mostly sortted with a few unsorted elements at the end.

These cases were generally identifiable "by hand" and if it made sense treated accordingly. Rareky did it make sense to try and go beyond this - the amount of time it would take to study tyhe situation to pick the right algorithm was usually large compared to the time difference between various algorithms.

It does no good to spend an hour trying to speed up a sort by 30 minutes. It may not even make sense to hire a team of programmers to speed up a sort by 30 minutes compared to just getting a faster computer.

 

[PeterDonis]

if you are sorting exactly 7 elements

How often will the number of elements being sorted be known at compile time?

 

[Baluncore]

Coding at the Assembly level was once a common optimization practice.

I am writing assembly code at the moment because I demand time critical control of external signals while all interrupts are disabled, and exceptions impossible.

An optimising compiler can get close enough to perfection for most applications.
I do notice with these AI generated sorts that it takes more time to prepare to save a cycle than will ever be saved by the slightly improved process. KISS.

 

[Vanadium 50]

How often will the number of elements being sorted be known at compile time?

Sometimes it is very, very stable. The number of hours in a day hasn't changed since the invention of computers. The number of states in the US has been stable for more than half a century. Even the number of schools in the Big Ten is constant on the time scale of compilimg.

But....

The most likely spot to find it is in a divide-and-conquer algorithm whrer you break N items into groups of M. N can vary but M can stay constant.

 

[.Scott]

How often will the number of elements being sorted be known at compile time?

An easy example that answers your question, but not the general point:
You decide that you will get sufficiently reliable results if you take the median value of 7 samples.
So you sort seven results and take the middle value.

But, if optimization was that important, you could optimize the entire 7-sample median algorithm.

 

[.Scott]

It does no good to spend an hour trying to speed up a sort by 30 minutes. It may not even make sense to hire a team of programmers to speed up a sort by 30 minutes compared to just getting a faster computer.

And sometimes it does.
So I need the median value from a list of 256 integer values. The total amount of time spent developing, documenting, and implementing the final optimized algorithm is several man-weeks - and the final result is very fast but only accurate enough (perfect over 99% of the time).
The un-optimized version took about 300 usec. The optimized version takes a couple of usec.
But it gets executed 20 times per second in a consumer automobile radar unit and 300usec was way over its time budget.