Hacker News Reader

Comment by marcosdumay | Hacker News Reader

> Neither have I been in a situation where big-o was relevant beyond the basic concept of not doing obviously stupid shit.

How do you know you are doing stupid shit if you don't know about complexity and don't know your algorithms?

Really, I do work on CRUD applications from time to time, and I often have to select algorithms based on complexity. Yeah, didn't have to implement one of them for ages¹, but I do have to tell coworkers things like "here you use a set", "here you use a list", "this sorting algorithm isn't stable", or "nah, just use brute force and get done" once in a while.

1 - Or, better, did implement a B-tree for a side project just a couple of months ago. Ended up just throwing it away, but I didn't know I wouldn't use it at the beginning.

View on HN

I learned big-o around 15 years ago, and have never used it professionally. (I forgot what it meant when I had a phone interview with Google).

I do know that some algorithms are more efficient than others, and some sorts depend on whether you expect the list to be random, sorted or partially sorted. If I find myself in a situation needing to choose between libraries. I would guess that half an hours reading would refresh what I need to know.

Just a year ago I was on a project that involved building a tree of data and we wanted the ability to try adding a few things and backtrack to multiple different points if it didn't work out, so there was a lot of shared data in the tree. Performance was critical and we had various operations that had to be performed regularly, so I did a lot of implementations and tested them directly.

My CS degree (which I got late in my career) was invaluable. I got it precisely because I had no idea what I was missing and if I hadn't I wouldn't have investigated half the options I did and would not have had a good framework for thinking about them. I would have gotten the job done without it, but it wouldn't have been as good a job and I wouldn't have known what I was missing.

> How do you know you are doing stupid shit if you don't know about complexity and don't know your algorithms?

So, one cannot understand complexity without Big O calculus? I only learned the notation after years of calculating memory and runtime complexities for real-time code, and that was only for interviews. I don't find comparisons at the Big O level to be useful in day-to-day work.

> Really, I do work on CRUD applications from time to time, and I often have to select algorithms based on complexity.

Really, you often have to select algorithms at that level of granularity? I never have, in almost ten years of full-time development. I frequently have to select or tune algorithms based on the factors that Big O throws out, though. Then again, I do very little with searching and sorting.

I have libraries that make sure I don't do stupid shit.

And my students have calculators so there is no need for them to know basic arithmetic.

My friend is a Maths teacher and can barely do mental arithmetic.

That's the point, there is no magic library that can do this for you. For example, let's say you're writing Python and have a list of receipt numbers. When you get a new receipt, you want to check if it's already in the list, so you do the pythonic thing: "if receipt_nr in receipts", assuming that the standard implementation of this operation in the library is efficient. The problem is, a set would be a lot more efficient here, but the standard library doesn't know you'll be checking if a number is in the list many times, so it cannot use the appropriate data structure.

So, in a way, the time and space complexity of each operation is part of the interface: maybe you don't really need to know how the internals are implemented, but at the very least you need to know the time and space complexity of the data structures you're using, and how to analyse the complexity of your code.

What's funny about your example is that using a set in that situation would be an example of premature optimization. If your entire list of receipts fits into memory users won't notice a difference between a list and a set.

Also, if you used a list in Python (or other similar dynamic languages) swapping a list out for a set is a trivial operation...

    receipts = []
    # ...becomes:
    receipts = set()

...and it would require no changes to the conditional logic of the application. So later, if it turns out you're having performance issues you (usually) make a few minor changes here and there and get your 10x or 100x or even 10,000x speedup.

> If your entire list of receipts fits into memory users won't notice a difference between a list and a set.

If you had said "small enough", I would agree, but linear walks of data that can fit in memory can easily be noticed by users, for large enough lists. (Very large lists can fit in memory.)

But, at a higher level, yes, this is always true when people talk about performance: make sure what you're optimizing actually matters. I think a charitable reading of what ThePawnBreak said should assume one has already determined this particular operation matters for performance.

Earlier this month I was looking at the question of "why does it take 160ms to scan a list of just 60,000 items?

The answer turned out to be "because they're not adjacent and on this embedded system every single cache miss costs you hundreds of nanoseconds".

I strongly agree that, like woodworkers, performance improvers should measure before they take out the power tools.

Not to mention that most of the kids today would have stowed their entire population of receipts in whatever the datastore flavor-of-the-week is. At that point, the lookup would effectively be a SELECT -- which the DBMS would optimize away for you.

.. unless they've forgotten the index, at which point the DBMS grinds to a halt.

Or they've written the query on the wrong side of the ORM so it has to pull in all the objects, check the value, and discard them.

A very simple example that I think is "real-world" enough is recursively descending the fields of some object which has cycles. If you use a list instead of a set this can be quite slow.

> What's funny about your example is that using a set in that situation would be an example of premature optimization. If your entire list of receipts fits into memory users won't notice a difference between a list and a set.

That's completely untrue if you're running this check often enough.

Next question: how often would this kind of malprogramming actually lead to deal-breaking performance issues in a project? After a decade in the industry, countless projects delivered and much shit code witnessed, I can empirically answer this question, and the the answer is -- even at places that are known for their technical excellence -- not often.

Look, I'm not advocating illiterate programming, nor am I a proponent of unprofessional work. I took my share of CS classes, and I can talk about algorithms and how to analyze them. The number of times I have had to do so on the job, however, can be counted on my bodily digits, without taking off my shoes.

This is probably not an original observation, but a big part of why these unproductive conversations keep on happening here has to do with how young HN demographic skews. When the biggest achievement in your life is getting that new degree you spent $BIGNUMBER $$/years on, you're going to want to belittle workmanlike programmers who don't measure up to your own standards. It takes a while for people to move on and grow up.

> how often would this kind of malprogramming actually lead to deal-breaking performance issues in a project?

Depends very much on your projects. Web developers generally have it easy, as it's cheap to add more servers and free to burn CPU in the browser. Even so you can get into trouble with anything that's O(N) in the number of users. I do wonder how much use of nosql is from people who think SQL is slow because they've not got their indexes set up properly.

Game developers, of course, live and breathe performance. As do embedded and similar low-level environments. Or people working with this trendy "big" data.

Performance will rarely be deal breaking. Instead people will toil away with slow systems and just accept it. It doesn't mean that they wouldn't be much happier with a faster system.

We recently replaced a system whose online store took about 900ms to respond, and their back end admin section on average around 1.7 seconds. It obviously wasn't deal breaking since they lived with it for 3 years but it still was still ridiculous, and definitely had an impact on both their productivity and bottom line.

How big is the list we're talking about?

Reply on news.ycombinator.com