8 ms·
Dawson's law strikes again! > O(n^2) is the sweet spot of badly scaling algorithms: fast enough to make it into production, but slow enough to make things fall
by daniel-thompson 3y ago
Dawson's law strikes again!
> O(n^2) is the sweet spot of badly scaling algorithms: fast enough to make it into production, but slow enough to make things fall down once it gets there.
https://randomascii.wordpress.com/2021/02/16/arranging-invisible-icons-in-quadratic-time/ https://randomascii.wordpress.com/2021/02/16/arranging-invis...
- 908B64B197 3y agoDiscoveries and analysis like this blog post and the parent show the difference between programmers and engineers.
- IshKebab 3y agoTrue but I think the real cause of this is surely that C makes it too hard to use a sorting library that someone competent has written. I would not be surprised if the author was fully aware of the N^2 complexity but opted for a simpler implementation anyway.
- pjc50 3y agoqsort() not good enough for you? (More realistically, below people are discussing that in the kernel environment the set of standard or third party library available may be unavoidably limited)
- jart 3y agoqsort() is pretty slow if you're sorting something like long[]. In that case, radix sort goes 5x faster and vectorized quicksort goes 10x faster. If you're sorting int[] then vectorized quicksort goes 25x faster than qsort(). Nothing goes faster. The issue is it's a big ugly c++ monstrosity that's a huge pain to compile.
- rcxdude 3y agoThat's fair if the constant factor is relevant, but if bubble sort is terminating in any reasonable timescale then the difference between qsort, C++ std::sort, and a custom implementation is really not a factor.
- jart 3y agoPeople who don't compute much data don't need computer science.
- paulddraper 3y agoBut if you're comparing to bubblesort.....
- nice2meetu 3y agoThere is a quirk (almost a bug?) in FreeBSD's qsort where it will switch to insertsort for the whole array under certain conditions, which we hit in production given how our data was arranged. (I think this was the check) https://github.com/freebsd/freebsd-src/blob/main/lib/libc/stdlib/qsort.c#L171 https://github.com/freebsd/freebsd-src/blob/main/lib/libc/st...
- stefan_ 3y agoI like how someone felt the need to write out insertion sort in some 4 line code golf challenge in the midst of qsort. This right here is why no one wants to deal with C anymore.
- erk__ 3y agoDid a bit of digging and found that there used to be a comment for why it was done, but it got removed [0] when they switched to the implementation from Bentley & McIlroy's "engineering a sort function" [1] around 1992. [0]: https://github.com/weiss/original-bsd/commit/d3fcf71e0db57cb346606f3e100c17a565b1cc2f#diff-80cbaaf17a9c3baf31292416f97d13837515bdc13c94eedc285a79504409c708L167-L181 https://github.com/weiss/original-bsd/commit/d3fcf71e0db57cb... [1]: https://cs.fit.edu/~pkc/classes/writing/papers/bentley93engineering.pdf https://cs.fit.edu/~pkc/classes/writing/papers/bentley93engi...
- JdeBP 3y agoNonetheless, qsort() is available in libkern.
- canucker2016 3y agoNot at the time that the bubble-sort code was used though. see https://news.ycombinator.com/item?id=36005209 https://news.ycombinator.com/item?id=36005209
- JdeBP 3y agoYou mean written. It's been available for many of the years that it has been used. (-:
- IshKebab 3y agoNo. In most languages sorting a container is `foo.sort()` or something similar. `qsort()` is much more faff. I mean, clearly it wasn't good enough otherwise they would have used it, no? Perhaps integrating it was a huge faff.
- JohnFen 3y ago> that C makes it too hard to use a sorting library that someone competent has written. This makes no sense to me. What about C makes it hard to use a good library?
- jjoonathan 3y agoC arrays suck on the best of days and qsort requires that you understand function pointers and types which are some of the hairiest C syntax in common use. The C Clockwise Spiral rule is truly special. It's easy to lose sight of the climb once you're at the top.
- JohnFen 3y agoWell, we could debate this, but it's all irrelevant to the assertion that C makes it hard to use good libraries.
- jjoonathan 3y agoOh, right, I forgot that C's library/package management situation sucks so hard that makes the awful syntax look like a comparatively small problem.
- JohnFen 3y agoThis actually made me laugh out loud. Yes, if your problem with C is that it doesn't need a package management mechanism like some other languages, then C is clearly not for you. But C is very far from the only language like this. It's a bit like criticizing a fish for having no legs.
- IshKebab 3y ago> if your problem with C is that it doesn't need a package management mechanism like some other languages The problem isn't that it doesn't need one, it's that it doesn't have one. I have no idea why you would think that it doesn't need one. Well there is vcpkg now anyway so it finally does have one.
- cultofmetatron 3y agodownvote me if you want but this is probably the best argument for rust I've ever seen
- EuropeOverlords 3y ago[flagged]
- cultofmetatron 3y agoin what way did I misunderstand? > C makes it too hard to use a sorting library that someone competent has written. rust makes it easy to create generic data structures via generics. It would be trivial to swap between different underlying sorting algos as long as it was given a type compatible function for how to compare the contained items. what exactly am I not understanding here?
- TingPing 3y agoThe fact that this was a developers mistake and has nothing to do with the language.
- somat 3y agoSlight scarcasm. yes too hard. http://man.openbsd.org/qsort http://man.openbsd.org/qsort having said that this specific sort is somewhere deep in kernel boot land. and kernel code can't really use the standard library. I am not sure if there is a standard kernel sort.
- kllrnohj 3y agoOf course it can. Just extract the qsort implementation to a static library pulled in by the kernel and by libc.
- markus_zhang 3y agoThanks, that's a fun read although I don't understand much of it. I do understand the gist.
- thomasmg 3y agoO(n^2) algorithms often cause performance issues. The main cases I have seen in business logic are: (A) offset pagination (select ... offset n) and then paginate over all entries, and (B) read a text value, append something, store, repeat.
- djbusby 3y agoSo, how to do offset w/o using OFFSET?
- eatonphil 3y agoInclude the last id (which should be indexed) of the previous page in the next where filter. https://use-the-index-luke.com/sql/partial-results/fetch-next-page https://use-the-index-luke.com/sql/partial-results/fetch-nex...
- adra 3y agoThat's pagination, not indexed page scanning. Both have their place but they're not the same. Pagination is way better to handle updates between page loads and generally more complicated to implement. As you're now doing head tail index cursor tracking. Flat boring offset/limit is amazingly simple for the happy lazy path which is probably fine for most apps.
- kdmytro 3y agoMake a query whose parameters exclude the previous page results altogether. I learned about this from here: https://www.citusdata.com/blog/2016/03/30/five-ways-to-paginate/ https://www.citusdata.com/blog/2016/03/30/five-ways-to-pagin...
- vbezhenar 3y agoIf you need to iterate over all records, just do it? Why do you need offset. Otherwise using offset usually is OK idea. Because users very rarely will inspect page #2153. They're interested with page 1, sometimes page 2. limit/offset works fine for those cases and it'll work for page 2153 for those who visit it once in a decade. Using ids makes logic to trac prev/next/page number incredibly complex and generally you don't need it.
- dangerlibrary 3y agoFor a collection of similar stories: https://accidentallyquadratic.tumblr.com/ https://accidentallyquadratic.tumblr.com/
- ouid 3y agothe funniest comment ever posted on HN was something like: "everytime this blog is linked, I end up reading the whole thing"
- deleted 3y ago[deleted]
- yjftsjthsd-h 3y agoAt least that's probably only O(n) time;)
- fdupress 3y agoNot if every single one of its posts gets linked.
- tgv 3y agoAbout the regexp one: I once wrote a regexp for CSS. It wasn't complete, but you would be able to pinpoint a syntactic error. I hooked it up to a text field, and started entering CSS. All went fine, until I hit a limit, and adding a single character froze Chrome for more than a minute (at which point I killed it). I don't think it was accidentally quadratic. More likely, it was exponential.
- charleslmunger 3y agoI submitted some posts to this but it doesn't seem like the author has updated it. I probably run into one of these once a month!
- dheera 3y agoProbably because it's MUCH easier to code bubblesort without making mistakes that cause it to not terminate or some such. Especially if they are writing the bootloader in assembly. For something mission critical like a bootloader that's more valuable than turning O(n^2) into O(n log n). People running systems like BSD largely don't care how long the system takes to boot, once it's booted the system runs for years.
- tinus_hn 3y agoYou shouldn’t write a sort algorithm because much smarter people have already done so and their work is included in the standard library.
- rrdharan 3y agoThe “standard library” often isn’t available in early boot scenarios.
- thomastjeffery 3y agoThe standard library can be statically linked...
- xorvoid 3y agoPeople who think this way haven’t written boot code.. I suppose you’re gonna link the c runtime too and it’s assumption of being a “process” under some “operating system”.. oh wait. Compared to the rest of the task, writing a sort is pretty darn trivial.
- tedunangst 3y agoThis is true if we're talking about the first stage bios boot that needs to fit in 512 bytes, but there aren't any particular restraints on kernel size at the point in question. Link in anything you want, including qsort.
- 3y ago
- TYMorningCoffee 3y agoGTA online was struck too How I cut GTA Online loading times by 70% https://nee.lv/2021/02/28/How-I-cut-GTA-Online-loading-times-by-70/ https://nee.lv/2021/02/28/How-I-cut-GTA-Online-loading-times...
- ahns 3y agoEvery few months or so I come back to that article always in awe
- dcdc123 3y agoI was happy to see R* patched the bug and gave him a $10k bounty for it since last time I saw it.
- szatkus 3y agoLesson here is to profile your software at some point. I'm playing a game (Fenyx Rising) and after launching it I always wonder why "Checking for additional content" screen takes 20-30 seconds. I'm pretty sure it should be just a single request.
- canucker2016 3y agoI doubt that GTA Online released the game with 60K+ items in their online store. The runtime for the release day store inventory count may have been okay, but I don't think that Rockstar kept profiling their game every time that they modified their store inventory. The amount of pain Rockstar inflicted on their 90K+ users shows that Rockstar didn't care that their game took more than 3 mins to startup for the majority of their users.
- kroltan 3y agoAs someone who worked on a smaller, but still millions-of-users live-service game, profiling of average resource usage and the loading screens was done periodically even if there were no code changes to the area of the game in question. Given that our team was over an order of magnitude smaller than Rockstar, I would be very surprised if they did not have anyone even casually browsing a profiler every 3 months or something, though I think at their scale (LinkedIn claims 5k employees) they can probably have a team or two where everyone's entire job description be performance maintenance.
- Avshalom 3y agoOff Topic: "Laying out icons on a grid should be an inherently linear operation" it doesn't seem mentioned in the HN thread the cause here is probably the same thing O(n^2): sorting. laying out icons is only linear if the icons are read in the order that they're placed. It's been a long time since I used windows regularly but my memory is the default placement is by creation time. So if they're read off disk by filename (or some sort of hash) they'd need to be sorted by timestamp.
- Someone 3y agoEven if the disk sorts directory entries by file name and you want to show them sorted by file name, chances are you have to sort. Reasons? Firstly, you’d have to know the entries are sorted. For that, you need an API that tells you that or hard-code information about file systems in your code. They may exist, but I’m not aware of any file system API that provides that information. Secondly, the file system may not return the names sorted in the locale you want to sort them in. Thirdly, the sorting code used in the file system may contain a bug. Once file systems are out there, you can’t fix them (happened in one of Apple’s file systems. HFS, IIRC) Lastly, modern GUIs tend to sort file names containing numbers non-alphabetically, so that, for example “file 2.jpg” gets sorted before “file 12.jpg”. So, I think it’s easier to always sort. I would pick an algorithm that works well when items are mostly sorted at the start, though.
- EuropeOverlords 3y agoyou have indexes............
- jug 3y agoThis made me recall modern AI and the issue with quadratic complexity in its transformers. Ooof! A breakthrough here would be a true Breakthrough™ with remarkably larger context sizes. Like it would barely even be a limit anymore and be transformative (har har) to what they can be used for.