11 ms·

Optimizers need a rethink

149 points by ingve 2y ago

nostromo177 2y ago
[dead]
leni536 2y ago
I think this is mostly a philosphical question, rather than optimizer quality. Once an optimization becomes part of the interface and it is guaranteed, is it really an optimization? Or did it just became part of the language/library/database/whatever? One example is return value optimization in C++. In C++17 the "optimization" became mandatory in some contexts. What really happened though is that the rules of temporary materialization changed, and in those contexts it just never happens prematurely by the language rules. This ceased to be an optimization and became a mechanism in the language. What I'm getting at is that unreliability is a defining quality of optimizations. Sure, there are certain optimizations that become load-bearing, in which case it would be better if they became part of the language's semantics and guarantees, therefore they ceased to be optimizations.
- gizmo686 2y ago
  It is still a useful distinction. Programming languages are complex enough to understand. It is useful to have a base of 'this is the simplest description of how programs will work' that is as simple as possible. Then, a separate set of 'and here is a separate description of its performance characteristics; nothing in this portion should be understood to change the defined behavior of any program". Even if that second description is stable and part of the guarantees you make, keeping it seperate is still incredibly useful from a user perspective. From an implementation perspective, there is also a useful distinction. Optimizations take a valid representation, and turn it into a different valid representation of the same type that shares all defined behavior. This is a fairly different operation than compilation, which converts between representations. In particular, for the compilation step, you typically have only one compilation function for a given pair of representations; and if you have multiple, you select one ahead of time. For optimizations, each representation has a set of optimization functions, and you need to decided what order to apply them and how many times to do so. Compilation functions, for their part, need to deal with every difference between the two representations, whereas optimization functions get to ignore everything except the part they care about.
- account42 2y ago
  C++ return value optimization has always been a language feature rather than a true optimization because it is/was allowed to change the observable behavior of the program.
nanolith 2y ago
One area that I have been exploring is building equivalence proofs between high-level specifications, an implementation in C, and the machine code output from the compiler. I'm still very early in that work, but one of my hopes is to at least demonstrate that the output still meets the specifications, and that we can control things like timing (e.g. no branching on secret data) and cache in this output. I think that the compilation and optimization step, as a black box, is a disservice for highly reliable software development. Compiler and optimizer bugs are definitely a thing. I was bitten by one that injected timing attacks into certain integer operations by branching on the integer data in order to optimize 32-bit multiplications on 8-bit microcontrollers. Yeah, this makes perfect sense when trying to optimize fixed point multiplication, but it completely destroys the security of DLP or ecDLP based cryptography by introducing timing attacks that can recover the private key. Thankfully, I was fastidious about examining the optimized machine code output of this compiler, and was able to substitute hand coded assembler in its place.
- cesarb 2y ago
  > One area that I have been exploring is building equivalence proofs between high-level specifications, an implementation in C, and the machine code output from the compiler. AFAIK, that's how seL4 is verified. Quoting from https://docs.sel4.systems/projects/sel4/frequently-asked-questions.html#what-does-sel4s-formal-verification-mean https://docs.sel4.systems/projects/sel4/frequently-asked-que... "[...] Specifically, the ARM, ARM_HYP (ARM with virtualisation extensions), X64, and RISCV64 versions of seL4 comprise the first (and still only) general-purpose OS kernel with a full code-level functional correctness proof, meaning a mathematical proof that the implementation (written in C) adheres to its specification. [...] On the ARM and RISCV64 platforms, there is a further proof that the binary code which executes on the hardware is a correct translation of the C code. This means that the compiler does not have to be trusted, and extends the functional correctness property to the binary. [...] Combined with the proofs mentioned above, these properties are guaranteed to be enforced not only by a model of the kernel (the specification) but the actual binary that executes on the hardware."
  - nanolith 2y ago
