When to do optimization?

Moderator note: This topic was split from What is faster? `Copy` or passing reference?

No, Rust compiler can not do that. Not in practice, at least. Glibc for GNU/Hurd can do that because Hurd kernel, Mach, has special support for CoW memory mappings. Without such capability compiler can not do anything practically usable.

And if you consider how expensive CoW-via-kernel is in practice… whether such “copy” would be a win or loss depends, very much, on the access pattern after copy.

If someone follows you advice, copies around plenty of [u8; 1048576] arrays (hoping compiler would make these copies cheap with magic TLB tricks) and then find out these tricks are not practical?

No, you can only afford to “write for clarity first” if you are writing a prototype which would later be fully rewritten. And more often then not once you have said prototype you would be hard pressed to stop using it. Remember that IPv4 story? The one which costed untold billions and is still not finished?

I strongly recommend people who use that premature optimization is the root of all evil to actually read the article where that cite comes from. And note that this same article includes also another piece of wisdom: In established engineering disciplines a 12% improvement, easily obtained,
is never considered marginal; and I believe the same viewpoint should prevail in software engineering
.

Only rely on optimisations you know you can achieve and ignore things which you can afford to optimize later by full rewrite. Basically: don't microoptimize, leave that to compiler. Not only modern compiler can do pretty efficient microoptimizations, but, more importantly, if compiler can not do that… worst case scenario one huge asm block would solve the issue.

But large-scale design? Something you can not change later? Think very carefully about such design choices. Otherwise you are not doing engineering, but playing lottery. C++ bet paid off (and Rust uses is as base), OOP, tracing GC, many other things? Nope, still don't work as they were supposed to work according to their proponents ads from 40 years ago (remember the first victim?).

Sometimes playing that lottery is a good choice (perfect is enemy of good, much-less-than-optimal code which works is always better that extremely optimal code which doesn't exist), but please don't handhave efficiency concert with let's write for clarity first and then manually optimize.

5 Likes

In what way does Rust use C++ as base? It's original compiler was written in OCaml before being self-hosted. It does use LLVM, which is written in C++, as compiler backend by default, but there are other backends. The one I made (rustc_codegen_cranelift) uses Cranelift, which is entirely written in Rust. As for language design Rust was inspired by OCaml, Erlang, Cyclone (C variant with something similar to rust's borrowck) and a whole lot of other languages. C++ was one of the inspirations, but I don't think it was the biggest one.

2 Likes

The big bet which C++ did quarter century ago was that you can write huge pile of redundant code and make a compiler which would optimize all these to very efficient, optimal code.

Evgeny Stepanov made a container library for C++ on that basis when it was just an idea. And it became an international standard before it was actually usable! And then that same Evgeny Stepanov made a benchmark… it wasn't pretty.

That is why many C++ developers, still, to this day despise STL and use bespoke data structures even when there are no real need.

But after about two decades of diligent work this bet actually paid off.

The important thing is not particularly LLVM, but the ability to optimize Rust code and make it as efficient as manually written code despite the fact that initial, unoptimized, version includes about 90-95% of useless code. Without such ability C++ would be entirely different language and Rust would be entirely different too. But C++ was designed before we had such compilers and Rust was designed after that point.

if you want to see utter failure of a very similar bet — look on Java. Java bet on similar ability of JITs to efficiently handle references, somehow. That's why it boxes everything, often even small ints.

The idea was that tracing GC and other tricks would be able to eliminate these references or, maybe, just make them less costly. Project Valhalla (with value types and generic specializations) is, basically, admission of defeat.

That failure affected Rust, too: that's why it has specializations. Yes, they are unstable, yet, people may try to pretend they don't exist, but without their use in std types Rust as we know it today wouldn't exist.

zero cost abstractions are something without which Rust, in it's current form, wouldn't be imaginable.

3 Likes

Hindsight is 20/20, and nobody knows what the counterfactual to this would have been in practice. IP could have easily gone the way of Betamax, with engineering effort going into optimizing the wrong attributes of the technology.

Despite its flaws, IPv4 successfully supported the Internet for decades; it's not the example I would pick of an engineering failure. Did it cost untold billions, or did it create billions in new economic opportunities? What would the world look like if the internet was kept "in the lab" for another 10-20 years until it was "ready"?

I didn't get that you were referring to that. In any case you are definitively right about this. In fact Rust gives LLVM even more garbage than C++. This is part of the reason why rustc is slower than C++ compilers. This (the compile time perf hit) is slowly starting to improve though through MIR optimizations like the recently enabled MIR inliner.

4 Likes

We kinda know. Just look on what happened to IP competitor.

Yes, IPv4 is huge success, but its 32bit addresses are a total failure. And it's not as if developers couldn't have reserved more bits for addresses (note how Ethernet developed in the same time as IPv4 uses 48bits which is still not a huge problem in practice even today). Their position was “hey, that's just an experiment, we would redo everything later”.

