5 ms·

I guess it is that season again ? :-) This article seems to pop up about every other year, and pretty much garner the same general reactions every time. A lot

by phkamp 7y ago

I guess it is that season again ? :-) This article seems to pop up about every other year, and pretty much garner the same general reactions every time. A lot of CS-majors immediately go in to defensive mode, starting to spew O(blablabla) formulas while thumbing their text-books. That actually just underscores the main point I tried to communicate in that article: CS education simplified the computing platform used for algorithmic analysis so much that it has (almost) lost relevance. The big-O has little to do with real-world performance any more, because of the layers of caching and mapping going on. In practice O(n²) can easily be faster than O(n) for all relevant n, entirely depending on ordering of access in the implementation. Also, CS-education tends to gloss over important footnotes. Take quicksorts worst-case performance, which even wikipedia describes as "rare". It is not. Sorted data are very, very common. Originally researchers were more careful about these issues, and they operated with several distinct big-O's. Re-read TAoCP about sorting on tape-drives for a classic example. Some pull out "Cache-Oblivious Algorithms", usually having never actually tried to implement, benchmark or use any of them. They are, as a rule, horribly complex, and seldom faster in practice, because they hide a very large performance constant in their complexity. More often than not, there are no available reference implementation, so people cannot easily try them out, and none of them are fast enough to compensate of the embuggerance of the software patents which cover them. There are usually one or two who claim that "Virtual Memory" is no longer a relevant concern and that one should just put "enough RAM" in the machine. Throwing hardware at the problem is a nice job if you can get it, and a nice hobby if you can afford it. However, even if the money is there, what about the energy consumption ? Our climate is rapidly deteriorating because of greenhouse gasses from our energy-production, and more and more algorithms run on battery-power. If I were writing a CS-thesis or CS-textbook today, it would be all about big-E() notation, and how it only weakly correlates with big-O() notation.

ReaLNero 7y ago
It seems like the majority of your comment focuses on your distaste on Big-O complexity, a tool used for algorithm analysis. > CS education simplified the computing platform used for algorithmic analysis so much that it has (almost) lost relevance. Do you have any constructive advice? How would you relax the model assumptions? What do you use to estimate algorithm speed?
- phkamp 7y ago
  My most constructive advice is that CS education should "go concrete" often enough to de-mythologize the predictive powers of big-O notation, and have the course contain at least one exercise which shows how misleading it can be in practice. Maybe have them download and sort a 32GB data set on a 64GB SD card on a RPi3 board ? The smart ones will realize that downloading can be their first pass over the data, and all of them will be befuddled by the interesting performance anomalies when photo-grade SD-cards go on sabaticals, if you annoy their simplistic flash-adaptation layers. If they characterize "the trouble", they may find that obsolete sequential algorithms for tapes run faster than random access algorithms in that environment. ...which is precisely the kind of thing companies expect a CS-graduate to be good at.
staticassertion 7y ago
I dropped out of a not very good program, but even in my time there we did learn that O(N^2) can (and almost certainly will) be faster than O(N) on most architectures due to data locality and large constants hidden by Big O notation. I'm not asking this to be snarky, again I'm a dropout and don't have a ton of insight into this sort of thing - do most CS programs not cover this in at least some detail at some point?
- Izkata 7y ago
  Mine not only did not (2006-2010), when the professor was demonstrating something he dropped a constant I knew from prior experience would overpower the big-O in question, then danced around it when I tried to ask about it. Didn't even try to go down the path of "we're focusing on big-O, so we're only ignoring it for this particular analysis", he just pretended the term didn't exist.
  - staticassertion 7y ago
    Interesting, thanks. I suppose it isn't necessarily part of a core curriculum (though I did not make it through the curriculum, which is why I was curious).