sebmellen 2y ago
I like that the author included their intended audience up front. Definitely not me, but it helped me read the article with a different perspective.
keybored 2y ago
The standard optimization user case story is absurd. 1. You’re not gonna get any guarantees that the optimization will happen. That makes it High Level. Just write code. We won’t force you to pollute your code with ugly annotations or pragmas. 2. In turn: check the assembly or whatever the concrete thing that reveals that the optimization you wished for in your head actually went through There’s some kind of abstraction violation in the above somewhere.
- jiggawatts 2y ago
  I have the same experience with database query planners. The promise is that you just write your business logic in SQL and the planner takes care of the rest. In practice you spend weeks staring at execution plans.
  - dspillett 2y ago
    A key difference between many compilers and DB query planners, is that a compiler can spend more time over its optimisations because it is run dev-side and the benefits (and none of the time taken) are felt by the users. A query planner needs to be more conservative with its resource use. This is not true of JIT compilers, of course, which have similar constraints to DB query planners. In these cases the goal is to do a good job pretty quickly, rather than an excellent job in a reasonable time.
    - jiggawatts 2y ago
      > A query planner needs to be more conservative with its resource use. The number of possible distinct query plans grows very rapidly as the complexity increases (exponentially or factorially... I can't remember). So even if you have 10x as much time available for optimisation, it makes a surprisingly small difference. One approach I've seen with systems like Microsoft Exchange and its undrelying Jet database is that queries are expressed in a lower-level syntax tree DOM structure. The specific query plan is "baked in" by developers right from the beginning, which provides stable and consistent performance in production. It's also lower latency because the time spent by the optimiser at runtime is zero.
pizlonator 2y ago
Compiler optimizers are designed from a “win in the average” mindset - so whether a particular optimization succeeds or not is really not something the user ought to rely on. If you’re relying on it then you’re playing with fire. (I say that as someone who has played with this particular kind of fire. Sometimes I’m ok, other times I get burned.) A great example of when winning in the average works is register allocation. It’s fine there because the cost of any particular variable getting spilled is so low. So, all that matters is that most variables are in registers most of the time. If spill heuristics change for the better, it usually means some of your variables that previously got spilled now are in registers while others that were in registers are now spilled - and the compiler writer declares victory if this is a speedup in some overall average of large benchmarks. Similar thinking plays out in stuff like common subexpression elimination or basically any strength reduction. (In fact, most of those optimizations have the peculiar property that you’ll always be able to craft a program that shows the optimization to be a bad idea; we do them anyway because on average they are a speedup.) In my view, if a compiler optimization is so critical that users rely on it reliably “hitting” then what you really want is for that optimization to be something guaranteed by the language using syntax or types. The way tail calls work in functional languages comes to mind. Also, the way value types work in C#, Rust, C++, etc - you’re guaranteed that passing them around won’t call into the allocator. Basically, relying on the compiler to deliver an optimization whose speedup from hitting is enormous (like order of magnitude, as in the escape analysis to remove GC allocations case) and whose probability of hitting is not 100% is sort of a language design bug. This is sort of what the article is saying, I guess. But for example on the issue of the optimizer definitely removing a GC allocation: the best design there is for the GC’d language to have a notion of value types that don’t involve allocation at all. C# has that, Java doesn’t.
- pjmlp 2y ago
  Java doesn't have it yet, but they are making progress, https://jdk.java.net/valhalla/ https://jdk.java.net/valhalla/ Yes, it was a bummer that Java didn't take up on the ideas of Cedar, Oberon linage, Modula-3, Eiffel,... even though some are quoted as its influences. Still I am confident that it might be getting value types, before C++ reflection, networking, senders/receivers, or safety gets sorted out. Or even that we can finally write portable C++ code using C++20 modules.
jonstewart 2y ago
At least databases have Explain. I'd love to get feedback from clang or gcc about why particular optimizations were not applied.
- einpoklum 2y ago
  Explain doesn't give you that information in many (most?) DBMSes. It's a bit like seeing the compiler IR code of your program. It lets you understand some things, while others remain a mystery.
- typesanitizer 2y ago
  I'm guessing you've tried these flags mentioned in the blog post but haven't had luck with them? > LLVM supports an interesting feature called Optimization Remarks – these remarks track whether an optimization was performed or missed. Clang support recording remarks using -fsave-optimization-record and Rustc supports -Zremark-dir=<blah>. There are also some tools (opt-viewer.py, optview2) to help view and understand the output.
gpm 2y ago
Arguing against query planning by pointing at a quote about databases is wild. Automatic query planning is ubiquitous and hugely succesfull in databases.
- bsder 2y ago
  And sometimes highly problematic. I'm surprised that the "query planner" doesn't have a way to eject an opaque object that is the "assembly language of the query" that you can run that it is not allowed to change.
  - gpm 2y ago
    Sure. It's definitely a tradeoff which definitely hurts on rare occasion. I agree that the lack of fallback in most databases is a bit strange. Altogether though the productivity benefits have proven larger than the drawbacks of not defaulting to a query planner.
  - twoodfin 2y ago
    Several commercial databases offer this capability, under a term like “frozen plans”.
- typesanitizer 2y ago
  I've added a clarification in the post to make my position explicit: > This is not to imply that we should get rid of SQL or get rid of query planning entirely. Rather, more explicit planning would be an additional tool in database user’s toolbelt. I'm not sure if there was some specific part of the blog post that made you think I'm against automatic query planning altogether; if there was, please share that so that I can tweak the wording to remove that implication.
  - gpm 2y ago
    > I'm not sure if there was some specific part of the blog post that made you think I'm against automatic query planning altogether; if there was, please share that so that I can tweak the wording to remove that implication. The quote from another article (which I didn't read) starting with "I dislike query planners". "Against ... altogether" is mildly stronger than I took away from this, more like "generally of the opinion that the tradeoff nearly everyone is making with sql isn't worth it". Judging by the lack of upvotes other people didn't react as strongly to this quote as I did, so take it as you will.
skybrian 2y ago
> The optimizer’s behavior is in some contexts load-bearing and has little margin for error (e.g. missing an optimization). Well, sure, sometimes, to an extent. But if it's load-bearing, maybe that's a bug? You might have written non-portable code that won't last, because it depends on an implementation detail that isn't standardized. There are widespread applications where performance isn't critical. For example, any time you do a network request. Web pages shouldn't break because the network is slow today, if you can possibly avoid it. The web provides no performance guarantees, but it tries pretty hard to provide compatibility guarantees. Your code should, usually, work on new browser versions and on devices that haven't been released yet. New browsers will have different JIT compilers with different performance cliffs. And yet, there are websites written many years ago that still work. When standardizing things, we need to be precise about what's standardized and what isn't, or protocols "rust shut" and can't be changed without breaking lots of stuff. Not standardizing performance is often a win. (With some exceptions like video game consoles where the hardware is standardized.) Hyrum's law suggests that all compiler optimizations will eventually be load-bearing for someone, but we should usually try to avoid it. To make sure that the code is robust, perhaps performance should vary. Maybe it would be useful to have something like a chaos monkey for programs, where optimizations vary based on a random seed?
- bsder 2y ago
  > But if it's load-bearing, maybe that's a bug? If your "debug optimization" code is so slow as to be unusable (see: Rust), then your optimizations qualify as load-bearing. The problem is that "optimization level" needs a mindset change. The optimization levels should be "release", "small" and "experimental". "Release level" needs to be perfectly usable for debugging as well as in production--"debug level" should be "release level". Compilation time should be reasonable and run time should be functional. After that, for embedded, you should have "small level"--checks should get turned off and any optimizations that make code significantly bigger should get turned off (loop unrolling, for example). You might enable some optimizations that make compile time brutally slow. Finally, there should be an "experimental level" which tests out optimizations before they go into release. And there should be no "fast" optimization level. If your optimization is that situation specific, it should stay stuck in "experimental". And through all of this, the compiler should also eject files that carry enough information to allow debuggers to make sense of the compiled code, unwind the optimizations when the users asks, and present a coherent version of what is going on. This is actually where compilers really break down nowadays. The compiler needs to eject enough information and context that a debugger can unwind what is going on rather than being an afterthought. We need the equivalent of an LSP (Language Server Protocol) for debuggers.
f33d5173 2y ago
the optimizer should be a magic black box. As soon as you start demanding a particular optimization, it shouldn't be an optimization anymore. In C you have inline assembly and intrinsics and pragmas and macros and so on. If you want the compiler to compile your code a particular way you should be using these, not trying to wrangle the optimizer to invoke a particular optimization.
- dzaima 2y ago
  Except even intrinsics aren't even that much of a guarantee - clang converts them to its internal operations and applies the same optimization passes over them as it does on its own autovectorized code; and there are no intrinsics for x86's inline memory operands, so issues can arise around those (or the inverse - I've seen clang do a memory load of the same constant twice (the second one being behind some branches), despite there being only one such load). And there also are no intrinsics for most scalar operations, e.g. if you wanted to force "x>>48 == 0x1234" to be actually done via the shift and not "x & 0xffff000000000000 == 0x1234000000000000" (or vice versa). And of course assembly means writing platform-specific code (potentially undesirable even if you want to only do the optimization for a single architecture, as it means having to learn to write assembly of said architecture). There is some potential middle-ground of doing black-boxing, but as-is in C/C++ the way to do this is with a no-op asm block, but that can make register allocation worse, and still requires some platform-specific logic for deriving the register kind from value type.
QuadmasterXLII 2y ago
Frankly, the problem is that (generally, across languages various compiler hints) @inline sometimes fails to inline. At this point I’ve given up on ever having an @inline that reliably inlines, and I would very happily settle for an @assert_inline that doesn’t change the generated assembly at all but reliably crashes out if the function isn’t inline. Julia is by far the worst language about this. It would be vastly more usable with the addition of @assert_type_stable, @assert_doesn’t_allocate, and @assert_doesn’t_error macros.
- dzaima 2y ago
  With gcc & clang you can use __attribute__((always_inline)) to force-inline, even at -O0, giving an error if it's impossible.
- andyferris 2y ago
  On the Julia front, I believe the evolving effect system may help a little bit with obtaining/surfacing that information. JET.jl should be able to solve the type stability (inference) one from a whole-of-program perspective. We have `@inferred` for unit tests. The macros would be a cool addition - I wonder if they would get overused though? I agree that Julia takes the idea of optimization to the extreme - it's semantically a very dynamic language and only fast due to non-semantically guaranteed optimization. On the other hand, getting access to the generated IR, LLVM and assembly and iteratively improving it is far easier than any other language I've seen.
  - pjmlp 2y ago
    What Julia offers is quite common in Common Lisp systems.
- affinepplan 2y ago
  just in case you're interested, Julia does (now) have tools similar to what you're describing, although of course there are still be lots of possible improvements to be made w.r.t. their UX to make these tools more reliable and easier to use in particular @assert_type_stable and @assert_doesn't_error is largely provided by JET.jl and the effects system, and @assert_doesn't_allocate is (at least partially) provided in AllocCheck.jl
h1fra 2y ago
I don't hate query planning, some people are better than me at writing algo and the database knows my data better than me. However, what I hate is the lack of transparency (and I feel like this article tries to pin-point just this). When I execute a query locally I get a different plan vs staging vs prod. A plan than can also change depending on some parameters or load or size. I don't care about understanding all the underlying optimizations, I just care that the query plan I saw is the same and is still the same in prod, and that I can be warned when it changes. PG does not return the hash of the query plan or metrics along the data, which is imo a mistake. With this you could track it in your favorite metrics store and be able to point when and why stuff are executing differently.
- wrs 2y ago
  Yes! The thing with SQL is that the DB “recompiles” the query plan from source every time you do the query. That results in changes at runtime, which are often good and healthy changes, but are sometimes a very bad surprise. I like the metrics idea, but by the time you see the change in the metric, it’s too late. For critical queries it might be helpful to be able to “freeze” a query plan just as one “freezes” a binary executable by compiling. In other words, let the query planner do its job, but only at a time of your choosing, so the performance of a production system doesn’t change suddenly. So no hints in the source, just an opaque token representing a compiled query plan that can be deployed alongside a binary. With tooling you could be notified if the planner wants to do it differently and decide whether to deploy the new plan, after testing. (And again, you’d only do this for a critical subset of your choice.)
einpoklum 2y ago
From the article: > Have a good mental model of what the optimizer can and cannot do. Most DB query planner designers and implementers have little imagination, and their mental model of what optimizers can and cannot do is, well, extremely narrow-minded. There is huge unexplored space of what query planning can be (at least for analytic queries, and we think in columnar terms) - if we just stop insisting on thinking of DBMS operations as black boxes.
mcfig 2y ago
Great article. One real case I encountered that I find thought provoking, is where a bunch of test failures were bucketed into the same bucket because link-time code-generation had noticed that a bunch of C++ getter functions had the same output code and combined them all. So stack traces became confusing because the address-to-symbol mapping was more complicated than the logic we had in place was prepared for. i.e. optimization had violated a rule we were implicitly relying on (that each non-inlined function should start at a distinct address, so that address-to-symbol mapping could be done easily). But that’s not an explicit guarantee and optimizers don’t seem to think about it much. (Well for inlining it seems to have had some thought, still sucks, but anyway this case doesn’t fit the pattern of inlining). I find it hard to say anyone is dead wrong in this case… but I would turn off that LTCG optimization any time I could, except where proven necessary.
andyferris 2y ago
If you have any language where it is "semantially correct" to execute it with a simple interpetter, than all optimizations in that language are not semantically important by definition, right? I've even seen interpretters for C... so while I 100% have felt the pain in this article, I don't know where that leaves us? These are more like compilation assertions/strategies than language features. (Not that these shouldn't be written inline with the code, e.g. it can be nice to write unit tests in the same files as the code in some languages). In the case of SQL, I'd love access to a flavor where I do the joins on indices explicitly, the query is executed as written, and each join (or filter) can be annoted with a strategy (btree lookup, etc). (The most difficult part about using indices by hand is correctly writing all the synchronous triggers on updates, not the queries, IMO).
- typesanitizer 2y ago
  > If you have any language where it is "semantially correct" to execute it with a simple interpetter, than all optimizations in that language are not semantically important by definition, right? Technically, yes. :) But I think this should perhaps be treated as a bug in how we define/design languages, rather than as an immutable truth. - We already have time-based versioning for languages. - We also have "tiers" of support for different platforms in language implementations (e.g. rarer architectures might have Tier 2 or Tier 3 support where the debugging tooling might not quite work) One idea would be to introduce "tiers" into a language's definition. A smaller implementation could implement the language at Tier 1 (perhaps this would even be within reach for a university course project). An industrial-strength implementation could implement the language at Tier 3. (Yes, this would also introduce more complications, such as making sure that the dynamic semantics at different tiers are equivalent. At that point, it becomes a matter of tradeoffs -- does introducing tiers help reduce complexity overall?)
- Archit3ch 2y ago
  > If you have any language where it is "semantially correct" to execute it with a simple interpetter, than all optimizations in that language are not semantically important by definition, right? Not when "correct" needs optimizations to meet real-time guarantees. It's hard to argue that a program which doesn't run is "correct".
WalterBright 2y ago
> D has first-class support for marking functions as “no GC”. It never occurred to me that this would be considered a hint to the optimizer. It doesn't affect code generation. What it does do is flag any use of the gc in the function and any functions it transitively may call. Optimizers have been likened to turning a cow into a hamburger. If you're symbolically debugging optimized code, you're looking at the hamburger. Nobody has been able to solve that problem. It's true that optimizers themselves are hard to show being correct. The one in the D compiler is a conventional DFA optimizer that uses data flow equations I learned from Hennessy and Ullman in a 1982 seminar they taught. So it has been battle tested for 42 years now(!) and it's pretty rare to find a problem with it, unless it's a new pass I added like SROA. The idea is anytime a problem is identified and corrected, it goes into the test suite. This has the effect of always ratcheting it forward and not regress. The GC dates from around 2000, when I wrote it for a Javascript engine. It was brutally tested for that, and has been pretty solid ever since. People complain about the GC, but not about it being buggy. A buggy GC is a real horror show as it is painfully difficult to debug.
- typesanitizer 2y ago
  Thanks for the feedback. The preceding paragraph had "and occasionally language features" so I thought it would be understood that I didn't mean it as an optimizer-specific thing, but on re-reading the post, I totally see how the other wording "The knobs to steer the optimizer are limited. Usually, these [...]" implies the wrong thing. I've changed the wording to be clearer and put the D example into a different bucket. > In some cases, languages have features which enforce performance-related properties at the semantic checking layer, hence, granting more control that integrates with semantic checks instead of relying on the optimizer: > > - D has first-class support for marking functions as “no GC”.
  - WalterBright 2y ago
    That's better, thanks!
- saagarjha 2y ago
  Languages that run in a VM are pretty good at turning the hamburger back into a cow when you're looking at it.
pornel 2y ago
Optimizations in compilers like LLVM are done by many individual code transformation passes, one applied to the result of the previous. This layering makes the order of the passes important and very sensitive. The passes usually don't have a grand plan, they just keep shuffling code around in different ways. A pass may only be applicable to code in a specific form created by a previous simplification pass. One pass may undo optimizations of a previous pass, or optimize-out a detail required by a later pass. Separation into passes makes it easier to reason about correctness of each transformation in isolation, but the combined result is kinda slow and complicated.
CalChris 2y ago
We are nearing the death of Proebsting's Law. AMD CEO Lisa Su's HotChips’19 keynote said that compilers had accounted for 8% performance increase over the decade. That means compilers are now only doubling performance every 90 years. https://www.youtube.com/watch?v=nuVBid9e3RA https://www.youtube.com/watch?v=nuVBid9e3RA
Mikhail_Edoshin 2y ago
One of reasons SQL is declarative is that queries run concurrently yet give the illusion of working in isolation. And unlike the concurrency of independent processes, which is mostly mechanical, this one involves detailed coordination because database queries work on the same data. With these constraints it may be not that easy to come up with an imperative model that is as simple as the current declarative one.
yxhuvud 2y ago
No. Language designers need to think about what their language promises and when some users have differing needs, they may need to fulfill those needs.
froh 2y ago
in the "closing thoughts" [1] of the OP article there's a pointer to "Proebstrings law" [2] which got me to a benchmark [3] how LLVM has improved over 10 years from 2.7 to 11 which leaves me with the strong intuition that indeed what mit benefit more from a rethink is not optimizers but focus on programmer productivity > Perhaps this means Programming Language Research should be concentrating on something other than optimizations. Perhaps programmer productivity is a more fruitful arena. [1] https://typesanitizer.com/blog/rethink-optimizers.html#closing-thoughts https://typesanitizer.com/blog/rethink-optimizers.html#closi... [2] https://proebsting.cs.arizona.edu/law.html https://proebsting.cs.arizona.edu/law.html [3] https://zeux.io/2022/01/08/on-proebstings-law/ https://zeux.io/2022/01/08/on-proebstings-law/
kragen 2y ago
Daniel Bernstein has given an interesting talk about "the death of optimizing compilers" (PDF slides at https://cr.yp.to/talks/2015.04.16/slides-djb-20150416-a4.pdf https://cr.yp.to/talks/2015.04.16/slides-djb-20150416-a4.pdf) claiming that less and less of our code is in that middle ground where it's performance-critical enough to risk running it through an optimizer but not so performance-critical that it needs to be rewritten in assembly. If we think of the high-level source code (whether in SQL, JS, or Python) as being a functional spec that the low-level implementation should provably follow, maybe we should check them both in, and at build time, run a proof assistant to verify that the implementation still complies with the spec? Rather than running an optimizing compiler every time. I think this is what nanolith is suggesting in https://news.ycombinator.com/item?id=41965701 https://news.ycombinator.com/item?id=41965701. Maybe you run the optimizing compiler once when you first write the code, and again when the proof assistant tells you an optimization is no longer valid, but you check the output before you check it in. Or maybe you have the compiler running all the time on a GPU cluster looking for new optimizations.
- 082349872349872 2y ago
  > maybe you have the compiler running all the time ... looking for new optimizations Anyone know if there was ever a retrospective on https://github.com/webyrd/Barliman https://github.com/webyrd/Barliman ?
  - kragen 2y ago
    I haven't seen one. He's apparently morphing into a YouTuber, though, so maybe we should grep his .vtts.
  - tmtvl 2y ago
    Will is on HN*, though I don't know whether he'll see this topic. * https://news.ycombinator.com/user?id=will_byrd https://news.ycombinator.com/user?id=will_byrd
  - gradschoolfail 2y ago
    Sufficiently “advanced”* program synthesis is indistinguishable from compiler optimization? *(= “correct”?) [sufficiently constrained madness is indistinguishable from ikigai?]
account42 2y ago
I'm not sure if this is the right way to look at it? Do you really care if some optimization was performed or not or do you only care about the performance characteristics of the resulting program? Maybe a more sensible solution would be to have better tests for performance regressions. Still not an easy task (performance is often highly dependent on the input and regressions can hide in very specific cases) but makes more sense to me than writing high level code and then worrying about the details of how the compier translated that high level code.
JonChesterfield 2y ago
The thing where people quote optimisers as only eeking out tiny percentages of performance over decades really annoys me. It's true for the numerical kernels written in C and Fortran where the code is essentially optimal already, and all the compiler has to do is not screw it up. It's grossly false for the vast majority of code, where the sludge written by thousands of engineers gets completely rewritten by the compiler before it executes. Compilers are the reason unskilled devs manage to get tolerable performance out of frameworks. The cpython is slow complaints? That's what life without a good compiler looks like.
- klodolph 2y ago
  “CPython is slow” is kind of a complaint about the Python object model. I’m not sure that I would pin this one on the compiler, per se. Everything you do in Python involves chasing down pointers and method tables, looking up strings in dictionaries, and that sort of thing. Maybe it’s splitting hairs to talk about whether this is down to the compiler or the language. > It's grossly false for the vast majority of code, where the sludge written by thousands of engineers gets completely rewritten by the compiler before it executes. It used to be true, for sure. What has changed since then is not the sludge or bloat or many cooks. Instead, the major change is that we have written a bunch of code on top of optimizing compilers with the assumption that these optimizations are happening. For example, nowadays, you might write C++ code with a deep call stack and lots of small functions (e.g. through templates), and it’s fast because the compiler inlines and then optimizes the result. Back in the 1990s, you would not have written code that way because the compiler would have choked on it. You see a lot more macro use in code from the 1990s rather than functions, because programmers didn’t trust that the functions will get inlined.
  - arka2147483647 2y ago
    > Everything you do in Python involves chasing down pointers and method tables, looking up strings in dictionaries, and that sort of thing. One of the things that a Cpp Compiler can do is De-Virtualize Function Calls. That is; solve those function pointer tables at Compile Time. Why could not a good compiler for Python do the same?
russellsprouts 2y ago
This reminds me of Halide (https://halide-lang.org/ https://halide-lang.org/), which is a really interesting design in this direction. In Halide, you specify the algorithm at a high level, then specify the "schedule" (execution order, vectorization, storage) separately. Then, it verifies that the two match. For tight loops like image kernels, it's often counter-intuitive which execution plan will give the best performance, so being able to experiment with the guarantee that you are still implementing the algorithm correctly is valuable. For a database, it would be as if you could send a high level SQL query and an execution plan together. Halide is very specific, but I could imagine a general-purpose language with a Python-like high level representation for code behavior, with the option to specify a lower-level implementation with a lot of performance annotations.
taeric 2y ago
I think this is misplacing the need for a rethink. Compilers are amazing at optimizing small programs. What they are less amazing at is optimizing large programs. The query planner for SQL databases is a good example of this. For small queries, the odds of the planner making a bad choice is rather low. Large queries, on the other hand, are comparatively easy to lead down a bad path. This is why the "no sql" family of databases see more predictable results for a lot of uses. If you can't do complicated queries, then you don't have that peril to worry about. Worth trying if you have the programs to play with. Run it with and without -O3 and see how the compiler does for you.
- sealeck 2y ago
  > This is why the "no sql" family of databases see more predictable results for a lot of uses. If you can't do complicated queries, then you don't have that peril to worry about. Can't you also just, well, not use complicated SQL queries?
  - taeric 2y ago
    Certainly, and that is my point? Throwing out query planners feels like the wrong thing to consider. Instead, focus on keeping the things being planned smaller.
looneysquash 2y ago
The postgresql query optimization one is an interesting one. I've been very frustrated at times that you can't just tell it to use a certain index or a certain query plan. But at the same time, the data in the table can change over time. So for that particular problem, postgresql's superpower is it can optimize and reoptimize your query at runtime as the data changes! Not an easy thing to do in most programming languages. But I do agree with the rest of the article to a large extent. For some cases, you need a way to say "do this optimization, fail to compile if you cannot". Most of the time though, I just want the optimizer to do it's best, and don't have something in particular in mind. What if the compiler could output the optimization or transformations it does to a file? A file that was checked into source code. Think of lockfiles for dependencies. Or snapshot testing. I don't mean output the entire IR. I mean more a list of applied transformations. When those change, you could then be aware of those changes. Maybe it could act as an actual lockfile and constrain the compiler? Could it also double as a cache and save time?
- deleted 2y ago
  [deleted]

149 points by ingve 2y ago

[dead]

I think this is mostly a philosphical question, rather than optimizer quality. Once an optimization becomes part of the interface and it is guaranteed, is it really an optimization? Or did it just became part of the language/library/database/whatever? One example is return value optimization in C++. In C++17 the "optimization" became mandatory in some contexts. What really happened though is that the rules of temporary materialization changed, and in those contexts it just never happens prematurely by the language rules. This ceased to be an optimization and became a mechanism in the language. What I'm getting at is that unreliability is a defining quality of optimizations. Sure, there are certain optimizations that become load-bearing, in which case it would be better if they became part of the language's semantics and guarantees, therefore they ceased to be optimizations.

gizmo686 2y ago
It is still a useful distinction. Programming languages are complex enough to understand. It is useful to have a base of 'this is the simplest description of how programs will work' that is as simple as possible. Then, a separate set of 'and here is a separate description of its performance characteristics; nothing in this portion should be understood to change the defined behavior of any program". Even if that second description is stable and part of the guarantees you make, keeping it seperate is still incredibly useful from a user perspective. From an implementation perspective, there is also a useful distinction. Optimizations take a valid representation, and turn it into a different valid representation of the same type that shares all defined behavior. This is a fairly different operation than compilation, which converts between representations. In particular, for the compilation step, you typically have only one compilation function for a given pair of representations; and if you have multiple, you select one ahead of time. For optimizations, each representation has a set of optimization functions, and you need to decided what order to apply them and how many times to do so. Compilation functions, for their part, need to deal with every difference between the two representations, whereas optimization functions get to ignore everything except the part they care about.
account42 2y ago
C++ return value optimization has always been a language feature rather than a true optimization because it is/was allowed to change the observable behavior of the program.

nanolith 2y ago

One area that I have been exploring is building equivalence proofs between high-level specifications, an implementation in C, and the machine code output from the compiler. I'm still very early in that work, but one of my hopes is to at least demonstrate that the output still meets the specifications, and that we can control things like timing (e.g. no branching on secret data) and cache in this output. I think that the compilation and optimization step, as a black box, is a disservice for highly reliable software development. Compiler and optimizer bugs are definitely a thing. I was bitten by one that injected timing attacks into certain integer operations by branching on the integer data in order to optimize 32-bit multiplications on 8-bit microcontrollers. Yeah, this makes perfect sense when trying to optimize fixed point multiplication, but it completely destroys the security of DLP or ecDLP based cryptography by introducing timing attacks that can recover the private key. Thankfully, I was fastidious about examining the optimized machine code output of this compiler, and was able to substitute hand coded assembler in its place.

cesarb 2y ago
> One area that I have been exploring is building equivalence proofs between high-level specifications, an implementation in C, and the machine code output from the compiler. AFAIK, that's how seL4 is verified. Quoting from https://docs.sel4.systems/projects/sel4/frequently-asked-questions.html#what-does-sel4s-formal-verification-mean https://docs.sel4.systems/projects/sel4/frequently-asked-que... "[...] Specifically, the ARM, ARM_HYP (ARM with virtualisation extensions), X64, and RISCV64 versions of seL4 comprise the first (and still only) general-purpose OS kernel with a full code-level functional correctness proof, meaning a mathematical proof that the implementation (written in C) adheres to its specification. [...] On the ARM and RISCV64 platforms, there is a further proof that the binary code which executes on the hardware is a correct translation of the C code. This means that the compiler does not have to be trusted, and extends the functional correctness property to the binary. [...] Combined with the proofs mentioned above, these properties are guaranteed to be enforced not only by a model of the kernel (the specification) but the actual binary that executes on the hardware."
- nanolith 2y ago

sebmellen 2y ago

I like that the author included their intended audience up front. Definitely not me, but it helped me read the article with a different perspective.

keybored 2y ago

The standard optimization user case story is absurd. 1. You’re not gonna get any guarantees that the optimization will happen. That makes it High Level. Just write code. We won’t force you to pollute your code with ugly annotations or pragmas. 2. In turn: check the assembly or whatever the concrete thing that reveals that the optimization you wished for in your head actually went through There’s some kind of abstraction violation in the above somewhere.

jiggawatts 2y ago
I have the same experience with database query planners. The promise is that you just write your business logic in SQL and the planner takes care of the rest. In practice you spend weeks staring at execution plans.
- dspillett 2y ago
  A key difference between many compilers and DB query planners, is that a compiler can spend more time over its optimisations because it is run dev-side and the benefits (and none of the time taken) are felt by the users. A query planner needs to be more conservative with its resource use. This is not true of JIT compilers, of course, which have similar constraints to DB query planners. In these cases the goal is to do a good job pretty quickly, rather than an excellent job in a reasonable time.
  - jiggawatts 2y ago
    > A query planner needs to be more conservative with its resource use. The number of possible distinct query plans grows very rapidly as the complexity increases (exponentially or factorially... I can't remember). So even if you have 10x as much time available for optimisation, it makes a surprisingly small difference. One approach I've seen with systems like Microsoft Exchange and its undrelying Jet database is that queries are expressed in a lower-level syntax tree DOM structure. The specific query plan is "baked in" by developers right from the beginning, which provides stable and consistent performance in production. It's also lower latency because the time spent by the optimiser at runtime is zero.

pizlonator 2y ago

Compiler optimizers are designed from a “win in the average” mindset - so whether a particular optimization succeeds or not is really not something the user ought to rely on. If you’re relying on it then you’re playing with fire. (I say that as someone who has played with this particular kind of fire. Sometimes I’m ok, other times I get burned.) A great example of when winning in the average works is register allocation. It’s fine there because the cost of any particular variable getting spilled is so low. So, all that matters is that most variables are in registers most of the time. If spill heuristics change for the better, it usually means some of your variables that previously got spilled now are in registers while others that were in registers are now spilled - and the compiler writer declares victory if this is a speedup in some overall average of large benchmarks. Similar thinking plays out in stuff like common subexpression elimination or basically any strength reduction. (In fact, most of those optimizations have the peculiar property that you’ll always be able to craft a program that shows the optimization to be a bad idea; we do them anyway because on average they are a speedup.) In my view, if a compiler optimization is so critical that users rely on it reliably “hitting” then what you really want is for that optimization to be something guaranteed by the language using syntax or types. The way tail calls work in functional languages comes to mind. Also, the way value types work in C#, Rust, C++, etc - you’re guaranteed that passing them around won’t call into the allocator. Basically, relying on the compiler to deliver an optimization whose speedup from hitting is enormous (like order of magnitude, as in the escape analysis to remove GC allocations case) and whose probability of hitting is not 100% is sort of a language design bug. This is sort of what the article is saying, I guess. But for example on the issue of the optimizer definitely removing a GC allocation: the best design there is for the GC’d language to have a notion of value types that don’t involve allocation at all. C# has that, Java doesn’t.

pjmlp 2y ago
Java doesn't have it yet, but they are making progress, https://jdk.java.net/valhalla/ https://jdk.java.net/valhalla/ Yes, it was a bummer that Java didn't take up on the ideas of Cedar, Oberon linage, Modula-3, Eiffel,... even though some are quoted as its influences. Still I am confident that it might be getting value types, before C++ reflection, networking, senders/receivers, or safety gets sorted out. Or even that we can finally write portable C++ code using C++20 modules.

jonstewart 2y ago

At least databases have Explain. I'd love to get feedback from clang or gcc about why particular optimizations were not applied.

einpoklum 2y ago
Explain doesn't give you that information in many (most?) DBMSes. It's a bit like seeing the compiler IR code of your program. It lets you understand some things, while others remain a mystery.
typesanitizer 2y ago
I'm guessing you've tried these flags mentioned in the blog post but haven't had luck with them? > LLVM supports an interesting feature called Optimization Remarks – these remarks track whether an optimization was performed or missed. Clang support recording remarks using -fsave-optimization-record and Rustc supports -Zremark-dir=<blah>. There are also some tools (opt-viewer.py, optview2) to help view and understand the output.

gpm 2y ago

Arguing against query planning by pointing at a quote about databases is wild. Automatic query planning is ubiquitous and hugely succesfull in databases.

bsder 2y ago
And sometimes highly problematic. I'm surprised that the "query planner" doesn't have a way to eject an opaque object that is the "assembly language of the query" that you can run that it is not allowed to change.
- gpm 2y ago
  Sure. It's definitely a tradeoff which definitely hurts on rare occasion. I agree that the lack of fallback in most databases is a bit strange. Altogether though the productivity benefits have proven larger than the drawbacks of not defaulting to a query planner.
- twoodfin 2y ago
  Several commercial databases offer this capability, under a term like “frozen plans”.
typesanitizer 2y ago
I've added a clarification in the post to make my position explicit: > This is not to imply that we should get rid of SQL or get rid of query planning entirely. Rather, more explicit planning would be an additional tool in database user’s toolbelt. I'm not sure if there was some specific part of the blog post that made you think I'm against automatic query planning altogether; if there was, please share that so that I can tweak the wording to remove that implication.
- gpm 2y ago
  > I'm not sure if there was some specific part of the blog post that made you think I'm against automatic query planning altogether; if there was, please share that so that I can tweak the wording to remove that implication. The quote from another article (which I didn't read) starting with "I dislike query planners". "Against ... altogether" is mildly stronger than I took away from this, more like "generally of the opinion that the tradeoff nearly everyone is making with sql isn't worth it". Judging by the lack of upvotes other people didn't react as strongly to this quote as I did, so take it as you will.

skybrian 2y ago

> The optimizer’s behavior is in some contexts load-bearing and has little margin for error (e.g. missing an optimization). Well, sure, sometimes, to an extent. But if it's load-bearing, maybe that's a bug? You might have written non-portable code that won't last, because it depends on an implementation detail that isn't standardized. There are widespread applications where performance isn't critical. For example, any time you do a network request. Web pages shouldn't break because the network is slow today, if you can possibly avoid it. The web provides no performance guarantees, but it tries pretty hard to provide compatibility guarantees. Your code should, usually, work on new browser versions and on devices that haven't been released yet. New browsers will have different JIT compilers with different performance cliffs. And yet, there are websites written many years ago that still work. When standardizing things, we need to be precise about what's standardized and what isn't, or protocols "rust shut" and can't be changed without breaking lots of stuff. Not standardizing performance is often a win. (With some exceptions like video game consoles where the hardware is standardized.) Hyrum's law suggests that all compiler optimizations will eventually be load-bearing for someone, but we should usually try to avoid it. To make sure that the code is robust, perhaps performance should vary. Maybe it would be useful to have something like a chaos monkey for programs, where optimizations vary based on a random seed?

bsder 2y ago
> But if it's load-bearing, maybe that's a bug? If your "debug optimization" code is so slow as to be unusable (see: Rust), then your optimizations qualify as load-bearing. The problem is that "optimization level" needs a mindset change. The optimization levels should be "release", "small" and "experimental". "Release level" needs to be perfectly usable for debugging as well as in production--"debug level" should be "release level". Compilation time should be reasonable and run time should be functional. After that, for embedded, you should have "small level"--checks should get turned off and any optimizations that make code significantly bigger should get turned off (loop unrolling, for example). You might enable some optimizations that make compile time brutally slow. Finally, there should be an "experimental level" which tests out optimizations before they go into release. And there should be no "fast" optimization level. If your optimization is that situation specific, it should stay stuck in "experimental". And through all of this, the compiler should also eject files that carry enough information to allow debuggers to make sense of the compiled code, unwind the optimizations when the users asks, and present a coherent version of what is going on. This is actually where compilers really break down nowadays. The compiler needs to eject enough information and context that a debugger can unwind what is going on rather than being an afterthought. We need the equivalent of an LSP (Language Server Protocol) for debuggers.

f33d5173 2y ago

the optimizer should be a magic black box. As soon as you start demanding a particular optimization, it shouldn't be an optimization anymore. In C you have inline assembly and intrinsics and pragmas and macros and so on. If you want the compiler to compile your code a particular way you should be using these, not trying to wrangle the optimizer to invoke a particular optimization.

dzaima 2y ago
Except even intrinsics aren't even that much of a guarantee - clang converts them to its internal operations and applies the same optimization passes over them as it does on its own autovectorized code; and there are no intrinsics for x86's inline memory operands, so issues can arise around those (or the inverse - I've seen clang do a memory load of the same constant twice (the second one being behind some branches), despite there being only one such load). And there also are no intrinsics for most scalar operations, e.g. if you wanted to force "x>>48 == 0x1234" to be actually done via the shift and not "x & 0xffff000000000000 == 0x1234000000000000" (or vice versa). And of course assembly means writing platform-specific code (potentially undesirable even if you want to only do the optimization for a single architecture, as it means having to learn to write assembly of said architecture). There is some potential middle-ground of doing black-boxing, but as-is in C/C++ the way to do this is with a no-op asm block, but that can make register allocation worse, and still requires some platform-specific logic for deriving the register kind from value type.

QuadmasterXLII 2y ago

Frankly, the problem is that (generally, across languages various compiler hints) @inline sometimes fails to inline. At this point I’ve given up on ever having an @inline that reliably inlines, and I would very happily settle for an @assert_inline that doesn’t change the generated assembly at all but reliably crashes out if the function isn’t inline. Julia is by far the worst language about this. It would be vastly more usable with the addition of @assert_type_stable, @assert_doesn’t_allocate, and @assert_doesn’t_error macros.

dzaima 2y ago
With gcc & clang you can use __attribute__((always_inline)) to force-inline, even at -O0, giving an error if it's impossible.
andyferris 2y ago
On the Julia front, I believe the evolving effect system may help a little bit with obtaining/surfacing that information. JET.jl should be able to solve the type stability (inference) one from a whole-of-program perspective. We have `@inferred` for unit tests. The macros would be a cool addition - I wonder if they would get overused though? I agree that Julia takes the idea of optimization to the extreme - it's semantically a very dynamic language and only fast due to non-semantically guaranteed optimization. On the other hand, getting access to the generated IR, LLVM and assembly and iteratively improving it is far easier than any other language I've seen.
- pjmlp 2y ago
  What Julia offers is quite common in Common Lisp systems.
affinepplan 2y ago
just in case you're interested, Julia does (now) have tools similar to what you're describing, although of course there are still be lots of possible improvements to be made w.r.t. their UX to make these tools more reliable and easier to use in particular @assert_type_stable and @assert_doesn't_error is largely provided by JET.jl and the effects system, and @assert_doesn't_allocate is (at least partially) provided in AllocCheck.jl

h1fra 2y ago

I don't hate query planning, some people are better than me at writing algo and the database knows my data better than me. However, what I hate is the lack of transparency (and I feel like this article tries to pin-point just this). When I execute a query locally I get a different plan vs staging vs prod. A plan than can also change depending on some parameters or load or size. I don't care about understanding all the underlying optimizations, I just care that the query plan I saw is the same and is still the same in prod, and that I can be warned when it changes. PG does not return the hash of the query plan or metrics along the data, which is imo a mistake. With this you could track it in your favorite metrics store and be able to point when and why stuff are executing differently.

wrs 2y ago
Yes! The thing with SQL is that the DB “recompiles” the query plan from source every time you do the query. That results in changes at runtime, which are often good and healthy changes, but are sometimes a very bad surprise. I like the metrics idea, but by the time you see the change in the metric, it’s too late. For critical queries it might be helpful to be able to “freeze” a query plan just as one “freezes” a binary executable by compiling. In other words, let the query planner do its job, but only at a time of your choosing, so the performance of a production system doesn’t change suddenly. So no hints in the source, just an opaque token representing a compiled query plan that can be deployed alongside a binary. With tooling you could be notified if the planner wants to do it differently and decide whether to deploy the new plan, after testing. (And again, you’d only do this for a critical subset of your choice.)

einpoklum 2y ago

From the article: > Have a good mental model of what the optimizer can and cannot do. Most DB query planner designers and implementers have little imagination, and their mental model of what optimizers can and cannot do is, well, extremely narrow-minded. There is huge unexplored space of what query planning can be (at least for analytic queries, and we think in columnar terms) - if we just stop insisting on thinking of DBMS operations as black boxes.

mcfig 2y ago

Great article. One real case I encountered that I find thought provoking, is where a bunch of test failures were bucketed into the same bucket because link-time code-generation had noticed that a bunch of C++ getter functions had the same output code and combined them all. So stack traces became confusing because the address-to-symbol mapping was more complicated than the logic we had in place was prepared for. i.e. optimization had violated a rule we were implicitly relying on (that each non-inlined function should start at a distinct address, so that address-to-symbol mapping could be done easily). But that’s not an explicit guarantee and optimizers don’t seem to think about it much. (Well for inlining it seems to have had some thought, still sucks, but anyway this case doesn’t fit the pattern of inlining). I find it hard to say anyone is dead wrong in this case… but I would turn off that LTCG optimization any time I could, except where proven necessary.

andyferris 2y ago

If you have any language where it is "semantially correct" to execute it with a simple interpetter, than all optimizations in that language are not semantically important by definition, right? I've even seen interpretters for C... so while I 100% have felt the pain in this article, I don't know where that leaves us? These are more like compilation assertions/strategies than language features. (Not that these shouldn't be written inline with the code, e.g. it can be nice to write unit tests in the same files as the code in some languages). In the case of SQL, I'd love access to a flavor where I do the joins on indices explicitly, the query is executed as written, and each join (or filter) can be annoted with a strategy (btree lookup, etc). (The most difficult part about using indices by hand is correctly writing all the synchronous triggers on updates, not the queries, IMO).

typesanitizer 2y ago
> If you have any language where it is "semantially correct" to execute it with a simple interpetter, than all optimizations in that language are not semantically important by definition, right? Technically, yes. :) But I think this should perhaps be treated as a bug in how we define/design languages, rather than as an immutable truth. - We already have time-based versioning for languages. - We also have "tiers" of support for different platforms in language implementations (e.g. rarer architectures might have Tier 2 or Tier 3 support where the debugging tooling might not quite work) One idea would be to introduce "tiers" into a language's definition. A smaller implementation could implement the language at Tier 1 (perhaps this would even be within reach for a university course project). An industrial-strength implementation could implement the language at Tier 3. (Yes, this would also introduce more complications, such as making sure that the dynamic semantics at different tiers are equivalent. At that point, it becomes a matter of tradeoffs -- does introducing tiers help reduce complexity overall?)
Archit3ch 2y ago
> If you have any language where it is "semantially correct" to execute it with a simple interpetter, than all optimizations in that language are not semantically important by definition, right? Not when "correct" needs optimizations to meet real-time guarantees. It's hard to argue that a program which doesn't run is "correct".

WalterBright 2y ago

> D has first-class support for marking functions as “no GC”. It never occurred to me that this would be considered a hint to the optimizer. It doesn't affect code generation. What it does do is flag any use of the gc in the function and any functions it transitively may call. Optimizers have been likened to turning a cow into a hamburger. If you're symbolically debugging optimized code, you're looking at the hamburger. Nobody has been able to solve that problem. It's true that optimizers themselves are hard to show being correct. The one in the D compiler is a conventional DFA optimizer that uses data flow equations I learned from Hennessy and Ullman in a 1982 seminar they taught. So it has been battle tested for 42 years now(!) and it's pretty rare to find a problem with it, unless it's a new pass I added like SROA. The idea is anytime a problem is identified and corrected, it goes into the test suite. This has the effect of always ratcheting it forward and not regress. The GC dates from around 2000, when I wrote it for a Javascript engine. It was brutally tested for that, and has been pretty solid ever since. People complain about the GC, but not about it being buggy. A buggy GC is a real horror show as it is painfully difficult to debug.

typesanitizer 2y ago
Thanks for the feedback. The preceding paragraph had "and occasionally language features" so I thought it would be understood that I didn't mean it as an optimizer-specific thing, but on re-reading the post, I totally see how the other wording "The knobs to steer the optimizer are limited. Usually, these [...]" implies the wrong thing. I've changed the wording to be clearer and put the D example into a different bucket. > In some cases, languages have features which enforce performance-related properties at the semantic checking layer, hence, granting more control that integrates with semantic checks instead of relying on the optimizer: > > - D has first-class support for marking functions as “no GC”.
- WalterBright 2y ago
  That's better, thanks!
saagarjha 2y ago
Languages that run in a VM are pretty good at turning the hamburger back into a cow when you're looking at it.

pornel 2y ago

Optimizations in compilers like LLVM are done by many individual code transformation passes, one applied to the result of the previous. This layering makes the order of the passes important and very sensitive. The passes usually don't have a grand plan, they just keep shuffling code around in different ways. A pass may only be applicable to code in a specific form created by a previous simplification pass. One pass may undo optimizations of a previous pass, or optimize-out a detail required by a later pass. Separation into passes makes it easier to reason about correctness of each transformation in isolation, but the combined result is kinda slow and complicated.

CalChris 2y ago

We are nearing the death of Proebsting's Law. AMD CEO Lisa Su's HotChips’19 keynote said that compilers had accounted for 8% performance increase over the decade. That means compilers are now only doubling performance every 90 years. https://www.youtube.com/watch?v=nuVBid9e3RA https://www.youtube.com/watch?v=nuVBid9e3RA

Mikhail_Edoshin 2y ago

One of reasons SQL is declarative is that queries run concurrently yet give the illusion of working in isolation. And unlike the concurrency of independent processes, which is mostly mechanical, this one involves detailed coordination because database queries work on the same data. With these constraints it may be not that easy to come up with an imperative model that is as simple as the current declarative one.

yxhuvud 2y ago

No. Language designers need to think about what their language promises and when some users have differing needs, they may need to fulfill those needs.

froh 2y ago

in the "closing thoughts" [1] of the OP article there's a pointer to "Proebstrings law" [2] which got me to a benchmark [3] how LLVM has improved over 10 years from 2.7 to 11 which leaves me with the strong intuition that indeed what mit benefit more from a rethink is not optimizers but focus on programmer productivity > Perhaps this means Programming Language Research should be concentrating on something other than optimizations. Perhaps programmer productivity is a more fruitful arena. [1] https://typesanitizer.com/blog/rethink-optimizers.html#closing-thoughts https://typesanitizer.com/blog/rethink-optimizers.html#closi... [2] https://proebsting.cs.arizona.edu/law.html https://proebsting.cs.arizona.edu/law.html [3] https://zeux.io/2022/01/08/on-proebstings-law/ https://zeux.io/2022/01/08/on-proebstings-law/

kragen 2y ago

Daniel Bernstein has given an interesting talk about "the death of optimizing compilers" (PDF slides at https://cr.yp.to/talks/2015.04.16/slides-djb-20150416-a4.pdf https://cr.yp.to/talks/2015.04.16/slides-djb-20150416-a4.pdf) claiming that less and less of our code is in that middle ground where it's performance-critical enough to risk running it through an optimizer but not so performance-critical that it needs to be rewritten in assembly. If we think of the high-level source code (whether in SQL, JS, or Python) as being a functional spec that the low-level implementation should provably follow, maybe we should check them both in, and at build time, run a proof assistant to verify that the implementation still complies with the spec? Rather than running an optimizing compiler every time. I think this is what nanolith is suggesting in https://news.ycombinator.com/item?id=41965701 https://news.ycombinator.com/item?id=41965701. Maybe you run the optimizing compiler once when you first write the code, and again when the proof assistant tells you an optimization is no longer valid, but you check the output before you check it in. Or maybe you have the compiler running all the time on a GPU cluster looking for new optimizations.

082349872349872 2y ago
> maybe you have the compiler running all the time ... looking for new optimizations Anyone know if there was ever a retrospective on https://github.com/webyrd/Barliman https://github.com/webyrd/Barliman ?
- kragen 2y ago
  I haven't seen one. He's apparently morphing into a YouTuber, though, so maybe we should grep his .vtts.
- tmtvl 2y ago
  Will is on HN*, though I don't know whether he'll see this topic. * https://news.ycombinator.com/user?id=will_byrd https://news.ycombinator.com/user?id=will_byrd
- gradschoolfail 2y ago
  Sufficiently “advanced”* program synthesis is indistinguishable from compiler optimization? *(= “correct”?) [sufficiently constrained madness is indistinguishable from ikigai?]

account42 2y ago

I'm not sure if this is the right way to look at it? Do you really care if some optimization was performed or not or do you only care about the performance characteristics of the resulting program? Maybe a more sensible solution would be to have better tests for performance regressions. Still not an easy task (performance is often highly dependent on the input and regressions can hide in very specific cases) but makes more sense to me than writing high level code and then worrying about the details of how the compier translated that high level code.

JonChesterfield 2y ago

The thing where people quote optimisers as only eeking out tiny percentages of performance over decades really annoys me. It's true for the numerical kernels written in C and Fortran where the code is essentially optimal already, and all the compiler has to do is not screw it up. It's grossly false for the vast majority of code, where the sludge written by thousands of engineers gets completely rewritten by the compiler before it executes. Compilers are the reason unskilled devs manage to get tolerable performance out of frameworks. The cpython is slow complaints? That's what life without a good compiler looks like.

klodolph 2y ago
“CPython is slow” is kind of a complaint about the Python object model. I’m not sure that I would pin this one on the compiler, per se. Everything you do in Python involves chasing down pointers and method tables, looking up strings in dictionaries, and that sort of thing. Maybe it’s splitting hairs to talk about whether this is down to the compiler or the language. > It's grossly false for the vast majority of code, where the sludge written by thousands of engineers gets completely rewritten by the compiler before it executes. It used to be true, for sure. What has changed since then is not the sludge or bloat or many cooks. Instead, the major change is that we have written a bunch of code on top of optimizing compilers with the assumption that these optimizations are happening. For example, nowadays, you might write C++ code with a deep call stack and lots of small functions (e.g. through templates), and it’s fast because the compiler inlines and then optimizes the result. Back in the 1990s, you would not have written code that way because the compiler would have choked on it. You see a lot more macro use in code from the 1990s rather than functions, because programmers didn’t trust that the functions will get inlined.
- arka2147483647 2y ago
  > Everything you do in Python involves chasing down pointers and method tables, looking up strings in dictionaries, and that sort of thing. One of the things that a Cpp Compiler can do is De-Virtualize Function Calls. That is; solve those function pointer tables at Compile Time. Why could not a good compiler for Python do the same?

russellsprouts 2y ago

This reminds me of Halide (https://halide-lang.org/ https://halide-lang.org/), which is a really interesting design in this direction. In Halide, you specify the algorithm at a high level, then specify the "schedule" (execution order, vectorization, storage) separately. Then, it verifies that the two match. For tight loops like image kernels, it's often counter-intuitive which execution plan will give the best performance, so being able to experiment with the guarantee that you are still implementing the algorithm correctly is valuable. For a database, it would be as if you could send a high level SQL query and an execution plan together. Halide is very specific, but I could imagine a general-purpose language with a Python-like high level representation for code behavior, with the option to specify a lower-level implementation with a lot of performance annotations.

taeric 2y ago

I think this is misplacing the need for a rethink. Compilers are amazing at optimizing small programs. What they are less amazing at is optimizing large programs. The query planner for SQL databases is a good example of this. For small queries, the odds of the planner making a bad choice is rather low. Large queries, on the other hand, are comparatively easy to lead down a bad path. This is why the "no sql" family of databases see more predictable results for a lot of uses. If you can't do complicated queries, then you don't have that peril to worry about. Worth trying if you have the programs to play with. Run it with and without -O3 and see how the compiler does for you.

sealeck 2y ago
> This is why the "no sql" family of databases see more predictable results for a lot of uses. If you can't do complicated queries, then you don't have that peril to worry about. Can't you also just, well, not use complicated SQL queries?
- taeric 2y ago
  Certainly, and that is my point? Throwing out query planners feels like the wrong thing to consider. Instead, focus on keeping the things being planned smaller.

looneysquash 2y ago

The postgresql query optimization one is an interesting one. I've been very frustrated at times that you can't just tell it to use a certain index or a certain query plan. But at the same time, the data in the table can change over time. So for that particular problem, postgresql's superpower is it can optimize and reoptimize your query at runtime as the data changes! Not an easy thing to do in most programming languages. But I do agree with the rest of the article to a large extent. For some cases, you need a way to say "do this optimization, fail to compile if you cannot". Most of the time though, I just want the optimizer to do it's best, and don't have something in particular in mind. What if the compiler could output the optimization or transformations it does to a file? A file that was checked into source code. Think of lockfiles for dependencies. Or snapshot testing. I don't mean output the entire IR. I mean more a list of applied transformations. When those change, you could then be aware of those changes. Maybe it could act as an actual lockfile and constrain the compiler? Could it also double as a cache and save time?

deleted 2y ago
[deleted]