Hacker News Reader

> Select candidates who are keenly interested in and knowledgeable about algorithms for positions where it's important (i.e. part of the regular course of development), not because of that slight chance there is one edge case where one adjustment to a more efficient algorithm might possibly be useful at some indeterminate point in the future.

Well put! At the end of the day, it's way more important to get your product out to customers/users rather than holding a microscope over every line of code you write and endlessly obsessing over big O numbers. It's fine if you're in academia, but it can be a death knell if you're working in a crowded domain. You can always go back and improve code later; customers/users are not going to come back later.

Customers won't necessarily come back after you rewrite your product to deal with all the perf problems your naive implementations caused.

I'm all for striking the right balance with perf concerns, but in my experience that's not "just deal with it later". Giving no thought to performance is as bad as micro optimizing at the beginning.

True. It's a balance, it's hard, and there is no silver bullet. I believe I should learn from my mistakes and move on rather than have rabid obsession over big O. If something is obvious or caught by code reviews, fix it then and there else move on.

I believe I should learn from my mistakes and move on rather than have rabid obsession over big O.

It's not even an obsession. Those pieces of knowledge could be fully mastered in about a half hour. It's first principles knowledge, like chemistry or thermodynamics. I can tell in a minute that something like "Solar Freakin Roadways" is a scam, whereas so many people gave that scam literally millions of dollars. Knowledge is literally power, in a very concrete way that expresses itself directly as dollars!

Instead of having some basic first principles knowledge to spot such things ahead of time, benefiting from the collective experience of your field, you'd rather just labor in ignorance and run into everything for the first time and get out the profiler? Imagine scaling that up to the size of the Amazon or Google workforce?

We agree to disagree.

I absolutely don't disagree with optimizing when it's obvious (two for loops instead of one, etc.) All I'm saying is that, when you have thousands of lines of code (millions?) and even more complicated/intricate connections in your head of different modules, all the while when trying to reach a deadline, things aren't as obvious. You have to make compromises, it's inevitable.

Amazon or Google did not scale up magically in one go by following established guidelines. I am very certain they had growing pains and I know that they had "hacks"[0] while figuring out the right solution for the problem at hand.

[0] As attested by a former Googler who works at my current workplace

I absolutely don't disagree with optimizing when it's obvious (two for loops instead of one, etc.)

What we disagree with, is the expansion of one's knowledge of what constitutes "obvious." Many people would say that the scam nature of "Solar Freakin Roadways" was far from obvious. Other people would smack their foreheads and ask why some people didn't pay attention in middle school and high school physics!

Details do not matter until they show up. Still take string concatenation as an example. Suppose you want to highlight some particular words while a user is actively typing characters in a dialog. If you naively concatenate every character, the user may have responsiveness issues or at least wastes CPU cycles/battery unnecessarily. Small cases like this add up in a big project.

My conjecture is that a big fraction of programs could get significant performance boost noticeable by end users if they were developed by good developers who have some knowledges in algorithms. You don't need to be an expert, but knowing very basics on time complexity and fundamental data structures is necessary to every programmer IMHO.

I tend to run in to more critical issues than performance, like shipping the product/feature at all, meeting deadlines, writing maintainable code, and writing documentation.

In your highlighting example, instead of working with someone who will optimize, I'd much rather work with the guy who will realize we can just debounce the dialog, write a one line comment about the performance issue, and then move on to the next thing.

Maybe I'm biased though. I've worked with the performance guy; he was brilliant and the code was clever and highly performant, but he was also slow and didn't write clear, maintainable code. We didn't ship in time and I had to find a new job when the project got scrapped. Damned if it wasn't fast though.

> In your highlighting example, instead of working with someone who will optimize, I'd much rather work with the guy who will realize we can just debounce the dialog, write a one line comment about the performance issue, and then move on to the next thing.

As long as you are aware of the issue with naive string concatenation, you can use a string buffer or a mutable string – it is trivial to solve in a few more lines of code. What's more difficult involves deletion in the previous text. If this happens often, you will need rope or skip list, which is challenging if you implement from scratch. In the latter case, I would leave a comment without implementing the optimal solution and let the profiler decide later.