peter_d_sherman 7y ago
This is applicable to any system that does paging and stores and retrieves data from those pages, whether that system be a Database or an OS... Best algorithm performance article I've read on HN for a long time!
mcnichol 7y ago
I think the problem was most companies ran internal data centers and were unflinching to the cost of internal bloat. IMO for a multitude of reasons this has hidden the cost of these deoptimizations due to the virtualized abstraction. I believe with public cloud dropping a comprehensive bill on the doorstep of these enterprises, compute will become a utility that will be optimized once again with virtualization at the heart of it all.
anonymoushn 7y ago
Why do you think quicksort's worst-case performance occurs when the data is already sorted?
- Izkata 7y ago
  Quicksort's worst-case occurs when all elements always land on one side of the pivot. If the pivot is naively chosen as the first or last element in the range, this will be the case for already-sorted data. Randomly selecting the pivot is an additional step easily skipped when first introducing the algorithm.
  - anonymoushn 7y ago
    I don't think this really justifies GP's gripes about Wikipedia or sorted data occurring a lot in the real world. To get the first-element pivot selection quicksort to regularly interact with the sorted data, we would need some standard library to actually ship a quicksort that always picks the first element as the pivot. I don't think any of these exist.
archi42 7y ago
Hm, maybe it's been too long since I had some AlgoDat lectures, but I recall we learned that memory hierarchy was rather important, and that having data in cache can make a huge difference. Of course for the undergrad course, learning proper analysis was more important, since the whole thing about big-O is how often $STUFF happens relative to the input size (or at least that was my big take away). That $STUFF is swappable, and in the lecture we usually used "number of compares". The idea was that a student could later analyze for other things, e.g. for loads, cache-misses, page-faults, cycles or a combination thereof. You're saying yourself: "they operated with several distinct big-O's.". So, what did you do then? From a theoretical/CS point-of-view, you're just optimizing for less VM paging. There is nothing wrong about it, quite the opposite: You're demonstrating knowledge of your machines architecture, and use it to keep memory latency low - which is both a good thing. But this isn't new, or unheard of. I recently looked something up w.r.t. tree data structures, and the 1997 8th edition of Cormen, Leiserson and Rivest even mentions how bad it is to access data from a spinning disk, and how that should be reduced (I didn't read that section in detail, because that was not what I was interested in). However, maybe sometimes people forget that, or the application of their knowledge is bad (e.g. optimize for "number of compares" when memory latency is dominant). With regards to that, I really liked the article: I do a lot of runtime analysis for assembler code across various platforms, and as such I am painfully aware how complex even decades old pipelines are - it's a pain that developers tend to forget about this. On the one hand I find (parts of) the linked article funny, on the other hand it's painful that you assume all other people to be ignorant, when this is not the case. Regarding big-E: That's also not new, but probably not as popular as it should/could be. I recall a friend mentioning that part of her PhD research was energy complexity of sorting algorithms. That was ~2008.
hinkley 7y ago
The next biggest lie that everyone believes is that everything is premature optimization. For a while I saw this even when our customers were unhappy with the speed of the app. Probably the first bad case of cognitive dissonance I encountered in the field. The one after that is that all performance work decreases code comprehension. There are plenty of techniques that do both, and these, as I discovered, fly below the radar of the anti-perf crowd.
bhl 7y ago
That’s the difference between a data structures and algorithms class versus a systems class: in the former the constant in front of the Big O doesn’t matter while in the matter it does. Any good CS curriculum would have both courses.

by phkamp 7y ago

ReaLNero 7y ago

It seems like the majority of your comment focuses on your distaste on Big-O complexity, a tool used for algorithm analysis. > CS education simplified the computing platform used for algorithmic analysis so much that it has (almost) lost relevance. Do you have any constructive advice? How would you relax the model assumptions? What do you use to estimate algorithm speed?

phkamp 7y ago
My most constructive advice is that CS education should "go concrete" often enough to de-mythologize the predictive powers of big-O notation, and have the course contain at least one exercise which shows how misleading it can be in practice. Maybe have them download and sort a 32GB data set on a 64GB SD card on a RPi3 board ? The smart ones will realize that downloading can be their first pass over the data, and all of them will be befuddled by the interesting performance anomalies when photo-grade SD-cards go on sabaticals, if you annoy their simplistic flash-adaptation layers. If they characterize "the trouble", they may find that obsolete sequential algorithms for tapes run faster than random access algorithms in that environment. ...which is precisely the kind of thing companies expect a CS-graduate to be good at.

staticassertion 7y ago

