16 ms·

Do not taunt happy fun branch predictor

314 points by mkeeter 4y ago

Malic 4y ago
Ow. My head hurts. And this is why optimizing compilers are some of the most complex programs there are. (or so I have been taught)
- shadowgovt 4y ago
  It's also why the modern rule of thumb is "don't optimize by writing your own assembly." The rule is a boiled-down version of the larger notion "Don't optimize by writing your own assembly, because even with domain knowledge of the problem you're trying to solve, you're probably not more clever than the engineer-decades that went into building your compiler toolchain and processor architecture, unless you're an expert in both fields, in which case good luck and shoulder that maintenance burden." The rule of thumb drops a lot of detail on the ground but is a good first approximation.
  - RodgerTheGreat 4y ago
    I would just phrase it as "if you optimize by writing your own assembly, don't expect your program or its performance to be portable."
  - astrobe_ 4y ago
    ... Which is kind of worrying; is it really a good thing that processors are so complex that you need "decades" to use them to fully. Bottom line, you end up with chaotic (in the "sensitive to the slightest change") performance behavior. OTOH this reminds of another saying, "don't roll your own crypto". But all those "don't" are a bit frustrating.
    - miloignis 4y ago
      I've seen people get frustrated by the "don't"s before, but I think that's generally taking the first degree approximation too literally. Feel free to hand-write assembly or roll your own crypto, but don't depend on it for anything serious unless you are an expert or have it reviewed by one. Doing so for learning and fun is fine, if that's clearly called out such that no one accidentally depends on it for something serious. There's only one way to become good at something, and that's good practice! In a professional setting there's a responsibility to the end user which generally precludes doing these dangerous things - that is, one should feel free to take up woodworking as a hobby but shouldn't offer to build someone's house unless you're a licensed professional.
    - olliej 4y ago
      But you don't need decades of experience: we have compilers and optimizers to do that.
      - bioint7812 4y ago
        It's interesting that the impedence the author was experiencing was one of the CPU incorrectly "speculating" about the intent. We as readers are left to speculate about the problem being solved by the author. Based on the content of his recent articles, we could assume he is continuing his development of a JIT for a Rust port of his graphics engine. Given that assumption, I would argue that the compiler writers are lagging here--specifically lack of dynamic compilation. For example, is there a JIT compiler for the Rust language? I was thinking about reproducing his experiment in SBCL, which does have dynamic compilation--although it wouldn't be a real "apples" to "apples" comparison because my work machine is a x86_64.
        olliej 4y ago
        JITs have very different constraints (but also many advantages) vs AOT compilers, so I don't think in the general case a language compiler can "support" JITs directly. llvm/clang for instance have a jit mode... for compiling C/C++, not some other language. Also obviously the compiler writers (AOT or JIT) need to know about and understand very minute details of how a cpu is behaving. I was responding to a person saying it was worrying that devs need that kind of knowledge and experience by saying that that isn't true because the tools exist (I feel that there's some analogy to what knowledge you need for a car: changing oil, servicing engine, replacing engine, designing an engine...). Once you are writing a JIT you're in the "making the tools" group, so you now need to know more than the vast majority of devs (not just more than the "average" dev) that's inescapable.
    - deleted 4y ago
      [deleted]
  - pjdesno 4y ago
    Maybe better expressed as "don't write your own assembly unless you know why it might be better than the compiler". Trying to beat the compiler at optimizing normal code is kind of like trying to beat a calculator with paper and pencil - computers are just better at that sort of thing than people are. One use case is where you want to use bizarre CPU functions (popcount, encryption, load CR3, etc.) that no one's taught the compiler how to generate, although for some of them you might be better off using compiler intrinsics. Another is when you're dealing with things underneath the language abstraction, like the Boost co-routines mentioned in a link a few comments above. Of course, if the language folks decide to add the capability you want (e.g. C++20 coroutines), you're back to being better off using the compiler. Finally there are pedagogical reasons, e.g. sometimes I show my classes the world's simplest "Hello World", using a few lines of assembler to invoke the write and exit syscalls.
    - JonChesterfield 4y ago
      The boost coroutines mentioned are not the same thing as the C++20 ones. Boost captures the stack, that's what the register shuffling is for. C++ is a compiler transform that moves some state onto the heap, but probably not the whole stack, and builds a switch dispatch style thing to transform the control flow. This is why C++ comes with co_* annotations and coroutines don't.
  - avgcorrection 4y ago
    I will never understand the trend of “using quotes around things”. Which is a shorthand version for “using quotes around things that I wanted to point to and say, hey, this is something that “goes over here”, you know, inside these quotes, to make sure that you understand exactly what I’m delimiting, since using commas, and semicolons, and colons wouldn’t fit for some reason. Oh look the thing that I’m quoting now consumes 80% of this paragraph. But this is way better than just saying “the modern rule of thumb is to not optimize by writing your own assembly.” Because then it isn’t 100% clear that the rule of thumb is delimited by (exactly) “[do] not optimize by writing your own assembly.” Ya see?”
  - magicalhippo 4y ago
    Another is that your assembly will never target newer CPUs, but the compiler will. I've gained a lot of performance by replacing handwritten assembly functions with plain code versions, just because CPUs and compilers have evolved over the last 15-20 years, while that assembly code is what it is.
- JonChesterfield 4y ago
  There's a sense in which they're complicated. It's a sequence of graph transforms which mostly deal with non-polynomial time problems using heuristics, where mistakes in the transforms can manifest quite a long way away from the error. There's a significant risk that they're implemented in languages unique to that compiler toolchain, as compiler devs are quite prone to solving problems by writing compilers. There's also a sense in which they're really simple. The input format and output format are (usually) well defined. The user interface is largely printing things to stderr and giving up, possibly in a retry loop when there's an editor involved. The program dependency graph is often quite small so the bug you're looking at is probably in the source code you checked out. Security is not the dominant concern you have elsewhere.
- bob1029 4y ago
  The state of modern compilers is pretty staggering to me. I've seen some code folding in RyuJIT that makes me feel inferior as a developer. You've got a few compilers (Java, .NET, et. al.) which are capable of re-compiling hot path code during live execution and then seamlessly transitioning to those paths. This recompilation can be based upon the statistics of the live process, so it's almost like a sort of adaptive AI. Which paths are hot in production does not need to be known at compile time with these approaches.
- astrange 4y ago
  Optimizing compilers don't model things like branch prediction well, and aren't great at autovectorizing either. They work just well enough. In general I think they aren't that complicated since they have a pass structure that's relatively easy to inspect and helps avoid spaghetti code.
ogogmad 4y ago
Minor erratum: Floating point addition actually is commutative; it's in fact non-associative.
- dekhn 4y ago
  with some significant exceptions, such as NaNs.
  - recursive 4y ago
    Can you think of some `x` where `x + NaN` is not identical to `NaN + x`? I can't.
    - dekhn 4y ago
      you mean, like 1 + NaN = NaN and NaN + 1 = NaN, but NaN != NaN? (I'm not a numerical expert, just repeating what others have told me)
      - CountSessine 4y ago
        Yes. An NaN in IEEE754 has all 1’s in the exponent, and then the high bit of the mantissa determines whether it’s quiet or signalling, but then rest of the mantissa is/can be a “payload”.
        bruce343434 4y ago
        Sign bit determines signalling
        robocat 4y ago
        Please double check your facts before disagreeing with somebody so abruptly. Sign bit is NOT the signalling/quiet bit. Bit 51 (edit or bit 50 - damn ***** IEEE for not publishing important standards for free public access) is according to the first result I looked at: https://craftinginterpreters.com/optimization.html https://craftinginterpreters.com/optimization.html Edit 2 from IEEE 754 (2008 version): 6.2.1 NaN encodings in binary formats This subclause further specifies the encodings of NaNs as bit strings when they are the results of operations. When encoded, all NaNs have a sign bit and a pattern of bits necessary to identify the encoding as a NaN and which determines its kind (sNaN vs. qNaN). The remaining bits, which are in the trailing significand field, encode the payload, which might be diagnostic information (see above). All binary NaN bit strings have all the bits of the biased exponent field E set to 1 (see 3.4). A quiet NaN bit string should be encoded with the first bit (d1) of the trailing significand field T being 1. A signaling NaN bit string should be encoded with the first bit of the trailing significand field being 0. If the first bit of the trailing significand field is 0, some other bit of the trailing significand field must be non-zero to distinguish the NaN from infinity. In the preferred encoding just described, a signaling NaN shall be quieted by setting d1 to 1, leaving the remaining bits of T unchanged. 6.3 The sign bit When either an input or result is NaN, this standard does not interpret the sign of a NaN. Note, however, that operations on bit strings—copy, negate, abs, copySign—specify the sign bit of a NaN result, sometimes based upon the sign bit of a NaN operand. The logical predicate totalOrder is also affected by the sign bit of a NaN operand. For all other operations, this standard does not specify the sign bit of a NaN result, even when there is only one input NaN, or when the NaN is produced from an invalid operation. When neither the inputs nor result are NaN, the sign of a product or quotient is the exclusive OR of the operands’ signs; the sign of a sum, or of a difference x−y regarded as a sum x+(−y), differs from at most one of the addends’ signs; and the sign of the result of conversions, the quantize operation, the roundTo- Integral operations, and the roundToIntegralExact (see 5.3.1) is the sign of the first or only operand. These rules shall apply even when operands or results are zero or infinite. When the sum of two operands with opposite signs (or the difference of two operands with like signs) is exactly zero, the sign of that sum (or difference) shall be +0 in all rounding-direction attributes except roundTowardNegative; under that attribute, the sign of an exact zero sum (or difference) shall be −0. However, x + x = x − (−x) retains the same sign as x even when x is zero. When (a×b)+c is exactly zero, the sign of fusedMultiplyAdd(a, b, c) shall be determined by the rules above for a sum of operands. When the exact result of (a × b) + c is non-zero yet the result of fusedMultiplyAdd is zero because of rounding, the zero result takes the sign of the exact result. Except that squareRoot(−0) shall be −0, every numeric squareRoot result shall have a positive sign. I.e. you are definitely wrong. The sign bit can be + or - for NaN (presumably a side-effect of the encoding for +/-Infinity ). And then that leads to a bunch of arse (section 6.3) because the spec needs to decide what happens to the sign bit in a bunch of different situations. PS: fucking infinity. Infinity should have been NaN. Infinity ≠ Infinity, except in in the egghead-land IEEE (side note: egghead is a compliment IMHO). Mind you, easy to see mistakes in retrospect, but corner cases are shit in programming. I do like NaN, although reading comments here, and the IEEE spec, forces me to learn how little I now about NaN encodings. Oh, and any NaN should equal any other NaN. Mathematically obviously not, but logically yes and IEEE is for programming. NaN is already defined as a nonsense, so at least keep the nonsense consistent. Changing if = to if ≠ should not introduce subtle logic bugs. Ranting edit #755: and while we are at it, -0 is an abomination in the eyes of the Great Architect in the Matrix - it should never have been allowed - perhaps -0 should have been NaN with signalling bits in the exponent (even though that would prevent some language virtual machine optimisations where 53 bits of NaN get used to pack other information, but the win would be compelling because reducing bugs due special cases is huge IMHO). How many developers understand IEEE corner cases: fuck all in my long experience.
titzer 4y ago
> More specifically, the branch predictor probably keeps an internal stack of function return addresses, which is pushed to whenever a bl is executed. When the branch predictor sees a ret coming down the pipeline, it assumes that you're returning to the address associated with the most recent bl (and begins prefetching / speculative execution / whatever), then pops that top address from its internal stack. There's no need for "probably" here. The micro-architectural mechanism is known as a return stack buffer[1] and is generally separate from the branch predictor unit, though the processor may make use of indirect branch prediction entries for returns as well. [1] It is, indeed, a tiny little stack of return addresses and indeed, the article hit performance issues by misaligning it. The (Intel chips') RSB is behind the Retbleed vulnerabilities.
jerf 4y ago
This is another good example of how our CPUs are in many ways specialized C processors. C is a structured programming language that uses functions, so our processors like functions. If you jump out of that paradigm, even if the assembly instructions nominally seem to allow it, you'll run more slowly. Even when it seems like what you're offering is a shortcut to the CPU. This is neither praise nor criticism of the current CPU paradigm; it's just something you need to understand if you want the best performance out of our machines. A different paradigm, like a concatenative-paradigm-based program, might naively be more inclined to compile into code that looks more like what the author tried, jumping between implementations of the stack operators without it actually being "functions". One can imagine processors that would be "happier" with that, and would be bothered by things that look like function returns more. But that's not the CPUs we have.
- yencabulator 4y ago
  > C is a structured programming language that uses functions, so our processors like functions. An interesting take on this is the (vaporware) Mill CPU, in which the machine code defines EBBs (Extended Basic Blocks), which can only be entered at the top. You cannot express jumping into the middle of a block from the outside, in their ISA. https://en.wikipedia.org/wiki/Extended_basic_block https://en.wikipedia.org/wiki/Extended_basic_block https://millcomputing.com/topic/introduction-to-the-mill-cpu-programming-model-2/ https://millcomputing.com/topic/introduction-to-the-mill-cpu...
- masklinn 4y ago
  Author was not jumping out of the paradigm here, they were deliberately misusing constructs specialised for the paradigm (br/ret). That’s like saying the toolcase is a specialised screw processor because you’re trying to drive nails using a screwdriver and it does not go well. And C is hardly the first or only procedural langage.
  - Nevermark 4y ago
    No but C is a better model of most processors assembly, than most other procedural languages.
snerbles 4y ago
While I was in undergrad I toyed around with abusing the branch predictor on a few different machines, compiling something like the following with optimizations off - it performs an identical computation regardless of branch outcome: void branchLoop(unsigned int condition, unsigned int &sum) { // put something suitably large here unsigned int loopCount = 0x0fffffff; unsigned int i; // compile with -O0 or this gets optimized away for (i = 0; i < loopCount; i++) if ((i & condition) == 0) sum++; else sum++; } The Core Duo on my Thinkpad T60 had some very distinct slowdowns on certain bit patterns, which were not repeatable on the handful of other CPUs I had access to at the time. I haven't tried this with more modern CPUs, however.
- gpderetta 4y ago
  Predictors are getting better and better at recognizing long patterns (sometime at the cost of not being optimal with short patterns).
gpderetta 4y ago
Yes, never push and ret. Here is something I wrote (/me checks calendar) more than 15 years ago about optimizing coroutine control flow: https://www.crystalclearsoftware.com/soc/coroutine/coroutine/linuxasm.html https://www.crystalclearsoftware.com/soc/coroutine/coroutine...
water-your-self 4y ago
If an HN reader wanted to play around with similar digging, what would be the essential tools to be aware of and where best could he start? Assuming prior knowledge of assembly/C but without much experience decompiling or testing speed.
- dcow 4y ago
  Your compiler can spit out assembly, you just need to know how to read it. Sounds like the author was also using Xcode Instruments https://help.apple.com/instruments/mac/current/#/dev7b09c84f5 https://help.apple.com/instruments/mac/current/#/dev7b09c84f... to check cpu counters. And they were using criterion https://crates.io/crates/criterion https://crates.io/crates/criterion to microbenchmark. My guess would be that the author is porting some C code to Rust and making sure not to regress performance along the way (probably hopefully trying to increase it). Likely their program was written in Rust and the section they were trying to optimize called some old c code. Sounds like they rewrote the section in Rust since Rust <-> C ffi calls break out of the happy realm the rust compiler likes and end up causing a performance hit themselves. You can write inline assembly in Rust using the macro https://doc.rust-lang.org/reference/inline-assembly.html https://doc.rust-lang.org/reference/inline-assembly.html.
- shoo 4y ago
  Learn how to use a decent profiler. if you're running linux, that's probably perf: https://man7.org/linux/man-pages/man1/perf.1.html https://man7.org/linux/man-pages/man1/perf.1.html https://www.brendangregg.com/perf.html https://www.brendangregg.com/perf.html Here's a fun article from the cloudflare blog that gives an example of using of perf to diagnose performance of a small utility: https://blog.cloudflare.com/when-bloom-filters-dont-bloom/ https://blog.cloudflare.com/when-bloom-filters-dont-bloom/ Matt Godbolt's compiler explorer is also worth checking out: https://godbolt.org/ https://godbolt.org/
londons_explore 4y ago
Observation: Almost any code, when micro-optimized, can gain about 10x performance. So, if we had the time and energy, we could probably make all of computing at least 10x faster. But we don't have the time or energy to dedicate that much effort to every line of code... But perhaps AI does?
- celeritascelery 4y ago
  I don’t think that is generally true. He only got a large speedup because he used SIMD, which has nothing to do with micro optimization. I would say a better take away is that micro optimization is really hard and you will often make things worse if you don’t know what you are doing. Even if you do, you are only going to get a few percentage points.
  - thethirdone 4y ago
    My experience micro optimizing things is that even without SIMD, most software can get at least a 5x in performance. With SIMD, you can often get 50x improvements. The reason why people thing "Even if you do, you are only going to get a few percentage points." is because it generally takes 5-50x the developer time to optimize such code. If it takes half a day to write naive code to do something like validate utf8, it probably takes ~25 workdays to make a fast SIMD version. If you instead spend an extra half a day, there is a good chance you get a 10-50% speedup using normal code.
    - mumumu 4y ago
      This is true on a few streaming application (such as parsing). And most of the speedup is because of tricks to avoid doing beaches. There is a great blog post from one of the authors of JSON SIMD discussing this. I'm on mobile, there is a link for the blog post on the simd JSON github repository.
      - mumumu 4y ago
        *avoid branches The blog post I mentioned: Paper: Parsing Gigabytes of JSON per Second https://branchfree.org/2019/02/25/paper-parsing-gigabytes-of-json-per-second/ https://branchfree.org/2019/02/25/paper-parsing-gigabytes-of... Another related post from Lemire: Ridiculously fast unicode (UTF-8) validation https://lemire.me/blog/2020/10/20/ridiculously-fast-unicode-utf-8-validation/ https://lemire.me/blog/2020/10/20/ridiculously-fast-unicode-... Those algorithms are fast. But to put them in perspective. A single x86 CPU can write 64B per cycle. At 5GHz, the theorical maximum bandwidth is 320 GBps. IIRC, the read bandwidth is twice that. There are others botlenecks, and is very hard to write code that writes at every cycle. A interesting consequence, is that the theorical maximum bandwidth is logarithmical to the number of cycles. Again, talking about branchless streaming application.
jefftk 4y ago
> The SIMD code does come with one asterisk, though: because floating-point addition is not associative, and it performs the summation in a different order, it may not get the same result as straight-line code. In retrospect, this is likely why the compiler doesn't generate SIMD instructions to compute the sum! What if you set -funsafe-math-optimizations, which allows "optimizations that allow arbitrary reassociations and transformations with no accuracy guarantees"?
- makapuf 4y ago
  You could just turn gcc to 11 and use -Ofast
  - zokier 4y ago
    Both clang and gcc vectorize if you ask them nicely: https://gcc.godbolt.org/z/xvjY8P4cM https://gcc.godbolt.org/z/xvjY8P4cM
- deleted 4y ago
  [deleted]
- not2b 4y ago
  It's a bad idea to scramble the order of floating point operations unless you can tolerate extreme inaccuracy, and in some applications accurate FP results don't matter, but the non-associativity of FP isn't just a technicality: you can lose all of your significant digits if the order of operations in well-written scientific code is changed.
  - thomasahle 4y ago
    But if we aren't assuming the original order was particularly nice, we are simple substituting one random (or arbitrary) order for another. No reason to expect it to be any worse or better.
    - not2b 4y ago
      The key is that if you do this, different optimization levels produce different numerical results, and also some problems in the code become unfixable; you can't group computations according to their expected value ranges because the compiler will ungroup them again, incorrectly assuming that FP addition and multiplication are associative. Certainly for some applications it's fine, but a test of whether it's fine would be, for example, that it works just as well with single-precision as double-precision and even 16-bit floats would be fine, for example weights in an NN.
iamsmooney 4y ago
Title is a reference to this old SNL skit: https://www.youtube.com/watch?v=GmqeZl8OI2M https://www.youtube.com/watch?v=GmqeZl8OI2M
- bioint7812 4y ago
  More translation: > for reasons https://www.urbandictionary.com/define.php?term=for%20reasons https://www.urbandictionary.com/define.php?term=for%20reason...
- sophacles 4y ago
  It's definitely a classic - if you haven't seen it I'd recommend it even if it wasn't related to the article :D
- Agentlien 4y ago
  It is actually linked from the article. In the sentence "In conclusion, do not taunt happy fun branch predictor with asymmetric usage of bl and ret instructions." the words "do not taunt happy fun branch predictor" are a link to the video on YouTube.
pranith 4y ago
Great investigative work! The stack structure you refer to here is called the Return Address Stack (RAS).
CalChris 4y ago
It took me a while to understand the mismatched bl/ret pairs because I'm used to reading matched bl/ret pairs. This confusion has to be similar to what the silicon is 'thinking': Human, I see matched bl/ret pairs all the time and I'm good at them. Why are you giving me mismatched pairs? I'll do the right thing but I'm not so good at them. Still, this seems like function inlining. But why not just inline and use a regular branch loop? Is foo() also being called from elsewhere? Is space at a premium?
- masklinn 4y ago
  > Upon seeing this program, it's a common reaction to ask "why is foo a subroutine at all?" > The answer is "because this is a didactic example, not code that's trying to go as fast as possible".
FullyFunctional 4y ago
Well, of course, the Return Address Stack (RAS) predictor maintains its own call stack and you need to understand how it works. However, there's a subtler way to break it: recurse too deeply. The RAS only has a fixed, small, and implementation dependent length. If you use deep recursion with non-trivial control flow (in particular multiple call sites), then the RAS will starting missing once you return from beyond that limit. Another consequence of the RAS is that co-routines switching is more expensive than they might appear at first. RISC-V has encoding hints to mark call(jal)/returns that are actually co-routine switching but the full cost can't be avoided.
- gpderetta 4y ago
  you can mitigate the cost by not 'call'-ing into your coroutine switch function but inlining the code into the surrounding coroutine. As a bonus you get a bit better branch prediction on your yield because distinct yields will share less state. Of course there is always going to be a penality for stackful coroutines that yield deep into a callstack.
  - 10000truths 4y ago
    Unfortunately, this is very difficult to do above the assembly level because it requires a custom calling convention that doesn’t yet seem to be supported by any systems programming language compiler. You have to use an assembler macro, or pipe the assembler output through sed, to patch the call and ret instructions: https://stackoverflow.com/questions/43894511 https://stackoverflow.com/questions/43894511
    - gpderetta 4y ago
      GCC inline assembly can be coerced to do the right thing.
      - saagarjha 4y ago
        It’s not great, though. Modern C compilers will generally fight you if you try to subvert structured programming.
efitz 4y ago
I think that the days where hand tuned assembly language outperform compiler generated code are largely behind us (let loose the contrary anecdotes). Compilers and microprocessors are way more complex than they were back in the 80s or 90s, and compiler engineers know way more about how instructions are actually executed than the vast majority of programmers.
- tubs 4y ago
  https://codegolf.stackexchange.com/questions/215216/high-throughput-fizz-buzz/236630#236630 https://codegolf.stackexchange.com/questions/215216/high-thr...
- makapuf 4y ago
  ... and yet in this article, the author beats by 10x a C compiled code with hand tuned assembly. (By using SIMD and unrolling, which the compiler did not. Granted linear compiler code is faster than hand made linear assembly)
  - zokier 4y ago
    Author beats compiler because floating point constraints, with -ffast-math compiler vectorizes the code.. I don't have arm64 hardware to test the result, but its probably again pretty fast: https://gcc.godbolt.org/z/xvjY8P4cM https://gcc.godbolt.org/z/xvjY8P4cM
- wolf550e 4y ago
  compiler autovectorization is poor, people often outperform it when writing SIMD code. intrinsics are so low level they might as well be assembly.
  - JonChesterfield 4y ago
    I've had really good results from the two in LLVM (one works on loops, one within basic blocks). Optimal loop body when the pointers had alignment metadata attached, though at the time it failed to unroll the tail. Using intrinsics with the control flow in C or C++ works really well - you get the right instruction selection from the intrinsics, easy to reason about control flow and the compiler deals with register allocation (and possibly instruction scheduling) which are a pain to do by hand.
sylware 4y ago
I write assembly mainly _not_ because it is faster, but because I don't depend on an absurdely complex and massive compiler.
- packetlost 4y ago
  So... how does that work? What sort of work do you do that you have the time to write raw ASM and still be productive? I'm asking in earnest, because I'm curious what sort of workflows still allow for writing ASM directly outside of very specific cases (such as initializing embedded MCUs, for example)
  - Am4TIfIsER0ppos 4y ago
    any audio or video work You don't want to be forced to trick the compiler into using the SIMD instructions you are aware of so you write an assembly function.
    - packetlost 4y ago
      Forcing SIMD instructions seems like a pretty reasonable, but specialized use-case that would warrant using ASM. But from what I understand, you'd still be using a compiler for whatever higher-level language (say, C/C++) for most of the work and ASM for the really performance sensitive portions of the code (or when trying to force the usage of some CPU extension). My interpretation of GP was that they exclusively write in ASM, though that may not have been correct.
      - Am4TIfIsER0ppos 4y ago
        Okay I can see how you thought that. And we do use something higher for all the other parts. Look at ffmpeg for an example. https://github.com/ffmpeg/ffmpeg https://github.com/ffmpeg/ffmpeg The github mirror says a mere 6.6% is assembly
ShroudedNight 4y ago
I feel like this treatment is incomplete without having tested the scenario where the unmatched ret is replaced with a br lr. EDIT: Reading the documentation after the fact, it appears that that was what br x30 was - naively I had interpreted the hex as a fixed offset to a label.
error503 4y ago
Interesting. I thought it would be interesting to compare the behaviour of (very) different AArch64 processors on this code. I ran your code on an Oracle Cloud Ampere Altra A1: sum_slice time: [677.45 ns 684.25 ns 695.67 ns] sum_ptr time: [689.11 ns 689.42 ns 689.81 ns] sum_ptr_asm_matched time: [1.3773 µs 1.3787 µs 1.3806 µs] sum_ptr_asm_mismatched time: [1.0405 µs 1.0421 µs 1.0441 µs] sum_ptr_asm_mismatched_br time: [699.79 ns 700.38 ns 701.02 ns] sum_ptr_asm_branch time: [695.80 ns 696.61 ns 697.56 ns] sum_ptr_asm_simd time: [131.28 ns 131.42 ns 131.59 ns] It looks like there's no penalty on this processor, though I would be surprised if it does not have a branch predictor / return stack tracking at all. In general there's less variance here than the M1. The SIMD version is indeed much faster, but by a smaller factor. And on the relatively (very) slow Rockchip RK3399 on OrangePi 4 LTS (1.8GHz Cortex-A72): sum_slice time: [1.7149 µs 1.7149 µs 1.7149 µs] sum_ptr time: [1.7165 µs 1.7165 µs 1.7166 µs] sum_ptr_asm_matched time: [3.4290 µs 3.4291 µs 3.4292 µs] sum_ptr_asm_mismatched time: [1.7284 µs 1.7294 µs 1.7304 µs] sum_ptr_asm_mismatched_br time: [1.7384 µs 1.7441 µs 1.7519 µs] sum_ptr_asm_branch time: [1.7777 µs 1.7980 µs 1.8202 µs] sum_ptr_asm_simd time: [421.93 ns 422.63 ns 423.30 ns] Similar to the Ampere processor, but here we pay much more for the extra instructions to create matching pairs. Interesting here that the mismatched branching is faster than the single branch. I guess absolute numbers are not too meaningful here, but a bit interesting that Ampere Altra is also the fastest of the 3 except in SIMD where M1 wins. I would have expected that with 80 of these cores on die they'd be more power constrained than M1, but I guess not. Edit: I took the liberty of allowing LLVM to do the SIMD vectorization rather than OP's hand-built code (using the fadd_fast intrinsic and fold() instead of sum()). It is considerably faster still: Ampere Altra: sum_slice time: [86.382 ns 86.515 ns 86.715 ns] RK3399: sum_slice time: [306.94 ns 306.94 ns 306.95 ns]
- sakras 4y ago
  If you’re only heavily using one of the cores, that core is free to use a lot more power, and can probably push its clock speed much higher than if this were an all-core workload. So I’d actually expect the opposite, that the ampere would be allowed to use a lot more power than the M1 (since it’s not a laptop).
nobody9999 4y ago
Thank you for posting this. Somewhat OT, but I miss Phil Hartman[0][1][2]. You may remember him[3] from shows like Saturday Night Live, The Simpsons and "Planet of the Apes."[4] [0] https://en.wikipedia.org/wiki/Phil_Hartman https://en.wikipedia.org/wiki/Phil_Hartman [1] https://en.wikipedia.org/wiki/Happy_Fun_Ball https://en.wikipedia.org/wiki/Happy_Fun_Ball [2] https://www.youtube.com/watch?v=GmqeZl8OI2M https://www.youtube.com/watch?v=GmqeZl8OI2M [3] https://screenrant.com/the-simpsons-funniest-troy-mcclure-quotes/ https://screenrant.com/the-simpsons-funniest-troy-mcclure-qu... [4] https://www.youtube.com/watch?v=yOeUXEpxzcc https://www.youtube.com/watch?v=yOeUXEpxzcc
ahh 4y ago
Interestingly, Matt has invented a variant on the retpoline [1] which _intentionally_ missteers the branch predictor to prevent various speculative attacks. (Invented by my former Google manager.). It's pretty cool how much simpler a retpoline would be in aarch64, since we have explicit control over the link register rather than having to play stupid games with stacks. (Real retpolines have a little more magic, naturally.) [1]https://stackoverflow.com/questions/48089426/what-is-a-retpoline-and-how-does-it-work https://stackoverflow.com/questions/48089426/what-is-a-retpo...
xKingfisher 4y ago
An interesting application of this is massaging the branch predictor using tail calls to speed up a parser/interpreter: https://blog.reverberate.org/2021/04/21/musttail-efficient-interpreters.html https://blog.reverberate.org/2021/04/21/musttail-efficient-i...
- saagarjha 4y ago
  The wins from tail calls are generally more from being able to skip the overhead that comes from a function call rather than better branch prediction.
  - xKingfisher 4y ago
    It's mentioned in passing at the end of the "the trouble with interpreter loops" section. A traditional switch/goto loop can thrash the branch predictor. Separating into different tail calling functions gives you more slots and allows the branch predictor to learn relationships between ops. Not to discount the many other benefits of tail calls. *Edit: I misspoke slightly, computed gotos can also split the patch jump, but less reliably[0]. [0]https://gcc.gnu.org/pipermail/gcc/2021-April/235891.html https://gcc.gnu.org/pipermail/gcc/2021-April/235891.html
LoganDark 4y ago
I love how "rewrite it in Rust" is an actual thing they tried, and it actually performed pretty well given the circumstances.
sacnoradhq 4y ago
After about the Pentium-/Pentium Pro-era, hand-coded assembly generally is premature optimization (and wasted effort). Once upon a time(tm), you could write self-modifying code or guess at keeping pipelines occupied by manual instruction reordering, but cache line invalidation and OOOE make these moot. The problem is that with a pipeline stall (wrong branch predicted) in hyper-deep pipelines, the penalty is enormous: waiting for the other condition calculation to percolate through the pipeline or independent stages. Processors are optimized for the mainstream, usually the current or last generation of compilers when the processors were designed. To generate the generally fastest bitcode, it would require an incremental JIT with history that can permute and mutate bitcode from runtime metrics. That's beyond HotSpot(tm), LLVM, or anything of the sort.

314 points by mkeeter 4y ago

Ow. My head hurts. And this is why optimizing compilers are some of the most complex programs there are. (or so I have been taught)

shadowgovt 4y ago
It's also why the modern rule of thumb is "don't optimize by writing your own assembly." The rule is a boiled-down version of the larger notion "Don't optimize by writing your own assembly, because even with domain knowledge of the problem you're trying to solve, you're probably not more clever than the engineer-decades that went into building your compiler toolchain and processor architecture, unless you're an expert in both fields, in which case good luck and shoulder that maintenance burden." The rule of thumb drops a lot of detail on the ground but is a good first approximation.
- RodgerTheGreat 4y ago
  I would just phrase it as "if you optimize by writing your own assembly, don't expect your program or its performance to be portable."
- astrobe_ 4y ago
  ... Which is kind of worrying; is it really a good thing that processors are so complex that you need "decades" to use them to fully. Bottom line, you end up with chaotic (in the "sensitive to the slightest change") performance behavior. OTOH this reminds of another saying, "don't roll your own crypto". But all those "don't" are a bit frustrating.
  - miloignis 4y ago
    I've seen people get frustrated by the "don't"s before, but I think that's generally taking the first degree approximation too literally. Feel free to hand-write assembly or roll your own crypto, but don't depend on it for anything serious unless you are an expert or have it reviewed by one. Doing so for learning and fun is fine, if that's clearly called out such that no one accidentally depends on it for something serious. There's only one way to become good at something, and that's good practice! In a professional setting there's a responsibility to the end user which generally precludes doing these dangerous things - that is, one should feel free to take up woodworking as a hobby but shouldn't offer to build someone's house unless you're a licensed professional.
  - olliej 4y ago
    But you don't need decades of experience: we have compilers and optimizers to do that.
    - bioint7812 4y ago
      It's interesting that the impedence the author was experiencing was one of the CPU incorrectly "speculating" about the intent. We as readers are left to speculate about the problem being solved by the author. Based on the content of his recent articles, we could assume he is continuing his development of a JIT for a Rust port of his graphics engine. Given that assumption, I would argue that the compiler writers are lagging here--specifically lack of dynamic compilation. For example, is there a JIT compiler for the Rust language? I was thinking about reproducing his experiment in SBCL, which does have dynamic compilation--although it wouldn't be a real "apples" to "apples" comparison because my work machine is a x86_64.
      - olliej 4y ago
        JITs have very different constraints (but also many advantages) vs AOT compilers, so I don't think in the general case a language compiler can "support" JITs directly. llvm/clang for instance have a jit mode... for compiling C/C++, not some other language. Also obviously the compiler writers (AOT or JIT) need to know about and understand very minute details of how a cpu is behaving. I was responding to a person saying it was worrying that devs need that kind of knowledge and experience by saying that that isn't true because the tools exist (I feel that there's some analogy to what knowledge you need for a car: changing oil, servicing engine, replacing engine, designing an engine...). Once you are writing a JIT you're in the "making the tools" group, so you now need to know more than the vast majority of devs (not just more than the "average" dev) that's inescapable.
  - deleted 4y ago
    [deleted]
- pjdesno 4y ago
  Maybe better expressed as "don't write your own assembly unless you know why it might be better than the compiler". Trying to beat the compiler at optimizing normal code is kind of like trying to beat a calculator with paper and pencil - computers are just better at that sort of thing than people are. One use case is where you want to use bizarre CPU functions (popcount, encryption, load CR3, etc.) that no one's taught the compiler how to generate, although for some of them you might be better off using compiler intrinsics. Another is when you're dealing with things underneath the language abstraction, like the Boost co-routines mentioned in a link a few comments above. Of course, if the language folks decide to add the capability you want (e.g. C++20 coroutines), you're back to being better off using the compiler. Finally there are pedagogical reasons, e.g. sometimes I show my classes the world's simplest "Hello World", using a few lines of assembler to invoke the write and exit syscalls.
  - JonChesterfield 4y ago
    The boost coroutines mentioned are not the same thing as the C++20 ones. Boost captures the stack, that's what the register shuffling is for. C++ is a compiler transform that moves some state onto the heap, but probably not the whole stack, and builds a switch dispatch style thing to transform the control flow. This is why C++ comes with co_* annotations and coroutines don't.
- avgcorrection 4y ago
  I will never understand the trend of “using quotes around things”. Which is a shorthand version for “using quotes around things that I wanted to point to and say, hey, this is something that “goes over here”, you know, inside these quotes, to make sure that you understand exactly what I’m delimiting, since using commas, and semicolons, and colons wouldn’t fit for some reason. Oh look the thing that I’m quoting now consumes 80% of this paragraph. But this is way better than just saying “the modern rule of thumb is to not optimize by writing your own assembly.” Because then it isn’t 100% clear that the rule of thumb is delimited by (exactly) “[do] not optimize by writing your own assembly.” Ya see?”
- magicalhippo 4y ago
  Another is that your assembly will never target newer CPUs, but the compiler will. I've gained a lot of performance by replacing handwritten assembly functions with plain code versions, just because CPUs and compilers have evolved over the last 15-20 years, while that assembly code is what it is.
JonChesterfield 4y ago
There's a sense in which they're complicated. It's a sequence of graph transforms which mostly deal with non-polynomial time problems using heuristics, where mistakes in the transforms can manifest quite a long way away from the error. There's a significant risk that they're implemented in languages unique to that compiler toolchain, as compiler devs are quite prone to solving problems by writing compilers. There's also a sense in which they're really simple. The input format and output format are (usually) well defined. The user interface is largely printing things to stderr and giving up, possibly in a retry loop when there's an editor involved. The program dependency graph is often quite small so the bug you're looking at is probably in the source code you checked out. Security is not the dominant concern you have elsewhere.
bob1029 4y ago
The state of modern compilers is pretty staggering to me. I've seen some code folding in RyuJIT that makes me feel inferior as a developer. You've got a few compilers (Java, .NET, et. al.) which are capable of re-compiling hot path code during live execution and then seamlessly transitioning to those paths. This recompilation can be based upon the statistics of the live process, so it's almost like a sort of adaptive AI. Which paths are hot in production does not need to be known at compile time with these approaches.
astrange 4y ago
Optimizing compilers don't model things like branch prediction well, and aren't great at autovectorizing either. They work just well enough. In general I think they aren't that complicated since they have a pass structure that's relatively easy to inspect and helps avoid spaghetti code.

ogogmad 4y ago

Minor erratum: Floating point addition actually is commutative; it's in fact non-associative.

dekhn 4y ago
with some significant exceptions, such as NaNs.
- recursive 4y ago
  Can you think of some `x` where `x + NaN` is not identical to `NaN + x`? I can't.
  - dekhn 4y ago
    you mean, like 1 + NaN = NaN and NaN + 1 = NaN, but NaN != NaN? (I'm not a numerical expert, just repeating what others have told me)
    - CountSessine 4y ago
      Yes. An NaN in IEEE754 has all 1’s in the exponent, and then the high bit of the mantissa determines whether it’s quiet or signalling, but then rest of the mantissa is/can be a “payload”.
      - bruce343434 4y ago
        Sign bit determines signalling
        robocat 4y ago
        Please double check your facts before disagreeing with somebody so abruptly. Sign bit is NOT the signalling/quiet bit. Bit 51 (edit or bit 50 - damn ***** IEEE for not publishing important standards for free public access) is according to the first result I looked at: https://craftinginterpreters.com/optimization.html https://craftinginterpreters.com/optimization.html Edit 2 from IEEE 754 (2008 version): 6.2.1 NaN encodings in binary formats This subclause further specifies the encodings of NaNs as bit strings when they are the results of operations. When encoded, all NaNs have a sign bit and a pattern of bits necessary to identify the encoding as a NaN and which determines its kind (sNaN vs. qNaN). The remaining bits, which are in the trailing significand field, encode the payload, which might be diagnostic information (see above). All binary NaN bit strings have all the bits of the biased exponent field E set to 1 (see 3.4). A quiet NaN bit string should be encoded with the first bit (d1) of the trailing significand field T being 1. A signaling NaN bit string should be encoded with the first bit of the trailing significand field being 0. If the first bit of the trailing significand field is 0, some other bit of the trailing significand field must be non-zero to distinguish the NaN from infinity. In the preferred encoding just described, a signaling NaN shall be quieted by setting d1 to 1, leaving the remaining bits of T unchanged. 6.3 The sign bit When either an input or result is NaN, this standard does not interpret the sign of a NaN. Note, however, that operations on bit strings—copy, negate, abs, copySign—specify the sign bit of a NaN result, sometimes based upon the sign bit of a NaN operand. The logical predicate totalOrder is also affected by the sign bit of a NaN operand. For all other operations, this standard does not specify the sign bit of a NaN result, even when there is only one input NaN, or when the NaN is produced from an invalid operation. When neither the inputs nor result are NaN, the sign of a product or quotient is the exclusive OR of the operands’ signs; the sign of a sum, or of a difference x−y regarded as a sum x+(−y), differs from at most one of the addends’ signs; and the sign of the result of conversions, the quantize operation, the roundTo- Integral operations, and the roundToIntegralExact (see 5.3.1) is the sign of the first or only operand. These rules shall apply even when operands or results are zero or infinite. When the sum of two operands with opposite signs (or the difference of two operands with like signs) is exactly zero, the sign of that sum (or difference) shall be +0 in all rounding-direction attributes except roundTowardNegative; under that attribute, the sign of an exact zero sum (or difference) shall be −0. However, x + x = x − (−x) retains the same sign as x even when x is zero. When (a×b)+c is exactly zero, the sign of fusedMultiplyAdd(a, b, c) shall be determined by the rules above for a sum of operands. When the exact result of (a × b) + c is non-zero yet the result of fusedMultiplyAdd is zero because of rounding, the zero result takes the sign of the exact result. Except that squareRoot(−0) shall be −0, every numeric squareRoot result shall have a positive sign. I.e. you are definitely wrong. The sign bit can be + or - for NaN (presumably a side-effect of the encoding for +/-Infinity ). And then that leads to a bunch of arse (section 6.3) because the spec needs to decide what happens to the sign bit in a bunch of different situations. PS: fucking infinity. Infinity should have been NaN. Infinity ≠ Infinity, except in in the egghead-land IEEE (side note: egghead is a compliment IMHO). Mind you, easy to see mistakes in retrospect, but corner cases are shit in programming. I do like NaN, although reading comments here, and the IEEE spec, forces me to learn how little I now about NaN encodings. Oh, and any NaN should equal any other NaN. Mathematically obviously not, but logically yes and IEEE is for programming. NaN is already defined as a nonsense, so at least keep the nonsense consistent. Changing if = to if ≠ should not introduce subtle logic bugs. Ranting edit #755: and while we are at it, -0 is an abomination in the eyes of the Great Architect in the Matrix - it should never have been allowed - perhaps -0 should have been NaN with signalling bits in the exponent (even though that would prevent some language virtual machine optimisations where 53 bits of NaN get used to pack other information, but the win would be compelling because reducing bugs due special cases is huge IMHO). How many developers understand IEEE corner cases: fuck all in my long experience.

titzer 4y ago

> More specifically, the branch predictor probably keeps an internal stack of function return addresses, which is pushed to whenever a bl is executed. When the branch predictor sees a ret coming down the pipeline, it assumes that you're returning to the address associated with the most recent bl (and begins prefetching / speculative execution / whatever), then pops that top address from its internal stack. There's no need for "probably" here. The micro-architectural mechanism is known as a return stack buffer[1] and is generally separate from the branch predictor unit, though the processor may make use of indirect branch prediction entries for returns as well. [1] It is, indeed, a tiny little stack of return addresses and indeed, the article hit performance issues by misaligning it. The (Intel chips') RSB is behind the Retbleed vulnerabilities.

jerf 4y ago

This is another good example of how our CPUs are in many ways specialized C processors. C is a structured programming language that uses functions, so our processors like functions. If you jump out of that paradigm, even if the assembly instructions nominally seem to allow it, you'll run more slowly. Even when it seems like what you're offering is a shortcut to the CPU. This is neither praise nor criticism of the current CPU paradigm; it's just something you need to understand if you want the best performance out of our machines. A different paradigm, like a concatenative-paradigm-based program, might naively be more inclined to compile into code that looks more like what the author tried, jumping between implementations of the stack operators without it actually being "functions". One can imagine processors that would be "happier" with that, and would be bothered by things that look like function returns more. But that's not the CPUs we have.

yencabulator 4y ago
> C is a structured programming language that uses functions, so our processors like functions. An interesting take on this is the (vaporware) Mill CPU, in which the machine code defines EBBs (Extended Basic Blocks), which can only be entered at the top. You cannot express jumping into the middle of a block from the outside, in their ISA. https://en.wikipedia.org/wiki/Extended_basic_block https://en.wikipedia.org/wiki/Extended_basic_block https://millcomputing.com/topic/introduction-to-the-mill-cpu-programming-model-2/ https://millcomputing.com/topic/introduction-to-the-mill-cpu...
masklinn 4y ago
Author was not jumping out of the paradigm here, they were deliberately misusing constructs specialised for the paradigm (br/ret). That’s like saying the toolcase is a specialised screw processor because you’re trying to drive nails using a screwdriver and it does not go well. And C is hardly the first or only procedural langage.
- Nevermark 4y ago
  No but C is a better model of most processors assembly, than most other procedural languages.

snerbles 4y ago

While I was in undergrad I toyed around with abusing the branch predictor on a few different machines, compiling something like the following with optimizations off - it performs an identical computation regardless of branch outcome: void branchLoop(unsigned int condition, unsigned int &sum) { // put something suitably large here unsigned int loopCount = 0x0fffffff; unsigned int i; // compile with -O0 or this gets optimized away for (i = 0; i < loopCount; i++) if ((i & condition) == 0) sum++; else sum++; } The Core Duo on my Thinkpad T60 had some very distinct slowdowns on certain bit patterns, which were not repeatable on the handful of other CPUs I had access to at the time. I haven't tried this with more modern CPUs, however.

gpderetta 4y ago
Predictors are getting better and better at recognizing long patterns (sometime at the cost of not being optimal with short patterns).

gpderetta 4y ago

Yes, never push and ret. Here is something I wrote (/me checks calendar) more than 15 years ago about optimizing coroutine control flow: https://www.crystalclearsoftware.com/soc/coroutine/coroutine/linuxasm.html https://www.crystalclearsoftware.com/soc/coroutine/coroutine...

water-your-self 4y ago

If an HN reader wanted to play around with similar digging, what would be the essential tools to be aware of and where best could he start? Assuming prior knowledge of assembly/C but without much experience decompiling or testing speed.

dcow 4y ago
Your compiler can spit out assembly, you just need to know how to read it. Sounds like the author was also using Xcode Instruments https://help.apple.com/instruments/mac/current/#/dev7b09c84f5 https://help.apple.com/instruments/mac/current/#/dev7b09c84f... to check cpu counters. And they were using criterion https://crates.io/crates/criterion https://crates.io/crates/criterion to microbenchmark. My guess would be that the author is porting some C code to Rust and making sure not to regress performance along the way (probably hopefully trying to increase it). Likely their program was written in Rust and the section they were trying to optimize called some old c code. Sounds like they rewrote the section in Rust since Rust <-> C ffi calls break out of the happy realm the rust compiler likes and end up causing a performance hit themselves. You can write inline assembly in Rust using the macro https://doc.rust-lang.org/reference/inline-assembly.html https://doc.rust-lang.org/reference/inline-assembly.html.
shoo 4y ago
Learn how to use a decent profiler. if you're running linux, that's probably perf: https://man7.org/linux/man-pages/man1/perf.1.html https://man7.org/linux/man-pages/man1/perf.1.html https://www.brendangregg.com/perf.html https://www.brendangregg.com/perf.html Here's a fun article from the cloudflare blog that gives an example of using of perf to diagnose performance of a small utility: https://blog.cloudflare.com/when-bloom-filters-dont-bloom/ https://blog.cloudflare.com/when-bloom-filters-dont-bloom/ Matt Godbolt's compiler explorer is also worth checking out: https://godbolt.org/ https://godbolt.org/

londons_explore 4y ago

Observation: Almost any code, when micro-optimized, can gain about 10x performance. So, if we had the time and energy, we could probably make all of computing at least 10x faster. But we don't have the time or energy to dedicate that much effort to every line of code... But perhaps AI does?

celeritascelery 4y ago
I don’t think that is generally true. He only got a large speedup because he used SIMD, which has nothing to do with micro optimization. I would say a better take away is that micro optimization is really hard and you will often make things worse if you don’t know what you are doing. Even if you do, you are only going to get a few percentage points.
- thethirdone 4y ago
  My experience micro optimizing things is that even without SIMD, most software can get at least a 5x in performance. With SIMD, you can often get 50x improvements. The reason why people thing "Even if you do, you are only going to get a few percentage points." is because it generally takes 5-50x the developer time to optimize such code. If it takes half a day to write naive code to do something like validate utf8, it probably takes ~25 workdays to make a fast SIMD version. If you instead spend an extra half a day, there is a good chance you get a 10-50% speedup using normal code.
  - mumumu 4y ago
    This is true on a few streaming application (such as parsing). And most of the speedup is because of tricks to avoid doing beaches. There is a great blog post from one of the authors of JSON SIMD discussing this. I'm on mobile, there is a link for the blog post on the simd JSON github repository.
    - mumumu 4y ago
      *avoid branches The blog post I mentioned: Paper: Parsing Gigabytes of JSON per Second https://branchfree.org/2019/02/25/paper-parsing-gigabytes-of-json-per-second/ https://branchfree.org/2019/02/25/paper-parsing-gigabytes-of... Another related post from Lemire: Ridiculously fast unicode (UTF-8) validation https://lemire.me/blog/2020/10/20/ridiculously-fast-unicode-utf-8-validation/ https://lemire.me/blog/2020/10/20/ridiculously-fast-unicode-... Those algorithms are fast. But to put them in perspective. A single x86 CPU can write 64B per cycle. At 5GHz, the theorical maximum bandwidth is 320 GBps. IIRC, the read bandwidth is twice that. There are others botlenecks, and is very hard to write code that writes at every cycle. A interesting consequence, is that the theorical maximum bandwidth is logarithmical to the number of cycles. Again, talking about branchless streaming application.

jefftk 4y ago

> The SIMD code does come with one asterisk, though: because floating-point addition is not associative, and it performs the summation in a different order, it may not get the same result as straight-line code. In retrospect, this is likely why the compiler doesn't generate SIMD instructions to compute the sum! What if you set -funsafe-math-optimizations, which allows "optimizations that allow arbitrary reassociations and transformations with no accuracy guarantees"?

makapuf 4y ago
You could just turn gcc to 11 and use -Ofast
- zokier 4y ago
  Both clang and gcc vectorize if you ask them nicely: https://gcc.godbolt.org/z/xvjY8P4cM https://gcc.godbolt.org/z/xvjY8P4cM
deleted 4y ago
[deleted]
not2b 4y ago
It's a bad idea to scramble the order of floating point operations unless you can tolerate extreme inaccuracy, and in some applications accurate FP results don't matter, but the non-associativity of FP isn't just a technicality: you can lose all of your significant digits if the order of operations in well-written scientific code is changed.
- thomasahle 4y ago
  But if we aren't assuming the original order was particularly nice, we are simple substituting one random (or arbitrary) order for another. No reason to expect it to be any worse or better.
  - not2b 4y ago
    The key is that if you do this, different optimization levels produce different numerical results, and also some problems in the code become unfixable; you can't group computations according to their expected value ranges because the compiler will ungroup them again, incorrectly assuming that FP addition and multiplication are associative. Certainly for some applications it's fine, but a test of whether it's fine would be, for example, that it works just as well with single-precision as double-precision and even 16-bit floats would be fine, for example weights in an NN.

iamsmooney 4y ago

Title is a reference to this old SNL skit: https://www.youtube.com/watch?v=GmqeZl8OI2M https://www.youtube.com/watch?v=GmqeZl8OI2M

bioint7812 4y ago
More translation: > for reasons https://www.urbandictionary.com/define.php?term=for%20reasons https://www.urbandictionary.com/define.php?term=for%20reason...
sophacles 4y ago
It's definitely a classic - if you haven't seen it I'd recommend it even if it wasn't related to the article :D
Agentlien 4y ago
It is actually linked from the article. In the sentence "In conclusion, do not taunt happy fun branch predictor with asymmetric usage of bl and ret instructions." the words "do not taunt happy fun branch predictor" are a link to the video on YouTube.

pranith 4y ago

Great investigative work! The stack structure you refer to here is called the Return Address Stack (RAS).

CalChris 4y ago

It took me a while to understand the mismatched bl/ret pairs because I'm used to reading matched bl/ret pairs. This confusion has to be similar to what the silicon is 'thinking': Human, I see matched bl/ret pairs all the time and I'm good at them. Why are you giving me mismatched pairs? I'll do the right thing but I'm not so good at them. Still, this seems like function inlining. But why not just inline and use a regular branch loop? Is foo() also being called from elsewhere? Is space at a premium?

masklinn 4y ago
> Upon seeing this program, it's a common reaction to ask "why is foo a subroutine at all?" > The answer is "because this is a didactic example, not code that's trying to go as fast as possible".

FullyFunctional 4y ago

Well, of course, the Return Address Stack (RAS) predictor maintains its own call stack and you need to understand how it works. However, there's a subtler way to break it: recurse too deeply. The RAS only has a fixed, small, and implementation dependent length. If you use deep recursion with non-trivial control flow (in particular multiple call sites), then the RAS will starting missing once you return from beyond that limit. Another consequence of the RAS is that co-routines switching is more expensive than they might appear at first. RISC-V has encoding hints to mark call(jal)/returns that are actually co-routine switching but the full cost can't be avoided.

gpderetta 4y ago
you can mitigate the cost by not 'call'-ing into your coroutine switch function but inlining the code into the surrounding coroutine. As a bonus you get a bit better branch prediction on your yield because distinct yields will share less state. Of course there is always going to be a penality for stackful coroutines that yield deep into a callstack.
- 10000truths 4y ago
  Unfortunately, this is very difficult to do above the assembly level because it requires a custom calling convention that doesn’t yet seem to be supported by any systems programming language compiler. You have to use an assembler macro, or pipe the assembler output through sed, to patch the call and ret instructions: https://stackoverflow.com/questions/43894511 https://stackoverflow.com/questions/43894511
  - gpderetta 4y ago
    GCC inline assembly can be coerced to do the right thing.
    - saagarjha 4y ago
      It’s not great, though. Modern C compilers will generally fight you if you try to subvert structured programming.

efitz 4y ago

I think that the days where hand tuned assembly language outperform compiler generated code are largely behind us (let loose the contrary anecdotes). Compilers and microprocessors are way more complex than they were back in the 80s or 90s, and compiler engineers know way more about how instructions are actually executed than the vast majority of programmers.

tubs 4y ago
https://codegolf.stackexchange.com/questions/215216/high-throughput-fizz-buzz/236630#236630 https://codegolf.stackexchange.com/questions/215216/high-thr...
makapuf 4y ago
... and yet in this article, the author beats by 10x a C compiled code with hand tuned assembly. (By using SIMD and unrolling, which the compiler did not. Granted linear compiler code is faster than hand made linear assembly)
- zokier 4y ago
  Author beats compiler because floating point constraints, with -ffast-math compiler vectorizes the code.. I don't have arm64 hardware to test the result, but its probably again pretty fast: https://gcc.godbolt.org/z/xvjY8P4cM https://gcc.godbolt.org/z/xvjY8P4cM
wolf550e 4y ago
compiler autovectorization is poor, people often outperform it when writing SIMD code. intrinsics are so low level they might as well be assembly.
- JonChesterfield 4y ago
  I've had really good results from the two in LLVM (one works on loops, one within basic blocks). Optimal loop body when the pointers had alignment metadata attached, though at the time it failed to unroll the tail. Using intrinsics with the control flow in C or C++ works really well - you get the right instruction selection from the intrinsics, easy to reason about control flow and the compiler deals with register allocation (and possibly instruction scheduling) which are a pain to do by hand.

sylware 4y ago

I write assembly mainly _not_ because it is faster, but because I don't depend on an absurdely complex and massive compiler.

packetlost 4y ago
So... how does that work? What sort of work do you do that you have the time to write raw ASM and still be productive? I'm asking in earnest, because I'm curious what sort of workflows still allow for writing ASM directly outside of very specific cases (such as initializing embedded MCUs, for example)
- Am4TIfIsER0ppos 4y ago
  any audio or video work You don't want to be forced to trick the compiler into using the SIMD instructions you are aware of so you write an assembly function.
  - packetlost 4y ago
    Forcing SIMD instructions seems like a pretty reasonable, but specialized use-case that would warrant using ASM. But from what I understand, you'd still be using a compiler for whatever higher-level language (say, C/C++) for most of the work and ASM for the really performance sensitive portions of the code (or when trying to force the usage of some CPU extension). My interpretation of GP was that they exclusively write in ASM, though that may not have been correct.
    - Am4TIfIsER0ppos 4y ago
      Okay I can see how you thought that. And we do use something higher for all the other parts. Look at ffmpeg for an example. https://github.com/ffmpeg/ffmpeg https://github.com/ffmpeg/ffmpeg The github mirror says a mere 6.6% is assembly

ShroudedNight 4y ago

I feel like this treatment is incomplete without having tested the scenario where the unmatched ret is replaced with a br lr. EDIT: Reading the documentation after the fact, it appears that that was what br x30 was - naively I had interpreted the hex as a fixed offset to a label.

error503 4y ago

Interesting. I thought it would be interesting to compare the behaviour of (very) different AArch64 processors on this code. I ran your code on an Oracle Cloud Ampere Altra A1: sum_slice time: [677.45 ns 684.25 ns 695.67 ns] sum_ptr time: [689.11 ns 689.42 ns 689.81 ns] sum_ptr_asm_matched time: [1.3773 µs 1.3787 µs 1.3806 µs] sum_ptr_asm_mismatched time: [1.0405 µs 1.0421 µs 1.0441 µs] sum_ptr_asm_mismatched_br time: [699.79 ns 700.38 ns 701.02 ns] sum_ptr_asm_branch time: [695.80 ns 696.61 ns 697.56 ns] sum_ptr_asm_simd time: [131.28 ns 131.42 ns 131.59 ns] It looks like there's no penalty on this processor, though I would be surprised if it does not have a branch predictor / return stack tracking at all. In general there's less variance here than the M1. The SIMD version is indeed much faster, but by a smaller factor. And on the relatively (very) slow Rockchip RK3399 on OrangePi 4 LTS (1.8GHz Cortex-A72): sum_slice time: [1.7149 µs 1.7149 µs 1.7149 µs] sum_ptr time: [1.7165 µs 1.7165 µs 1.7166 µs] sum_ptr_asm_matched time: [3.4290 µs 3.4291 µs 3.4292 µs] sum_ptr_asm_mismatched time: [1.7284 µs 1.7294 µs 1.7304 µs] sum_ptr_asm_mismatched_br time: [1.7384 µs 1.7441 µs 1.7519 µs] sum_ptr_asm_branch time: [1.7777 µs 1.7980 µs 1.8202 µs] sum_ptr_asm_simd time: [421.93 ns 422.63 ns 423.30 ns] Similar to the Ampere processor, but here we pay much more for the extra instructions to create matching pairs. Interesting here that the mismatched branching is faster than the single branch. I guess absolute numbers are not too meaningful here, but a bit interesting that Ampere Altra is also the fastest of the 3 except in SIMD where M1 wins. I would have expected that with 80 of these cores on die they'd be more power constrained than M1, but I guess not. Edit: I took the liberty of allowing LLVM to do the SIMD vectorization rather than OP's hand-built code (using the fadd_fast intrinsic and fold() instead of sum()). It is considerably faster still: Ampere Altra: sum_slice time: [86.382 ns 86.515 ns 86.715 ns] RK3399: sum_slice time: [306.94 ns 306.94 ns 306.95 ns]

sakras 4y ago
If you’re only heavily using one of the cores, that core is free to use a lot more power, and can probably push its clock speed much higher than if this were an all-core workload. So I’d actually expect the opposite, that the ampere would be allowed to use a lot more power than the M1 (since it’s not a laptop).

nobody9999 4y ago

Thank you for posting this. Somewhat OT, but I miss Phil Hartman[0][1][2]. You may remember him[3] from shows like Saturday Night Live, The Simpsons and "Planet of the Apes."[4] [0] https://en.wikipedia.org/wiki/Phil_Hartman https://en.wikipedia.org/wiki/Phil_Hartman [1] https://en.wikipedia.org/wiki/Happy_Fun_Ball https://en.wikipedia.org/wiki/Happy_Fun_Ball [2] https://www.youtube.com/watch?v=GmqeZl8OI2M https://www.youtube.com/watch?v=GmqeZl8OI2M [3] https://screenrant.com/the-simpsons-funniest-troy-mcclure-quotes/ https://screenrant.com/the-simpsons-funniest-troy-mcclure-qu... [4] https://www.youtube.com/watch?v=yOeUXEpxzcc https://www.youtube.com/watch?v=yOeUXEpxzcc

ahh 4y ago

Interestingly, Matt has invented a variant on the retpoline [1] which _intentionally_ missteers the branch predictor to prevent various speculative attacks. (Invented by my former Google manager.). It's pretty cool how much simpler a retpoline would be in aarch64, since we have explicit control over the link register rather than having to play stupid games with stacks. (Real retpolines have a little more magic, naturally.) [1]https://stackoverflow.com/questions/48089426/what-is-a-retpoline-and-how-does-it-work https://stackoverflow.com/questions/48089426/what-is-a-retpo...

xKingfisher 4y ago

An interesting application of this is massaging the branch predictor using tail calls to speed up a parser/interpreter: https://blog.reverberate.org/2021/04/21/musttail-efficient-interpreters.html https://blog.reverberate.org/2021/04/21/musttail-efficient-i...

saagarjha 4y ago
The wins from tail calls are generally more from being able to skip the overhead that comes from a function call rather than better branch prediction.
- xKingfisher 4y ago
  It's mentioned in passing at the end of the "the trouble with interpreter loops" section. A traditional switch/goto loop can thrash the branch predictor. Separating into different tail calling functions gives you more slots and allows the branch predictor to learn relationships between ops. Not to discount the many other benefits of tail calls. *Edit: I misspoke slightly, computed gotos can also split the patch jump, but less reliably[0]. [0]https://gcc.gnu.org/pipermail/gcc/2021-April/235891.html https://gcc.gnu.org/pipermail/gcc/2021-April/235891.html

LoganDark 4y ago

I love how "rewrite it in Rust" is an actual thing they tried, and it actually performed pretty well given the circumstances.

sacnoradhq 4y ago

After about the Pentium-/Pentium Pro-era, hand-coded assembly generally is premature optimization (and wasted effort). Once upon a time(tm), you could write self-modifying code or guess at keeping pipelines occupied by manual instruction reordering, but cache line invalidation and OOOE make these moot. The problem is that with a pipeline stall (wrong branch predicted) in hyper-deep pipelines, the penalty is enormous: waiting for the other condition calculation to percolate through the pipeline or independent stages. Processors are optimized for the mainstream, usually the current or last generation of compilers when the processors were designed. To generate the generally fastest bitcode, it would require an incremental JIT with history that can permute and mutate bitcode from runtime metrics. That's beyond HotSpot(tm), LLVM, or anything of the sort.