Get the top HN stories in your inbox every day.
no_wizard
softfalcon
I can also anecdotally agree with your analysis. I've seen for myself how much more some folks will respect you during interviews if you "get past" the part about fizzbuzz (algorithms) and move onto immediately talking about data structures, architecture, and how that analogues to the domain in question.
All of the sudden, the interviewer relaxes and you can just see on their face the, "oh, we've got an actual senior engineer on the call here." They open up about their technical problems and stop caring about "proving if you can even code".
Similarly, the teams I've had the most problems creating positive change, meeting milestones, or collaborating together properly as a team with is where no one seems to have a good grasp of data structures and code architecture. It seems to have become more common too. Many folks are quite used to having a framework that can just do everything, and if it can't, someone "smarter than them" has made a plugin or middleware to save them from having to think too hard.
I personally find engineers who avoid data structures to be shooting themselves in the foot, they're giving up on one of the most useful tools in their arsenal and I witness how it limits them day-to-day. It's tough to watch.
pklausler
Asking "FizzBuzz" is not done to test algorithmic knowledge.
dagw
Which is why all the LeetCode interviews always struck me as odd. They focus on algorithms, not data structures
I helped my nephew preparing some competitive coding event, and transforming the data into the right data structure was a huge part of solving most problems. For example most of the code you might end up writing is for finding the longest path through a weighted DAG, but the trick was realising that you could represent the problem as a weighted DAG, and if you did then the length of the longest path through that graph was your answer. If you didn't spot that then you might very well still be able to solve the problem, but your solution would end up being much slower and more complicated.
mikhailfranco
This is the low-hanging fruit algorithm:
- build the DAG with heavy nodes (e.g. lead split-shot)
- use string or fishing line for edges, with length proportional to 'weights'
- hold the root node(s) high in the air, if more than one, hold them together, at the same height
- the lowest node, or the length of taught line (drop distance below your hand), is the answer
a1369209993
That doesn't actually work, because a DAG only lacks directed cycles. Consider:
/-3-> D
A -1-> B -1-> C
\------4------^
roughly
What’s great is that it’s constant time, once you’ve prepared the data structure. Never underestimate the parallelism of physical systems.
pfisherman
How much of this is finding the right data structure (graph) vs translating the problem into a new domain?
I think maybe the former follows from the latter?
jasode
>Which is why all the LeetCode interviews always struck me as odd. They focus on algorithms, not data structures,
The typical leetcode questions also focus on "data structures" because the candidate needs to have the mental catalog of data structures in his brain to pull from when he "pattern matches" on the problem/solution.
The interviewer isn't going to volunteer whether the candidate needs a "priority queue", or "adjacency matrix", or "trie", etc to solve various algorithm questions. If the candidate is stuck, then the interviewer might give a hint to the data structure to use. But of course, too much hand-holding will not make the candidate come across as a strong hire signal.
no_wizard
Its been a time since I interviewed in such a manner, perhaps things have shifted. When I was interviewing a few years back, it was algorithm heavy, often a basic data structure was provided and there was alot of focus on traversal (hence the memes around reversing binary trees and such)
Icathian
To add another point of anecdata, my experience very recently at tech companies aligns with the parent comment.
bitwize
"Show me your flowcharts, but keep your tables hidden, and I shall continue to be mystified. Show me your tables, and I won't need to see your flowcharts, they'll be obvious."
kwhitefoot
You forgot the credit: Fred Brooks, Mythical Man Month,
jrpelkonen
Great quote and so true in the general case. Unfortunately, I have seen some database designs that have left me more mystified than I was before.
capableweb
I've seen programs that got more mystical the more the employees showed me how it worked internally.
mikebenfield
I don't really see how you can choose one without at least a rough idea of the other. How do you know what data structure to use if you have no idea how you'll be accessing the data?
softfalcon
You're not wrong, data structures and an algorithm for data retrieval are often connected and developed together. You often see someone come up with a novel way of traversing data, then they model an elegant data structure to match it and enable said traversal.
What isn't covered in this flow is how composition of multiple data-structure/algorithm pairings work together amidst many others. It's often not an algorithm on its own that defines an overall solution. It's the connecting of many of them together, to build a whole software stack, domain language, etc.
When you understand the algorithms, the corresponding data structures, when to use them, similarities in various frameworks in your chosen domain, how that analogues to your current problem set, etc you really start getting somewhere.
eska
* data structures and an algorithm for data retrieval are often connected and developed together*
Often? Always! An algorithm always only works on a certain data data structure.
no_wizard
I have found you can, even if its slowest of the slowest, brute force your way through traversal of a data structure, if you need to, since most languages (all?) give you iteration out of the box.
Being able to choose the appropriate data structure and explain trade-offs etc is much more valuable than simply knowing how to reverse a binary tree sorta stuff.
As I noted elsewhere in the thread, I haven't interviewed in awhile where I needed to grind out DS&A questions, but at the time where I did, I often found myself given a particular structure and asked to traverse it in some way, with is pretty heavy on the algorithmic thinking but not really testing my knowledge on data structures themselves.
Sounds to me like things have become a little more even handed out there
BearOso
> Being able to choose the appropriate data structure and explain trade-offs etc is much more valuable than simply knowing how to reverse a binary tree sorta stuff.
Indeed. The simplest way to invert a binary tree is to include an "invert" flag in the data structure. If it's set, walk the tree right to left instead of left to right.
bob1029
All software is effectively a set of ETL jobs with a user-friendly interface wrapped around. Those fancy algorithms, languages, frameworks, etc are simply a very ceremonious way to get data from A to B.
The schema/data are completely agnostic to the computation. You don't even need a computer. 100% of schemas are possible to print out on sheets of physical paper and iterate offline.
gridspy
Computer used to be the job title for people who DID do this by hand. It was co-opted by the technology which replaced the job.
Of course modern computation is often impractical to do by hand. It might even be so complex that humans would make too many errors and take to long to ever complete correctly.
esafak
Common use cases were abstracted into libraries and services because nobody should have to reinvent the wheel. This let people operate at a higher level of abstraction and concentrate on more complicated tasks. These too became abstracted, and the cycle repeated.
sirsinsalot
While true, I think this is reductive.
When you're dealing with most modern software, there's so many of these ETL-like pipelines, abstractions, black-boxes and just sprawling complexity that the job becomes much more about complexity management than anything.
No component exists in a vacuum, I would argue software is as much about managing the complexity of the data and algorithms towards a purpose as it is about the purpose, data or algorithms.
Entropy comes for us all, after all.
jacobgorm
See also Peter Naur's letter to the editor in https://dl.acm.org/doi/pdf/10.1145/365719.366510 . In Denmark, CS is not called CS but Datalogy.
asalahli
I prefer the term Informatics over Computer Science for this reason.
lawn
I'm not a fan of leetcode, but when I did some competitive programming it was quite common that you first had to transform the input data into the proper data structure, and then you can apply some algorithm to produce the answer.
epiccoleman
> Fancy algorithms are slow when n is small, and n is usually small. Fancy algorithms have big constants. Until you know that n is frequently going to be big, don't get fancy. (Even if n does get big, use Rule 2 first.)
Another point on this, which I really saw in action on a recent project - a "big" n is probably much bigger than you think. Sometimes it can be easy to think "oh, this is going to have to do 100,000 operations, I definitely need to optimize it" - but computers are fast, and 100,000 multiplications (for example) happens so fast you probably don't need to think too hard about it.
That's not to say you shouldn't think at all, just that it's often surprising how insanely fast modern computing hardware is.
kevincox
I don't know how strongly I agree with this one. Quadratic algorithms are the kind of thing that bite you when you least expect it. I have seen production outages due to accidentally quadratic code and it is also the type of code where some users are suffering with a really slow application because they are frequently experiencing a big N even though 99% of users have a small N all the time. In most cases I would prefer to pick a less than quadratic algorithm even if it is a bit slower for the common case and a bit more complex to implement. Slow common cases get optimized, slow in rare cases often slips by the developers (who don't hit those cases) or break in production.
Of course this is a tradeoff with Rule 4. If the fancy algorithm is much more complicated I will be more likely to pick the simple one even if it is quadratic and the data has the chance of occasionally being large. But by default I try to stick sub-quadratic if possible.
I wrote an article about this relatively recently: https://kevincox.ca/2023/05/09/less-than-quadratic/
lynguist
We recently had a HN article about it: https://news.ycombinator.com/item?id=26296339
Some amazing person found that the load time of GTA V Online was awfully slow. It was slow because the developers put in a quadratic function at a time when the iteration object was small. But over time that object grew and so grew the load times quadratically until it was unbearable. And it was unbearable for millions of GTA V Online users.
I fully agree that the accidentally quadratic functions will eventually come back to bite you/the user.
mumblemumble
The memory hierarchy plays into this, too. A lot of fancy algorithms have poor locality of reference and additional branching, so they tended to work better 40 years ago when CPUs weren't that much faster than memory and branch misprediction wasn't a thing that people had to worry about on consumer-grade hardware.
nine_zeros
I also keep seeing leetcode interview problems about iterating over a list of 100k items a few times. I can see that it is not optimal but iterating over 100k items is NOTHING compared to the network call you made right after that iteration - in terms of actual production time.
And every time I interview, the hiring managers want me but my hiring decision gets vetoed by a leetcode newbie who hasn't experienced production scars yet.
mikhailfranco
So true. Managers really want to hire architects/seniordevs who are experienced, practical, smart and get things done. But if they let the other devs into the interview process they will get vetoes all the way down, because the reports will be:
- envious of your amazing pragmatic and effective skills
- jealous guarding of the architect promotion that they covet for themselves
wizofaus
Good managers for dev teams should have enough technical knowledge themselves and demand explanations from participating devs why a candidate is or isn't good enough to see through that though. Further personally as a tech lead I've always been keen to take on new devs that clearly are a cut above, as they usually mean an opportunity to work more effectively as a team. And I really don't want to spend even more of day doing reviews of mediocre code.
undefined
diarrhea
In an async framework of execution, this doesn't apply. A lot of programming happens in that space, and in it, the network call is "free", but you're clogging the thread(s) with actual CPU work. If execution is single-threaded, the problem becomes very relevant, but it applies to multi-threaded async just the same (you might exhaust the pool of workers).
Keeping this in mind isn't esoteric either, as it applies to JavaScript, Python, Rust, C#, and probably others.
nine_zeros
> In an async framework of execution, this doesn't apply.
That's right. Async execution prevents the IO from being the bottleneck by offloading it to a different thread.
There are 3 situations where this statement falls apart:
1. If the execution is single threaded, as you rightly pointed out
2. If the response of the async execution matters to the final response of your service. In this case, the primary thread may finish its work but its still waiting for IO to complete. Basically making it synchronous but using async primitives.
3. The CPU utilization of iterating over 100k items in a list is negligible compared to the hundreds of daemons and services running on the host. Even a docker container will utilize more CPU than iteration over 100k items.
The point is: over-indexing over iteration and time-complexity in interviews is pointless as real systems are going to face challenges far beyond that.
mikhailfranco
The canonical reference for this:
Scalability! But at what COST?
zoogeny
When I got my first real programming job at a games company in the early 2000s, the Technical Director of the project once gave me some advice: if the number of things you are working with is on the order of 10,000 then don't bother optimizing it. Given the increase in computer power in the last 20 years I believe bumping that to 100,000 is pretty appropriate.
wizofaus
And yet some of the worst performance issues I've had to deal with were in code typically dealing will merely 100s of items, but using algorithms and slow network-based operations that caused everything to run sluggishly most of the time and not infrequently making the resulting user experience intolerable.
I do agree though that a lot of time is wasted on premature or even completely counterproductive optimisations for situations where the data being processed is too small to cause noticeable slowness in processing.
kagakuninja
I was testing something, and wanted to add some useless for-loop addition code to simulate "doing work". I had to make huge nested loops before I noticed any significant CPU usage on my laptop.
ska
Optimizing compilers are tricky this way, if you want to do it with optimzations turned on, you usually have to make the work "real" in some sense. Sometimes making enough nesting depth that the compiler can't fully reason it out works, but usually it's easier to modify some memory it can't be sure isn't touched otherwise (and hence elide or register allocate it or whatever).
cratermoon
Were you using a language where the compiler/interpreter was smart enough to optimize out certain kinds of busy loops? It can sometimes take a little extra work to convince the compiler or runtime. In C the keyword 'volatile' can help.
fasterik
Not only that, but often our intuitions about what is "fast" are wrong if we are basing them on theoretical big-O concerns rather than the specifics of modern hardware. One example that's ubiquitous is using a hash table with chaining when a linear array lookup would be faster due to cache locality.
lkjflakjsdeowe
Sigh, here we go again.
> Tony Hoare's famous maxim "Premature optimization is the root of all evil."
It's actually from Donald Knuth and this quote is frequently taken out of context to argue against optimization in general.
Here is the entire quote
"We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil. Yet we should not pass up our opportunities in that critical 3%."
The point is to spend time optimizing where it will have impact.
karmakaze
Knuth attributes it to Hoare, and Hoare attributes it to Knuth. So it come's down to who you want to believe. Probably best to attribute it to both. My guess would be that Tony said it first, Knuth refined and printed it.
It's always good to have the longer quote which gives needed context.
eesmith
Hoare attributed it to Dijkstra. See https://hans.gerwitz.com/2004/08/12/premature-optimization-i... .
"I’m sorry I have no recollection how this quotation came about. I might have attributed it to Edsger Dijkstra."
karmakaze
Someone needs to make a Spider-man meme with the quote.
zelphirkalt
Maybe it is in the end a secret deal between them, to have a joke about circular references. ; )
preommr
Also people forget that quote is from the 70s. Almost 50 years go.
Programming used to be very different from what it is now. "Premature optimization" wasn't "hey just use this popular lib cause it scales", it was "let's use some impossible to understand bit fiddling algorithm that only works on this piece of hardware".
ska
> Programming used to be very different from what it is now
Programming has definitely evolved. This maxim seems to be exactly as applicable then as it is now though, and as misunderstood.
bluGill
In any compiled language your optimizer will do all those weird things for you, and will even handle all the different generations of CPUs for you. Compilers never give you a better algorithm if you write the wrong one.
Almost all languages have a standard library that has all the normal algorithems you would want, and where something wierd is better they have that done for you.
eesmith
Compilers can and do replace some (simple) algorithms with a better one.
At https://stackoverflow.com/questions/74417624/how-does-clang-... is someone asking why the compiler replaced:
int a = 0;
while (n--)
a += (n * n);
a = n * (n-1) / 2 + nundefined
randomdata
I don't see how the larger quote adds any additional meaningful context. Once you have identified (measured) the critical 3%, the state is no longer premature. That is already implied in "Premature optimization is the root of all evil". The the maxim is not "Optimization is the root of all evil".
Narishma
> The the maxim is not "Optimization is the root of all evil".
In my experience, that's exactly how most people understand it.
MarkMarine
Too many people take this as dogma and just don’t learn the efficient way to do things. I’ve lost count of the number of FE devs that interview in my company’s DS&A section and tell me bubble sort is the best we can do. I don’t need a derivation off the top of your head, just know a couple and tell me a good choice for the problem and I’m good… same thing here. If people live the “don’t prematurely optimize” to the point that they don’t even know the efficient ways to do things, how will they know where it’s important.
mcphage
> this quote is frequently taken out of context to argue against optimization in general
Maybe it is, but that's not how it's being used in this context.
undefined
bawolff
I don't see anyone taking this out of context here. The entire quote is less pithy but not different in meaning. "Premature" is literally the first word.
avg_dev
How is this not covered by points 1 (don't put in hacks because of guessing) and 2 (measure)?
undefined
ttfkam
> Rule 5. Data dominates. If you've chosen the right data structures and organized things well, the algorithms will almost always be self-evident. Data structures, not algorithms, are central to programming.
This goes double for databases. Folks who use a DB as a dumb bit bucket or a simple 1:1 reflection of their object definitions are often surprised when the DB takes it personal and dooms performance.
If I ever see another ORM-generated DB schema it'll be too soon.
mrweasel
> If I ever see another ORM-generated DB schema it'll be too soon.
I'd argue that most ORMs generate the schema you ask it to. Using an ORM isn't going to create a worse database layout that you could do by hand. The issue is that some/many developers don't know SQL, nor have the required knowledge of their databases to use an ORM.
The ORM requires you to know what lies underneath, it is a fairly leaky abstraction. Understanding that, you can get most ORMs to create nice schemas.
ttfkam
ORMs are typically lowest common denominator for compatibility with many database engines. The best thing you can do is learn about the underlying engine (Postgres, MySQL, MS SQL Server, SQLite, etc.) and its distinct feature set. Once you know that, you will often find yourself quite a ways away from the lowest common denominator.
That may be built in temporal table support in MS SQL Server or MariaDB, so you don't need explicit audit tables in your schema. Or perhaps timestamp ranges with exclusion constraints in Postgres for enforcing valid schedules without hacks in the app layer.
Eventually you notice that you're having to define everything twice: once for the DB and again for the ORM definition.
This is why I prefer solutions like PostgREST, Postgraphile, and Hasura (for Postgres while other DBs have other similar solutions). Define it once in the DB and just let it bubble up. You may want to expose your storage API through views, but it still ensures optimal data structure at the foundation.
DB -> data-generated API service -> client API codegen -> client app such as web or mobile.
With a typical ORM, you're building from the middle out. It almost always results in a faulty foundation. Pour and set the foundation first. Always.
https://postgrest.org/ https://postgraphile.org/ https://hasura.io/
KronisLV
> This is why I prefer solutions like PostgREST, Postgraphile, and Hasura (for Postgres while other DBs have other similar solutions). Define it once in the DB and just let it bubble up. You may want to expose your storage API through views, but it still ensures optimal data structure at the foundation.
> DB -> data-generated API service -> client API codegen -> client app such as web or mobile.
This seems like a nice approach, albeit mine is even more basic. I pick a DB, create SQL migrations for the schema (sometimes even generate those from an ERD planning tool, with manual edits where needed), apply them to a DB with something like dbate: https://github.com/amacneil/dbmate
After that, if I want to use an ORM, I generate entity mappings from the tables/views in a schema-first approach, for example, like https://blog.jetbrains.com/dotnet/2022/01/31/entity-framewor... or https://www.jetbrains.com/help/idea/persistence-tool-window....
I don't think that sort of codegen is as popular as it should be, but for the most popular frameworks in each language, the schema-first approach is usually doable with no additional software that would need to be deployed to prod.
mrweasel
> ORMs are typically lowest common denominator for compatibility with many database engines.
That really depends on what you mean and the ORM. Typically the larger and more popular ORMs can and do take advantage of database specific features, if you let it.
Using the database specific feature will prevent you from using the ORM as an abstraction for replacing you DBMS, but outside open source projects that support SQLite, MariaDB and Postgresql, I've never seen that used in professional settings. One system I've worked with had on paper support for DB2, Sybase and MS SQL. It ran solely on MS SQL, the others had not been tested in years and the developers had pulled in so many MS SQL specific features that it was never going to run on neither DB2 nor Sybase ever again.
no_wizard
That assumes that you should just expose your Postgres tables as your data.
As someone who consumes more APIs than they write nowadays, I appreciate when data is scoped to task[0]. Employing window functions and stored procedures that can make queries into data fit for purpose is the ideal - databases are faster at manipulating data than any intermediate language, most of the time. Unfortunately, I don't see them employed enough. Backend developers seem content with throwing the schema over the wall way too often.
[0]: As an aside, this is why I personally like GraphQL so much. The middleware lets me cleanup data that backend engineers simply refuse to do, most of the time.
dkarl
If you are sophisticated enough to design a good relational model and use an ORM to generate it, what does an ORM give you? Serious question. The answers I've seen typically stress the advantages for developers who are uncomfortable with SQL (who I think are either going to get comfortable or fail, and the ORM will only delay them getting comfortable or enable them to create a more expensive failure) or more easily generate lots of different complex queries (which sounds plausible, but I've never seen it.)
mrweasel
The ORM, in my mind, is just there to help you translate data into objects, that's it really. You could do that manually and I have worked on projects where we did just that, but it's a lot of repetitive work that brings little value.
I have seen and done complex queries using a DSL for an ORM, in my case Django, but now you're just learning a different query language, so you're right that the ORM doesn't bring much to the table. Realistically, those who are uncomfortable with SQL are going to create poor queries with the ORM as well.
For quick prototyping and systems with limited amounts of data ORMs can speed up development quite a bit. Technically there's a cost, but computers are fast enough that it doesn't matter on the small scale.
skydhash
Before it was about “What if we need to change the database DBMS?” But now it’s more readable code and easy conversion to the language data structures. But it’s the first thing that is looked at when improving performance
nabla9
Let's add Conway's law to that:
"Any organization that designs a system will produce a design whose structure is a copy of the organization's communication structure." (Melvin E. Conway(
"The structure of any system designed by an organization is isomorphic to the structure of the organization" (Yourdon and Constantine)
Coming back to your point. How do you ensure that data structures are organized well and stay that way as design changes?
You separate data and code in organizational level. You keep the design of database schema, use cases, and mapping between them is separate from the implementation of the rest. This group also writes all integrity checks and etc. Data and code organizations are separate.
IF you don't do it this way, it's hard to separate code and data because the structure of the organization does not separate them.
ttfkam
> Coming back to your point. How do you ensure that data structures are organized well and stay that way as design changes?
It's a hard problem if not THE hard problem. Using an ORM or not has no bearing on this. Conway's Law extends to the lowest levels. If an organization changes substantially, no UI, data structure, or database schema will be left unscathed.
Solve the problems you know about. Tomorrow always delivers problems you couldn't (and shouldn't) anticipate. You'll drive yourself and your coworkers crazy by trying to cover all possibilities. It's a disease called Flexibility Syndrome.
nabla9
Your viewpoint is from someone who writes code for others.
My viewpoint is hiring others to write code. My business is tomorrow and keeping contractors in check.
Planning and maintaining data and their schemas in-house and contracting out writing code has been incredibly successful so far.
pjmlp
Stored procedures for the win.
alkonaut
My additional rule: tiny bits of wasted perf will accumulate and eventually make the program slow even though each one doesn't cost much. So don't leave perf on the table so long as complexity/readability/maintainability/implementation cost isn't affected. That is: all else being mostly equal, it's not OK to choose the slower of two options.
Also: if you assume your N's are small then you can get away with almost anything. But if you write a piece of code that is going to work well for N below 100, but suck for N over 10000 Say, anything with O(N^2), then just cap it. Make a big fat error if the small N assumption breaks. It's still better than the AWS bill surprise or hung program or whatever it could be otherwise.
cratermoon
> tiny bits of wasted perf will accumulate and eventually make the program slow even though each one doesn't cost much
Rules 1 and 2 apply here, though.
alkonaut
If you spend 100ns you spend 100ns. It doesn't matter if it's in a bottleneck or not. Note that this of course assumes that spending 100ns anywhere is actually making the program and user _wait_ 100ns, i.e. it assumes we are cpu bound all the time.
For any program that does I/O this wouldn't be the case. A "bottleneck" is going to be a network request, and for much of the programs execution time you can just make the CPU do anything without the user even noticing.
So this argument is based on CPU bound interactive programs, which isn't all programs. In programs with e.g. IO (which would be most) then rules 1+2 would come along.
But I guess the thing is that in an interactive CPU-bound program like a game, there _is_ one single bottleneck and most of the code is on that hot path. It's pretty easy to establish that you are in the bottleneck: it's when you are writing per-frame code.
gfiorav
Many of these guidelines essentially boil down to strategies for preventing over-engineering.
I concur; in my experience, premature optimization is one of the most expensive pitfalls. This primarily stems from the fact that circumventing potential issues too early leaves them unchallenged, resulting in the next team having to devise expensive solutions to address the unnecessary complexity.
The approach that was instilled in me is this: optimizations rely on presumptions, and these presumptions are often incorrect in the beginning.
Additionally, I've discovered that managing ego and understanding psychology play crucial roles in dissuading individuals from creating overly complex code.
vrosas
I like to say, “solve problems you have, not problems you think you have.”
arethuza
vrosas
Sort of, but people get defensive and start to argue that they _will_ need whatever it is at some point. But my argument is that, fine, you may be right, but if it's not needed _right at this very moment_ there's no reason to rush it in. Often the best way to prepare for the future is to do as little as possible - keeping things simple now makes adaptions much easier down the road if and when the need actually arises.
undefined
kvmet
This concept is also in-line with Lean/Six-Stuff and identifying "wastes". Overproduction (analogous to over-engineering) is usually considered the worst type of waste because not only are you making something you don't need, you're spending effort that could have been used on something that you _do_ need.
goto11
And digging a step deeper: Over-engineering often happen because you think you might need the complexity later, but it will be more difficult or risky to extend the system at a later time.
E.g. starting out with a microservice architecture even though you only have 100 users, because you think it will be too difficult to re-architect a monolith the day you hit a million user.
So you should address why it feels like the code becomes less malleable over time.
m463
Someone I know said - don't get fancy with errors. fail early and simply.
quelsolaar
Generally these are good, but in practice #1 doesn't hold.
When you start out you need to have a _theory_ about what will be you bottleneck. A lot of times you cant implement XYZ, and then measure what was slow and fix that. X, Y, and Z are connected and sometimes you need to build X and Z in a specific way, just so that Y can be made fast, and you know that Y is going to be the bottle neck. Later, when you do measure and know for a fact what is slow, you still have to make a bet on an approach that will make it faster. The more educated you bet is the better.
Good programmers measure, but good programmers have to litterate less because they can predict what will be slow, buggy, use too much memory, and make educated bets in advance, that avouid issues. If you start saying that its a rule that you cant predict performance behaviour, then you are dismissing a lot of experience and skills that good programmer accumulate.
mumblemumble
In practice, #1 is an iron rule for people who don't believe it, and a loose guideline for people who do.
Because observing rule #1 happens to be the best way to get the experience and empirical background that are necessary to develop a good intuition for where to expect bottlenecks.
sjducb
You can spike the algorithm that you think will be slow. Usually the slow algorithm is simple to implement and test.
If you’re wrong about predicting the speed of the algorithm then you’ve got needlessly complicated code for the rest of the life of the project.
People are wrong about the speed of algorithms all the time. Often O(n) and O(n^2) take the same amount of real time because the computer spent 99% of the time getting n from the database server.
Your algorithm written in C is often slower than the equivalent Python because the bytecode compiler did something clever.
I’ve spent a lot of time speeding up legacy code. It’s usually much easier than you think, and it’s slow for reasons that wouldn’t have been obvious to the original authors.
In fact it’s usually slow because the codebase got so complicated that the original author of the slow code couldn’t reason about it any more. But it’s easy for me to fix because I have a concrete example that is “too slow” so I can debug it by running the code and observing the slow points.
physicles
I love it when I find an actual performance problem with code that doesn’t hit the disk or network. Optimizing is super fun, but it’s so rarely needed.
My last time was last year. I noticed that our metrics service, which had been running for a couple years, was now often using 100% cpu. That can cause issues for other services on that node, so I looked into it. Turns out the Go code I wrote to parse Prometheus metrics was a little clunkier than you’d like for the sheer amount of metrics coming from some monitor (I think I’d just upgraded cadvisor or something). I tried getting it to return fewer metrics, but couldn’t figure it out.
So I spent an afternoon and rewrote my parser. My hypothesis was that I could make it faster by allocating fewer strings, which turned out to be correct. End result was nearly 10x faster. 10/10, super fun and satisfying.
I’ve got about a half dozen other things I’d love to optimize with our current system, but for now I can’t justify the cost.
matt_j
That’s a good opportunity to run a profiler and it will tell you pretty quick which things are taking the most time/cpu/memory.
furyofantares
I think you are (understandably) not responding to the whole quote.
It says not to put a "speed hack" in until you know where the bottleneck is. That doesn't sound like what you described at all.
If you're making a video game with tons of physics objects and you know for sure from experience that collision detection is gonna be a major problem, and this is what you're pushing the limits on, I don't think it's a "speed hack" to design the game and its systems around this.
Additionally, if you're working on something that you know is gonna be a big performance concern then you definitely want to measure it! Not to find out if it's a concern but to find out how successful you are at dealing with the concern.
e12e
Could you give a few concrete examples? I'm doubtful it makes a difference in most cases?
If you're building a new system, from new requirements - often just getting started is fine? Build, test/measure, throw-away/refactor - repeat?
Take rust as an example - start with a draft language, a compiler in ocaml. Iterate.
(I concede that Hoare might have known the project might move from ocaml to self-hosted at some point - but I'm not sure that makes much of a difference?)
quelsolaar
Sure, Right now I'm working on a Constructyive Solid Geometry algorithm, it requires me to cast a lot of rays, so i know this will be slow. I can up-front say that the Raycaster needs to have fast data structure and that its worth giving up some performance to set that data up correctly. I also know it needs to be multithreaded, so thinking up front about how to manage that is a given too.
A lot of times, I try to count the zeros. If im doing anything over the network, its going to be miliseconds, but if i do something with memory its going to be nano seconds, so optimize to take remove network requests. If i work on a problem that is multi threaded, i need to conside what can be multi-threaded and what can not. Can i minimize the stuff that cant be multi-threaded, and is there other work to be done while waiting for things that cant be multi-threaded? A lot of times I consider latency vs bandwidth. I know that Latency will always be a harder problem, and a problem hardware has harder time solving, so I try to design for low latency first, and then worry about bandwidth.
These are all architectiual decission, that are made early and have a big impact. They are VERY expencive to change, so you want to be as right as you can be the first time. If one part turns out to be slow you can profile and work on it, but changing the struecture of how the program operates and how data is stored and flows is much harder.
The author is right, that data structures are the most important tool for optimization. Especially on modern hardware where cache misses are so expencive. The problem is that _everything_ depends on your data structures, so changing them is a lot of work. (I was just at the blender conference where there was a talk about changing the mesh structure from arrays of structs, to structs of arrays, and it took them two years to make this simple change)
ska
> I can up-front say that the Raycaster needs to have fast data structure and that its worth giving up some performance to set that data up correctly.
I don't think this is a great example, really. You're going to want the brute force raycast working anyway for testing, and you're not going to know the details of what the right space partitioning approach will be until you a) understand the CSG application better, and b) have done some measurements.
So it follows the 5 rules pretty well - the only thing I'd add is that you architect the system knowing that the data structures will change for representing the collections of objects and object/ray intersection paths etc. But your first pass should almost certainly be pretty simple and slow, and you should have your measurement code implemented and testing before you try anything sophisticated on the data side. Same goes for chunking up work across threads.
physicles
> structs of arrays
It’s such a bummer that the optimal memory layout is also a pain to code with in most languages (thinking of numpy in particular, oof). Are there any languages out there that abstract this away? You’d have to give up pointers, but it’s worth it for some use cases.
randomdata
> they can predict what will be slow
If that were the case, would developer-lead startups not have a 100% success rate? After all, a function that takes hours to complete, when an optimized function could take milliseconds, is still more than fast enough if you have no users. I'm not sure anyone has actually proven that they can make such predictions accurately.
quelsolaar
No, Pro Poker player loose all the time, but they are far better than your average players becasu they make better bets, because they understand the game and the odds better. Good programers are wrong all the time, (I know i am) but they make less misstakes, and they can fix the misstakes faster, because they can predict when there may be an issue.
Also being a good programmer is not the same as being good at running a startup.
randomdata
> Also being a good programmer is not the same as being good at running a startup.
But being able to predict the future of the business is necessary to determine where to optimize. Again, if you have no users, you don't need to optimize at all –period. The success rate should be 100%, as those who predict what to optimize will know when not to go into business.
If you get it wrong, you haven't predicted anything. You were guessing.
aidenn0
1. GP didn't say that they could predict what will be "fast enough" they can predict what will be "slow".
2. A kind reading of GP would also understand that one is predicting what will be slow under some set of conditions.
3. Requiring 100% accuracy to call it a prediction is absurd. A weather forecast is definitely a prediction even though it's not 100% accurate. The NOAA isn't "guessing" weather in the general usage of the term "guess"
4. By your definition extensive benchmarking, measuring a program, and optimizing based on those results is wrong, because we don't even know if the end user will ever run the program!
mrkeen
Counter-point to 5:
Complex algorithms over simple data can have big performance payoffs, remove obstacles, and even simplify things.
For instance, binary search over a sorted array (as opposed to a BinaryTree object):
• simplifies merging (it's just concat & sort)
• no pointers, which makes serialisation easier, but also...
• bypasses the need for serialisation
• an array can be on disk, or in memory, or both (via mmap)
• the data can be bigger than your ram
• allows for 'cold starts': just point your program at the file/mapping and tell it to run, no 'loading into ram' step.
• it's also cache-oblivious
Another example is huffman coding. If you studied it at uni, you probably saw it as a Tree-based algorithm with the associated O(n logn) time complexity. I was unaware that there was an in-place, array-based method of constructing a Huffman tree in linear time.
Of course 99% of the time, I'm doing back-end microservices and just using standard collection data structures. But if I ever had a 'big data' task at work, I would strongly prefer to be able to do it on a single machine with a big disk locally rather than buy into whatever the current flavour of MapReduce is.
kagakuninja
IMO binary search is not a fancy algorithm. Modern sort functions are fancy, and can have subtle bugs, which is why ordinary devs should not write their own. Even quicksort has foot guns.
Rob Pike's response would probably be to profile the code first, then see if your fancy code or alternate data structure makes it faster.
returningfory2
I don't see this as being a counterpoint. From the perspective of Pike's advice both "binary search over a sorted array" and a "BinaryTree object" are identical. They are just different implementations of the same data structure.
rapsin4
Don't forget, you, the dev is 99% of the time the most expensive resource. Maintainability and first to market are usually way more important.
wredue
>dev is the most expensive resource
This is not true. Ask Facebook, who have rewritten things multiple times explicitly because this is not true, but someone assumed it was
>maintain ability and first to market are usually more important
Maintainability and first to market are not trade offs for performance in most cases, no matter how much you want to propagate this ridiculous propaganda.
arp242
But the question is, would Facebook still be around if they didn't "just ship this turd lol"? I don't really have any insight in Facebook engineering over the years and it's a "what if" type of question that's essentially unanswerable, but the answer to that being "no" is very plausible.
And Facebook really does have unique(-ish) scalability problems, and I bet rewrites would have been inevitable even with the best possible engineering, because who can write an application to deal with a billion users (2012, currently 3 billion) right from the start? When Facebook launched in 2004 this was pretty much unheard of, and even in today it remains pretty rare (much less 2012).
bigstrat2003
This type of thinking is what has turned everyone's "desktop" app into an Electron piece of shit. It turns software into a race to the bottom where as long as it's just good enough for users to not drop it, companies say "ok let's do it". It's not good advice to give, imo.
zelphirkalt
I would not count electron app build on top of NPM or similar as a good example of what the GP was stating.
RetroTechie
> Don't forget, you, the dev is 99% of the time the most expensive resource.
That boils down to not valuing time of the people who use your software. Despicable attitude imho.
Developer time is wasted once. User time is wasted for every user, each time the software is used, for as long as it remains in use.
All these can be large: billions of users, many uses each day, software in use for decades.
If you're the only user, no point to spend time on optimizing anything, unless you perceive it as too slow.
If software has billions of users, then almost any effort in optimizing the tiniest bottleneck in it, is worth the effort. A good example of "the needs of the many (users) outweigh the needs of the few (developers)".
A lot of software sits somewhere in between though (not that many users & performs at acceptable speed).
jd3
I first read this on cat-v 10+ years ago and it left an indelible effect on the way that I approach and think through both design and complexity
ndr
How does one go from
> Rule 5. Data dominates. If you've chosen the right data structures and organized things well, the algorithms will almost always be self-evident. Data structures, not algorithms, are central to programming.
to
> Rule 5 is often shortened to "write stupid code that uses smart objects".
"smart objects" left such a bad taste in my mouth, the original rule is so much better albeit lengthier.
cgdub
I think Rob Pike would agree that "smart objects" is the wrong way to think about it: https://commandcenter.blogspot.com/2012/06/less-is-exponenti...
dbalatero
Seems pretty clear to me, what issue are you having?
lowq
Agreed. I find that "smart objects" are much more difficult to make cohesive with one another. Punting your "smart" logic to a higher level is easier to understand, test, and change.
sowbug
Write code that naturally follows from well-structured objects.
hardkorebob
Great format. Love easy to view fast pages. Great advice too for the true hacker. Today the advice goes well but only for a small, tiny niche group. What is considered today as mainstream programming is so abstracted that speed of an algorithm is not a concern on anyone's plate when they fire up an Electron app.
lowq
One might say Electron's algorithmic constant is quite large..
eftychis
Are these quotes the reason we end up with bloated rarely optimized or respectful for memory, CPU, or other resources software systems nowadays?
https://www.techradar.com/news/move-over-chrome-macos-monter...
https://www.tomsguide.com/news/google-chrome-reportedly-dest...
A great majority using these quotes act like no engineering design work is allowed whatsoever.
I have seen that mentality permeate everything even hitting concurrency decisions for obvious things. (E.g. We need to respond to HTTP requests while doing stuff in the background, and accessing IO and run multiple server state syncing but let us have purely synchronous, single threaded code and we will figure it all out later. That went well.)
And for some reason there is a subgroup that thinks security architecture is "optimizations."
It depends on the product but when you have https://news.ycombinator.com/item?id=38029479 or https://news.ycombinator.com/item?id=38076636 it is not over-engineering: it is management and business forcing poor product.
Get the top HN stories in your inbox every day.
I love this
>Data dominates. If you've chosen the right data structures and organized things well, the algorithms will almost always be self-evident. Data structures, not algorithms, are central to programming.
I completely agree with this. Which is why all the LeetCode interviews always struck me as odd. They focus on algorithms, not data structures, which is exactly what you don't want to do out of the gate, most of the time.
I suppose, if you don't know algorithms at all you wouldn't realize when it is either
A) an exception to the rule
or
B) A time where you need to lean into specific algorithm for X, Y or Z reason
However, you can teach algorithms in relatively short order, I have honestly found people grok which data structures to use less easily, though its all anecdotal