I dropped out of a not very good program, but even in my time there we did learn that O(N^2) can (and almost certainly will) be faster than O(N) on most architectures due to data locality and large constants hidden by Big O notation. I'm not asking this to be snarky, again I'm a dropout and don't have a ton of insight into this sort of thing - do most CS programs not cover this in at least some detail at some point?

Izkata 7y ago
Mine not only did not (2006-2010), when the professor was demonstrating something he dropped a constant I knew from prior experience would overpower the big-O in question, then danced around it when I tried to ask about it. Didn't even try to go down the path of "we're focusing on big-O, so we're only ignoring it for this particular analysis", he just pretended the term didn't exist.
- staticassertion 7y ago
  Interesting, thanks. I suppose it isn't necessarily part of a core curriculum (though I did not make it through the curriculum, which is why I was curious).

peter_d_sherman 7y ago

This is applicable to any system that does paging and stores and retrieves data from those pages, whether that system be a Database or an OS... Best algorithm performance article I've read on HN for a long time!

mcnichol 7y ago

I think the problem was most companies ran internal data centers and were unflinching to the cost of internal bloat. IMO for a multitude of reasons this has hidden the cost of these deoptimizations due to the virtualized abstraction. I believe with public cloud dropping a comprehensive bill on the doorstep of these enterprises, compute will become a utility that will be optimized once again with virtualization at the heart of it all.

anonymoushn 7y ago

Why do you think quicksort's worst-case performance occurs when the data is already sorted?

Izkata 7y ago
Quicksort's worst-case occurs when all elements always land on one side of the pivot. If the pivot is naively chosen as the first or last element in the range, this will be the case for already-sorted data. Randomly selecting the pivot is an additional step easily skipped when first introducing the algorithm.
- anonymoushn 7y ago
  I don't think this really justifies GP's gripes about Wikipedia or sorted data occurring a lot in the real world. To get the first-element pivot selection quicksort to regularly interact with the sorted data, we would need some standard library to actually ship a quicksort that always picks the first element as the pivot. I don't think any of these exist.

archi42 7y ago

Hm, maybe it's been too long since I had some AlgoDat lectures, but I recall we learned that memory hierarchy was rather important, and that having data in cache can make a huge difference. Of course for the undergrad course, learning proper analysis was more important, since the whole thing about big-O is how often $STUFF happens relative to the input size (or at least that was my big take away). That $STUFF is swappable, and in the lecture we usually used "number of compares". The idea was that a student could later analyze for other things, e.g. for loads, cache-misses, page-faults, cycles or a combination thereof. You're saying yourself: "they operated with several distinct big-O's.". So, what did you do then? From a theoretical/CS point-of-view, you're just optimizing for less VM paging. There is nothing wrong about it, quite the opposite: You're demonstrating knowledge of your machines architecture, and use it to keep memory latency low - which is both a good thing. But this isn't new, or unheard of. I recently looked something up w.r.t. tree data structures, and the 1997 8th edition of Cormen, Leiserson and Rivest even mentions how bad it is to access data from a spinning disk, and how that should be reduced (I didn't read that section in detail, because that was not what I was interested in). However, maybe sometimes people forget that, or the application of their knowledge is bad (e.g. optimize for "number of compares" when memory latency is dominant). With regards to that, I really liked the article: I do a lot of runtime analysis for assembler code across various platforms, and as such I am painfully aware how complex even decades old pipelines are - it's a pain that developers tend to forget about this. On the one hand I find (parts of) the linked article funny, on the other hand it's painful that you assume all other people to be ignorant, when this is not the case. Regarding big-E: That's also not new, but probably not as popular as it should/could be. I recall a friend mentioning that part of her PhD research was energy complexity of sorting algorithms. That was ~2008.

hinkley 7y ago

The next biggest lie that everyone believes is that everything is premature optimization. For a while I saw this even when our customers were unhappy with the speed of the app. Probably the first bad case of cognitive dissonance I encountered in the field. The one after that is that all performance work decreases code comprehension. There are plenty of techniques that do both, and these, as I discovered, fly below the radar of the anti-perf crowd.

bhl 7y ago

That’s the difference between a data structures and algorithms class versus a systems class: in the former the constant in front of the Big O doesn’t matter while in the matter it does. Any good CS curriculum would have both courses.