10 ms·

Debunking CISC vs. RISC code density

69 points by mbitsnbites 4y ago

deleted 4y ago
[deleted]
dragontamer 4y ago
The definition of RISC has changed. Remember when RISC didn't have division instructions because that was a complex microcode? I remember. Over in CISC land, x86 'DIV' was all you needed to divide. In RISC land (ARMv7 or earlier), you needed to write a division loop. ------ With RISC machines getting divide instructions, the delineation of RISC vs CISC is meaningless to me. All RISC machines have taken the best parts of CISC (Divide instruction. SIMD-instructions. AES instructions. Complex addressing schemes), and all CISC machines have taken the best parts of RISC (high register counts, pipelines, load/store architectures)
- gumby 4y ago
  > Remember when RISC didn't have division instructions because that was a complex microcode? I remember. > Over in CISC land, x86 'DIV' was... Don't forget that the same thing existed / exists in the CISC world. In the "old days" floating point was an optional unit, not just on some Mainframes but on early x86s as well, with the 8087 unit, whose quirks were in the design of IEEE 754 (avoiding the quirks!). Vector units and such were also external add ons. The guiding theme, if there is/was one of CISC architectures was the ability for people to write assembly code. That's why there are all those string manipulation instructions and the like: think of those old instruction sets as basically ALU manipulation plus some convenience subroutines implemented in hardware/microcode. The breakthrough of the 801 was realizing that with the rise of compilers, those convenience features were no longer needed and all the work required to support them was wasted and could be jettisoned. I really don't understand why Intel and AMD haven't fully implemented this point: just implement the instructions that compilers use, plus the ones needed for bootstrapping and kernels. Put all the "legacy" instructions into user mode library code. It would simplify the silicon, likely reducing bugs. BTW we are still in this functional unit environment, in spades: look at how much die area on the Apple M1 is used for non-CPU computation units.
  - dragontamer 4y ago
    > I really don't understand why Intel and AMD haven't fully implemented this point: just implement the instructions that compilers use, plus the ones needed for bootstrapping and kernels. Put all the "legacy" instructions into user mode library code. It would simplify the silicon, likely reducing bugs. You mean how x87 instructions is microcode emulated on SSE, which is microcode emulated on AVX hardware? (EDIT: I had a tidbit on MMX but I think I got my history wrong there) None of those x87 instructions "exist" anymore. The CPUs support them, but its just microcode emulation. There's no x87 stack, or 80-bit registers on modern computers anymore. Its all careful emulation. > The guiding theme, if there is/was one of CISC architectures was the ability for people to write assembly code. That's why there are all those string manipulation instructions and the like REP MOVSB is actually the fastest way to memcpy on Intel machines, actually, thanks to "enhanced movsb". It turns out that a single instruction to do memcpy is a really, really good idea.
    - gpderetta 4y ago
      I'm pretty sure that x87 is not microcode emulated (at least the basic arithmetic ops). I'm sure they use the same FPUs as SSE of course.
      - dragontamer 4y ago
        x87 is 80-bit floating point. They literally don't fit inside of 64-bit doubles of SSE. The extra bits need to be emulated. EDIT: And I'm sure there's some program out there that actually relies on those extra 16-bits of precision, and they'd be pissed if their least-significant bit had a fraction-of-a-bit more error per operation.
        gpderetta 4y ago
        They are not emulated, they run at optimal latency (in fact on Ice Lake FADD has better latency than ADDSD!), although at a lower throughput as there are less dedicated execution units.
- repiret 4y ago
  Your point is taken, but to be pedantically correct, ARMv7-R has an optional DIV instruction.
  - brandmeyer 4y ago
    Its even optional in ARMv7-A and Cortex-A9 doesn't have it.
- Joker_vD 4y ago
  Ha, AMD Am29000 had single-step MUL and DIV instructions, that is, they did a single addition/subtraction and shift; to actually divide two numbers you literally wrote a sequence of 32 identical (except of the very first/last one) MUL or DIV instructions: look at [0], sections "7.1.6. Integer multiplication" and "7.1.7. Integer division" on pp. 203–207. [0] http://www.bitsavers.org/components/amd/Am29000/1987_Am29000_Users_Manual.pdf http://www.bitsavers.org/components/amd/Am29000/1987_Am29000...
  - aap_ 4y ago
    The PDP-1 did this too, unless it was equipped with the automatic multiply-divide extension.
  - monocasa 4y ago
    The SH processors did this too.
