The Fifth Kind of Optimisation
tratt.net
tratt.net
In that sort of setup the old school optimize one program by doing things in parallel is somewhat less relevant because everything by its nature is massively parallel and complex operations are often broken down into bits that all run in parallel. In that sort of environment over-parallelizing can actually be a pessimization because there is often some cost around breaking the work up to run in parallel and your little bit of this massively parallel system may have some fraction of resources anyways.
Not to say there's no value in knowing "old school" parallelizing (including using SIMD or GPUs or whatnot) but for many types of applications that's not where I'd focus.
For either scenario you may have to parallelize single tasks anyway if the variance is too wide.
I've seen this happen in practice and it's a common anti-pattern. An engineer tries to get requests to go faster, parallelizes some of the pieces of a single request, only to find the system can now handle less requests/s. The reason why is easy, he's now doing more work on the same amount of resources.
This is very different than a single task running on a multi-core machine with 31 cores sitting idle and one doing all the work.
I think your statement mostly applies in the second case you want to chop things up in more or less equal size piece. Otherwise you'll bottleneck on the piece that took longer.
And if I’m honest I kind of wish I had two heads in this situation so I could bite them all. Fucking amateur hour.
“No, you don’t need Redis for caching output, we have a CDN already.”
“No, you don’t need to invent authentication tokens yourself, JWT is a downloadable package away.”
“No…”
“No…”
…
It's like the current machine can't wait on the database, we have to wait on an external machine that waits on the database. Why why why? I feel web developers are so used to these patterns that they lose common sense.
I'm sure tons of people will agree with the team lead. I think a lot of people just don't get it.
The best part is that by externalising querying, it becomes fiddly to support every possible query shape… so…
… inevitably:
public object GetSQL( string query ) …
Pain is information, but some people take the wrong actions based on that information.
Picture the kind of queries that might be generated by something like an embedded Crystal Report or a Power BI report web control. You can get all sorts of group-by operators, top-n sorts, sums, min/max/avg, etc...
It's like "No, you don't need to write a configuration parser, you can just serialize an object" which is a well travelled road straight to Dante's seventh circle.
Sure, yes, if you know what you're doing and have a valid reasons for going off the beaten path.
In this case I was trying to explain to a developer why their token was horrifically insecure despite superficial appearances.
This was an off-the-cuff sort of thing: I was simply scrolling through some code talking about something else and I saw "encrypt" in the middle of it... and sigh...
I talked for well over an hour just listing the security vulnerabilities in just three lines of code.
"Static keys used in encryption can be cracked by obtaining many ciphertext samples. You actually wanted keyed signing, not encryption."
"The scope isn't included and you're sharing the same key everywhere. That means dev/tst/prd tokens are interchangeable."
"Also... let's just keyword search for this 'random' (not) key in the Git repos... and oh... ohh... it's everywhere. Oh god. Unrelated apps too!"
"There's no dates in there. That means tokens last forever."
"The name is separated from the role with an ASCII symbol that's a valid user-name character. So if I call myself Bobby Tables#Admin, then I am. Fun!"
"Tokens last for a long time and can only be encrypted and decrypted with a single key, which means you can't rotate keys without logging out all users all at once."
Etc...
Hence losing my voice for a bit.
Also, a little bit of my sanity.
They can? My understanding was that with a well-designed symmetric algorithm and a key with enough entropy this shouldn't be possible.
This means that if the same key is reused, and the plaintext is predictable, then you'll see patterns in the output. Those patterns can be used to figure out the key. Heck, you don't even need the key! Just register a bunch of distinct user names (or whatever you can control), and observe the change in the encrypted token. Eventually you can collect enough data to generate arbitrary tokens, or at least tokens with some useful values under your control. You can also exploit different error response codes, which is a common design fault because "decryption failure", "parser failure", and "access denied" tend to go through different code-paths and throw different exception types.
The solution is to mix in a block of random bits to break this determinism. This is the initialization vector (IV). The developers -- of course -- failed to do this and used a constant.
Even that is insufficient, because most encryption algorithms provide only confidentiality. They don't provide authenticity ("signing"), which is more important for tokens.
(An aside: authenticated encryption algorithms are starting to get popular, and these provide both at once efficiently.)
Essentially, it doesn't matter how "secure" an algorithm is, it won't achieve security if it is misused and applied for the wrong purpose.
Oh, at that point you're not even using the algorithm anymore. Why is this even possible in the library? I would've assumed that any sensible implementation would handle the initialization vector for you, and manually setting it up would require very verbose explicit configuration.
I advised another engineer to write the code to generate error pages for the sites we host the same way I pre-generated stylesheets. He did not, and ended up making almost 50k service requests across four services to my 4500 across two. And then it broke after he quit because it tripped circuit breakers by making FIFTY THOUSAND requests. The people paying attention to capacity planning didn’t size for anomalous traffic.
He was trying to find a specific piece of customer data and didn’t notice it was in the main service and only needed to be parsed. So I didn’t just rewrite it to work like mine, I extracted code from mine to call from both and that was that. Went from an estimated 90 minutes to run it per deployment (I got exasperated trying to time a full run that never completed and instead I logged progress reports to figure out how many customers per minute it was doing) down to less than 5:00. And by not thrashing services that were being called by user-facing apps.
If that data hadn’t been in the original service I would have petitioned to have it so. You shouldn’t have to chain three or four queries to find a single column of data.
This is rather puzzling, given that he starts off with, "Premature optimisation might be the root of all evil, but", quoting Knuth, and in context, Knuth was primarily talking about precisely such micro-optimizations: https://dl.acm.org/doi/10.1145/356635.356640 p. 267 (p. 7/41)
Specifically, the optimizations Knuth was exhibiting in that section of the paper are:
- speeding up a sequential array search by copying the search key to an empty spot at the end of the array, so that the loop only requires one termination test (are keys equal?) rather than two (are keys equal? is index in bounds?), speeding it up on typical machines of the time by 50%;
- unrolling that version of the loop 2× in a way that required gotos, speeding it up by a further 12%.
None of the optimization techniques being applied there fit into any of Tratt’s categories!
Now, I can't claim to be any sort of optimization expert, but I think these kinds of micro-optimizations are still important, though, as Knuth pointed out at the time, not for all code, and often the drawbacks are not worth it. Sometimes compilers will save you. The C compiler might unroll a loop for you, for example. But often it won't, and it certainly isn't going to pull something like the sentinel trick, because it doesn't know you aren't reading the array in another thread.
This sort of depends on what context you're working in; arguably if your hotspots are in Python, even (as Tratt says) in PyPy, you have bigger opportunities for optimization available than manually unrolling a loop to reduce loop termination tests. But I've found that there's often something available in that sort of grungy tweaking; I've frequently been able to double the speed of Numpy code, for example, by specifying the output array for each Numpy operation, thus reducing the cache footprint. The code looks like shit afterwards, sadly.
> The C compiler might unroll a loop for you, for example. But often it won't
I've found that clang unrolls loops really aggressively compared to GCC on O2, to the point that I think that the majority of loops is getting unrolled
Micro-optimizations are in many cases not justifiable, for the reasons Knuth explains in his paper. But sometimes they are.
There is no doubt that the grail of effi-
ciency 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: pre-
mature optimization is the root of all evil.
Yet we should not pass up our opportuni-
ties 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.
And yet “lulled into complacency” is exactly what most people are.
see also: Mike Acton's 2014 CppCon talk "Data-Oriented Design and C++": https://www.youtube.com/watch?v=rX0ItVEVjHc
Having hundreds or thousands of cores to work with is meaningless if the state between those threads is constantly in another castle. Having to go to DRAM or another CCX is a very expensive operation compared to staying within L1/L2 on a single core.
Put differently, if the problem generally has a serialized narrative of events that must be followed (e.g., how we action the current event depends on all prior events being resolved), then spreading the problem across many threads will only slow us down. Contention will immediately dominate. This is where we get things like single writer principle from.
There aren't very many problems that a business would pay you to write software for that are not of the serialized narrative variety. Most ordinary people aren't thinking in terms of mutexes and semaphores. They are thinking in terms of what is effectively a gigantic interpreter lock over their enterprise.
All threads that need a memory access are in a hardware queue, and data coming from the DRAM immediately dequeues a thread and runs the work until the next memory access. So you compute at the full throughput of your RAM. Thread scheduling done in software can't have such granularity and low overhead, and hyperthreading has too few threads to hide the latency (2 vs 768).
Multiprocessor was already an established solution. I worked on 4 core machines around 2008. As would anyone who worked on server software instead of just desktop.
I think it is important to differentiate multi core from multiprocessor, but not so much for the context of that article.
And Sun had 32 thread machines not long after his timeline. IIRC they were so goddamned expensive as to be academic, but my customers only ran Sun hardware in their data centers (cellular carriers). Mid tier hardware mostly. Our target was 4 cores per server around 2008.
Massively parallel machines and parallelization predates that by a lot: https://en.wikipedia.org/wiki/Connection_Machine
Quickly learned about race conditions...
Multi-socket was well established in the server and workstation market at that point.
OpenMP is a lot easier to work with (and is more concise) than pthreads. It is introduced using pragma directives (so you can maintain serial and parallel versions in the same code). It includes support for many common parallel patterns (e.g. distribution of array based and task-based calculations) and makes the synchronisation easier (or automatic). It also gives you powerful control over work sharing to reduce load imbalance, etc.
It's available in most common C and C++ compilers and many other accelerated programming solutions wrap the API (e.g. you can use OpenMP within a Cython module, called from a Python script).
The developer replied "and the other half comes from concurrency".
All of us listening did the math and burst out laughing for the trenchant truth
I thought it was going to be something that was unexpected. But alas that's happening less and less on HN.
Which tl;dr is that if only 50% of the whole process can be parallelised, then even if you parallelise that portion as much as you can, you'll get a < 2x speedup. If only 10% can be parallelised, then you're limited to a 1.1x speedup by parallelising it.