Hacker News Reader

Comment by jerf | Hacker News Reader

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.

View on HN

It's just a natural side effect of software and hardware forming a symbiosis and that they cannot really be separated. New software is (or should be!) built to run well on existing hardware, and new hardware is built to run existing software well. Besides, subroutine call instructions were a thing long before C became mainstream and manual assembly coding ruled supreme.

If you want to encode a series of indirect jumps between concatenated functions, you can do that already and the return address stack won’t get involved; you’ll simply get the normal branch predictors.

But generalized branch prediction is expensive (multiple entries in the BTB hashed by the previous program flow, and mispredicts if the next function in the chain changes); the point of an RAS is that it’s a very cheap way to keep some 100% predictable branches from using those general resources. Concatenation pretty much requires branches without unique characteristics, so no fast path shortcuts and everything is a bit slower.

> Concatenation pretty much requires branches without unique characteristics, so no fast path

Discussion the other day, of optimizing dispatch overhead in no-jit-allowed lightweight-word vm's, raised a brainstormy idea of having multiple copies of some words, and the compiler juggling them with awareness of their tailcall-next-word varied branch predictor states. Sort of a dynamic version of reducing dispatch by identifying hot phrases and creating multi-word-composite new words for them.

Would that be feasible on something like iOS that doesn't allow third-party JIT?

Could this allow for translating WASM or emulator workloads to something that runs fast with those restrictions?

Re iOS, yes. But runs fast? The words have to be small enough that the branch misprediction penalty (order-10 cycles) is significant. So for example, if a word is a single 3 cycle op then the dispatch matters, but with a dependency chain just a few ops long, the potential win drops under 50%. And having multiple copies of words will increase pressure on the instruction cache, so there will be a tradeoff, which may or may not be a win. So... perhaps this could be a way to dynamically optimize loop interiors? Or... perhaps to permit low-cost register shuffling words to glue together larger words with varied hard-wired register expectations? Or... insert creative idea here? There are blog posts around where someone writes a simple vm and incrementally optimizes it. But I don't recall seeing one yet with an iOS-ish focus of no-JIT, lots of registers, modern branch prediction... and so throws creative stuff against the wall and measures if anything sticks. It might be interesting to take such a blog post/series and do a followup?

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.

No but C is a better model of most processors assembly, than most other procedural languages.

Not sure how that is relevant. The GP asserts (and bemoans) the reverse cause-and-effect.

Only when we are talking about PDP-11.

Thankfully nowadays we have Compiler Explorer supporting almost every flavour of mainstream compiled languages to dispel myths.