- msla 4y ago
  Here's John Mashey, a designer of MIPS, on what RISC is: https://danluu.com/risc-definition/ https://danluu.com/risc-definition/ START QUOTE A: there is a very specific set of characteristics shared by most machines labeled RISCs, most of which are not shared by most CISCs. The RISC characteristics: a) Are aimed at more performance from current compiler technology (e.g., enough registers). OR b) Are aimed at fast pipelining in a virtual-memory environment with the ability to still survive exceptions without inextricably increasing the number of gate delays (notice that I say gate delays, NOT just how many gates). Even though various RISCs have made various decisions, most of them have been very careful to omit those things that CPU designers have found difficult and/or expensive to implement, and especially, things that are painful, for relatively little gain. I would claim, that even as RISCs evolve, they may have certain baggage that they'd wish weren't there ... but not very much. In particular, there are a bunch of objective characteristics shared by RISC ARCHITECTURES that clearly distinguish them from CISC architectures. I'll give a few examples, followed by the detailed analysis: MOST RISCs: 3a) Have 1 size of instruction in an instruction stream 3b) And that size is 4 bytes 3c) Have a handful (1-4) addressing modes) (it is VERY hard to count these things; will discuss later). 3d) Have NO indirect addressing in any form (i.e., where you need one memory access to get the address of another operand in memory) 4a) Have NO operations that combine load/store with arithmetic, i.e., like add from memory, or add to memory. (note: this means especially avoiding operations that use the value of a load as input to an ALU operation, especially when that operation can cause an exception. Loads/stores with address modification can often be OK as they don't have some of the bad effects) 4b) Have no more than 1 memory-addressed operand per instruction 5a) Do NOT support arbitrary alignment of data for loads/stores 5b) Use an MMU for a data address no more than once per instruction 6a) Have >=5 bits per integer register specifier 6b) Have >= 4 bits per FP register specifier END QUOTE Not having a hardware division opcode isn't on the list; in fact, the MIPS chips had hardware division, but it was odd in that it used the hi and lo registers and had an architectually-visible latency such that the compiler or human was encouraged to schedule opcodes such that they wouldn't stall the pipeline by trying to read the results of a division right after the division opcode had issued. https://devblogs.microsoft.com/oldnewthing/20180404-00/?p=98435 https://devblogs.microsoft.com/oldnewthing/20180404-00/?p=98... The divide opcode also didn't have a divide-by-zero exception. The point is that the MIPS, like a lot of RISC designs, prioritized pipelineability over convenient assembly language behavior, and expected compilers and humans to pick up the slack and write code to implement what, in a CISC design, would have been implemented in microcode.
froh 4y ago
the most common optimization for release builds and the one used by Linux distrubutions is -O2, not -O3. this is justified by real world measurements, btw, alas I don't have the article link at hand on the smartphone. the quintessential learning from that article was: measure and ideally profile before going beyond -O2 . and to see the size difference, I'd love to see -Os optimize for size used in comparison to -O2/-O3 which is unrolling loops and inlining static functions as it deems fit, beyond the inline keyword (which is a mere hint). another paradoxical effect of increasing generated code size with aggressive optimizations is that you may outgrow caches: if you're unlucky paging into slow DDR ram becomes necessary in inner loops and the execution speed decreases. I'd suggest to read the article with an extra grain of salt.
- colejohnson66 4y ago
  > [...] Linux distrubutions is -O2, not -O3. this is justified by real world measurements [...] No. It's because Linus fears -O3 for no reason. He even ordered the removal[1] of the -O3 Kconfig flag[0] (CONFIG_CC_OPTIMIZE_FOR_PERFORMANCE_O3) because "-O3 has a *loong* history of generating worse code than -O2"[1], whatever that means. From [2]: > Other upstream kernel developers also criticized that higher optimization level over the default -O2 level due to the risks, particularly with older compilers and memories from times when -O3 tended to be more buggy. In other words, because of bugs in previous versions that have been fixed, we won't use the feature. Linus and Co. are sticking their heads in the ground regarding -O3. He says he needs evidence -O3 is good, but doesn't actually provide evidence beyond hearsay that it's bad. Just because Linus says -O3 is bad doesn't mean he's right. [0]: https://www.phoronix.com/news/O3-Optimize-Kernel-2022-Patches https://www.phoronix.com/news/O3-Optimize-Kernel-2022-Patche... [1]: https://www.phoronix.com/news/Linus-Against-O3-Kernel https://www.phoronix.com/news/Linus-Against-O3-Kernel [2]: https://www.phoronix.com/news/Linux-6.0-Drops-O3-Kconfig https://www.phoronix.com/news/Linux-6.0-Drops-O3-Kconfig
  - gpderetta 4y ago
    There is a lot of cargo culting in the -O2 decision. But it also true that O3 enables a lot of loop optimizations that are not particularly relevant for the kernel. Also the kernel is less reliant of more aggressive inlining and interprocedural optimizations than, say, highly abstracted C++ code.
fweimer 4y ago
Inlining heuristics used for -O3 are architecture-specific, so this just shows that things have been tuned in a particular way, probably based on the most prevalent icache sizes. -O2 numbers might be different because of reduced inlining. I would expect the -O2 numbers to reflect better the actual ISA capabilities. The choice of sub-architecture matters as well. It's probably not fair to compare against outline atomics. In my experiments at least, VEX was more compact even for scalar code, etc.
- inkyoto 4y ago
  > Inlining heuristics used for -O3 are architecture-specific […] Yes, the inlining strategy is non-deterministic and does not yield same results across different ISA. Moreover, it does not even guarantee the same result for a single ISA if the code was compiled for a specific submodel of a CPU with a different instruction cache line size. Especially for the x86 ISA where instructions are variable length, it is common for instructions to inadvertantly spill over into the next I-cache line thus yielding a substantial performance penalty for a performance critical/sensitive code path. Therefore, a common technique for the optimiser was (I have not checked recently tho) to take into account the I-cache line size, group instructions in such a way that if a fat code sequence were to cross the cache line, fill in the rest of the cache line with NOP's and place the fat instruction into the next cache line. Such a problem is nearly non-existant for RISC ISA's although I would surmise that one has to watch out for tight loops anyway. > I would expect the -O2 numbers to reflect better the actual ISA capabilities. I would go on to add that today «-O3 -fno-inline-functions» would give a more accurate and faithful reflection of generic ISA capabilities today. For a long time, «-O3» was no more than «-O2 -finline-functions»; however, since then further optimisations have been added to «-O3» that are rather useful generic optimisations for modern CPU's (i.e. loop vectorisation and more). The article is especially lacklustre in this particular regard as the author does not go beyond generic bloviations and does not make an attempt to understand what hides beyond «-O3».
- mbitsnbites 4y ago
  The article has been updated with -O2 numbers. Spoiler alert: ARM & RISC-V still win over x86 & z/Arch.
- 4y ago
gpderetta 4y ago
> Dynamic code density [...] > We will not go down that rabbit hole. It seems to me that, unless you are on an embedded system, the dynamic code density is the only thing that matter. A proxy is to simply measure the I$ hit rate for similar pieces of code on similar machines, although this is very machine dependent (then again, code size in a vacuum is not terribly important). Measuring the static space taken by instructions is also very misleading as some RISCs do not have a good support for inline constants and need to load them from the constant pool (which I think is not in the code segment) and has non trivial effects on cache efficiency. Then again, with all prefixes, x86 is not particularly dense.
- mbitsnbites 4y ago
  Just using I$ hit ratio is problematic in many ways. E.g: - You'll probably not find implementations of different ISAs with identical cache configurations (size, associativity etc). - It says little about what work is actually done (different ISAs = insns do different amounts of work). - On x86 all bets are off w.r.t. the effect of the uop cache on the L1I cache hit ratio, and the uop cache hit ratio can't be compared to any other machine. - You need to reproduce the same program flow on different architectures to be able to compare the numbers. ...etc. I think that the only reasonable way to do it is to have a multi-ISA simulator where you are in full control of all these aspects. And it would be really hard work.
  - gpderetta 4y ago
    Re 2, the work per instruction doesn't matter if you compare the same program/program execution, in practice you will get an estimated of the resident set size over the amount of work. All your other points do stand and that's what I mean with 'is very machine dependent'. And yes, if you want to isolate fully the effect of instruction density an emulator might be the only solution. Still I think that profiling counters can get you 90% there.
    - mbitsnbites 4y ago
      I just don't see how I would run profiling counters on a z15 machine for instance ;-) With my limited resources this got me much more architecture coverage. And as usual, the answers are in the data, it's merely a matter of what questions you think that you are asking...
chasil 4y ago
It is far more impactful upon code density to compile 32-bit binaries, and eschew 64-bit. Solaris was known to do precisely this for everything in /bin. I recently saw this in action on a copy of SmartOS, and I imagine that OpenIndiana does the same. It's a shame that no major Linux distribution has openly performed this analysis for x86-64 and AArch64. ARM Thumb is also the smallest Busybox available for ARM 32-bit. On the other hand, two copies of libc are essentially thrashing the instruction cache.
- pclmulqdq 4y ago
  Most common x86-64 instructions are 4 bytes already. The next most common instruction size used in many compiled 64-bit programs is 3 bytes, followed by 5 bytes. I believe that AArch64 still uses 4-byte encodings for many instructions too, with a few that need 8 bytes.
  - chasil 4y ago
    Looking closer, I see that the difference between the latest busybox i686 and x86_64 versions is not large: busybox (i686) 2022-01-17 17:40 1.0M busybox (x86_64) 2022-01-17 18:53 1.1M However, the savings on ARM Thumb appears to be larger, even for the various 32-bit binaries (v7m is Thumb, as I understand it): busybox-armv7m 2019-06-10 14:02 867K busybox-armv5l 2019-06-10 14:02 1.1M busybox-armv7l 2019-06-10 14:02 1.1M busybox-armv7r 2019-06-10 14:02 1.1M busybox-armv8l 2019-06-10 14:02 1.1M Strange that Super-H is this large, as it inspired Thumb: busybox-sh4 2019-06-10 14:02 1.0M https://busybox.net/downloads/binaries/ https://busybox.net/downloads/binaries/
    - retrac 4y ago
      SH4 is relatively compact (16-bit instructions) but it isn't really compressed in the same way Thumb is. They shaved some corners to make things fit; e.g. there's only room for a 4 bit displacement in a load [R + disp] -> R type instruction. If you want to use an 8 bit displacement you have to use R0. This naturally leads to a lot of two-instruction sequences to calculate an offset into the stack, etc. which ends up practically more like classic MIPS in density.
Symmetry 4y ago
The "Network transfer speed / cost." issue was worse than this make it seem. In the first CISC designs you were reading in the instruction one byte at a time over the same bus that you would use to load or store data. An extra byte in the instruction meant that the instruction took an extra cycle to complete.
- bell-cot 4y ago
  > ...In the first CISC designs... In the x86 world, this issue applied all the way through the 80386 CPU. Or through the 80486, if you're a bit harsher in judging it's unified (code + data) 8KB cache*. (True, not one byte at a time once you got to the 8086. But the 32-bit 80386 and 80486 only had 32-bit busses, and those were still serious bottlenecks.) *The cache was "write-through" on all but a very few variants, yielding extra congestion on the bus.
elygre 4y ago
Whenever risc va cisc is discussed, I remember reading that it’s not a “reduced set of instructions”, but rather a “set of reduced instructions”. I always think of various addressing modes, and rather having the divide instruction know about these, risc would force you to handle those in separate steps.
pizlonator 4y ago
I don’t buy it. There’s nothing preventing GCC from having different inlining/outlining heuristics as well as different cost models for versioning based on target. Unless you control for that, the results are meaningless. My own tests say that x86 and arm thumb2 are about equally compact and everything else is fatter. But even those tests probably lacked all the controls you’d need to get it right.
- Joker_vD 4y ago
  > There’s nothing preventing GCC from having different inlining/outlining heuristics as well as different cost models for versioning based on target. Does it actually have that different logic? Because otherwise this sounds like that tired "nothing prevents the compiler to be arbitrarily smart" argument — sure, nothing prevents that except for the fact that someone has to actually implement this smartness.
  - pizlonator 4y ago
    I know that llvm has different logic. I know that every compiler that I’ve ever written ends up having different logic for this based on target, for a myriad of complex reasons. So I would assume GCC landed in the same place as anyone writing a complex compiler.
- mbitsnbites 4y ago
  The results mean what they mean: If you compile your software with GCC -O3 you will typically get smaller code and fewer instructions on average for modern fixed size RISC ISAs than for modern CISC ISAs. You would have to do further and other investigations to draw any other conclusions.
codedokode 4y ago
Totally unfair in my opinion: 1) They have excluded i386. It is well known that 64-bit archs waste lot of memory and 32-bit arch could probably save something 2) They should have disabled position-independent code generation because on i386 it takes more memory 3) Instead of optimizing for speed whole program it is better to optimize for speed only "hot" parts and optimize the rest for size. Or optimize everything for size.
- knorker 4y ago
  1) The article is checking what's the case in 2022. In my opinion it's quite reasonable to not let 32bit compete at all. (though there is a 32bit RISC there) 2) do you mean also on 64bit x86? Yeah, probably would be nice to see. But then again I would say that today's code is position independent. It's not useful with choice of ISA to compare a mode you would not run anyway. 3) That's not the argument this article aims (successfully) to debunk, though.
  - gpderetta 4y ago
    Re point 2, AMD64 supports IP relative addressing, so PIC code is more efficient than x86 and it is not penalized compared to the RISCs.