Both, obviously. It's similar to idea of pointers: the addition of references to the languages both created the ability to create much more complicated designs, but the addition of NULL and conflation of reference to something and optional reference to something in most modern languages costed untold billions, too.

The same way IPv4 enabled huge opportunities (and if we had to use ITU-T alternative lots of money would have been wasted) but choice of 32bit address costed as a lot.

These examples kinda show how optimizations should be handled: if something is easily replaceable later then you don't need to think long and hard about these things but if something may be backed into decisions which you may not easily change later (like data formats or on-the-wire protocols, for example) then you need to spend a day or a week to design them right from the beginning.

2 Likes

I've read it before, but since it's been a while I've just skimmed through it again. Here are a few key quotations, followed by my commentary:

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. (p 268)

Despite this concern with efficiency, I should actually have written the first draft of Example 3 without that go to statement, ... since this formulation abstracts the real meaning of what is happening. (p 270)

[W]e shouldn't merely remove go to statements because it's the fashionable thing to do; the presence or absence of go to statements is not really the issue. The underlying structure of the program is what counts, and we want only to avoid usages which somehow clutter up the program. (p 275)

We need to be subconsciously aware of the data processing tools available to us, but we should strive most of all for a program that is easy to understand and almost sure to work. (p 294)

Engineering has two phases, structuring and integration; we ought not to forget either one, but it is best to hold off the integration phase until a well-structured prototype is working and understood. (p 295)

Standard operating procedure nowadays is usually to hand code critical portions of a routine in assembly language. Let us hope such assemblers will die out, and we will see several levels of
language instead: [...] With an integrated system it will be possible to do debugging and analysis of the transformed program using a higher level language for communication. (p. 295)

Knuth's primary concern throughout the entire article is that program text should clearly communicate intent between programmers, which the contemporary trend of removing gotos sometimes hindered. His secondary concern is on program efficiency, and he notes a few points regarding it:

  • Most performance gains can be obtained by optimizing a few small critical sections.
  • Programmer intuition fails when attempting to identify these critical sections, and program analysis is needed instead.
  • The optimizations needed often compromise clarity, so the optimized version should be considered a production artifact instead of the primary record of the program's purpose.

Overall, Knuth is arguing for a 3-step process to writing programs:

  1. Write a program that is obviously correct
  2. Use program analysis tools to identify the parts of the program from (1) that are worth optimizing, at a cost of clarity
  3. Optimize those parts so identified

Furthermore, he notes that the optimizations required are often quite mechanical in nature, and hopes that future tooling will be able to take care of that part for us.

Or, in even shorter form,

4 Likes

I think you simply missed parts where Knuth talks about relevant things. Knuth mostly talks about control flow optimizations, which compilers today do amazingly well. But take this, for example:

A few years ago, several students and I looked at a typical sample of FORTRAN programs [51], and we all tried hard to see how a machine could produce code that would compete with our best hand-optimized object programs. We found ourselves always running up against the same problem: the compiler needs to be in a dialog with the prograrmner; it needs to know properties of the data, and whether certain cases can arise, etc. And we couldn't think of a good language in which to have such a dialog.

This is true for this very day. This is basically, why Java bet on boxing everything and allowing JIT to unbox things when needed failed: simple, local transformation of code just don't work for that.

And remember another 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.

That's practical observation from The Mythical Man-Mouth.

And in the article we are discussing Knuth says this:

Control structure is merely one simple issue, compared to questions of abstract data structure.

Basically, observation is simple: code is easy to change and very often very simple, local changes help immensely.

