3 ms·

The thing about Computer Science nowadays is that the machines are stupidly fast so that a lot of the algorithm stuff is redundant. Bubble sort can be good enou

The thing about Computer Science nowadays is that the machines are stupidly fast so that a lot of the algorithm stuff is redundant. Bubble sort can be good enough or isn't even required for implementation as the higher order primitives are already implemented. In a lot of ways it's why SW development nowadays is nauseatingly awful. Sprints and all that web baggage have killed the enjoyment and challenge. The only challenging SW roles I see nowadays are close to the HW.

deathanatos 4y ago
> The thing about Computer Science nowadays is that the machines are stupidly fast so that a lot of the algorithm stuff is redundant. Accidentally quadratic is such a thing there's a blog[1], and it's regularly the source of problems of a certain blogger who debugs problems in Windows that are usually causing his "stupidly fast" hardware to run bog slow[2]. Just this week, I hit what seems to be an accidentally-quadratic bug in macOS's tail — tail! I'm not even sure how you write an accidental O(n²) in implementing tail, but yet macOS tail takes 7 minutes to process a log file on my system that GNU tail can process in 80 milliseconds. Regex regularly lead to oops-O(n²) due to devs not grokking the greedy nature of the star character, and for a while last year it felt like every week some NPM package was getting a security vuln. for a DoS vuln. due to quadratic regexes. Understanding how B-Trees work — and more importantly, when they don't — in database queries is a perennial source of bugs in every company I've worked at where queries get written that won't hit an index, and don't get noticed until they're hitting production levels of rows. Dev confusion entails — "but the index has the columns I'm querying!" … yes, but that's not how a B-Tree works. And it's not just the order-notation. I've seen, numerous times, people re-discover topological sort, or worse, hack a solution onto a problem where the problem is a DAG, and the solution is topo-sort, but instead you get something that isn't topo-sort, and just performs worse. Gitlab's CI failed to model CI jobs as a DAG[3], and as a result, will not launch jobs in some cases that can be run when they can be run. > Sprints Yeah, these destroy dev's souls. [1]: https://accidentallyquadratic.tumblr.com/ https://accidentallyquadratic.tumblr.com/ [2]: https://randomascii.wordpress.com/ https://randomascii.wordpress.com/ [3]: I hear it has been fixed, but I've since left it so I've not had an opportunity. Regardless, the point is that the solution was obvious … if you know the theory. Or even contemporaries, like Make.
- stormbrew 4y ago
  > Just this week, I hit what seems to be an accidentally-quadratic bug in macOS's tail — tail! I'm not even sure how you write an accidental O(n²) in implementing tail, but yet macOS tail takes 7 minutes to process a log file on my system that GNU tail can process in 80 milliseconds. If you're curious you might be able to find out why for yourself: https://github.com/apple-oss-distributions/text_cmds/tree/text_cmds-138.100.3/tail https://github.com/apple-oss-distributions/text_cmds/tree/te... It's presumably based on an old freebsd (circa v3 or v4) version of tail. (it's possibly you may already know this is out there, but it used to be a lot harder to find macos-related source code and they only recently put it all up on github so just in case)
  - hnfong 4y ago
    The easier way (or a supplementary way) would be to reproduce the slow situation, open Activity Monitor, choose the `tail` process and click "sample process". You'll get a stack trace.
sicp-enjoyer 4y ago
> machines are stupidly fast so that a lot of the algorithm stuff is redundant. This is just not true. Growth rates matter a ton and there is no way around that. A better conclusion to draw from your point about hardware would be that algorithmic performance is the only performance worth optimizing for, which is more accurate, but still not the case. Also it's not as if software is just getting faster, it's getting slower, so something else has gone wrong.
- vinyl7 4y ago
  > Also it's not as if software is just getting faster, it's getting slower, so something else has gone wrong. Javascript, electron, developers don't know how CPU works, developers don't know how to manage memory so that it's optimized for CPU prefetching, abstractions and libraries out the ass that make it impossible to reason about performance. Modern software is an absolute mad house, and developers think they can get away with it because computers will always get faster. Computers are very very fast, the problem is that software is written such that it doesn't take advantage of it...and I'm not even talking about multithreading.
mattferderer 4y ago
> The thing about Computer Science nowadays is that the machines are stupidly fast so that a lot of the algorithm stuff is redundant. Plenty of basic computer science problems are not well understood by a lot of devs out there. One of my current projects has a daily data import process from each customer. Some of the states were taking well over 2 hours to import with a good CPU, lots of memory & fast SSD. A bad data import or a mistake could cost the company a decent chunk of money & upset their state customers. Plus we would have to re-import which meant another 2 hour wait. The prior code was modifying the string every field instead of using pointers when importing the data. That took a 2 hour plus import down to under 1 minute. There was also encryption being done on certain fields. Re-using some keys instead of generating them for no valid reason every line ended up bringing the import down to 10 seconds.
robjan 4y ago
They are until they aren't. Or you add latency into the mix. I've seen far too many N+1 problems, quadratic loops and full table scans to believe that computers are fast enough such that understanding data structures and algorithms is unnecessary.
gorbachev 4y ago
Most of the issues on delivering value at work I face these days are figuring out how to get the teams that own the various internal platforms we use to authorize me to do things on those platforms. Or waiting on a vendor to deliver what they said they would. Or getting interrupted by the 1000th mandatory firmwide migration project this quarter that has to be finished today, or else. Or waiting for the CI/CD environment to come back up after they had to finish the 1001th mandatory firmwide migration project. I wish I had software issues, at least they would be interesting. I'm exaggerating a bit, but this is the life at an enterprise company for many devs.
nunez 4y ago
Machines are stupid fast but cycles are cycles, and O(n^2) time complexity will always be suboptimal. There are (I feel) so many examples of stuff getting locked up because it's just for loops, right?

deathanatos 4y ago

> The thing about Computer Science nowadays is that the machines are stupidly fast so that a lot of the algorithm stuff is redundant. Accidentally quadratic is such a thing there's a blog[1], and it's regularly the source of problems of a certain blogger who debugs problems in Windows that are usually causing his "stupidly fast" hardware to run bog slow[2]. Just this week, I hit what seems to be an accidentally-quadratic bug in macOS's tail — tail! I'm not even sure how you write an accidental O(n²) in implementing tail, but yet macOS tail takes 7 minutes to process a log file on my system that GNU tail can process in 80 milliseconds. Regex regularly lead to oops-O(n²) due to devs not grokking the greedy nature of the star character, and for a while last year it felt like every week some NPM package was getting a security vuln. for a DoS vuln. due to quadratic regexes. Understanding how B-Trees work — and more importantly, when they don't — in database queries is a perennial source of bugs in every company I've worked at where queries get written that won't hit an index, and don't get noticed until they're hitting production levels of rows. Dev confusion entails — "but the index has the columns I'm querying!" … yes, but that's not how a B-Tree works. And it's not just the order-notation. I've seen, numerous times, people re-discover topological sort, or worse, hack a solution onto a problem where the problem is a DAG, and the solution is topo-sort, but instead you get something that isn't topo-sort, and just performs worse. Gitlab's CI failed to model CI jobs as a DAG[3], and as a result, will not launch jobs in some cases that can be run when they can be run. > Sprints Yeah, these destroy dev's souls. [1]: https://accidentallyquadratic.tumblr.com/ https://accidentallyquadratic.tumblr.com/ [2]: https://randomascii.wordpress.com/ https://randomascii.wordpress.com/ [3]: I hear it has been fixed, but I've since left it so I've not had an opportunity. Regardless, the point is that the solution was obvious … if you know the theory. Or even contemporaries, like Make.

stormbrew 4y ago
> Just this week, I hit what seems to be an accidentally-quadratic bug in macOS's tail — tail! I'm not even sure how you write an accidental O(n²) in implementing tail, but yet macOS tail takes 7 minutes to process a log file on my system that GNU tail can process in 80 milliseconds. If you're curious you might be able to find out why for yourself: https://github.com/apple-oss-distributions/text_cmds/tree/text_cmds-138.100.3/tail https://github.com/apple-oss-distributions/text_cmds/tree/te... It's presumably based on an old freebsd (circa v3 or v4) version of tail. (it's possibly you may already know this is out there, but it used to be a lot harder to find macos-related source code and they only recently put it all up on github so just in case)
- hnfong 4y ago
  The easier way (or a supplementary way) would be to reproduce the slow situation, open Activity Monitor, choose the `tail` process and click "sample process". You'll get a stack trace.

sicp-enjoyer 4y ago

> machines are stupidly fast so that a lot of the algorithm stuff is redundant. This is just not true. Growth rates matter a ton and there is no way around that. A better conclusion to draw from your point about hardware would be that algorithmic performance is the only performance worth optimizing for, which is more accurate, but still not the case. Also it's not as if software is just getting faster, it's getting slower, so something else has gone wrong.

vinyl7 4y ago
> Also it's not as if software is just getting faster, it's getting slower, so something else has gone wrong. Javascript, electron, developers don't know how CPU works, developers don't know how to manage memory so that it's optimized for CPU prefetching, abstractions and libraries out the ass that make it impossible to reason about performance. Modern software is an absolute mad house, and developers think they can get away with it because computers will always get faster. Computers are very very fast, the problem is that software is written such that it doesn't take advantage of it...and I'm not even talking about multithreading.

mattferderer 4y ago

> The thing about Computer Science nowadays is that the machines are stupidly fast so that a lot of the algorithm stuff is redundant. Plenty of basic computer science problems are not well understood by a lot of devs out there. One of my current projects has a daily data import process from each customer. Some of the states were taking well over 2 hours to import with a good CPU, lots of memory & fast SSD. A bad data import or a mistake could cost the company a decent chunk of money & upset their state customers. Plus we would have to re-import which meant another 2 hour wait. The prior code was modifying the string every field instead of using pointers when importing the data. That took a 2 hour plus import down to under 1 minute. There was also encryption being done on certain fields. Re-using some keys instead of generating them for no valid reason every line ended up bringing the import down to 10 seconds.

robjan 4y ago

They are until they aren't. Or you add latency into the mix. I've seen far too many N+1 problems, quadratic loops and full table scans to believe that computers are fast enough such that understanding data structures and algorithms is unnecessary.

gorbachev 4y ago

Most of the issues on delivering value at work I face these days are figuring out how to get the teams that own the various internal platforms we use to authorize me to do things on those platforms. Or waiting on a vendor to deliver what they said they would. Or getting interrupted by the 1000th mandatory firmwide migration project this quarter that has to be finished today, or else. Or waiting for the CI/CD environment to come back up after they had to finish the 1001th mandatory firmwide migration project. I wish I had software issues, at least they would be interesting. I'm exaggerating a bit, but this is the life at an enterprise company for many devs.

nunez 4y ago

Machines are stupid fast but cycles are cycles, and O(n^2) time complexity will always be suboptimal. There are (I feel) so many examples of stuff getting locked up because it's just for loops, right?