- bell-cot 4y ago
  > 1) They have excluded i386... From a few old articles, my impression was that x86-64 code is, in a fair number of cases, notably denser & faster than the i386 equivalent. Main reason why - only 8 architectural registers for the i386 code to use, vs. 16 for the x86-64 code. So the i386 CPUs can waste a lot of instructions & time shuffling data between registers and memory, because they've run out of registers.
- mbitsnbites 4y ago
  1) i386 is not representative of bleeding edge CPU architectures (as mentioned in the article). It would only be icluded for purely academic reasons - which was out of scope. 2) ... 3) In the real world most programs use a single optimization/tuning config for the entire program. The article aimed to analyze real world programs running on contemporary modern architectures.
babel_ 4y ago
Reaching for -O3 as the only option feels like a problem with the methodology. Is there the chance for -O2 or -Os as supplementary graphs? Or stacked / marked onto the existing graphs? -O3 is optimising for speed at a space-cost, after all, so it hardly feels like the absolute-correct option for this (hence my suggestion for, at the very least, -O2 as well, and -Os would be nice for contrast of "how dense" they _can_ get).
- mbitsnbites 4y ago
  Will have a look at -O2, time permitting.
AtlasBarfed 4y ago
I think we need to reexamine the "code size doesn't matter". Because as serial code execution has petered out, know what a great way to speed things up is? Keep your code in cache. if serial code speed is done in improvement, you can (especially with all the excess silicon real estate since moore's law the transistor count is progressing still) hardware implement code. Or you can fit it in the closest/fastest cache to CPUs there is. Which is why I think while the last two decades of computing were owned by Java, Python, Ruby, and Javascript, we will swing back to far less bloated languages in the next thirty years and start streamlining. CISC approaches may be needed in code to annotate what they do, with exploding core counts, you also need what the JVM does on steroids: you want something that can intelligently schedule compiled code against many cores. Right now, this is the domain of the programmer. Wave the magic AI wand?
- gpderetta 4y ago
  The thing is that code prefetches extremely well due to good branch prediction. On the other hand a cache miss can worsen the misprediction penality.
adrian_b 4y ago
The comparison was not really unbiased, because for RISC-V the compressed instruction extension was used, which artificially makes RISC-V appear to have shorter programs. RISC-V with the compressed instruction extension should be compared only with ARMv8-M (i.e. Thumb2), nanoMIPS or other such ISA's, which target similar levels of CPU performance, not with ARMv8-A, which is intended to be implemented at much higher levels of performance. The graph with the number of instructions reveals that the RISC-V programs were not shorter than the AArch64 programs, but longer by more than 12% (all AArch64 and RISC-V instructions have the same length). RISC-V has only one great feature that is the cause of a significant program length reduction, the combined compare-and-branch instructions, which save one instruction, i.e. one 32-bit word, at each conditional branch, i.e. at every 4 to 5 instructions, in comparison with AArch64. However the other weaknesses of RISC-V are great enough that even with the compare-and-branch advantage the RISC-V programs end longer than the AArch64 programs.
- imtringued 4y ago
  In RISCV compressed instructions are just an extension that you can mix with uncompressed instructions. There is no reason to not use them. Thumb2 is a completely different instruction set that is mutually exclusive with the uncompressed instruction set. If you want to be pendantic then RISC V compression is just adding more 32bit mini VLIW instructions.
- monocasa 4y ago
  RV-C is intended to be implemented on high perf systems; it's not some tiny, embedded core only extension like ARMv8-m. And I don't think it's misleading, instruction count isn't the only metric that matters. I$ pressure is very real. So they show both metrics.
  - gpderetta 4y ago
    It is meant for high performance implementations. But do they exist already?
    - 4y ago
akuma73 4y ago
This isn't totally surprising. x86 vs. ARM/RISC-V has fewer registers which can mean more spill/fill to the stack which results in more instructions to do the same work. The instruction decode length for x86 has been creeping up with 64-bit encodings and SIMD extenstion (prefix bytes) as you can see it's 3.96 for x86 vs. 4.00 for ARM.

69 points by mbitsnbites 4y ago

deleted 4y ago

[deleted]

The definition of RISC has changed. Remember when RISC didn't have division instructions because that was a complex microcode? I remember. Over in CISC land, x86 'DIV' was all you needed to divide. In RISC land (ARMv7 or earlier), you needed to write a division loop. ------ With RISC machines getting divide instructions, the delineation of RISC vs CISC is meaningless to me. All RISC machines have taken the best parts of CISC (Divide instruction. SIMD-instructions. AES instructions. Complex addressing schemes), and all CISC machines have taken the best parts of RISC (high register counts, pipelines, load/store architectures)

gumby 4y ago
> Remember when RISC didn't have division instructions because that was a complex microcode? I remember. > Over in CISC land, x86 'DIV' was... Don't forget that the same thing existed / exists in the CISC world. In the "old days" floating point was an optional unit, not just on some Mainframes but on early x86s as well, with the 8087 unit, whose quirks were in the design of IEEE 754 (avoiding the quirks!). Vector units and such were also external add ons. The guiding theme, if there is/was one of CISC architectures was the ability for people to write assembly code. That's why there are all those string manipulation instructions and the like: think of those old instruction sets as basically ALU manipulation plus some convenience subroutines implemented in hardware/microcode. The breakthrough of the 801 was realizing that with the rise of compilers, those convenience features were no longer needed and all the work required to support them was wasted and could be jettisoned. I really don't understand why Intel and AMD haven't fully implemented this point: just implement the instructions that compilers use, plus the ones needed for bootstrapping and kernels. Put all the "legacy" instructions into user mode library code. It would simplify the silicon, likely reducing bugs. BTW we are still in this functional unit environment, in spades: look at how much die area on the Apple M1 is used for non-CPU computation units.
- dragontamer 4y ago
  > I really don't understand why Intel and AMD haven't fully implemented this point: just implement the instructions that compilers use, plus the ones needed for bootstrapping and kernels. Put all the "legacy" instructions into user mode library code. It would simplify the silicon, likely reducing bugs. You mean how x87 instructions is microcode emulated on SSE, which is microcode emulated on AVX hardware? (EDIT: I had a tidbit on MMX but I think I got my history wrong there) None of those x87 instructions "exist" anymore. The CPUs support them, but its just microcode emulation. There's no x87 stack, or 80-bit registers on modern computers anymore. Its all careful emulation. > The guiding theme, if there is/was one of CISC architectures was the ability for people to write assembly code. That's why there are all those string manipulation instructions and the like REP MOVSB is actually the fastest way to memcpy on Intel machines, actually, thanks to "enhanced movsb". It turns out that a single instruction to do memcpy is a really, really good idea.
  - gpderetta 4y ago
    I'm pretty sure that x87 is not microcode emulated (at least the basic arithmetic ops). I'm sure they use the same FPUs as SSE of course.
    - dragontamer 4y ago
      x87 is 80-bit floating point. They literally don't fit inside of 64-bit doubles of SSE. The extra bits need to be emulated. EDIT: And I'm sure there's some program out there that actually relies on those extra 16-bits of precision, and they'd be pissed if their least-significant bit had a fraction-of-a-bit more error per operation.
      - gpderetta 4y ago
        They are not emulated, they run at optimal latency (in fact on Ice Lake FADD has better latency than ADDSD!), although at a lower throughput as there are less dedicated execution units.
repiret 4y ago
Your point is taken, but to be pedantically correct, ARMv7-R has an optional DIV instruction.
- brandmeyer 4y ago
  Its even optional in ARMv7-A and Cortex-A9 doesn't have it.
Joker_vD 4y ago
Ha, AMD Am29000 had single-step MUL and DIV instructions, that is, they did a single addition/subtraction and shift; to actually divide two numbers you literally wrote a sequence of 32 identical (except of the very first/last one) MUL or DIV instructions: look at [0], sections "7.1.6. Integer multiplication" and "7.1.7. Integer division" on pp. 203–207. [0] http://www.bitsavers.org/components/amd/Am29000/1987_Am29000_Users_Manual.pdf http://www.bitsavers.org/components/amd/Am29000/1987_Am29000...
- aap_ 4y ago
  The PDP-1 did this too, unless it was equipped with the automatic multiply-divide extension.
- monocasa 4y ago
  The SH processors did this too.
msla 4y ago
Here's John Mashey, a designer of MIPS, on what RISC is: https://danluu.com/risc-definition/ https://danluu.com/risc-definition/ START QUOTE A: there is a very specific set of characteristics shared by most machines labeled RISCs, most of which are not shared by most CISCs. The RISC characteristics: a) Are aimed at more performance from current compiler technology (e.g., enough registers). OR b) Are aimed at fast pipelining in a virtual-memory environment with the ability to still survive exceptions without inextricably increasing the number of gate delays (notice that I say gate delays, NOT just how many gates). Even though various RISCs have made various decisions, most of them have been very careful to omit those things that CPU designers have found difficult and/or expensive to implement, and especially, things that are painful, for relatively little gain. I would claim, that even as RISCs evolve, they may have certain baggage that they'd wish weren't there ... but not very much. In particular, there are a bunch of objective characteristics shared by RISC ARCHITECTURES that clearly distinguish them from CISC architectures. I'll give a few examples, followed by the detailed analysis: MOST RISCs: 3a) Have 1 size of instruction in an instruction stream 3b) And that size is 4 bytes 3c) Have a handful (1-4) addressing modes) (it is VERY hard to count these things; will discuss later). 3d) Have NO indirect addressing in any form (i.e., where you need one memory access to get the address of another operand in memory) 4a) Have NO operations that combine load/store with arithmetic, i.e., like add from memory, or add to memory. (note: this means especially avoiding operations that use the value of a load as input to an ALU operation, especially when that operation can cause an exception. Loads/stores with address modification can often be OK as they don't have some of the bad effects) 4b) Have no more than 1 memory-addressed operand per instruction 5a) Do NOT support arbitrary alignment of data for loads/stores 5b) Use an MMU for a data address no more than once per instruction 6a) Have >=5 bits per integer register specifier 6b) Have >= 4 bits per FP register specifier END QUOTE Not having a hardware division opcode isn't on the list; in fact, the MIPS chips had hardware division, but it was odd in that it used the hi and lo registers and had an architectually-visible latency such that the compiler or human was encouraged to schedule opcodes such that they wouldn't stall the pipeline by trying to read the results of a division right after the division opcode had issued. https://devblogs.microsoft.com/oldnewthing/20180404-00/?p=98435 https://devblogs.microsoft.com/oldnewthing/20180404-00/?p=98... The divide opcode also didn't have a divide-by-zero exception. The point is that the MIPS, like a lot of RISC designs, prioritized pipelineability over convenient assembly language behavior, and expected compilers and humans to pick up the slack and write code to implement what, in a CISC design, would have been implemented in microcode.

froh 4y ago

the most common optimization for release builds and the one used by Linux distrubutions is -O2, not -O3. this is justified by real world measurements, btw, alas I don't have the article link at hand on the smartphone. the quintessential learning from that article was: measure and ideally profile before going beyond -O2 . and to see the size difference, I'd love to see -Os optimize for size used in comparison to -O2/-O3 which is unrolling loops and inlining static functions as it deems fit, beyond the inline keyword (which is a mere hint). another paradoxical effect of increasing generated code size with aggressive optimizations is that you may outgrow caches: if you're unlucky paging into slow DDR ram becomes necessary in inner loops and the execution speed decreases. I'd suggest to read the article with an extra grain of salt.

colejohnson66 4y ago
> [...] Linux distrubutions is -O2, not -O3. this is justified by real world measurements [...] No. It's because Linus fears -O3 for no reason. He even ordered the removal[1] of the -O3 Kconfig flag[0] (CONFIG_CC_OPTIMIZE_FOR_PERFORMANCE_O3) because "-O3 has a *loong* history of generating worse code than -O2"[1], whatever that means. From [2]: > Other upstream kernel developers also criticized that higher optimization level over the default -O2 level due to the risks, particularly with older compilers and memories from times when -O3 tended to be more buggy. In other words, because of bugs in previous versions that have been fixed, we won't use the feature. Linus and Co. are sticking their heads in the ground regarding -O3. He says he needs evidence -O3 is good, but doesn't actually provide evidence beyond hearsay that it's bad. Just because Linus says -O3 is bad doesn't mean he's right. [0]: https://www.phoronix.com/news/O3-Optimize-Kernel-2022-Patches https://www.phoronix.com/news/O3-Optimize-Kernel-2022-Patche... [1]: https://www.phoronix.com/news/Linus-Against-O3-Kernel https://www.phoronix.com/news/Linus-Against-O3-Kernel [2]: https://www.phoronix.com/news/Linux-6.0-Drops-O3-Kconfig https://www.phoronix.com/news/Linux-6.0-Drops-O3-Kconfig
- gpderetta 4y ago
  There is a lot of cargo culting in the -O2 decision. But it also true that O3 enables a lot of loop optimizations that are not particularly relevant for the kernel. Also the kernel is less reliant of more aggressive inlining and interprocedural optimizations than, say, highly abstracted C++ code.

fweimer 4y ago

Inlining heuristics used for -O3 are architecture-specific, so this just shows that things have been tuned in a particular way, probably based on the most prevalent icache sizes. -O2 numbers might be different because of reduced inlining. I would expect the -O2 numbers to reflect better the actual ISA capabilities. The choice of sub-architecture matters as well. It's probably not fair to compare against outline atomics. In my experiments at least, VEX was more compact even for scalar code, etc.

inkyoto 4y ago
> Inlining heuristics used for -O3 are architecture-specific […] Yes, the inlining strategy is non-deterministic and does not yield same results across different ISA. Moreover, it does not even guarantee the same result for a single ISA if the code was compiled for a specific submodel of a CPU with a different instruction cache line size. Especially for the x86 ISA where instructions are variable length, it is common for instructions to inadvertantly spill over into the next I-cache line thus yielding a substantial performance penalty for a performance critical/sensitive code path. Therefore, a common technique for the optimiser was (I have not checked recently tho) to take into account the I-cache line size, group instructions in such a way that if a fat code sequence were to cross the cache line, fill in the rest of the cache line with NOP's and place the fat instruction into the next cache line. Such a problem is nearly non-existant for RISC ISA's although I would surmise that one has to watch out for tight loops anyway. > I would expect the -O2 numbers to reflect better the actual ISA capabilities. I would go on to add that today «-O3 -fno-inline-functions» would give a more accurate and faithful reflection of generic ISA capabilities today. For a long time, «-O3» was no more than «-O2 -finline-functions»; however, since then further optimisations have been added to «-O3» that are rather useful generic optimisations for modern CPU's (i.e. loop vectorisation and more). The article is especially lacklustre in this particular regard as the author does not go beyond generic bloviations and does not make an attempt to understand what hides beyond «-O3».
mbitsnbites 4y ago
The article has been updated with -O2 numbers. Spoiler alert: ARM & RISC-V still win over x86 & z/Arch.
4y ago

gpderetta 4y ago

> Dynamic code density [...] > We will not go down that rabbit hole. It seems to me that, unless you are on an embedded system, the dynamic code density is the only thing that matter. A proxy is to simply measure the I$ hit rate for similar pieces of code on similar machines, although this is very machine dependent (then again, code size in a vacuum is not terribly important). Measuring the static space taken by instructions is also very misleading as some RISCs do not have a good support for inline constants and need to load them from the constant pool (which I think is not in the code segment) and has non trivial effects on cache efficiency. Then again, with all prefixes, x86 is not particularly dense.

mbitsnbites 4y ago
Just using I$ hit ratio is problematic in many ways. E.g: - You'll probably not find implementations of different ISAs with identical cache configurations (size, associativity etc). - It says little about what work is actually done (different ISAs = insns do different amounts of work). - On x86 all bets are off w.r.t. the effect of the uop cache on the L1I cache hit ratio, and the uop cache hit ratio can't be compared to any other machine. - You need to reproduce the same program flow on different architectures to be able to compare the numbers. ...etc. I think that the only reasonable way to do it is to have a multi-ISA simulator where you are in full control of all these aspects. And it would be really hard work.
- gpderetta 4y ago
  Re 2, the work per instruction doesn't matter if you compare the same program/program execution, in practice you will get an estimated of the resident set size over the amount of work. All your other points do stand and that's what I mean with 'is very machine dependent'. And yes, if you want to isolate fully the effect of instruction density an emulator might be the only solution. Still I think that profiling counters can get you 90% there.
  - mbitsnbites 4y ago
    I just don't see how I would run profiling counters on a z15 machine for instance ;-) With my limited resources this got me much more architecture coverage. And as usual, the answers are in the data, it's merely a matter of what questions you think that you are asking...

chasil 4y ago

It is far more impactful upon code density to compile 32-bit binaries, and eschew 64-bit. Solaris was known to do precisely this for everything in /bin. I recently saw this in action on a copy of SmartOS, and I imagine that OpenIndiana does the same. It's a shame that no major Linux distribution has openly performed this analysis for x86-64 and AArch64. ARM Thumb is also the smallest Busybox available for ARM 32-bit. On the other hand, two copies of libc are essentially thrashing the instruction cache.

pclmulqdq 4y ago
Most common x86-64 instructions are 4 bytes already. The next most common instruction size used in many compiled 64-bit programs is 3 bytes, followed by 5 bytes. I believe that AArch64 still uses 4-byte encodings for many instructions too, with a few that need 8 bytes.
- chasil 4y ago
  Looking closer, I see that the difference between the latest busybox i686 and x86_64 versions is not large: busybox (i686) 2022-01-17 17:40 1.0M busybox (x86_64) 2022-01-17 18:53 1.1M However, the savings on ARM Thumb appears to be larger, even for the various 32-bit binaries (v7m is Thumb, as I understand it): busybox-armv7m 2019-06-10 14:02 867K busybox-armv5l 2019-06-10 14:02 1.1M busybox-armv7l 2019-06-10 14:02 1.1M busybox-armv7r 2019-06-10 14:02 1.1M busybox-armv8l 2019-06-10 14:02 1.1M Strange that Super-H is this large, as it inspired Thumb: busybox-sh4 2019-06-10 14:02 1.0M https://busybox.net/downloads/binaries/ https://busybox.net/downloads/binaries/
  - retrac 4y ago
    SH4 is relatively compact (16-bit instructions) but it isn't really compressed in the same way Thumb is. They shaved some corners to make things fit; e.g. there's only room for a 4 bit displacement in a load [R + disp] -> R type instruction. If you want to use an 8 bit displacement you have to use R0. This naturally leads to a lot of two-instruction sequences to calculate an offset into the stack, etc. which ends up practically more like classic MIPS in density.

Symmetry 4y ago

The "Network transfer speed / cost." issue was worse than this make it seem. In the first CISC designs you were reading in the instruction one byte at a time over the same bus that you would use to load or store data. An extra byte in the instruction meant that the instruction took an extra cycle to complete.

bell-cot 4y ago
> ...In the first CISC designs... In the x86 world, this issue applied all the way through the 80386 CPU. Or through the 80486, if you're a bit harsher in judging it's unified (code + data) 8KB cache*. (True, not one byte at a time once you got to the 8086. But the 32-bit 80386 and 80486 only had 32-bit busses, and those were still serious bottlenecks.) *The cache was "write-through" on all but a very few variants, yielding extra congestion on the bus.

elygre 4y ago

Whenever risc va cisc is discussed, I remember reading that it’s not a “reduced set of instructions”, but rather a “set of reduced instructions”. I always think of various addressing modes, and rather having the divide instruction know about these, risc would force you to handle those in separate steps.

pizlonator 4y ago

I don’t buy it. There’s nothing preventing GCC from having different inlining/outlining heuristics as well as different cost models for versioning based on target. Unless you control for that, the results are meaningless. My own tests say that x86 and arm thumb2 are about equally compact and everything else is fatter. But even those tests probably lacked all the controls you’d need to get it right.

Joker_vD 4y ago
> There’s nothing preventing GCC from having different inlining/outlining heuristics as well as different cost models for versioning based on target. Does it actually have that different logic? Because otherwise this sounds like that tired "nothing prevents the compiler to be arbitrarily smart" argument — sure, nothing prevents that except for the fact that someone has to actually implement this smartness.
- pizlonator 4y ago
  I know that llvm has different logic. I know that every compiler that I’ve ever written ends up having different logic for this based on target, for a myriad of complex reasons. So I would assume GCC landed in the same place as anyone writing a complex compiler.
mbitsnbites 4y ago
The results mean what they mean: If you compile your software with GCC -O3 you will typically get smaller code and fewer instructions on average for modern fixed size RISC ISAs than for modern CISC ISAs. You would have to do further and other investigations to draw any other conclusions.

codedokode 4y ago

Totally unfair in my opinion: 1) They have excluded i386. It is well known that 64-bit archs waste lot of memory and 32-bit arch could probably save something 2) They should have disabled position-independent code generation because on i386 it takes more memory 3) Instead of optimizing for speed whole program it is better to optimize for speed only "hot" parts and optimize the rest for size. Or optimize everything for size.

