4 ms·
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
by jez 6y ago
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/why-sorbet-is-fast/
- https://blog.nelhage.com/post/reflections-on-performance/ https://blog.nelhage.com/post/reflections-on-performance/
- tshaddox 6y ago> 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.
- jez 6y agoTo 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.
- moomin 6y agoThere’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...
- deleted 6y ago[deleted]
- dbbk 6y ago> some things simply cannot be done in linear time Boy am I glad I didn't take CS
- pjscott 6y agoFor 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 https://en.wikipedia.org/wiki/Comparison_sort
- renewiltord 6y agoThat's smart. I didn't take Physics and now I can travel faster than EM waves in a vacuum.
- ric2b 6y ago"I'm cool because I never learned some things"
- higerordermap 6y ago"webshit pride"
- dbbk 6y agoIt was a lighthearted comment because the concept went over my head.
- legerdemain 6y agoAnything 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!
- machiaweliczny 6y agoRadix sort exists
- tshaddox 6y agoGood luck using that for a big list of strings!
- lomereiter 6y agoIf 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 https://en.wikipedia.org/wiki/Burstsort)
- codemac 6y agoSure, 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.
- Silhouette 6y agoSure, 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. :-)
- codemac 6y agoHuh? 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.
- toast0 6y agoAt 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.
- wruza 6y agoMaybe they expect you to ask how many elements are out of their place.
- neutronicus 6y agoThe answer is you get stuck maintaining a cache and playing whack a mole with whatever performance metric execs care about this month
- davidmurdoch 6y agoAh, yes, the good ol' Stalin Sort!
- hoseja 6y agoQuasilinear is still fine too.
- mbar84 6y ago> 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".
- TheRealPomax 6y agoTo quote a recent post: quadratic time is good enough to land to production, and bad enough to fail in production.
- dmlittle 6y agoThat'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.