Hacker News Reader

Comment by tecleandor | Hacker News Reader

What kind of processes are heavily (or, at least, moderately) impacted by the performance improvement of sorting algorithms?

By my lack of knowledge (and the heat of today :0 ) can't guess what algorithms or processes do lots of sorting behind the scenes.

View on HN

I worked in embedded development and sorting large lists of files was a surprisingly big bottleneck for many of our projects because of the very slow microcontrollers. Even worse we couldn't cache the results because of no memory.

So I was tasked to improve that and I had to write inline assembly to abuse specific cpu instructions that could effectively do much more char comparisons per clock cycle. We ended up not using it because of the usual reasons (not portable, hard to maintain) and our customers had to live with the 20-30s delay when entering a large directory, versus the 5-6s my code achieved.

(Sorry this has little to do with the topic at hand, I don't really know when sorting becomes a problem on a multicore 5ghz cpu)

Sorting is pretty common in the numerics world because a lot of algorithms or techniques can be optimized heavily with sorted inputs. You either get to skip steps or bisect the dataset. Sort of like how most fast fft implementations will run 10-20% faster if you pad vectors to reach a power of 2 length. A typical "preprocess pipeline" would involve splitting vectors into power of 2 sizes or padding them to maximize cache lines, normalizing (and often mapping to an integer domain), and sorting.

Databases would be me suggestion

I might be wrong but I don't think any databases operation is limited by sorting. Even naive quicksort with compiler optimization performs very fast and it is much more faster than reading from disk even with extra log n factor. Maybe things like redis sorted sets could benefit from it, but most implementations of things like these are priority queue.

It’s pretty common for most SQL queries to be reading data that is entirely cached in memory. In these cases, the performance limitations often come from sorts or hash joins.

(Hopefully) gone are the days when DBs are spending the bulk of their time blocking in I/O waiting for spinning disks to spin. They spend a lot of intelligence on keeping active tuples paged-in, and memory sizes are exponentially bigger than they used to be, and intelligent query optimization is going to do as much as it can into memory and then apply join algorithms which... are usually sorts.

And even writes, there's sorting there. An LSM or a B-epsilon-tree, etc. they're doing sorting and ordered key traversals before paging out.

Disk read access access is less and less relevant in normal business application DBs.

It is common at the far ends of scalability spectrum: low end where people use $2 VPS, and high end where big tech can afford to invest a lot in engineering effort to build complex systems that are fine tuned for many levels of memory hierarchy.

Most systems can just add memory until data fits. (of course frequently they still don't, and keep doing more expensive things like having many separate copies for different purposes built in various different expensive projects... Sometimes additionally faux justified by using cloud platforms that charge prohitively for memory)

What isn't impacted by sorting algorithms would be more of the question?

Anything using an ordered data structure -- btrees, red-black tree etc maps and sets, they're doing sorting.

Which, well, databases. Huge one.

3D graphics.

Reply on news.ycombinator.com