knorker 4y ago
1) The article is checking what's the case in 2022. In my opinion it's quite reasonable to not let 32bit compete at all. (though there is a 32bit RISC there) 2) do you mean also on 64bit x86? Yeah, probably would be nice to see. But then again I would say that today's code is position independent. It's not useful with choice of ISA to compare a mode you would not run anyway. 3) That's not the argument this article aims (successfully) to debunk, though.
- gpderetta 4y ago
  Re point 2, AMD64 supports IP relative addressing, so PIC code is more efficient than x86 and it is not penalized compared to the RISCs.
bell-cot 4y ago
> 1) They have excluded i386... From a few old articles, my impression was that x86-64 code is, in a fair number of cases, notably denser & faster than the i386 equivalent. Main reason why - only 8 architectural registers for the i386 code to use, vs. 16 for the x86-64 code. So the i386 CPUs can waste a lot of instructions & time shuffling data between registers and memory, because they've run out of registers.
mbitsnbites 4y ago
1) i386 is not representative of bleeding edge CPU architectures (as mentioned in the article). It would only be icluded for purely academic reasons - which was out of scope. 2) ... 3) In the real world most programs use a single optimization/tuning config for the entire program. The article aimed to analyze real world programs running on contemporary modern architectures.

babel_ 4y ago