Global data structures (and, where appropriate, APIs… that term haven't existed when Knuth wrote this article) are very hard to change and they have deep, profound impact on the speed and memory consumption of your code.

If you would design you program with the assumption that you can easily and cheaply copy [u8; 1048576] because of some TLB trick compilers may eventually implement… you would have hightly inefficient, extremely slow program for two decades. Minimum. If it would even survive for two decades.

And I think final observation which changes things significantly:

Most programs are probably only run once; and I suppose in such cases we needn't be too
fussy about even the structure, much less the efficiency, as long as we are happy with the answer.

That's probably the most compelling reason for do who you are advocating: if you, indeed, want to run program just once… then perhaps writing is with “clarity first” approach is, indeed, the best choice.

But in reality, in today's world, that's probably the biggest change: whileas in times when that article was written you would get a privilege to run your program once per week and it was important to ensure that it would compile cleanly and run on first try… today we are not running program once. Not even the programs we develop for themselves!

It wouldn’t survive for 5 minutes. You’re ignoring the last two steps, “measure for things to optimize” and “optimize them.” Nobody is advocating relying on anything that present compilers don’t already do. If [u8; 1048576] is the semantically-correct type, start with that. Then, measure what you’ve written. Then, refactor [u8; 1048576] into Rc<[u8; 1048576]> or Vec<u8> or something when it proves to be a problem. In practice, though, the semantically-correct type will almost certainly be struct Buffer { /* private fields */ }.

In my experience, the resulting design will likely not be ideal, but the quality improvement for each unit of engineering effort will be higher, resulting in an overall better program. This calculus changes, of course, if a poor design risks human safety— There’s a reason safety systems are a lot more expensive than “equivalent” ones used for non-human purposes.


For larger programs, an iterative development process certainly helps: Instead of writing the whole program before measuring and optimizing, write one modular part at a time. But still, any given section of the program goes through the stages in the same order: Make it correct, then evaluate performance, then make it fast.

3 Likes

Well, that's reasonable. And doesn't contradict things which I'm talking about.

Seriously? I think you don't estimate (or maybe overestimate?) humans. I have seen way to many people who interpret this

in the following way:

  1. Write the code which is clear and simple.
  2. Show it to the others. Get approval and bonus.
  3. Deploy/release it. Switch to other project if you want more bonuses.
  4. When people complains about slowness and/or your bills for hosting grow to high — start thinking about optimization process. Usually that's problem for someone else than who did #1, #2 and #3.

Note that they perform your algorithm perfectly: till stage #4 they haven't verified that they can do a better job than the compiler. Because they never tried to optimize anything.

How can [u8; 1048576] be reject with such approach in 5 minutes — I have no idea.

When should you do that? That's the question. Way too often that step is pushed for after delpoyment/release stage. That is how we end up with JavaScript which doesn't have integers or with Windows Update which needs three weeks to update Windows and other such things.

Means when Windows Update starts taking weeks? Are sure you would be able to replace [u8; 1048576] with Rc<[u8; 1048576]> or Vec<u8> at this point?

1 Like

Engineering as a discipline usually isn’t about producing the highest-quality product, but rather producing the cheapest product that meets the brief. If you’re building a bridge, that means that it needs to look kind-of nice, withstand particular loads, and last for a sufficient service life. If you’re writing software, the requirements can be quite varied, all the way from “We need some kind of revenue tomorrow so the company doesn’t go bankrupt” to “We need to fly this plane automatically without killing people.”

The poorly-performant software, then, should be rejected at step #2 as not fulfilling the business requirements. In practice, though, many businesses have a blind spot for these sorts of performance problems. Fixing that is a whole other kettle of fish— You need to figure out how to align customers’ desires for a performant piece of software with the developer’s¹ desire for profits.

¹ The company, not the individual programmer.


Edit: There’s also such a thing as engineering ethics, one aspect of which is a concept of minimum standards. A bridge builder should refuse to design and build a bridge that isn’t strong enough to carry reasonably-expected loads, even if the client requests a lower load limit. Outside of life-safety situations, these minimum standards don’t really exist for software engineering at the moment.

3 Likes

By that time you often have tens if not thousands of lines of code built on top of poor abstractions which are very hard to optimize.

And if you are building a bridge you can *actually see that bridge model is different from real thing. It's 100cm long, not 100m long for one thing.

The problem with software is that business doesn't even thing about the fact that there are something behind these pixels on the screen.

And engineers, according to your advice, don't think about efficiency when business doesn't ask for it. Which only ever happen after deployment.

That's the next step. First we need to have to build certain amount of software engineers who would care about efficiency a bit earlier than when Windows update would start taking three weeks.

In software engineering people often do things sloppily not even because this allows them to build something faster and/or cheaper but simply because no one punishes them for doing things badly.

I’m not super familiar with the history of engineering, but I think you might have your causality backwards. In the early Industrial revolution, lots of engineered structures (like bridges) failed, killing a lot of people. The railroads and other companies that commissioned these bridges didn’t care much, as long as they got enough value out if the structure before it failed.

The populace was understandably upset, so laws were passed requiring a registered engineer to sign off on every bridge design. If a bridge failed due to a design fault, the responsible engineer was made personally liable for damages, regardless of the nominal requirements. Thus is where minimum standards and engineering ethics got started.

If we want software engineering to follow a similar road, we just need to legislate that individual programmers are responsible for harms caused by their software, and can’t hide behind their employer— Programmers will start insisting on doing things “right” quite quickly if the government is willing to go after them personally for doing things “wrong.”

NB: I’m just trying to point out historical precedent, and don’t endorse or advocate actually taking this course.

1 Like

I think we are discussing different things. You are talking about how you can force software engineers to do the right things.

I'm pointing out that before we can force them to do anything we have to teach them.

Which catastrophe would actually trigger the decision to hold engineers personally responsible is not very important: with software taking more and more control over our lives one or another will happen.

I'm talking about how to arrive on other other side after such catastrophe in best possible shape.

1 Like

And I believe that before we can teach them, they must want to learn. Imposing personal consequences for failure is the only thing I know of that has worked in the past, but it’s a painful road. I hope somebody can come up with something gentler, but I don’t have any ideas.

2 Likes

That's the only thing that can possibly work. There are too many developers writing (barely) functional software for too many companies that only care that it (barely) works.

It shouldn't just be on the developers though. Companies should be completely liable for things like data breaches due to flawed software.

5 Likes

Do you have any examples of such punishment of individuals for engineering failures working?

It can go horribly wrong as in the famous "Diesel Gate" case. Oliver Schmidt was jailed for seven years. It's clear that he was only a peripheral character in the whole sorry saga. Meanwhile those that designed the emissions test cheat software, that built it, that wanted it, that authorised it, got away scot free.

Point is that typically it is not down to one or even a few people to build anything now days. There are whole teams, there are quality control people, etc, etc.

I hate to think that one day a Boeing 777 falls out of the sky and I end up in jail because of a mistake I made in an integration test script for the Primary Flight Computers. Sure I might have made a mistake but the whole development process has failed if that mistake gets through review, testing etc. I don't want to end up as a scapegoat like Oliver Schmidt.

1 Like

It’s extremely difficult to pin down the good these regulations do because, if successful, there is no failure and therefore no punishment— The threat should motivate better quality work in the first place. Also, these systems have been in place so long that many of their effects are so pervasive as to feel inevitable.

There are certainly instances of engineers going to extraordinary lengths to fix problems, despite an instinct to cover them up instead. It’s impossible to say how much of LeMessurier‘s actions, for example, are attributable to basic human nature, professionalism¹, or the direct threat of reprisal.

¹ Which itself owes a lot to society’s response to early engineering failures


If you edit that quote a bit, you get why I choose not to work on safety-critical systems:

I hate to think that one day a Boeing 777 falls out of the sky [partly] because of a mistake I made in an integration test script for the Primary Flight Computers.

I want the people who work on these systems to be empowered to tell their bosses “No; I refuse. I will be sent to jail if I do what you ask.” I especially want to avoid diffusion of responsibility to the “development process,” such that no person is actually responsible for anything.

2 Likes

I think you are kinda both right: we need such legislation, but we also need a plan to enter it gradually.

Because if you would make it possible for the guys who achieved that Boeing 737 MAX fiasco to shift their responsibilities to rustc developers then we wouldn't have any rustc developers in a very short order.

And that's in spite the fact that they are are almost obsessed with robustness and security.

We couldn't expect these types of legislation to be miracles: they they work, but only if you tighten the screws slowly and carefully.

Think about how seat belts were introduced. Something similar should happen with software.

But I don't think it's actually useful to discuss that part here. Some people would do an awful things and some would try to achieve perfection, not matter what you do. Legislation, work culture and other things may change proportions, they are, basically, the question “do we need good software at all?”.

And I think it's pointless to discuss that question on URLO. You can not make language which would make it impossible to write bad software. You can try to make it harder, but… it is impossible to make anything foolproof, because fools are so ingenious.

Rather we should concentrate on the other question: how can we write good software if we decide to do so?. It doesn't matter why people want to write good software, but whether it's legislation or professionalism, or just their inner desire… if they don't know how to do that they would be unable to. Even if you would literally hold the gun to their neck.

And…

if taken literally is quite bad advice. Rather you should do it in steps:

  1. Think about your data structures and think about cost of using them .
  2. Write code and and don't think about its speed.
  3. Optimize code in places where you hit the bottleneck.

Because in practice once a data structure is chosen it's very hard to change it. Sometimes, when advantage of a a better data structure is obvious you can start the herculean effort of rewriting everything… but often than not if the win is “small” (like: mere 5x memory reduction or 2x speedup) and price is high (like: you need to rewrite thousand lines of code to fix anything)… nothing happens.

The most relevant example for URLO is probably rustc itself: it's much slower than it can be… and yet developers can not do anything to significantly speed it up. And these are not a dumb developers by any means.

2&3 here sound an awful lot like the advice I gave, so you’re really advocating for an additional step in front to work out something about how the program data is organized. I can’t really argue with that, as it’s something that I do all the time. I just lump it in mentally with strategizing, whereas the actual writing is a more tactical concern. And my advice was meant to be given in a tactical, rather than strategic, context.

No piece of advice, and certainly not a single-sentence quip, can hope to capture the nuances of a field as diverse as software development— At best it can be situational, directional guidance for the uninitiated and a reminder of fundamental principles for those with experience. If anyone is taking this sort of advice as universal truth to be applied literally in all situations, that is the most important problem to address.