Zero Cost Abstractions

Is messing up branch prediction "Breaking Bad?"

From context, no, it seems to be "Heroic Compiler".

Nope. But I like it :-)

"helden" is also Dutch for "heroes" and concatenation like that is also fine in Dutch.

My term for stuff like this is "software that suffers from overly-clever syndrome".

Value types only avoid refcounts if they contain only primitive fields, which is not all that often in interesting code.

For example, count the number of atomic refcounts on each iteration of the following loop:

  // given
  struct S {
    var x: [Int]
    var y: [String]
    var z: NSView
  }

  var array: [S]

  for element in array {
    // maybe do something with the NSView
  }

That's three atomic increments and three decrements per loop iteration, as the array entry is copied into element because it can't prove the NSView operation wouldn't cause the array to zero somehow.

Given atomic memory operations are some of the most expensive things on a modern CPU, this is brutal, and a place where Rust-style memory ownership would be a big improvement.

I haven't seen the optimizer convert atomic refcounts to non-atomic refcounts - do you have an example situation where that happens?

(By the way, I think Swift is a delightful language, but the pervasive reference counting threw some cold water on my passion as it means today we're not really close to replacing C/C++/Rust for machine-level performance.)

That's exactly the point: the optimizer can drop atomicity. All these ref-counts may be optimized away. Or not. The opposite of predictability.

Can't wait to hear more about swift's opt in borrowing!

This also explains the shift in functional programming from languages with good reasoning about correctness (Haskell, but also SQL) to languages which additionally allow of good reasoning of performance (OCaml, Rust, etc.).

Moreover, this explains the NASA coding rule that all loops shall have an explicit upper bound.

The deeper issue seems to be: If you write code in a fashion that you can reason easily about its performance, then you might not get the optimal performance in all cases, but you establish an minimum level of performance.

So performance stability is more important than reaching optimal performance, because the latter may be easily destroyed accidentally in future versions of the software.

The only exception are well-defined tasks with stable input/output definitions (e.g. numeric primitives like matrix multiplication, fourier transformation, etc.) where the whole point of newer versions is performance improvements and nothing else.

I don't doubt that you make code 10x to 1000x faster, but could this be selection bias? I.e., you are focusing on the code that is slow and not the code that the compiler has already had substantial impact on?

Well, maybe they should? Don't really see how else you're going to figure out why a line of code is as fast/slow as it is.

Well, we do it, even if you don't see us. Tell your friends to do it too!

I do it at least once a week. Certainly C programmers do this, so inasmuch as rust is working to be a better C, once might expect Rust programmers to do it.

Also SBCL has instruction level profiling.

Why are you pretty sure it wasn't? Swift is usually pretty efficient. Massive numbers of CoWs is by far the most likely culprit for any kind of huge slowdown. And without actually profiling it, it's hard to detect when CoWs are happening, you mostly just have to be aware of when you're writing code that keeps multiple references to a CoW data structure that you're mutating. It's very common to get single accidental CoW copies. Getting a large number of them tends to require slightly odder code. For example, saying something like `col.reduce([], { $0 + $1.elements })`, which is a normal idiom for Haskell, will introduce a CoW copy on the accumulator array at every single step. And this is true even if you modify it to something like `col.reduce([], { var ary = $0; ary.append(contentsOf: $1.elements); return ary })`, because behind the scenes the reduce method will still have a reference to the accumulator while the closure is executing.

That's totally fair, but that may have something to do with how well you know Rust. I obviously don't know your familiarity level, but once your mental models "snap" out of thinking about moving data around, and start thinking about operations upon the data, it gets really intuitive.

On the other hand, the Rust code is guaranteed at compile time to be free from buffer overruns, off-by-one errors, and a whole host of other nasties.

I know, I know, the C code you write never has buffer overruns, just like the C code I write never does, well, except that one time, but then I caught it in the debugger during testing and it was easy to fix. Oh, and then that other time, but I caught that one too, and then.....

Whoops! You're totally right. I missed the outer loop. Thanks for the correction.

I think this is still a little off. Maybe you used bufp[i + j] where you meant buffer[i + j]? I may have something wrong too, but I probably would go with:

    for (size_t i = 0; i < 12; i++) {
        int64_t sum = 0;
        int32_t *bufp = buffer + i;
        for (size_t j = 0; j < 12; j++)
            sum += coefficients[j] * bufp[j];
        *bufp += (int32_t)(sum >> qlp_shift);
    }

I think this will put it in a form where the compiler should vectorize it[1], probably making the loop about twice as fast as the version shown: 3 vector loads, 3 vector multiplications, 3 vector additions and a horizontal sum versus 16 scalar loads[2], 12 scalar multiplications and 12 scalar additions.

[1] I presume the "various reasons the above snippet is not as obvious to vectorise as it might seem at first sight" is because the coefficients[] are 64-bit and buffer[] is 32-bit. But a smart compiler should be able to use PMOVSXDQ (packed move sign extend double-word to quad-word) here. Unless there is some other issue, I think the author may be underestimating the benefit of vectorizing here.

[2] While the author is right that most of coefficients stay in registers, there isn't actually room for all 12, so 4 of them are loaded from the stack every iteration. Since only 3 128-bit vector registers are required, they should remain there. I'm not sure if the excess loads are actually a bottleneck, though.

Have you ever learned a new spoken language? At first, the learner understands by translating to primary language. Only later, with repeated experience does the learner stop doing so and become "fluent".

Its very similar when learning the functional style of programming. Even today having most of this functional style be intuitive, when I see a complex iterator chain (usually only when constructing a `Map`), I need to mentally unfold it into a loop.