#code for the optimizer

[mentalisttraceur-software]

When I was younger and still stuck thinking in terms of concrete current implementations more than abstract semantics and their best possible implementations, I kept wanting to bypass the standard library, especially in low-level languages like C, because the standard library had code paths I didn't need.

If I knew I didn't need my newly allocated memory to start zeroed out, I disliked calling calloc, because a naive implementation of calloc implies extra work, and most implementations would imply extra work at least some of the time. Because I failed to conceive of the OS and hardware having extremely efficient code and circuitry for giving us zeroed out memory pages, and I failed to conceive of optimizing compilers generating code which doesn't bother zeroing out that memory if you truly never read those bytes before writing them.

If I just wanted one memory allocation for the lifetime of the program, I disliked calling malloc at all, because most malloc implementations have a complex memory allocator which is only more optimal for larger and churnier memory usage. I wanted to call the rawest, most direct memory allocation operation - for example, on modern Linux that's an mmap system call asking for an anonymous page (or for a mapping of /dev/zero, although I later learned of sloppy/overbroad SELinux policies in production, f.e. on some Android devices, which reject opening or mapping /dev/zero). Or I wanted to just manually try to grow the stack (and have raw feedback from the kernel if I didn't have enough). Because I was stuck thinking about what the concrete implementations I had on hand would do. Instead, I should've been imagining the optimizing compiler which can look at a simple "malloc", and at everything else in the code, and at any optimization preferences and other information passed in when invoking the compiler, and just compile that malloc as a raw memory system call, or as a stack allocation, if that's actually the best thing to do in that situation.

Painstakingly chipping away at this has been one of the most liberating and healing things for me as a software developer. This is why I eventually realized that we should "code for the optimizer" rather than optimizing by hand in almost every situation. But it took the overwhelming accumulation of examples of actual real-world situations where automatic optimizations beat manual fiddling, or did just as well, and where the manual fiddling was actively counter-productive.

I wish they taught this in schools or something. Just one class, one semester, which is mostly just a showcase of "here's some code. here's how it could be inefficient. how might we optimize this? yeah, yeah, cool, cool... good ideas class. Now here's what a modern compiler can do if you just give it the simple code that doesn't try to optimize. Notice how it did everything you thought of, plus things you didn't. And oh look, if we change the optimization tuning from execution speed to memory usage for example, the compiler can optimize the simple code totally differently, but our hand-optimized code is stuck using more memory, because the compiler can no longer discern the relevant intent and invariants in this code - and neither could a human, without extensive comments and context".

I know lots of developers just don't care, but it would go a long way towards either unblocking or constructively directing the type of developer who can be very productive but would otherwise spend too much time prematurely or needlessly optimizing in the wrong places.

[mentalisttraceur-software]

A little example of clear abstract code "aging efficient":

if you use Arm's solution in pure software to implement pow(x,y) on an x86 machine, then it'll go 5x faster than Intel's native x87 instructions for doing the same thing. [alleged here]

If true, and I suspect it is (I would just want to verify how/why, and if any edge cases were left on the cutting room floor, just in case) then code which went out of its way to use inline assembly instead of the "pow" C function is now slower - assuming your C library or compiler takes advantage of these techniques (notably, even if there are edge cases where it behaves differently than the instruction, if the C compiler can prove that you will never hit them, or if it would be undefined behavior per the C standard to hit them, your code could benefit from this at any time).

Code for the optimizer.

[mentalisttraceur-software]

Aging Efficient

[this is an unfinished post! I may never finish it, or may substantially rewrite, add-to, or split up parts of it; some sentences trail off, and it has no ending]

It is well recognized that code can age poorly, but like many things, code can also age well. Like a fine cheese or wine, code can get better when left unattended.

In particular, I want to talk about how code "ages efficient" - as optimizations improve, and your language or system gets those optimizations implemented, your code will sometimes get more efficient for free.

But! Just like aging grapes need the right preparation to turn into wine instead of rotting slush, your code needs to be written in the right ways to be amenable to optimizations, instead of resisting and defeating optimizations.

