Comment by jez | Hacker News Reader

Comment by jez | Hacker News Reader

In posts talking about how someone made something fast, I see the same idea repeat time after time: it has linear time complexity, has great cache locality, and saturates all available processors.

It's annoying to me how much time I had to spend outside of school before I realized that this is the real recipe for fast code. In particular, even code that is nominally O(n^2) by standard measures is still a dis-economy of scale: the bigger the problem the slower it gets. In school, there's a premium given for finding a polynomial-time solution, but in practice every job where I've been tasked with making something fast, only linear time complexity was good enough.

In practice these linear algorithms tend to also be completely data parallel and have great cache locality. Not only do these properties make the code fast the second you harness them, but then tend to be exceedingly simple architectures to maintain over time.

For some other reading I really like on software performance in the real world:

- https://blog.nelhage.com/post/why-sorbet-is-fast/

- https://blog.nelhage.com/post/reflections-on-performance/

> but in practice every job where I've been tasked with making something fast, only linear time complexity was good enough.

But of course we remember from our CS school that some things simply cannot be done in linear time. I’m not sure what happens when your employer tells you to sort a big list and insists that only linear time complexity is good enough.

To that I find that the answer is usually: find ways to avoid needing to sort the list! This is more viable for many problems than you might otherwise think.

There’s also vastly faster ways of sorting lists of bounded numbers (or tuples), the most linear being: cut straws of the exact right length labelled with an Id, bang them on a table so the ends without the ids all line up, read the ids back in order.

I only said it took linear time, I didn’t say it was fast...

> some things simply cannot be done in linear time

Boy am I glad I didn't take CS

For example, a comparison-based sort can't do better than O(n log n) time in general. More information here:

https://en.wikipedia.org/wiki/Comparison_sort

That's smart. I didn't take Physics and now I can travel faster than EM waves in a vacuum.

"I'm cool because I never learned some things"

"webshit pride"

It was a lighthearted comment because the concept went over my head.

Anything you didn't learn in Christian Science courses at university, you can find and learn more at your local Christian Science Reading Room! Most cities and towns in the USA have one, and even many airports for people on the go. If you're flying through SFO, you can visit the one in terminal 2!

Radix sort exists

Good luck using that for a big list of strings!

If we are talking about linear in number of characters, an easy answer is building a trie and traversing it left to right. (Cache-friendly variation: https://en.wikipedia.org/wiki/Burstsort)

Sure, but it has the classic problems of the memory/storage required for the sort (minimum double all your keys), and a classic math issue relating to it's speed being O(k*N) and since k = number of bits/digits, N can only be as large as the number of bits/digits allow for.

This means quicksort and the like end up faster in practice for any "sort this list" operations. Radix/bucket sorting can be SUPER awesome when what you need is a single level of bucketing at all rather than exact order.

Sure, but it has the classic problems of the memory/storage required for the sort

No problem, just create a file of the necessary size on disk if you don't have enough RAM available.

Today's comment was brought to you by a large number and the letters big-O and c... where c, a large number, is the hidden constant of proportionality waiting to bite you every time you mention big-O. :-)

Huh?

If we're reading from disk, then we DEFINITELY don't want radix, as then it's almost guaranteed that all time will be dominated by loading pages rather than cpu cache locality being leveraged by linear time algorithms - which is what this entire discussion is about.

He was sarcastic

Radix sort is still O(n logn). More precisely, it's O(w * n) where w is the size in bits of the data being sorted, but then it follows that w scales with log n, since n distinct items requires log n bits and hence you arrive at n logn.

At one job we used to joke "i don't care if it's right, as long as it's fast"

Of course, it was only half a joke. For some pages, we really did want data quickly, so we were willing to accept stale data or somewhat inaccurate data, it that helped. For other pages/sections, accuracy was more important so caching wasn't possible or invalidation was critical.

But product design is always about tradeoffs between what features are desirable, what features are possible, what features are easy to build, and how features interact. Features that are possible but not easy to build can sometimes be replaced with features that are easy to build and close enough.

Maybe they expect you to ask how many elements are out of their place.

The answer is you get stuck maintaining a cache and playing whack a mole with whatever performance metric execs care about this month

Ah, yes, the good ol' Stalin Sort!

> in practice every job where I've been tasked with making something fast, only linear time complexity was good enough.

Presumably you weren't tasked with making something fast, were linear time complexity was overkill. In other words, quadratic complexity may have been fine in many cases, but you weren't tasked to make those fast.

I'm not saying you claimed otherwise, but somebody might misread you as saying "in practice, only linear time complexity is ever good enough".

To quote a recent post: quadratic time is good enough to land to production, and bad enough to fail in production.

That's a pretty good quote!

It's also worth noting that if your size is bounded a simpler quadratic algorithm might be more maintainable overtime than a linear one (if it's easier to grok). Say max(n) = 25, it doesn't really matter if it's linear (say 4N = 100) or quadratic (N^2 = 625). In practice they're both fast enough (even though one is 6x faster) and not worth optimizing but if it can grown unbounded that's when the BigO runtimes start to matter. For something like ESBuild your input size grows larger and larger as your codebase increases and that's when you start to see slowness creep in.

Quasilinear is still fine too.

Reply on news.ycombinator.com