We didn't ship in time and I had to find a new job when the project got scrapped. Damned if it wasn't fast though.

Sounds more like a project management issue to me, than a problem with that coder.

Three man team and he was the lead. Yes, it was a project management issue.

I'd rather see basic project management skills than basic knowledge of algorithms. Unfortunately, the former is much more rare.

Sure. But at the scale of e.g. Google, Amazon, etc. how often do you think they are performing these lower level computations?

From my experience: very frequently.

So it's useful at these corporations for all engineers to have this understanding, I think.

From my admittedly limited experience at Google, given the size of the input data even a "small" project deals with those little algorithmic inefficiencies really add up quickly. You have to do a lot of optimizing and using clever data structures to make something work at all.

I haven't worked at any of these companies so I wouldn't know how often they're performing these computations. My conjecture is broad, of course, and a statistical suggestion at that: it seems unobjectionable to claim that for some companies the "typical application" lives in the 20%-25% "outlier" region most of the time.

Where I work our core rendering algorithm which runs several times on every page load used naïve string concatenation. When I initially wrote it I knew string concatenation was inefficient but never got back to it and for 99.9% percent of cases it didn't matter! We finally hit that 0.1% case and after optimizing the algorithm, it didn't make a dent on our overall performance numbers at all.

The biggest impact to our performance has been switching one JSON serialization library for another, no algorithmic knowledge needed, just basic benchmarking skills.

Your one anecdote obviously proves everything once and for all. The biggest recent performance gains in my personal project had to do with switching to WebRTC and switching libraries.

Knowing when you can just slap in the naive string concatenation and move on is also a useful result of the right skills. If you had better profiling tools/skills, I posit that you wouldn't have had to do the useless optimization.

What made you reimplement the rendering algorithm and/or switch JSON libraries (eg were these changes backed by data/measurements)?

Conjecture: the majority (by far, probably on the order of 75%-80% or more) of programming and engineering problems to be solved in a typical company or typical application will not see significant differences in performance by selecting a naive implementation.

True. And people who clutter their code by using some fancy "StringStream" class when they could've just used a concatenation are also part of the problem!

Saying that programmers don't need a basic knowledge of algorithms is like saying drivers don't need to know how to back up a trailer or do a 3 point turn. Over 90% of the time, you don't need it. But when you do, you really do!

Well, sure but one person's "basic" is another's "esoteric," and "when you do" is something I think is relatively infrequent. I cared deeply about this sort of thing when I was writing code for HPC modeling of physical systems, but in very specialized and narrow context. Since I've left academia I have rarely encountered a problem where understanding implementation details behind complexity was really necessary.

Knowing the typical time and space complexity for an algorithm (without even understanding one bit about the implementation details) in a given category might be considered too trivial to be even basic, but I submit it's about the most "advanced" piece of knowledge for what a typical engineer really must know to write good, high quality and performant enough code.

Most can get by using a given language's library implementation of an "obvious" data structure and naive algorithms around it. For example, in Python, the "obvious" structure to map keys to values is a dict, and iteration over the keys or item tuples is a typical access pattern. An engineer doesn't need to know whether the dict insert or lookup is amortized O(1) or any other value, and he doesn't need to know the space required is O(n), etc. In almost every case he's likely to put it to use for the dict is fine.

Knowing the typical time and space complexity for an algorithm (without even understanding one bit about the implementation details) in a given category might be considered too trivial to be even basic, but I submit it's about the most "advanced" piece of knowledge for what a typical engineer really must know to write good, high quality and performant enough code.

I think we're both saying that it's generally a good level of 1st Principles knowledge for programmers to have.

"Good" and "necessary" are different things, though. I consider it "good" to know as much as possible about things I'm interested in. I don't consider it "necessary."

It's not about using this knowledge all the time.

It is about your base knowledge (which should include algorithms) and knowing those algorithms when its matters.

If you have the choice of two identical software engineers and one knows 1 algorithm more than the other, he/she wins.