Remember the XOR swap? For a brief moment in history, it was a more efficient way to swap variable values than using a temporary variable, because a compiler with no or minimal optimizations would just save that temporary variable on the stack. Then one day, compilers learned to keep a map in memory between registers used by the machine code and variables used by the source code - this was very simple, and had huge sweeping efficiency benefits across almost all code, because the compiler no longer had to keep moving stuff between the stack and registers for every single operation. And just like that, with no deliberate optimization of that specific special case, variable swaps through a temporary variables became free no-ops. Meanwhile the XOR swap remained three XOR operations, because it is much harder, and far less universally valuable, to write analysis that can symbolically simulate several operations on all possible inputs and notice when they cancel each other out, what effects they may have, and what other operations have the same effects but are more efficient.

We see this pattern repeat across software history.

Manual loop unrolling was more efficient once, but a good compiler or JIT optimizing VM can unroll your loops for you, and unlike you manually tweaking the source, the automatic optimization is in a better position where to choose the unrolling that best for the current target hardware.

Duff's Device was more efficient once, but it's easier and more broadly useful to have algorithms that can turn a clear simple loop into one of several options including a Duff's Device, than to have algorithms that can reverse-engineer the clear simpler loop from a Duff's Device.

And so on.

The thing is, it comes down to just one simple principle: write easy-to-analyze code:

Write code that sieves out and collapses possibilities as soon as possible. The sooner you error out on bad data or programmer error, the more of the code paths after can be transformed in ways that are more efficient but only produce the same result for the correct inputs.

Write code that maximizes locality of behavior and correctness.

Write code that most clearly and directly expresses your big-picture intended result. The more the intended result has to be inferred from the code, the harder it is

Write code that says what you mean in the semantics of that programming language,

Conveniently, you have a human brain, which is very limited in terms of working memory and speed, so when rigorously stepping through code, you can literally feel when code is harder or easier to analyze based on how much effort it takes to keep track of the full possibility space of what could happen at each operation.

This, by the way, is why coding for the human is incidentally often coding for the optimizer. An optimizer needs to prove that certain things can't happen to apply optimizations. The further it has to look to

[mentalisttraceur-software]

One of my many "eventually maybe" project ideas - although I'm hoping other optimizations at other levels of the tech stack will make it mostly unnecessary - is an optimizing compiler turning shell scripts into single binaries with inlined implementations of all the shell commands it knows about.

That way for example canonical source code can look like `curl ... | sed 's/foo/bar/'` and the binary might use something like libcurl (ideally in a static includes way, although I suspect the world will keep insisting on the less efficient-to-implement approach of link-time optimization) and an inlined implementation of just the string-replacing logic of sed.

The unfortunate thing is that a realistic implementation would need a dictionary of heuristics and definitions - for a program with this name, parse the arguments like so, and based on that pick a pre-written implementation of it, and inline it. So if you have a non-standard or uncommon program, or are using a program in a very unusual or unexpected way, you might need to add/enhance/override the detection heuristics or program definition.

It would also probably never have full coverage over weird behavior edge cases. For example, if you are deliberately doing something weird like sending a SIGSTOP to one process in your shell script while another process piping into it is still running, then you can't optimize that pipeline into one process, at least not in the general case. (On Linux you can signal a specific thread instead of process, but then the sender has to be adjusted too.)

[mentalisttraceur-software]

Code for the Optimizer

After coding for the human, our next priority should be coding for the optimizer. The desire to write the most optimized code is good, but the best way to do that is by writing the most optimizable code.

The easier and simpler it is to analyze code - to prove what can or can't happen, what inputs can have what values, which values depend on each other, when resources are last used, and so on - the lower the bar for turning it into the most efficient form for any given targets and use patterns.

Hand-optimizing code usually destroys or severely obfuscates exactly that information, and often is only more optimal given additional assumptions that are invisible in the code and become false as the underlying hardware and software improves.

This is also a very constructive perspective for preventing premature optimization. Sure, don't optimize until your code has proven itself too slow or too big and you have measured where the worst execution time or space costs are. But nowadays, even after measuring, you might be able to get better performance by making code simpler and clearer, so that automated optimizer passes have an easier time proving what's happening.

[mentalisttraceur-software]

Here's a great talk to watch if you don't yet have the vision for why we should just write code that optimizes for ease of understanding and inferring intent, and focus our performance-improving efforts on writing better optimizer passes: https://youtube.com/watch?v=vzfy4EKwG_Y

Code for the human first, code for the optimizer second. Clear expression of big-picture intent maximizes the information and opportunity for optimizer passes. Hand-optimizing the code to mimick the most efficient machine operations tends to destroy that information or at least raise the bar on how smart optimizer passes should be.