Reaching for -O3 as the only option feels like a problem with the methodology. Is there the chance for -O2 or -Os as supplementary graphs? Or stacked / marked onto the existing graphs? -O3 is optimising for speed at a space-cost, after all, so it hardly feels like the absolute-correct option for this (hence my suggestion for, at the very least, -O2 as well, and -Os would be nice for contrast of "how dense" they _can_ get).

mbitsnbites 4y ago
Will have a look at -O2, time permitting.

AtlasBarfed 4y ago

I think we need to reexamine the "code size doesn't matter". Because as serial code execution has petered out, know what a great way to speed things up is? Keep your code in cache. if serial code speed is done in improvement, you can (especially with all the excess silicon real estate since moore's law the transistor count is progressing still) hardware implement code. Or you can fit it in the closest/fastest cache to CPUs there is. Which is why I think while the last two decades of computing were owned by Java, Python, Ruby, and Javascript, we will swing back to far less bloated languages in the next thirty years and start streamlining. CISC approaches may be needed in code to annotate what they do, with exploding core counts, you also need what the JVM does on steroids: you want something that can intelligently schedule compiled code against many cores. Right now, this is the domain of the programmer. Wave the magic AI wand?

gpderetta 4y ago
The thing is that code prefetches extremely well due to good branch prediction. On the other hand a cache miss can worsen the misprediction penality.

adrian_b 4y ago

The comparison was not really unbiased, because for RISC-V the compressed instruction extension was used, which artificially makes RISC-V appear to have shorter programs. RISC-V with the compressed instruction extension should be compared only with ARMv8-M (i.e. Thumb2), nanoMIPS or other such ISA's, which target similar levels of CPU performance, not with ARMv8-A, which is intended to be implemented at much higher levels of performance. The graph with the number of instructions reveals that the RISC-V programs were not shorter than the AArch64 programs, but longer by more than 12% (all AArch64 and RISC-V instructions have the same length). RISC-V has only one great feature that is the cause of a significant program length reduction, the combined compare-and-branch instructions, which save one instruction, i.e. one 32-bit word, at each conditional branch, i.e. at every 4 to 5 instructions, in comparison with AArch64. However the other weaknesses of RISC-V are great enough that even with the compare-and-branch advantage the RISC-V programs end longer than the AArch64 programs.

imtringued 4y ago
In RISCV compressed instructions are just an extension that you can mix with uncompressed instructions. There is no reason to not use them. Thumb2 is a completely different instruction set that is mutually exclusive with the uncompressed instruction set. If you want to be pendantic then RISC V compression is just adding more 32bit mini VLIW instructions.
monocasa 4y ago
RV-C is intended to be implemented on high perf systems; it's not some tiny, embedded core only extension like ARMv8-m. And I don't think it's misleading, instruction count isn't the only metric that matters. I$ pressure is very real. So they show both metrics.
- gpderetta 4y ago
  It is meant for high performance implementations. But do they exist already?
  - 4y ago

akuma73 4y ago

This isn't totally surprising. x86 vs. ARM/RISC-V has fewer registers which can mean more spill/fill to the stack which results in more instructions to do the same work. The instruction decode length for x86 has been creeping up with 64-bit encodings and SIMD extenstion (prefix bytes) as you can see it's 3.96 for x86 vs. 4.00 for ARM.