I don't think the author's interpretation of #5 to mean use smart objects (which I'll guess means objects in the object-oriented sense) is correct. I interpret Pike's meaning to be to use dumber objects that make the data visible and obvious. That's also consistent with Go's emphasis on simple datatypes.
It's very close (in my opinion) to a restatement of Brook's quote "Show me your flowcharts and conceal your tables, and I shall continue to be mystified. Show me your tables, and I won’t usually need your flowcharts; they’ll be obvious."
No, it doesn't mean objects in the object-oriented sense. It means something more like "don't build an array and then iterate through it to get the minimum item, if you could just build a minheap." I.e., if you can, use data structures that do the heavy lifting of your algorithms "for free."
Total tangent, but it occurs to me that if all you want is the minimum item, you maybe don't even need a minheap. You can just keep a single item--the smallest--and replace the operation of adding to the array with the operation of compare-and-possibly-replace.
Exactly. There seems to be a huge amount of confusion here about this. Beyond that quote (which is excellent, btw) there's the point that creating machine-efficient data structures requires understanding the limitations of the architecture and packing the data in a way that it can be accessed efficiently by whatever algorithm you plan to use.
Things like whether you have an array of structs or a struct of arrays can have a massive effect on how the same algorithm will perform, because of factors like data locality, alignment and cache coherence (the latter mainly if it's a concurrent algorithm).
The trouble with studying algorithms without actually working on optimisation in a low-level language like C or Go is that it completely abstracts away what is really happening in the hardware, which is absolutely critical to real-world performance. In a LISP-like language you generally have no idea what the compiler is actually doing.
No, that's almost diametrically opposed to the intent of #5. I'm not even sure object programmers know what a data structure is. Likewise, using a minheap because you sometimes need to find the minimum value of an array is the opposite of #4.
I feel torn about the "premature optimization" stuff. On the one hand it's clearly true that we're terrible at predicting bottlenecks and it makes no real sense to second guess them at any fine level of detail. On the other hand, I think about products that I love to use and they are all fast. I think about the first iPhone and how utterly crucial that first user experience was. Did they achieve that by just writing giant gobs of code and then circling back afterwards to fix a few hotspots? I think about how Chrome was such a delight after FireFox got slower and slower and more bogged down. Clearly, Chrome was written from the ground up to avoid that. I am not so sure you can really optimise for performance after the fact, at least not universally. There are times when you have to build it into the very fabric of a project right from the start. Once a project has a giant mass of moderately slow code, there's nothing you can do except rewrite it to get better performance.
Yes, that is exactly what Apple did with the iPhone. They wrote the interface then tested it over and over again and made optimisations on every iteration.. This was before it was released to the general public.
The article is talking about optimising before you can prove where the problems are... Apple had excellent testing which showed where a lot of issues were. Some issues may well have not been discovered until a wider audience had access though.
Testing can happen before you release a product you know? You new fangled startup MVP types only think good testing happens on paying customers. Fuck you guys.
To me premature optimization goes far beyond just speed: it's a judgment call, and it affects everything we do as programmers.
Should I spend more time here making this variable readable? Should I structure this script to be maintainable, or is it going to be of no use in 2+ weeks?
Sometimes the answer is yes; sometimes the answer is no. The key is not to pre-maturely optimize. You have to use your own good judgment and an iterative problem solving process to figure out what the metaphorical bottle neck is and fix it (I say metaphorical because, again, it's not just about speed).
Yes - I think this is what I was trying to express. I guess I think the message about premature optimization is much more subtle than usually accounted for. It's about decisions to introduce complexity, to sacrifice design integrity, etc. in favour of performance.
But it is not about devaluing having a careful discipline and intuitive sense of the performance of code and a rigour about how you think about performance in your work. All those things are still incredibly important.
I think there's some truth to this. The assumption that there will be low hanging fruit in the profiler when you eventually start worrying about performance isn't always true.
Also, the more you worry about writing performant code, the easier it will be for you to write it that way in the first place without making sacrifices in code readability or maintainability. It's a myth that high performance code is always more complex and error prone. If performance is always something put off as something to address later, you can end up with as you describe 'a giant mass of moderately slow code'.
What I do agree with is that picking the correct data structures has more of an impact that algorithm noodling, though that has it's place.
I think the take away is not "do not optimise at all ever"
it's about not just optimising your code, but optimise the time you spend optimising it. Do not spend 2 weeks micro-optimising a loop that, in reality, has no effect on the end user's experience, and ultimately makes the code base just much more difficult to maintain.
What you want to do is try to get most of your FINITE and EXPENSIVE development time on optimising things that actually matter to user experience.
It's completely orthogonal to that. It's not about what language you are using but about how you write the code in that language. The "premature optimization" thing can easily be intepreted as "it's OK to be lazy" and I think that's a misinterpretation.
Just making up an example, often I need to return multiple values from a function in languages that don't directly support that. The pure & efficient way might be to make a new data structure and return that. The "lazy" way is to just stuff them in a map / dictionary / hashtable and return it instead. The cost of those key-value lookups is enormous compared to a direct field lookup, but I can rationalize it as avoiding "premature optimziation". But if you end up with a whole code base that is doing this, eventually the whole thing is operating an order of magnitude slower than it should be. (it's also going to be a nightmare to maintain and refactor, but that's another story ...).
It's not okay to be lazy. But it's wise to prioritize architecture over performance until you have numbers to show you where you should put necessary optimizations. In my experience, optimized code is almost always harder to work with, so there better be a good reason to write it that way.
It's a lot easier to optimize well-architected code than to re-architect optimized code.
If you find yourself regularly having to force that kind of behaviour out of a language that doesn't support it, you're using the wrong language or you have a bad design.
There is no doubt that the grail of efficiency leads to abuse.
Programmers waste enormous amounts of time thinking about, or worrying
about, the speed of noncritical parts of their programs, and these
attempts at efficiency actually have a strong negative impact when
debugging and maintenance are considered. 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 %. A
good programmer will not be lulled into complacency by such reasoning,
he will be wise to look carefully at the critical code; but only after
that code has been identified. It is often a mistake to make a priori
judgments about what parts of a program are really critical, since the
universal experience of programmers who have been using measurement
tools has been that their intuitive guesses fail. After working with
such tools for seven years, I've become convinced that all compilers
written from now on should be designed to provide all programmers with
feedback indicating what parts of their programs are costing the
most; indeed, this feedback should be supplied automatically unless it
has been specifically turned off.
I think what happens with all intermediate or senior programmers is that we start to think about the best solution instead of just getting the job done.
Most code we write will either not be used or eventually rewritten anyways.
> Most code we write will either not be used or eventually rewritten anyways.
But it's like the advertsing paradox: we know most of our code will be discarded or rewritten, but we don't know which parts won't. And even worse, it is often the bad parts that survive because people become afraid to touch them.
We're screwing ourselves badly with that attitude in the long term. Because of similar attitudes in setting up industrial contro systems, you can now shut down an entire factory with a misplaced ICMP ping. Layers of hacks built on layers and layers of other hacks will bite us hard at some point, and I mean in the "lives lost" sense of biting.
I find that when working on large projects, the code does get rewritten... in a totally different location in the source tree... and we can never delete the old code.
Anyone have good before and after examples of Rule 5? That is, a "dumb" data structure with "smart" code refactored to a smart data structure with dumb code?
I don't have actual code. But when tutoring CS1 and CS2 students during undergrad, it was common for students to try to implement algorithms in terms of linked lists when they should have been using a tree.
The really persistent students would get things to almost work -- often with hundreds or thousands of lines for something that, with a tree, doesn't take more than 10-50 lines.
This is also an interesting case study in human behavior; the students were typically too impatient to spend 20 minutes thinking about the problem before coding, but could spend 20-30 hours on a single assignment. Odd combination of work ethic and lack of patience...
> the students were typically too impatient to spend 20 minutes thinking about the problem before coding, but could spend 20-30 hours on a single assignment. Odd combination of work ethic and lack of patience...
I wouldn't call it a lack of patience, per se. In most modern models of the brain, exercising executive control to think abstractly ("using System 2") expends energy for as long as you're doing it, and the explanation for many of the brain's inherent shortcuts and biases is to to prevent you from switching into System 2 for longer than absolutely necessary.
I have a feeling that a large part of what is characterized as "intelligence" is simply the brain being willing, for whatever reason, to switch into System 2 "mode" more often, and stay in it for longer.
Kahneman chose the names "1" and "2" because he asserts that those names are easier to remember than "autopilot" and "deliberate", and so don't require System 2 thinking when you use them. I find that the confusion arouns these names undermines Kahneman's theory, as seen in this thread.
At first, the database was normalized. You have the obvious relations where of students, periods, class/grade, etc... so was a tree.
At the time of editing and printing (this was circa 2000 with FoxPro) things get complicated... fast (was important that editing the scores for each students be very fast).
It was my first serious job, and I'm a self-taught developer, so I don't know back them that my tables were a tree, neither any data-structure apart from the used in Fox.
But one day it hit me: Why I'm doing the tables this way? I see the pice of paper that show how manually a teacher do the scores, and I think: I will do the tables EXACTLY LIKE THIS (ie: As you see in the image above).
Suddenly, everything else get easy. Printing was easy. Editing was fast. Less errors. The app was a hit in part for that "small" change. Look like the competitors never get that idea back them.
I don't have an example of a refactoring, but the git data model [0] is extaordinarily simple, to the point that you can understand what goes on behind the scene on whatever ui you use and stop being mystified, and even extend the data model beyond its primary use [1].
My take: poorly designed data models (persistence structures) relying on clever hacks in the program to overcome incorrect ordinality and cardinality rules, data redundancy etc ...
This will require programs to make sure that no more than 1 employee can be a DepartmentHead. For every update to the IsDepartmentHead property of an instance of Employee the program will have to iterate through the list of Employees to flush the switch before assigning the new one.
This is a much better data structure since you can only ever have one Employee assigned to a Department as a head. The program will of course need to prevent Employees from Departments they don't belong to from becoming Heads of the Departments they are NOT in.
> Rule 3. 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.)
Thing is, I don't know; n is definitely small in our unit tests, but if it isn't guaranteed¹ to be small, I'd rather start the code off as something with O(decent) as opposed to O(whatever an array gets me). It's not clear to me if this is what Rob Pike means though: does simply using a hashtable when appropriate to avoid iterating through a list count as "fancy"?
When the ultimate bounds of n aren't certain, I'd rather start with a good O(...) algorithm, and then apply the "measure, and optimize."
¹and even then, if my "guarantee" is coming from something other than physics, I'm wary.
If you can get a naive n^2 solution, or build a complicated nlgn solution, and you know the size of the data will be ~100 items, certainly never >1000 solutions, I'd choose the naive solution.
This is great advice. What I take away from it is, keep it simple, keep it readable, and save the detailed optimization for later, when you have time to really test and measure it.
This shouldn't replace understanding the problem domain and carefully planning before tackling a moderate to large scale project. Yes, one shouldn't tune each individual piece with unjustified optimization but the high level design should be thoughtfully laid out prior to hammering out large swaths of code.
Too many developers plow forward in a brute force manner creating unmanageable inconsistent messes and use rules like these to justify their lousy (lack of) design choices.
My rules:
1. Understand the problem domain.
2. Design flexible solution using common patterns.
3. Stub out skeleton of system encompassing majority of specs.
4. Revisit design and consider all conceivable exceptions and outlier and tweak design as necessary.
5. Review above work with others and tweak design further as necessary.
Maybe this is part of the problem. I'm relatively young, so I've only seen a few design patterns, but it'd be interesting to have a high-level look at some of the most common patterns and what they're good at and what they aren't. For instance, I've never really used a messaging queue, but it seems like a genius design for a particular type of problem. I wonder how many other designs are out there that I'm not using, instead opting to shoe-horn in my existing ways of thinking.
Pre-optimization is one of the biggest problems with today's programmers.
First priority should always be releasing the software.
Let it break. Make optimizations when and where necessary.
When I say first priority is releasing the software - it means releasing software that works functionally. We cant optimize stuff which we are not sure will even break due to performance issues.
Analyze traffic/usage of parts of the application - mark areas which are used most - analyze performance - optimize if not up to mark.
If stress is always on elegant code - it'll always end up taking more time. In real-life scenario, no module is ever "bug-free". The cases change from day to day. When you're absolutely sure that the functionality is exactly what is required - then you should spend time optimizing it.
"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."
Quite ironic coming from the creator of Go. Algebraic data types, anyone?
Even simple things like doubly linked lists are complicated with ADTs.
On the other hand I don't know about good examples of ADTs used outside of the context of functional programming, do you have some pointers?
"You can argue that advanced language constructs will make it easier to write correct code to implement data structures, but it's not a magic bullet."
There is nothing advanced about ADTs.
"The Go authors argue that a simple programming language with loops, pointers and arrays is all you need to implement any data structure you need."
It's all about increasing the level of abstraction. There is a reason we don't code in assembly anymore. Of course machine code is all you need to implement any data structure, but how convenient is it?
"I find this a good example of a data structure for which I see little or no benefit in being modeled as an ADTs:"
So you found a single counterexample which (according to you) would not benefit from ADTs.
" On the other hand I don't know about good examples of ADTs used outside of the context of functional programming, do you have some pointers?"
I dislike pointers (a necessary evil if you have mutation I guess...), but here is one example:
data Gender = Male | Female vs type Gender int; const ( Male Gender = iota; Female )
Combine the first with pattern matching and you find yourself in awesomenessland (ie. code becomes readable, type safe).
>> On the other hand I don't know about good examples of ADTs used outside of the context of functional programming, do you have some pointers?
> I dislike pointers (a necessary evil if you have mutation I guess...), but here is one example
Perhaps there was a misunderstanding. I asked you if you had some links to some interesting examples of ADT outside the context of functional programming.
Because I was assuming that this wasn't a discussion about Go vs purely functional data structures.
Your example clearly shows the benefits of strong typing with fully described types.
My point that this is orthogonal with Rob Pike's position about the importance of data structures.
Data structures exist independently on how we represent them. I don't see any irony or conflict in highlighting the importance of data structure vs. implementing language features that make it easier to write correct implementation of them.
I was totally unfamiliar with any linking between functional programming and Abstract Data Types before reading your post. They are certainly present outside of that world.
Back in my university data structures class, an Abstract Data Type was just the collection of "a data structure and its operations". For example, a tree ADT could be a struct of two pointers and some value, along with operations like addNode, removeNode, findNode, copy, create, destroy, etc... We wrote lists, stacks, trees, hashes, and graphs in C as self-contained ADT libraries. This wikipedia page [1] explains the differences in approach.
The concept of data+operations was a lead in to objects for us, and seems very simple. Is the ADT idea in functional programming inherently more complex? I see from that page that it is intended to be immutable, which is certainly a difference.
Oh, interesting. It's the middlebrow dismissal. I thought it had become an endangered species, but here it is, stepping right out into a crowded thread and trying to take out Rob Pike of all people. Good show!
Of course pg hates the "middle brow" dismissal. Part of his schtick is Malcolm Gladwell style 'intellectual porn' essays that ignore facts and complexity to paint an aesthetically pleasing (but false) narrative to people who are not subject experts. At this stage I'm not sure if PG does it deliberately like Gladwell admitted doing. I'm willing to give him the benefit of the doubt and say he does it inadvertently by writing about topics where he has no knowledge of previous study, coupled with a large ego born of being rich and constantly surrounded by sycophants trying to get funding.
The middle brow dismissal is apt/damaging in these situations because it saves everybody a lot of time by quickly demonstrating that the author ignored those pesky real world facts and complexities that spoilt the ideological narrative.
It's too bad The Master has departed, I'm going to miss his words being quoted to "settle any possible HN argument" in the words of this great comment: https://news.ycombinator.com/item?id=1716028. Also going to miss all the pearl clutching about "this comment/thread is horrible", okay maybe not. I assume work was never finished on the Lisp AI that would block comments he disagrees with, any of the mods still working on that?
It was poorly expressed, but I think gnuvince was referring to the fact that it is possible to implement machine-friendly ADTs. Rust is just one example of a language that has them.
I'm not your shrink, but thanks to the handy "Search" feature on the site, I had read every comment you've written that mentions Golang or Rust before I wrote that. I stand by what I wrote.
I'm getting pretty sick of hearing this trope regurgitated all the time.
Developer time is often more expensive, but it's always a one-off cost. Machine costs are ongoing. Machines can also impose hard limits on scalability.
In the real world, software optimisation is often necessary. Ever play a computer game? Those have pretty hard limits on much time they can spend processing. You can't just throw hardware at the problem to make it go away when you don't control the client.
"Just add more hardware" is also an ecologically unsound and unsustainable approach. Ever wondered about the carbon footprint of the average data centre?
Maybe one day we'll have optimising compilers so good that thinking about machine-level data structures won't be necessary. They've come a long way in the last 20 years, but aren't quite there yet. In the meantime, if you ever find yourself actually needing to make something run within some hard limits on CPU time, RAM, etc., listen to people like Rob Pike: he know's what he's talking about, even if you don't like what he's saying.
In the meantime if you're working on an MVP, by all means optimise for developer time. In that context it's almost always the right decision.
"Developer time is often more expensive, but it's always a one-off cost."
Bear in mind that opportunity cost is an unrecoverable loss. Game programming where you press a DVD is an exception, but in the majority of areas the greater cost is actually in maintenance.
Exactly. I cannot imagine this kind of sloppy thinking being applied to any other form of engineering.
Machine time eventually translates to user time. Slow code leads to poor user experience and if your product is successful, wasting the time of millions of people.
I hope I don't prove to be too detrimental to your health.
"Developer time is often more expensive, but it's always a one-off cost. Machine costs are ongoing. Machines can also impose hard limits on scalability."
A one off cost? I have never seen a codebase which gained consciousness, became self operating, fixed the bugs in itself and implemented new features, I hope I will, that's gonna be a truly glorious moment for humanity.
"Ever play a computer game?"
I did, but Go is rarely used for creating games. Typical use case: backend server services.
"In the meantime if you're working on an MVP, by all means optimise for developer time. In that context it's almost always the right decision."
Yes! On this site most people are working on some startup which will fail in 2 years. Performance is barely an issue.
>A one off cost? I have never seen a codebase which gained consciousness, became self operating, fixed the bugs in itself and implemented new features, I hope I will, that's gonna be a truly glorious moment for humanity.
No, but I've seen lots of projects who were completed, shrink wrapped, and shipped, with the team disbanded or moving on to other projects (sometimes with a few people left behind for bug fixing).
Especially most large scale enterprise /government / organisational projects are mostly one off, fire and forget affairs. A large team is assembled to create them, and then the support is offloaded to smaller team for fixes (and some tacked-on new features), and they run for decades on end.
>I did, but Go is rarely used for creating games. Typical use case: backend server services.
Which is bedide the point. The discussion was about those "programming principles" Rob Pike put forward, and the costs of developer vs machine etc -- not about Go in the least.
Machines have a cost, developers have a cost. One must optimize for both costs, and assuming machines or developers were free compared to the other would be very stupid.
There are many problems that require some efficiency to solve effectively, especially in pike's field of systems.
And who else is in a similar field? 3% of all programmers? In that case, fine. But most people I see raving about Go can afford the performance hit any time (if there is any).
The systems community is quite large, consisting of probably around 30-50% of the dev jobs in companies like microsoft, Google, Facebook, Apple.
Go was designed as a system's language, I think it just eventually went in a different direction when people realized it would never match C++ or even Java in performance.
Re: your edit regarding ADTs: it's not that they are expensive to implement, it's that they give you no control over the physical structure of the data, which is the really, really important thing when it comes to how expensive it is to perform operations on that data. That's the point Rob was making in #5.
BTW, if you want to gain an understanding of this stuff, the difference it can make and why, I'd recommend reading basically anything by Michael Abrash.
I think we can agree that having that level of control is unnecessary for most programming tasks. In fields where it matters, fine. Otherwise I let the compiler do it's job, probably they will get better/are already better at it than me. I don't trust humans, including myself. My compiler never made a bad decision so far because it woke up with a hangover/in a bad mood.
Your compiler has no idea about whether data structure A will perform 100 times faster than data structure B because B is scattered all over memory and incurs a page fault on every reference and A has locality of reference.
No compiler optimization is going to get you a 100 to 1 improvement with a conventional language, but choosing the right data structure and algorithm for a task certainly can.
And if your problem requires only one of each, and needs them for the same amount of time, then your optimization would be the correct one.
Now scale this to a situation where solving the problem requires ten thousand machines for each developer working on code, and where each minute of time spent writing code translates into two days of machine time running that code, and the numbers start to look different.
When I will solve problems which require 10k machines/dev, I will get paid so much that I will be happy to write in brainfuck or lolcode.
Meanwhile I just want to deliver the features for my product owner as quickly as possible! So we can both go home to our families in time and still deliver tons of business value.
Well, I'm no super fan of go, but given the ideas they were working with, I think they ended up with a fair compromise. I mean, if you want Haskell (or ML), use that?
I think it is a question of how far you're willing to take generalization over how easy it is to come up with a reasonable concrete solution to a concrete problem.
The c mindset of unions/structs coupled with functions doesn't contradict the idea of "chose the right data structures".
[edit: It appears others have made this point better while I was typing. The gist seems to be (to paraphrase another comment): (abstract) data types and types are not the same thing. types can help with the implementation of ADTs, but that's not really relevent to the 5th rule.]
I don't understand the question... an ADT is something like "a stack", where "a stack" is the collection of procedures that manipulate a stack, and have an interface that integrate with the type system. So a stack takes a type, and allows it to be pushed on, and popped off. Together these form an ADT. Now, if you have algebraic types, you might have an easier time implementing the stack ADT in a way that it can handle both text strings (push a string onto a stack) as well as numbers. Or you could just say that everything is a number: and "push by reference" -- so you can push a complex record to the stack -- but all the stack sees is an integer (a pointer to the record).
Type safety (checking that all integers pushed to the "record-of-type-library-card stack" are in fact valid pointers to valid library-card-records) can be helpful, but not needed to implement ADTs.
Am I close to clearing up what I was talking about above?
[edit: typo, also: you mis-quoted me, dropping the "abstract" in "abstract data type" -- which might be the source of the confusion?]
I think the parent comment is assuming ADT is short for "algebraic data types" and not "abstract data types", since the former is the subject of the rest of the thread. You used both long forms and the acronym without saying which you meant.
As to the meat of the discussion, algebraic data types imply that you can apply algebraic operators to types. Since this is traditionally a purely compile-time feature you can imagine why the parent comment is incredulous that you could implement this without language support.
Your specific statement, "data types and types are not the same thing," is particularly confusing. You are making assumptions that aren't warranted, for example that "data types" encompass both a compile-time type check and an interface allowing abstract operations, while "types" are simply static type guarantees on values. In fact, both terms can refer to either.
Fair enough, but I didn't say "data types and types are not the same thing", I said "(abstract) data types and types are not the same thing" (unless I did for a moment before a quick edit, but I don't think so).
Anyway, I think we've cleared up what I apparently didn't put very clearly in the first place: Algebraic Data Types can help with implementing Abstract Data Types, but one doesn't need the former for the latter -- and I suspect the data structures of "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." are indeed closer to using the right simple data structures along with the correct abstract data types -- so there's no direct contradiction between the 5th rule and Go not having (proper) Algebraic Types.
It's very close (in my opinion) to a restatement of Brook's quote "Show me your flowcharts and conceal your tables, and I shall continue to be mystified. Show me your tables, and I won’t usually need your flowcharts; they’ll be obvious."