6 ms·

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 proce

by 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.
  - masklinn 4y ago
    Not sure how that is relevant. The GP asserts (and bemoans) the reverse cause-and-effect.
  - pjmlp 4y ago
    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.
    - Nevermark 4y ago
      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?
    - flohofwoe 4y ago
      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.
      - pjmlp 4y ago
        How do you map C statements to AVX512 instructions?
        flohofwoe 4y ago
        ...by doing the only sensible thing and use intrinsics. Auto-vectorisation is exactly where compiler optimisations stop being useful.
ablob 4y ago
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).
- int_19h 4y ago
  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.
  - masklinn 4y ago
    > 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.
  - tsimionescu 4y ago
    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.
flohofwoe 4y ago
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.
deleted 4y ago
[deleted]
brigade 4y ago
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.
- mncharity 4y ago
  > 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.
  - tmzt 4y ago
    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?
    - mncharity 4y ago
      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?
prohisto 4y ago
[flagged]
dmurray 4y ago
> 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.
deleted 4y ago
[deleted]
deleted 4y ago
[deleted]
pjmlp 4y ago
> 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, ...
sacnoradhq 4y ago
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.

by jerf 4y ago

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.
- masklinn 4y ago
  Not sure how that is relevant. The GP asserts (and bemoans) the reverse cause-and-effect.
- pjmlp 4y ago
  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.
  - Nevermark 4y ago
    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?
  - flohofwoe 4y ago
    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.
    - pjmlp 4y ago
      How do you map C statements to AVX512 instructions?
      - flohofwoe 4y ago
        ...by doing the only sensible thing and use intrinsics. Auto-vectorisation is exactly where compiler optimisations stop being useful.

ablob 4y ago

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).

int_19h 4y ago
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.
- masklinn 4y ago
  > 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.
- tsimionescu 4y ago
  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.

flohofwoe 4y ago

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.

deleted 4y ago

[deleted]

brigade 4y ago

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.

mncharity 4y ago
> 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.
- tmzt 4y ago
  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?
  - mncharity 4y ago
    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?

prohisto 4y ago

[flagged]

dmurray 4y ago

> 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.

deleted 4y ago

[deleted]

deleted 4y ago

[deleted]

pjmlp 4y ago

> 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, ...

sacnoradhq 4y ago

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.