>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
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.
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.
That doesn't actually work, because a DAG only lacks directed cycles. Consider:
/-3-> D
A -1-> B -1-> C
\------4------^
In this case, the longest path is A-C, but C will be held at level 2 by B, leaving D lowest at level 3. This works for a fully-acyclic directed graph (eg a tree), but not for a directed-acyclic directed graph. It can also find the node whose shortest path is the longest (so longest shortest path, minimax style). (It also works for a acyclic undirected graph, as illustrated at [0], but that's a bit tangential.)
Actually it works for all trees, fruit or otherwise (and also for some non-tree graphs, though I'd have trouble giving a useful category more general than tree).
>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.
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)
"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."
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?
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.
" Show me your tables, and I won't usually need your flowcharts;
they'll be obvious."
But to be fair, you need to be a pretty damn good comp sci person (and
actively thinking in algs and DS) to quickly look at DS and see the
"obvious" processing implied.
A problem I see a lot is when the flowcharts should be obvious, but aren't because whoever wrote the code didn't write the obvious solution.
Instead they wrote a horrible buggy mess that tries (and usually fails at least a little) to do the same thing as the obvious solution but with much more, and more convoluted, code.
I appreciate your particularness in this regard, and you'll have to forgive me as I've spent a lot of time with folks who are very wary of the word "data structures".
I tend to use softer words like "often" as it makes folks feel less defensive towards the discussion. If someone came up to you and told you that your outlook on something is 100% definitively wrong, you might balk at the statement merely because I said "100%". Just as you have stated "Always!" and corrected me so emphatically.
Since I've found this to be a difficult topic for some, and given this is a public forum, I chose to be cautious in my wording.
Also they're just straightforwardly wrong. For example, binary search works on a array, or on a predicate like \x->(x*x <= 2.0), or on a hash table with contiguous integer indexes, or even on a linked list. Of course it works very badly on a linked list (worse than linear scanning unless the comparison is ruinously expensive), but they didn't say "An algorithm always only works properly on a certain data data structure.".
A binary search on a linked list is a different algorithm than on a a sorted array (which is different from a generic array). In this case linked lists don’t have random access for example. So binary search on a linked list is actually not possible.
`list.get_nth(n)` has O(N) runtime, as does `list.length()`, so binary search is actually completely possible, with runtime O(N^2) (aka "works very badly").
(Fair point that all four data structures need to be sorted, though, although ideally that would go without saying, since it's kind of inherent in what binary search is.)
No, having efficient random access means that it's O(1). That just usually goes without saying, because anything that has access at all can be made to have inefficient random access. But in this case, the fact that it's (necessarily) inefficient is the point: binary search works very badly on a linked list, and you shouldn't actually use that algorithm with that data structure even though you technically can.
Conversely, using the same algorithm on a (sorted) array, (monotonic) predicate, or (sorted,contiguously-keyed) hash table works fine, even though those are three different data structures.
At that point the definition would be useless. It’s not the definition I’ve seen during my CS education, in papers and even what’s written about it on Wikipedia.
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
> 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.
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.
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.
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.
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.
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.
If you want a better data-structure you must ask: Better for whom? Better for the algorithm that manipulates the data!
So I don't think that "data dominates". You may need to adapt your data to the algorithm or vice versa. What dominates is what we want to do. Without algorithm we are doing nothing.
In a sense data is part of the algorithm, it is implicitly coded into the assumptions the algorithm makes about its arguments and results.
On the other hand, algorithms are just data. In the end it's just a set of bytes that determines what happens to other sets of bytes. Data structures and algorithms are two sides of the same thing. In the abstract meaning space in our minds, data structures are an extension of the algorithm's logic. In the memory space, algorithms are just data structures that change other data structures.
Seeing the connection from both sides is insightful.
Yes. But there is a difference between data and program. Program is data as you say but it must be data that can be interpreted as a set of possibly conditional steps. It is often pointed out that Lisp programs are "just data" but not every list can be executed as a function.
Further programs are what interpret data, by making branching decisions based on the data. Program must be interpreted by the language interpreter, and then on the 2nd level the interpreted program interprets the data.
Although LeetCode does have a strong algo slant, choosing the optimal data structure is almost always a key part in solving the problems.
If you think leetcode-like problems is always about the algo, "BFS or DFS" etc., then at best you are not realizing the data structure choices you are making, at worst you may not be so good at solving them or haven't progress that much through leetcode-like challenges.
Indeed! I've long been a fan of "table oriented programming" where the common CRUD objects are specified mostly as data. You could also create them in code by calling a RAM-table constructor, so it's not either/or. Most the data fields, navigation structure, and event handlers (or handler stubs) could be readily table-ized.
Code is a lousy place to store boat-loads of attributes. You can do data-oriented transformations and filters on them if in a data structure. Hierarchical file systems are limiting and messy, because grouping by one factor de-groups another. I want to be able to "query" dev code units via SQL or similar. CRUD patterns are pretty consistent across industries such that most CRUD idioms shouldn't need custom re-invention, and thus should be attribute-tized.
You will still need occasional code-based tweaking, and this can be accomplished by having the attributes generate "runtime draft" UI markup and/or SQL clauses, which can then be tweaked via code as needed.
I'm building a proof-of-concept that uses what I call "fractal rendering" to be able to intercept the "draft" construction of screens and SQL clauses at a fine level or course level, depending on need. This avoids the all-or-nothing problem of prior attempts per attribute-vs-code debate. Ya git both! (Dynamic SQL generation should probably be avoided for public-facing sites, per injection risk, but limits the wonderful power of query-by-example.)
I don't claim it will be as performant as the code-centric approaches, but if it catches on, performance tweakers will find a way to scale it. (For CRUD apps, the performance bottleneck should usually be the database, not app code anyhow, unless you doing something wrong or special.)
The CASE tools of the 1980's and 90's started going in this direction, but were too expensive & clunky, and then the OOP push ended the idea by favoring attributes-in-code, back to square one, sigh. (CASE tools don't have to be proprietary.)
It's ripe area for groundbreaking R&D. CRUD may not be sexy, but it runs the world.
> 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.
Which is one of the reasons why I will never use that style of problems as an interview question.
And the other reason is: that style of problems also don't teach anything about architecture.
> Which is why all the LeetCode interviews always struck me as odd
90% of leetcode is choosing the right data structure. If your algorithm doesn’t wanna come together, you probably missed a better way to model the data.
I had a checklist one time for interviews. One of the items was: "consider data structures x, y, z" - only maybe 4 or 5 data structures. It worked 95% of the time.
> >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've been thinking about it a lot. I want to still believe it, but then my experience tells me that the "right data structure" is usually "the data structure most convenient for the operations/algorithms you want to run". Which makes this principle either backward, or circular.
The right data structure is the one that's produced and consumed in a way that matches the domain you're trying to model. That domain can be inputs to a particular algorithm, but it can also be things like "states of this system" (constructors correspond to state transitions), "witnesses to this property" (constructors correspond to valid inferences), etc.
Leaving aside the unusual, to me, meaning of "domain" in this context, your description matches what I wrote above: the right data structure is determined by what you're planning to do with the data.
It only convinces me further that Pike's take is wrong. Specifically:
- "Data dominates" and "Data structures, not algorithms, are central to programming" are just plain wrong;
- "If you've chosen the right data structures and organized things well, the algorithms will almost always be self-evident" is correct only in the descriptive sense, not in the prescriptive sense. That is, it only works when you read it as restatement of Brooks's "tables vs. flowcharts" line (quoted elsewhere in this thread): it's easier to guess what your code is doing from how you organized your data, than it is to guess how you organized your data by looking at the code. I.e. it's an advice on where to start understanding someone's existing solution; it has nothing to say about solving new problemms / writing new code.
But the distinction is meaningless. A data structure is just a collection of algorithms for working on underlying memory. More complex algorithms are built with simpler algorithms as building blocks. With that in mind, it essentially boils down to picking algorithms which when put together allows solving the problem in an as easy way as possible.
Which of course is self evident. Though I suppose it doesn't hurt to remind people to step back and look at the full picture.
> 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.
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.
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.
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.
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.
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
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.
> 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.
I have a hunch that this is quite rare in most companies. Most managers are unskilled enough to override their own intuitions in favor of the mediocre leetcode dev that just vetoed a strong engineer.
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.
> 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.
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.
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.
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.
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).
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.
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.
> 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.
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.
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".
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.
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".
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.
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.
> 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.
> 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.
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.
> 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
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.
> 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.
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.
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.)
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.
I guess the way you describe it is the way I like to work, keeping my object model in code close to the relational model to minimize the mental and performance cost of mapping back and forth, and using a SQL library to minimize boilerplate. I don't think of it as using ORM because my favorite tools for working that way don't bill themselves as ORMs, but I'm not sure what I'd use in Python other than SQLAlchemy. Even projects that seem to be stripped down non-ORMs like SQLModel turn out to be built on top of SQLAlchemy.
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
"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.
> 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.
For what it's worth, most of my time is spent inside the DB, not app code. I learned long ago that once bad data gets in, it's far harder to get out and trust the system again. Best defense against bad data is a well-designed, strict schema. In other words, proper data structures.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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?)
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)
> 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.
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.
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.
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.
> 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.
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!
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.
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.
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.
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.
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).
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.
> 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).
> 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.
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.
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.
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."
On my first Amazon interview, I'm pretty sure I bombed because I brute forced the algorithm question.
In the real world, when we have an issue on production, I fix it first, then find a solution. Meaning in that first hour customers are complaining, I'm not gonna try to create a fancy algorithm that can handle all cases. I'll make it work with nested loops if need be. Then I can sit down and figure out a permanent and elegant solution.
Yup, when I was interviewing for Google I was expecting basically the same. I would like you to work though the problem and come up with something simple, bonus points if you noted places that could be buggy, slow or anything else. Then we would look at it and discuss what could be improved and if we had time maybe even make those improvements.
I could really care less what Rob Pike things about programming rules, coming from the person who things capitalising is a great way to export things, ignoring that capitalised characters are mostly just a Latin thing, and so the whole concept of his toy language is just that... forever a silly toy language.
its a shame that you would toss away an entire language because of a small gripe. I agree that the case thing is annoying, but Go has many strengths and is broadly useful in a variety of situations.
when I started C++ was the "defacto" language, even taught in schools. for many years I avoided programming and I didn't know why. once Go came along it all clicked. I avoided programming because languages like C++ are awful. I could give reasons but people mostly know what they are. Go is great because its mostly simple, and the dev team is not afraid to "say no", even aggressively, if a feature is not strongly useful. plus the tooling is better than most languages one might come across.
Unfortunately, Rob didn't stipulate what "fancy" means. For instance: A* is definitely fancy, but it's neither buggy nor particularly hard to implement. And because of what it solves, there isn't even a simple alternative to it.
I'd probably replace "fancy algorithms" with "self-invented algorithm" instead: you're not solving a new problem, resist the urge to "tackle it yourself" and just look up the almost-certainly-decades-old, and documented-by-thousands-of-people algorithm that's going to get the job done.
(Of course, that'll be less fun for you, but if the only person who appreciates a piece of code you wrote is you, that's one of the signs that you wrote bad code.)
These are all correct and good advice, but I suspect most people misinterpret "avoid premature optimisation" style advice as "don't bother to write efficient code".
Caring about basic efficiency, and being thoughtful about compute is _not_ the same as premature optimisation. This kind of wastefulness in modern software is what causes death by 1000 cuts style inefficiency, it's not because we aren't optimising, it's because we are wasting.
I call this premature pessimization. Often we know of the best algorithm, so not using it is wasteful. Often not making many copies is easy in the language but we do it anyway.
I think the wastefulness comes from people imposing a top-down structure on the code before they have a working system. If you first write stupid simple code that solves the problem, then identify areas that need to be faster, you won't have layers of abstraction getting in the way of optimizing it.
>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.
Isn’t this a plug for some sort of object oriented programming? Or at least highly structured programming? Interesting in today’s trendy clime of “objects bad/passe, function(al) good.”
Having done quite a bit of OOP where “binding behavior to data” is the thing in an ideal laboratory for it (Smalltalk and others), I gained some experience with watching people do this. I observed that there were plenty of good ideas across the industry on how to model data (inheritance, prototype, classification, mixins, mutability,etc), but what I observed is that which data groups together well is very much an art, and that was where people struggle to succeed with the data centric emphasis. The easy objects/structs are of course easy, Point, Rect, Person. But as the data got more complex, getting people to come up with good boundaries gets more and complex quickly, and you ended up with really poor object constitutions. Reification is hard. I don’t think it is impossible, I’ve seen people who have a knack for reification come in a refactor an object soup into a cluster of data structures that was beautiful. But yeah, good reification I fear is as much an art as science.
> Isn’t this a plug for some sort of object oriented programming?
No. You see the same thing happen in SQL database design. How you lay out the tables has a profound effect on the final application. Or indeed in database engines. Some use write behind, some write ahead, some log structured. In fact you can often predict how well they will do locking, perform on writes and mass inserts by knowing what datastructure they chose on day 1. Possibly the best examples are in source code control. Git won, yet git has a very ordinary API (command line interface). Git won because Linux used content addressable memory as his underling data structure, and it turned out to be an inspired choice.
The other side of the coin is once you've decided on a data structure, it's often damned hard to change. Thus one Linus chose CAM, git was going to live or die on that choice. Once there were a few git repo's out there, changing it got very hard. Changing the API is not so hard: add a new one, depreciate the old one.
I find the statement is true for either object oriented or functional programming.
As someone who has done both extensively, I find that the patterns are still applicable to both. The presentation is very different, but still viable. For instance, you might use recursion to traverse data over a for-loop, but that doesn't inherently change the concept of a data "structure".
No matter what, we're still speaking in design patterns and if we share that common language, we can apply it to a domain and solve the larger problems of our day-to-day.
If you want more examples of this, look up Data Driven Development, but also append Haskell or C++ to your search queries, you'll find they repeat the same concepts in two very different "grammars"... ahem... I mean "languages".
Yes, given the downvotes, I fear my comment may be misconstrued as a function(al) bash. I write lots of Elixir these days. And see the same issues. All I was trying to say is that, my experience in OOland, that was hyper focused on this idea, gave me lots of opportunity to see that while this rule is obvious and good and everyone wants to do it, I observed that for many programmers decomposing complex data structures is a very non-intuitive task, and difficult to actually realize this rule.
The downvotes are most probably becasue data structures have nothing to do with the concepts of OOP. the datastructures stand on their own and have been present long before the concept of OO came about. yes you can model them as classes/objects to incapsulate the set of operations that you can do on them but it's not mandatory and certainly does not require any concept of inheritance, mixins etc.
Rule 0: you often can predict where the program is going to spend a lot of its time; don't use rule 1 as an excuse to be completely CS-ignorant. Likewise, don't use rule 3 as an excuse to use completely lame algorithms; "not fancy" doesn't mean Bubblesort. Unlike Pike in 1989, you have libraries.
> 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.
As a corollary, types are important. If everything is a string or a hash table, then things won’t be so self-evident.
One more that I've heard just recently: "If your code is just juggling with pointers/references, it is likely that it isn't doing much useful. It is only when it starts dealing with actual values that it is starting to do something useful."
“Make it work, then make it beautiful, then if you really, really have to, make it fast. 90% of the time, if you make it beautiful, it will already be fast. So really, just make it beautiful!”
Then when he designed Go he made the act of data modelling akin to having one hand tied behind your back, because it supports only product types and not sum types too.
Fair enough but I'd say this thread can only be considered such where it veered into "Go error handling". My data comment if cheeky was relevant to the quote.
Your comment spawned a generic flamewar-style tangent that lowered the discussion quality enough that we got email complaints about it.
Btw, the site guidelines also include "Don't be snarky." - I realize that takes some of the fun out of posting a particular kind of comment, but people tend to overrate the quality of what they post when they post that way, and tend to underrate the degrading effect it has on discussions, and that's a double whammy of badness. Having a don't-be-snarky rule, and sticking to it, is a way of globally optimizing for fun—specifically the fun of interesting, curious discussion. That's more important than the sugar rush of being "cheeky".
It's not 75% of the code-base. During the error handling proposals, the Go team analyzed a large corpus of Go, and it turns out people drastically overstate how much error handling contributes to the line count.
It does make me wonder if the fact that people feel this way says something about how much cognitive effort is consumed by error handling and that it might be disproportionate.
Error handling is something you always need to think about for serious code, but often feels like unnecessary work and boilerplate for exploratory programming or simple hacks.
Buggy "edge case handling" is the source of many critical failures[1]. Go makes explicit where a called function can return and also provide information for any anomalous conditions encountered. The alternative of just pretending like a return means success is wrong, and other ways to determine if the result of called function is acceptable (e.g. checking errno in C) are just as verbose and introduce other failure modes.
Here's a thought experiment for you: pretend the return type is something other than 'error': result, statuscode, responseContext, anything that doesn't imply failure. Would you then suggest handling that is "noise"?
ETA: "there are countless other [than if err != nil] things one can do with an error value, and application of some of those other things can make your program better, eliminating much of the boilerplate that arises if every error is checked with a rote if statement."[2]
> Buggy "edge case handling" is the source of many critical failures[1]
And to fix this, we introduce 10 places per function to improperly unwind the stack, have a chance at missing an error result, and completely ignoring that fact that anything can fail anyway, even a simple addition. Instead of just writing exception safe code in the first place.
Is kind of an understatement. If the handling code for that is duplicated as 75% of your code base, there's something wrong with the language. There's got to be some other way than all that noise.
Explicit error handling is a design choice, not a language defect. If you don't like it, you don't have to use the language. Many people choose to use explicit error handling even in languages that support exceptions. Knowing that every function call returns a value that is handled locally makes it a lot easier to reason about your program and debug it.
Also, this 75% number sounds made up out of thin air. If your program is doing something non-trivial, it should have far more code doing work than checking errors.
I asked a Go programmer how much of the code base was Go error handling boilerplate. He measured it and said 75% I suppose it varies from code base to code base. There’s no denying it’s high though.
> handled locally
Except in practice, you don’t. You just keep returning the error up the call stack until something handles it at the top, probably by trying again or more likely just logging it.
I recall reading back in the 1970s or 80s that error checking and handling took 80% of the lines of code of production-ready software. That would be pure procedural code, not exceptions, not FP style. (And that's all I've got - one hearsay-level report from decades ago.)
I have not, ever, seen any numbers for exception style or FP style. My perception is that their numbers might be lower, but I have no evidence, and I am not dogmatic about my guess.
I can't really imagine 80% error handling for the whole codebase unless literally all of your functions look like this:
int foo(Data *data) {
int error = do_some_io_request(data);
if (error) log_error(error, "Request failed");
return error;
}
For propagating errors up the stack, the ratio is only 50%:
int error = foo(data);
if (error) return error;
For the rest of your code, I guess it's domain specific. But most projects should have a significant amount of the codebase doing things with data in memory that can't fail.
Alternative is using result or either monad and have first-class support for nomadic operations in the language so you don't have to waste three lines on every function call just to propagate the error up
That's just a hard-core technique for sweeping noise under the rug. It helps with this and similar cross-cutting concerts, but at a huge cost elsewhere.
We are unlikely to improve on this until we finally abandon the idea of working directly on a single, plaintext codebase.
Can you please explain, how exactly is this sweeping noise under the rug? Type system still forces you to explicitly handle the error case, one way or another.
Monadic techniques let you hide most of the noise coming from passing around the Result type, especially in code that would only pass the error state through. You still need to handle the error case explicitly somewhere, but you avoid writing error checks and early returns everywhere else. I say it's sweeping under the rug, because you still can't exactly ignore the presence of error handling when not interested in it, and the extra complexity cost of monadic mechanisms themselves still pops up elsewhere to ruin your day.
That's exactly what sweeping under a rug is. When you use exceptions, you throw type safety out of the window and have an implicit spooky dependency at a distance between one place in the code that throws an exception and another that catches it.
There's nothing magic-like with exceptions, and no spooky distance. It's what it looks like when you _really_ assume everything can fail. Go admits that with panics.
Of course there is. If you throw a FileNotFoundError exception from function readFile(), you have to actually read documentation or it's source code to know that you have to catch this exception when you use it (in most languages except like early versions of Java). Type system doesn't check it for you. And if at some point readFile() also begins throwing InsufficientPermissionError exception, the type system, once again, doesn't tell you to fix the code that uses it.
If that's not the spooky action at a distance between the place where exception is thrown and where it should be handled, I don't know what is.
>Checked exceptions need to be declared in a method or constructor's throws clause if they can be thrown by the execution of the method or constructor and propagate outside the method or constructor boundary.
This is like... the one thing that Java did absolutely right, but for some reason it's also the thing people hate most about it? I've never understood why.
No parametric polymorphism in exception specifications. Like if you have a record parser that invokes a user-defined callback for each record, then you literally can’t type it in such a way as to allow the callback to throw exceptions (that the caller is presumably prepared to handle, having provided the callback in the first place).
To be clear, this is not simple. It seems to me like it’ll quickly go into full-blown effect typing territory, which is still not completely solved today and was in an absolutely embryonic state in the early 2000s.
Aside from issues with the type system and composability, it's just an impractical idea that stops working smoothly in anything bigger than toy projects.
From a caller's perspective, "res, err :=" and "throws Exception" is the same thing: you need to handle the error on site, which (in contrast to the Go gospel), is not a good thing. In the absolute majority of cases it can't be done sensibly there, you need to pop it up the stack to a place which has more context. Certainly, it's none of a method implementor's business to decide "if a client can reasonably be expected to recover from the error". You know nothing, Jon Snow.
Java has figured out it's a bad concept decades ago, but Go is frustratingly re-enacting Java's early mistake. At least, redeclaring a checked exception was a simpler way of dealing with the error than Go's err ceremony.
Typically, that happens at the top layer. The API, the UI, etc. All layers in between don't care, and should not care, about this, other than correctly cleaning up. But it's not "distance". Also, it makes the correct thing easy ("catch Throwable").
Specific functions where returning a tuple of error and something else makes sense are always free to do so. Why does their existence mean that the other 95% of functions that can error need be given the wrong return type and pretend to return a tuple when they never do? (i.e. some element of the tuple will be garbage, euphemistically called a Zero Value)
> Why does their existence mean that the other 95% of functions that can error need be given the wrong return type and pretend to return a tuple when they never do?
They don't, do they? One really nice thing about Go is writing and calling functions that _don't_ return any error. You can be confident that they will not throw any exceptions at all.
It's not great in some cases, but "one hand tied behind your back" really is overstating things. In most cases you probably should limit things to simple types and collections (primitives, simple collections such as structs and arrays), using more complex modellings like sum types only when there's no other good solution.
If it's considered advanced, that's only because it's been left out of many languages and so people have unfamiliarity. It's the dual of product types, the other side of the same coin.
If I see that a value can have two or more types then obviously this is "more advanced" (or perhaps better, "more complex") than if it's just one type.
Sometimes this makes things better. Sometimes it doesn't.
Of course it's possible and people can "cope". A lot of things are possible and people can "cope" with a lot of stuff, but that doesn't mean it's good, isn't overly complex in some cases, or is the best solution.
This is just a dismissal instead of an argument, and one that can be applied to almost anything.
sum types are awful for data modeling once you put them in an array. So much wasted padding around the tag bit, and wasted space to allow storing the largest variant
Bad advice IMO. Not because it's wrong - it mostly isn't - but because people will hear it and think "ah I don't need to consider performance at all until... later".
His first people is not technically wrong but it is highly misleading. Sure you can't know which bits of a program are going to be slow without measuring, but that doesn't mean you have no clue at all. You can often make a very good guess!
Yeah I find the first few rules here ... fit for a very different era.
Back then, some devs would do something much more complicated to try to be faster, and often the overall program was worse off.
Nowadays, some devs do something much more complicated, make the program 100x or 1000x slower than the simple obvious way, and think they're doing solid engineering because they're definitely not "prematurely optimizing", they made it so slow and convoluted that you could never accuse them of that!
In my experience, those 1000x slower situations are because people cobble together things without understanding their underlying performance characteristics, and there's usually a bunch of defensive copying and other redundant working going on that just keeps getting compounded. Also, dynamic languages that don't have good VMs can end up boxing even the basic numbers in the language, so everything is crazy slow because the very bottom is allocating boxes all the time and hunting for properties in polymorphic objects. In JS, some frameworks are so poorly designed that they abuse objects in ways that make it difficult for the VM to make it fast. So even reasonable-looking code is crazy slow because of hitting hidden slowpaths in the JS implementation.
Another thorn is hiding RPCs, DB queries, and other remote operations behind abstraction boundaries. When people think that .getFooBar() is as cheap as a field access, they have a tendency to not cache+pass forward, but just recompute it, which ends up generating a large amount of redundant queries. That will rack up your 1000x's pretty quick.
wow, I didn't get that impression at all. And he clearly does say "Measure", not "shut off your brain".
I would assume that if you measure enough things and code enough you may start to get a feel for what is going to be expensive and what is not. And then - as before - you can continue to measure and iterate.
(Also, I think you said "first people" when you meant "first point")
> And he clearly does say "Measure", not "shut off your brain".
Yes but he doesn't say that if you don't measure (which most people won't) then you should still engage your brain.
That's the missing point. Measuring is typically more effort than applying a little brain power and experience. So the choices shouldn't be "measure or nothing", but that's how people always interpret it.
The key thing that drives rule 1 and 2 is the assumption in rule 4: all other things being equal, terser code is easier to work with. The cheapest code to maintain is the code that doesn't exist.
Therefore, given a choice between writing a little code to make the program work or writing a lot of code to maybe make the program work faster... Write a little code and go back and write the longer code iff it will actually help performance as per measurements. You're better off expanding a simple skeleton than moving bones around in an already-complex assembly.
I don't see Pike recommending one ignore performance and I assume given the target audience for the advice, the audience is assumed to know that you can't ignore performance in the same way that a chef knows you can't ignore presentation.
The focus of the advice to me is that software engineers frequently overestimate their ability to predict performance bottlenecks and efficiently allocate time to preemptively address them in the middle of writing the core of the system (for multiple reasons, including both the overall complexity of a complete system and the fact that performance is also a function of the way users interact with the system).
I've built multiple systems where a component we never expected to become a bottleneck becomes the bottleneck because users choose to use the machine in an extremely novel way relative to our intent when we built it. Getting the software in front of users to get signal on the difficult-to-predict user factor was consistently a better use of our time than swapping out a functional n squared algorithm with an also functional n log n algorithm on a piece of the system that no users were operating with yet.
> I assume given the target audience for the advice, the audience is assumed to know that you can't ignore performance
That's why it's bad advice! Perhaps I should rephrase: it's not incorrect advice (to the right target audience), but it most definitely is inadvisable advice.
Who is the audience for the famous "premature optimisation" quote? Maybe originally it was "people who know you shouldn't ignore performance", but it definitely isn't now.
Easily misinterpreted advice is bad advice in my book.
> Sure you can't know which bits of a program are going to be slow without measuring, but that doesn't mean you have no clue at all. You can often make a very good guess!
You can make a good guess! Just, measure it to be sure before you start optimizing.
No, that's my point! Measuring is good, but some things are obviously slower.
For example preallocating arrays. You don't need a benchmark to tell you it will be faster because it literally can't not be.
Another example from my recent real life: I changed a data structure from a hashmap to an array with integer keys. I didn't profile it because can't not be faster. And I knew it needed to be fast because it is called for every branch in my program.
> For example preallocating arrays. You don't need a benchmark to tell you it will be faster because it literally can't not be.
This assertion is false for JavaScript arrays in the v8 engine in some contexts. Preallocation of a JS array causes the engine to make a heterogeneous array, which is more expensive because it's an object under-the-hood. Allocating the array using repeated `push` calls of homogeneous data lets the engine know it's a homogeneous-type array, which is an "exotic object" that can use more optimal representations under-the-hood. (Faster than both is preallocating a homogeneous array, although that of course requires us to know what kind to preallocate).
This is another example of where premature optimization can lead a developer astray. Abstractions are far too complicated these days, and it's too easy to guess wrong without hard data.
Forget everything you have learned about the famous BigO analysis for 99% of the cases because it assumes a computing model that is no where near what we have today. It was close in the 80-s but now it's totally wrong.
the most glaring example i can offer is that nowdays for example a datastructure based on a linked list will almost always be slower than one based on arrays even though the BigO analyses says otherwise.
CPU cache plays a much bigger role and it pays more to chase a consistent cache access rather than jumping all over through pointers and thrasshing the cache.
likewise most algorithms would be faster looping through all array items rather than for example using a set or hashMap when number of items is small (and by small we are still talking about hundreds of elements, the exact number when one datastructure becomes better than the other will depend on many factors.
that's why, don't assume but measure, it's the best advice there is.
Well, yes I can because I know everything you just said already...
> a datastructure based on a linked list will almost always be slower than one based on arrays even though the BigO analyses says otherwise.
Cache locality is one reason that linked lists are usually slower, but I think you've got a bit mixed up because the big O analysis also says they'll be slower (in most common cases).
> that's why, don't assume but measure, it's the best advice there is.
You missed my point (thus proving why this is misleading advice!)
May not be very popular of an opinion, but rule #1&2 have been used as a crutch to create bloatware and slow as dogshit software that is always dismissed under a guise of someone is going to find the time to retroactively implement some tracing and introspection system and then rewrite portions of the application in magically isolated interfaces that will make the slow POC fast. It very rarely happens and is usually in the form of a complete rewrite that is forced onto a short timeline so.... you can't possibly be so new as to prematurely optimize! (just rewrite it in a new stack it will solve it somehow)
*edit to offer something less whiney
I think optimizations that rely on specific non-core business rules are a root of evil - but you should still be properly indexing your queries, not doing them in loops, trying to make parallel work run in parallel, not write a ton of junk over the wire when ever you can, be conscious of nesting any loops and generally the best optimization is even listed: choosing the correct data types for a problem.
> you should still be properly indexing your queries, not doing them in loops, trying to make parallel work run in parallel, not write a ton of junk over the wire when ever you can, be conscious of nesting any loops and generally the best optimization is even listed: choosing the correct data types for a problem.
I don't think anyone disagrees with that, but the indexing is a good example of "measure, don't assume" because SQL engines can do surprising things, and the best way to know what to index is just to measure (and sometimes no index is actually best!)
And "completely pretend performance is not a thing" is of course the other extreme from "optimise everything from the get go".
Unfortunately there are always people who these sort of "rules", "laws", and "best practices" as cudgels to beat other arguments with, rather than some loose commentary (which is usually what it is). Previous comment: https://news.ycombinator.com/item?id=36417264
Most of those are bad. I don't know why people keep rewriting and perpetuating those rules.
For #1 and #2, well you should know beforehand. Don't you know what your software does? The details of how the time is spent surely will be surprising, and there may be a hidden bomb here or there, but if you can't see from the requirements where most of the time will be spent, you have a problem that you should work on fixing.
Of course, that doesn't mean you should go and optimize it. You should have an idea of your implementation performance before writing it, and you should be able to tell if it's acceptable. But heavy optimization does need profiling.
People are repeating that bastardization of the "avoid premature optimization" for decades. Go follow the original, with its nuance; those generalizations are trash.
On rules #3 and #4, the fancy algorithm is usually already written and well debugged. Go use it. The performance when n is small usually doesn't matter. If it's not written, then go read the thing about optimization. You should know how big n will be. If you don't know, ask around.
Rule #5 is the only one that actually stands without much nuance. There are exceptions, but not many.
As for #1 and #2, you really DO need to measure. Over the years I've spent a lot of time optimizing other people's code and many performance problems are quasi-bugs. Doing things like inserting data into sorted data structures (as opposed to doing all your inserts and THEN sorting) aren't so much "This is an obvious hot spot from the problem definition" as "A poor decision made this a hot spot."
Profiling finds this sort of low hanging fruit quite easily.
So, you had a performance bomb somewhere. That doesn't change the fact that you know beforehand what kind of problem takes a lot of CPU time and what doesn't.
Profiling doesn't find things of the kind of "this takes a lot of computer time, we should program everything around it"; "this takes a lot of computer time, are you sure we can run it profitably?"; or "this takes a lot of memory, are we willing to get new servers?". Besides, the worst moment to optimize your code is after everything is written and people depend on its interface.
Profiling is some duck tape you can use to cover small problems, and mostly only that.
> you know beforehand what kind of problem takes a lot of CPU time and what doesn't
Do you? Do you really know the ins and outs of the optimizations of the CPU you're going to be running on? If you do, you're in a specific domain that may not match to many other developers today.
Modern CPUs are incredibly complex machines running emulation of a PDP-11 single-threaded architecture. If you're starting from the beginning with a belief that you know what the source code you write is going to do on the CPU to a level of precision that means you can skip rule 1 and 2... Most people who believe that are flatly wrong. And if you aren't, you're probably doing embedded computing, which follows its own set of rules (Rob's rules are a lot more tuned to business, cloud, and consumer-desktop-environment computing).
> the worst moment to optimize your code is after everything is written and people depend on its interface.
Honestly, that's exactly opposite of my experience. The interface is designed apart from the machine, and as a software engineer it's my job to fit the machine to that interface. Because the user matters most.
> How do you differentiate code that is using the wrong data structure from the one that is solving a hard problem?
You don't until you have to. At the limit, every piece of code is using the wrong data structure; the hardest problems get addressed by building custom hardware to maximize speed by stripping away every other possible concern in the transformation of the symbols and building as many of those as you possibly can force to work in parallel.
Almost nothing is that important, so when your program is too slow, you search for what is taking the most time and do the cost/benefit analysis of re-representing the problem in a way that matches the existing hardware better (which encompasses everything from requiring fewer steps in the computation to caching the right data to caching the right data in the right location, i.e. L0-L1 cache performance, all the way to, sometimes, pushing the computation onto a GPU or out into multiple parallel execution nodes in a cluster if the problem demands it).
None of this is black-and-white and there are degrees. You can certainly, during the design phase, look at a problem and go "That's probably going to want a cluster." But the point of Pike's 1 and 2 is "If you don't have a firm reason to believe a more complicated approach should be taken, err on the side of the simpler approach because it's easier to grow a simpler approach than move a complicated approach."
> At the limit, every piece of code is using the wrong data structure
So, at the example you commented earlier, you inspect every single function, sorted by execution time until the program was fast enough?
> do the cost/benefit analysis of re-representing the problem
How do you do that without knowing the speed you can get with another representation? You rewrite it on every possible way and test?
> But the point of Pike's 1 and 2 is "If you don't have a firm reason to believe a more complicated approach should be taken, err on the side of the simpler approach
Yet we are what, 5 messages down a thread where people vehemently deny you can't have reason to believe anything.
> Yet we are what, 5 messages down a thread where people vehemently deny you can't have reason to believe anything.
No, nobody's denied that at all. https://news.ycombinator.com/newsguidelines.html "Please respond to the strongest plausible interpretation of what someone says, not a weaker one that's easier to criticize. Assume good faith."
The argument made by eschneider and reenforced by myself is "People usually guess wrong when they try to add performance optimization at the design phase," not "epistemology is dead." It's a soft rule from experience, not a black-and-white hard rule; most everyone who's been programming for years has a story about the time they built a complicated gadget that ended up being a waste of time because it either wasn't on the critical path where the bottleneck showed up or users didn't choose to use the software in a way that aggravated that bottleneck anyway.
I'll share my own. Way back in the day I hammered for weeks on getting the physics model right for a nascent game engine. Started from an open-source option and then beat the hell out of it because I knew physics was likely to scale badly, was easy for developers to "hold wrong," and needed to be plug-simple to use and understand.
In the end, 95% of our users only used the game engine as a rendering architecture and never turned the physics engine on. All of that optimization time was zero-business-value.
> you should know beforehand. Don't you know what your software does?
If you think you know beforehand without measuring it I suggest you do measure it now and then. Because if there's anything I've learned about performance it's how terrible one's intuition can be about performance.
> The performance when n is small usually doesn't matter.
Sure, when the problem is simple enough that there's only N and not also M and K.
Oh, sure, I'm not saying you shouldn't measure. What I'm saying is that you should know beforehand (with much less precision), and on the are many decisions you have to make you should apply that knowledge, and not go with YAGNI every time without questioning it.
YAGNI is not at all a good principle. It only works as a slight bias. If you use it as any stronger kind of rule, it's disastrous.
I never voiced my opinion on programming much because i am self taught and i do C++, a language with a tendency to make you feel that you don‘t know much in general. Its just a feeling but i think you are right.
>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