This PDP-11 vs C thing always seems to come down to the PDP-11's auto-increment addressing modes vs C's ++ and --. Are there are any other PDP-11 features baked into C? Because this increment/decrement thing is hardly unique (the 68k CPUs had that too, and every CPU with a stack pointer also does it, some CPUs just made that a general addressing mode accessible in the instruction set.

While today's compiler do a lot more transformations which can result in surprising output, it's still fairly straightforward to map C statements to CPU instructions.

How do you map C statements to AVX512 instructions?

...by doing the only sensible thing and use intrinsics. Auto-vectorisation is exactly where compiler optimisations stop being useful.

On which page of ISO C can I find the intrinsics specification?

Not sure what your point is. There are no instruction-level parts to the standard. The C standard doesn't dictate how individual CPUs should operate.

The point is that C is very far away from being a "portable assembly" for any kind of modern processor. For the PDP-11 and other processors from that era, there was indeed some pretty simple 1:1 mapping between C instructions and their assembly. This has not been true for decades.

The point is in reference to flohofwoe's earlier comment which stated "it's still fairly straightforward to map C statements to CPU instructions.". By pointing out the existence of vectorized instructions, which are entirely absent from the C standard, pjmlp was making an argument by counter-example. That while you can map C statements to CPU instructions, most compilers typically don't apply such a 1-1 mapping.

The seeming non-sequitur referring to the ISO C standard was because flohofwoe responded to the rhetorical question as if it were a normal question, leading pjmlp to restate the rhetorical question in a stronger form.

The C standard only matters for compiler writers. What matters for compiler users is what specific compilers actually implement (and it's pretty much impossible to write a non-trivial C program which is 100% standard compliant, the Windows headers alone are full of MSVC idiosyncrasies).

> The C standard only matters for compiler writers.

There's two types of projects: those that are so big that any compiler writer will test against them to guard against Hyrum's Law, and those that are not. The former have no need for the C standard, as compiler writers would be loathe to break compatibility with it. The latter have a strong need for the C standard, as anything outside the C standard may be broken unknowingly by compiler writers.

> What matters for compiler users is what specific compilers actually implement

What matters for me is the likelihood that a compiler upgrade will break my code. If I stay within the standard, then any such breakage is a bug. If I stray outside the standard, then all I know is that this specific compiler, in this specific context, on this specific machine, for this specific compilation, has produced some machine code.

My home projects are not so large that gcc/clang/msvc authors would test their upgrades against my project, so the bounds of the standard are the limits that I can trust.

> the Windows headers alone are full of MSVC idiosyncrasies

I'd put the Windows headers in the category of sufficiently-large projects that compiler writers would test against them, rather than the other way around.

> My home projects are not so large that gcc/clang/msvc authors would test their upgrades against my project, so the bounds of the standard are the limits that I can trust.

You'll need to check your code against each new compiler release you want to support anyway, because each release adds a shitton of new warnings which are also not covered by the C standard but should be fixed nonetheless.

Absolutely, and it's really fantastic seeing how many bugs get caught from the new warnings. However, the effort required to check warnings is far, far less than the effort required to validate the assembly output, and so I think the point still stands.

Hence, C is only "portable assembly" for processors similar to a PDP-11, not for modern processors with modern ISAs.

Intrinsics are C language extensions outside the standard, but they are still an integral part of the "C language" that a specific compiler implements. In practice it really doesn't make much sense to separate the "standard C parts" and the "non-standard language extension" of a specific compiler.

Autoincrement and autodecrement didn't come from the PDP-11

https://web.archive.org/web/19980220175804/http://cm.bell-la...

> People often guess that they were created to use the auto-increment and auto-decrement address modes provided by the DEC PDP-11 on which C and Unix first became popular. This is historically impossible, since there was no PDP-11 when B was developed. The PDP-7, however, did have a few `auto-increment' memory cells, with the property that an indirect memory reference through them incremented the cell. This feature probably suggested such operators to Thompson; the generalization to make them both prefix and postfix was his own. Indeed, the auto-increment cells were not used directly in implementation of the operators, and a stronger motivation for the innovation was probably his observation that the translation of ++x was smaller than that of x=x+1.

--- Dennis Ritchie

The point is that C maps quite poorly onto the ISAs of most processors other than a PDP-11. There are various features of even 8086 that are not easily available in C (such as overflow detection) and huge numbers of instructions in newer ISAs that don't have any direct mapping to C code.

Additionally, modern processors have execution models that are entirely different from the C machine model, but this is often hidden even from the ISA. For example, modern x86-64 cores execute code by splitting up instructions into micro-instructions, determining data dependencies between them, then queueing them up on any of the available execution units (of various kinds) in parallel - which is about as far from the C model of executing instructions 1 by 1 in a series as it is from Haskell.

Well from the pov of machine or assembly code, C is without a doubt a high level language.

But at the same time it's the lowest-level high-level language (that's popular at least).

I'm also not aware of any high level programming languages that allow access to the CPUs status flags (for instance to check for overflow).

(there are a couple of interesting 'mid-level' languages for 8-bit processors though, like Millfork: https://github.com/KarolS/millfork)

I'd be all over a proper mid-level language that's closer to modern CPUs than C and has less 'optimization magic'. But this idea doesn't seem to be very popular amongst the compiler writer crowd.

Unless you know a widely used high level language that is is a better model of newer assembly, then C would still remain “the best”, no?

“Not as good lately”, doesn’t change that status without another language superseding it, right?

> C is a structured programming language that uses functions, so our processors like functions.

The main alternative paradigms that are ever mooted are LISP machines, which elevate the importance of functions, and maybe stack-based programming languages like Forth, which emphasize the feature of functions seen here (that they keep popping things off the stack).

It's hard to argue that C has led us down to a local minimum because it's just too functional.

This has more to do with the ISA than C I'd assume. C was built as an "easy assembler". Furthermore, the computer doesn't really care about structure (in the structured programming sense).

In this case the implementation of the ISA stores information on each 'ret' depending on some 'bl' that came before. One can imagine that a different optimization technique which actually leads to a speedup exists. Without a branch-predictor, the program that Matt wrote might've been faster.

Imo, this has nothing to do with paradigms, but how control-flow interacts with the system. This interaction is different between different implementations of an architecture.

Code written for Cache-locality and paradigms that work well with it, for example, only became a "winner" after caches were widely implemented. Before that, the cost of sequential array access and random array access was identical. With caches, a linear search for an element can be faster than a binary search, even though it requires a lot more memory accessess. Thus, the optimal implementation for finding an element in an array is now dependent on size as well. (I.e. after an ordered array reaches a certain size, binary search should become faster on average).

The point is that the ISA is assuming that BL and RET opcodes come in pairs - which is an assumption that does reflect what structured code is typically compiled down to. Going by the semantics of the opcodes themselves, there's no reason why RET should be treated differently from a simple indirect jump here.

> there's no reason why RET should be treated differently from a simple indirect jump here.

There’s its very existence. If you’re looking for a general purpose indirect jump, use that.

As far as I understand, the ISA explicitly intends for BL and RET to come in pairs. The only point of RET is to jump to the address last stored by BL. If you don't need this behavior, there's no reason to use RET - as the article itself shows, B x30 does the exact same job, and doesn't come with the extra assumptions.

That's my point - the ISA is designed around the notion that function calls (a structured programming concept!) are a thing that BL will be used for, and not arbitrary jumps where you happen to have some clever use of the link address.

And while it's not something that the example code in the article demonstrates, but based on the description of how it confuses the branch detector, it sounds like having multiple BLs without a matching RET for each would also be a problem.

Subroutines predate structured programming.

I was using the terminology as OP did, and yes, it is not quite right. But the point as I understood it was that branch predictors optimize around specific "structured" usage patterns of opcodes - in this case, the particular way to use BL/RET to implement function calls typical of C - to the point where any other use is too slow to be practical for anything.

what's the difference between a subroutine an a proper C function??

theyr'e so close to what they're in principle.

IMO, C functions are the answer to the problem exposed in the famous quote "goto considered harmful".

assembly is all about GOTOs.. C provides a *structure* way to deal with them without getting bored to day (it all becomes way to much to soon)

but I think (for reasons that I wish I could get into) that in the end, the goto-based assembly code can go up to multiplication, but then with C and their computer-functions one can go beyond exponentiation.

What is there beyond, I can only name by reference but wouldn't say I undesrtand it... which tetration.

so riddle me this: why is 2[op]2=4 for all these operations: addition, multiplication, exponentiation, tetration, pentation!?

imma go keep being insane. thxbai

Early subroutines were really just a branch/return - no stack frames and thus no proper argument passing or recursion or locals. If you've seen a BASIC dialect with GOSUB in it, that's pretty much it. It's a bit more structured than simple jumps, but still much lower level than C functions.

Structural programming is traditionally considered subroutines + conditionals + loops. In its purest form, it also means no branches other than the ones implicit in this list (i.e. not only no goto, but also no return, no break/continue etc).

No, the ISA overall is not designed around that notion. The designers merely recognized that this is a common pattern, and added 1 or 2 instructions specifically for it (it's not clear to me whether using BL for other purposes would have the same detrimental effects that using RET as in the article). This would likely be a very good addition even in a purely hypothetical world where it wasn't a common pattern in 99.9% of languages.

Also, I'm not sure why you believe that there is any kind of language where this pattern isn't common. Even something like Forth relies heavily on jumping into subroutines and back.

> Going by the semantics of the opcodes themselves,

This is RISC wishful thinking that makes it sound like BL is not CALL. Maybe in ARM 1 it wasn't, it is now.

> Going by the semantics of the opcodes themselves, there's no reason why RET should be treated differently from a simple indirect jump here.

RET is documented as a subroutine return hint in the official ARM architecture reference manual. That's the only reason it has a distinct opcode from BR.

BL is also documented as a subroutine call hint.

I agree, because this semantic difference between br x30 and ret doesn't exist in many other RISCs which also mostly run C-like languages. Power just has blr, and MIPS jr $ra, for example. This feels more like a well-intentioned footgun in the ISA.

The potential population for that footgun is compiler writers, who should safely fall into 'know what they are doing' territory.

> C is a structured programming language that uses functions, so our processors like functions.

So were most of the structured programming languages from 1960's.

PL/I, ESPOL, NEWP, ALGOL, Pascal, ...

General-purpose CPUs began as universal Turing machines for running any sort of mathematic calculations automatically. This was done in binary on punch cards and/or with panel cable settings. Then came textual assemblers to make that easier. Imperative procedural programs were then grafted-on to simplify writing assembly rather than in any sort of assembly language.

Most processors have accumulated functionality beyond minimal instructions for the simplification and acceleration of operating system services, hardware interfacing, cryptography, vector & matrix integer and floating-point math, arbitrary precision math, string processing, virtualization (IO and CPU), secure computing, and virtual memory management; just to name a few. :)

A future era of green field development closer to the technological singularity will look across the software-hardware interface boundaries to optimize both silicon (or superconductors) and compilers to generate fast, small, and/or power efficient designs and code without as many limitations. Generative AI and holistic algorithms with enormous computing power will make this possible. It's almost possible now, it's just a few leaps beyond what EDA and compilers are already doing.

> 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://millcomputing.com/topic/introduction-to-the-mill-cpu...

Reply on news.ycombinator.com