Chip designers have noticed this similarity in the past have and attempted to push some of the work done by the CPU back into the compiler. Itanium and the Mill CPU both work(ed) like this I believe.
Mill CPU never existed in silicon, so there are questions to that. But IIRC Ivan said that they didn't do anything that compilers didn't do already for DPSs. He specifically mentioned that they don't want to be like Itanic.
This will never work due to incentive structure, unless the compiler devs are working for the same company that makes the CPU. Otherwise, compiler devs will target a lowest common denominator and call it a day. And even if the compiler devs perfectly support new CPU instructions, compiler users usually want a single binary that can run on as many CPUs as possible, and so will use the lowest common denominator once again. Currently, your CPU will 99% of the time run basic AMD64 instructions, regardless of its capabilities. So Intel and AMD try to make their CPUs really good at running AMD64 code.
> unless the compiler devs are working for the same company that makes the CPU
Every CPU manufacturing company have a compile team.
> This will never work
VLIW processors do work, and for a while now.
This type of architecture performs better for data-intensive workloads, so you don't see them in the general-purpose world.
But if you are talking about Mill, yes it will never work.
VLIW works _really_ well if you have deterministic memory timings, e.g. DSP/risc style architectures, and you're up for writing a complicated compiler.
> But if you are talking about Mill, yes it will never work.
Maybe Mill Computing won't pull it off, but why do you think the approach is bad? It seems sufficiently different from Itanium to not have the exact same problems.
They don't have a "deliver at all costs" philosophy and they are creating a new and different CPU architecture from scratch, a task where even teams oriented at delivering at all costs tend to almost always fail.
The architecture itself looks very good. If it was built in a way similar to RISC-V, it would probably become very influential. (But then, I'm not sure you can create something that innovative by the same procedures RISC-V was created.)
The architecture looks like a dead end compared to other novel architecture like the Reduceron which reached 33% of the performance of a single core 2 duo processor core while running on an FPGA with only 90MHz without using pipelining or out of order execution. The catch is that the execution model of the Reduceron is graph reduction which basically means lambda calculus/lazy functional programming languages.
The Reduceron's raw arithmetic performance isn't better, but it doesn't matter because lazy evaluation is memory intensive, the more memory intensive the algorithm, the better the Reduceron performs, which is very unlike classical C machines like x86 or ARM or RISC-V where memory intensitivity must be avoided at all costs for good performance. Where the Reduceron does a single graph reduction per clock cycle, a C machine has to do it with several sequential instructions so a massive clock rate advantage isn't worth much.
Well, first of all, because it shows no results after +10 years. There is definitely no indication that it will work someday.
And above all because there are too many choices that are too specific, outdated and too exotic. (e.g. the split-stream encoding is way too exotic)
I work in a small company that makes processors, and I know from experience that developing a processor is a very complicated subject, you have to go step by step (Mill does not).
When you come up with a new design/idea, you try to simulate it, test it and implement it. You don't pile up new ideas without getting feedback on them.
And at least the Intel compiler was/is pretty good at producing a single binary that uses whatever features your CPU has available by switching to different code paths depending on the cpuid flags. At least if your CPU is an Intel CPU, it's more conservative with that on AMD CPUs.
It's quite complicated. Sometimes hardware instructions are awkward or redundant enough that compilers ignore them. Or they're broken in hardware and the compiler tries to patch around them. Sometimes there are invariants that are easy for compilers and really annoying for assembly programmers. A given sequence of instructions may execute correctly on multiple (sub)architectures with widely divergent performance behaviour.
The one binary that does minimal to no self modification on boot is popular with users but intrinsically slower. Arm's variable length vector instructions are catering to that.
One binary that is specialised to hardware and expected arguments is the fastest you can do without optimising while the program is starting/running.
However hardware usually changes slower than software. Specifically if a program starts running on a specific x64 chip it's likely to stay on that chip until it finishes running. Linux used to patch itself on boot to pick a faster memcpy (may still do).
It seems obvious that fastest for sufficiently long running processes is to ship a compiler IR, specialise first to the hardware and second to patterns in the data. OpenCL/spir-v have a finaliser premise where you lower to a given GPU just before running on it. Specialising on program data is branded JIT compilation. I don't know of anything doing both yet.
> Otherwise, compiler devs will target a lowest common denominator and call it a day.
Mill's idea for that is that compiler outputs a multi-target binary, which is specialized to the current CPU at install/first-run time, by fixing the size of the belt and other such hardware details.
> "genAsm is a dataflow language, essentially a programmable representation of a single-assignment compiler IR."
Linn (the hifi people, not the drum machine people) made a CPU called "Rekursiv" (because they like odd spelling like that) which had objects and GC implemented in hardware, on a couple of very large custom chips on VMEBus boards. These were horrendously expensive and were to be plugged into a Sun 3 box, making it all quite breathtakingly spendy.
When Sun brought out their SPARC hardware the language they run was ported to that, and ran about four times faster clock-for-clock.
You can gain some measure of the Rekursiv's success from the fact that the only complete machine known to still exist can be found on the bottom of the Forth and Clyde Canal, somewhere around the Possil Road Aqueduct.
I can't imagine the thought process by which a niche Hi-Fi company decides the best way to automate their production system is to custom develop a totally new class of CPU... which is why I am glad there are at least a few people in the world that make the attempt.
(This whole thing also reminds me of the Intel 432... had some similar properties)
An advanced interpreter has many features of a compiler.
For instance there is the kind of simple interpreter that I know how to write off the top of my head which evaluates the nodes of an expression tree which is horribly inefficient.
Then there is something like Python which "compiles" code to bytecode which is then interpreted by a "virtual machine". That kind of system admits very complex optimizations about as far you as can imagine, including compiling some of the bytecode all the way to machine code the way PyPy or the JVM does it.
Note most interpretations of the Intel architectures break complex instructions up into RISC-like "micro-ops", which is a bit like bytecode interpretation.
One of the biggest concerns in a modern CPU is that memory accesses are very slow relative to a CPU cycle so you want to be executing a large number of instructions at a time to hide the latency of memory access. Intel's failed Itanium had the compiler try to explicitly schedule this but it didn't work because the compiler can't know ahead of time (for general purpose code) what is in what level of the cache and what isn't -- and in a worse case scenario this can hang up not only one instruction but many other instructions that depend on the result of that instruction, ether because they really depend on the result or because the CPU gets hung up. The CPU, on the other hand, does know, and can be opportunistic about taking advantage of available parallelism.
Like ARM, there are many implementations of the x86. Intel has all the various "creeks" and "lakes", AMD has various implementations and there have been others like Cyrix.
If there's a serious problem w/ the x86 architecture it's that the instructions are variable length from 1 to 14 bytes so if you wanted to build a decoder that fetches, say, 5 instructions at a time it would have to read 70 bytes. It has to run very quickly, ideally it doesn't consume a lot of power, so it is going to take up a lot of die area and if you want to make it wider still it is a challenge.
Intel and AMD do really well despite this and the long instructions mean you can build all sorts of acceleration into the CPU which can make up for this (some of why the double-pumped AVX512 is effective on AMD's latest is that even when it s getting work down at AVX256 speeds at the core, it is wasting fewer resources dealing with instructions.)
What you do is extract up to N instructions from a block of memory (in this case, 16 bytes). If there are fewer than N instructions, well, you can only issue as many as you have; if there are more than N instructions, well, you can only issue N instructions that cycle. Note that most instructions are only a few bytes length; I don't have hard data on the average instruction length of an x86-64 instruction in practice, but my guess is it's around 3-4 bytes.
The hard part about a variable-length ISA, as I understand it (hardware is not my expertise), is that you have to build essentially a mux that can steer from 16 source places to 5 outputs.
> The hard part about a variable-length ISA, as I understand it (hardware is not my expertise), is that you have to build essentially a mux that can steer from 16 source places to 5 outputs.
It's not just the mux, it's the control signals for the mux. If your first instruction in your 16-byte window is three bytes long, you can't realistically mux bytes 3-15 to the second decoder input, because you don't know that it needs to start decoding at byte 3 until /after/ the first instruction has decoded; so your gate delays would be the sum of the five decoders, plus muxing etc, and we're trying to do this at a single cycle.
The alternative is to have 16 decoders, each decoding what an instruction /would/ be if it started at a given byte. These all complete in parallel, but many of them might produce garbage. So we need to find the first five of these that have non-garbage outputs, and /then/ mux those sixteen possible outputs down to five channels. This is doable (and done), but it's a lot more hardware in both decoders and muxing than you might think at first.
Basically: To decode five instructions per cycle from a fixed-instruction-width stream takes five decoders. To decode up to five instructions per cycle from a variable-instruction-width stream takes number-of-possible-starts decoders and a mess of muxing. There really is a cost here.
The Thumb ISA is left as an exercise for the reader.
It all depends how much you want to get that last bit of performance and what you are willing to pay for it in terms of power, die area, all that.
And of course every part of it has to be balanced. It makes no sense to decode instructions faster than the system downstream can handle it, particularly if you are wasting resources to do so.
The reason why Intel has so many different implementations of x86 is to meet the needs of different market segments.
Yep. And it's worth saying that, contrary to my previous over-simplification, the trade-offs change once you give up on single-cycle instruction decoding. With a longer pipeline, you can do a split into 16 simple, small pre-decoders, that basically just extract the length of the instruction, /then/ mux on the inputs to just five full decoders. It adds a pipeline stage, but it can be lower area for the same sustained performance.
Trade-offs are everywhere. But certainly fixed width instructions, or variable-width-but-trivial-to-determine-length (Thumb before Thumb2, RISC-V compressed) have real advantages.
> The alternative is to have 16 decoders, each decoding what an instruction /would/ be if it started at a given byte. These all complete in parallel, but many of them might produce garbage. So we need to find the first five of these that have non-garbage outputs, and /then/ mux those sixteen possible outputs down to five channels.
I believe reading somewhere that that's pretty much how more or less recent Intel processors do that.
> The alternative is to have 16 decoders, each decoding what an instruction /would/ be if it started at a given byte. These all complete in parallel, but many of them might produce garbage. So we need to find the first five of these that have non-garbage outputs, and /then/ mux those sixteen possible outputs down to five channels. This is doable (and done), but it's a lot more hardware in both decoders and muxing than you might think at first.
Length decoding is a finite state machine, and the transition function of finite state machines is associative, which means you can actually compile them into a reduction tree to do it in parallel.
I don't think the x86 decoder is actually a particularly complex state machine (I haven't attempted to actually build it), so it's probably overall far less complex than most people assume it is.
Very nice explanation! It gets very complex very quickly... And then there's of course also the fact you never know if your last bytes in the Ifetch you get from the cache is a full instruction or not. You'll need to keep that around until the next line arrives which will have the rest of that instruction.
And then add to that the complexity of speculative and out of order execution: you will want to very early decide, i.e. (pre)decode, where branch instructions are, in order to make sure your branch prediction unit has the right inputs in time, to decide where to fetch the next instructions from.
And after all that, on a branch mispredict earlier on (or pipeline flush for another reason), you might need to throw almost all of that expensively decoded instructions away and start fetching from elsewhere...
Surprisingly, there is not that much distance between tree-walking evaluator and (stack-oriented-)bytecode emitter: you just have slightly different accumulator (integer vs. list of bytecodes) with slightly different operations on it (arithmetics vs. appending line "add/sub/etc." to the end of list).
Throw in some more of context tracking (e.g. "did the left-hand side turn out to be a constant" or "are we in the (X+Y)+Z situation?" etc.) and you can start doing optimization such as constant folding and expression-tree rebalancing.
Then you can start emitting chunks of assembly instead of bytecode ("iconst X" turns into "push X", "add" turns into "pop eax; pop ecx; add eax, ecx; push eax" etc). Again, with enough context tracking (for example, what's in what registers), you can emit much less stupid assembly.
To help me keep the spellings straight, I pronounce them as "pie pea eye" and "pie pie" respectively. That's also the PyPI project's preferred pronunciation.
Compilers translate a text to (typically) a lower level, optimized, which is stored for later execution. The length of time the output is stored is arbitrary.
Interpreters operate sequentially in time.
They take the compiler output, combine it with parameters from the world outside the cpu, and sequentially produce results that affect the physical world in some way, even if it’s just writing a result to memory.
The interpreter may use the compiled text many times.
At some point, it’s interpreters all the way down, at first in object code, then microcode. The ALU itself is a sequential hardware interpreter.
That simple interpreter is inefficient, sort-of. It's 10X slower than compiling to code. It's 10X faster than ordinary interpreters. A compromise solution in some instances.
> An advanced interpreter has many features of a compiler.
There's a historical line from a CS great (I am not sure who) that goes something like:
When you first start writing software, you will not understand the difference between an interpreter and a compiler. After you've been writing software for a certain amount of time, you will never confuse an interpreter and a compiler. But after you've been writing software for a bit longer than that, you will again not understand what the difference between them really is.
ML, Lisp, and Logic derived languages are all relatively easy.
Hence why on my degree their were forbidden for compiler assignments, even though we had a strong ML and Prolog set of lectures in programming languages I and II, LP II.
We were supposed to earn the compiler design assignment, from the professor´s point of view.
Although the year I took it, it was about the time Java was being introduced, so doing it with Java, SableCC while not as easy wasn't that harder, specially following alongside the Tiger book.
Wow, that is awful. For compiler writing, you should use a good language for that purpose, so that the hard parts of the program are the actual compilation algorithms, not debugging segfaults in a graph structure or whatever, or wasting time on electricity-and-running-water infrastructural code whose existence should be taken for granted.
There is plenty of "cred" to be earned without that; you can still be pulling your hair out debugging a compiler written in Lisp, find years-old bugs in it and so on.
I don't know anything else about your ex-prof other than what you have in the comment, but based on that, my Ouija board's planchette is edging toward "insufferable asshole".
Mental note: be sure not to be that guy if you ever turn professor.
This is not terribly hard, though,—Forth implementations have long explored[1] the road from emiting a list of VM instructions (“token threading”) to emitting a list of VM instruction implementation entry points (“direct threading”, although “indirect threading” arguably fits this as well) to emitting a stream of call instructions targeting said entry points (“subroutine threading”) to copying the implementation bodies into the stream (“inline threading”).
With sufficient dedication, you can even cut out the bodies from the binary the compiler of your high-level implementation language produced, to piggyback on its target support. Gforth[2] among others does this in the land of Forth, but the more well-known implementation is perhaps the dyngen code generator[3] used in Qemu before the switch to TCG in version 0.10.
Generating machine code isn’t difficult, and neither is modifying a (low-level) bytecode generator to do it[4]. Generaring good machine code is difficult.
From the software side, what is it exactly that makes it so difficult to write a higher-level language that must be optimized, instead of a language that already exposes the optimizations in a friendly way?
("higher-level language" meaning c, not python or something)
Well the low-level implementations differ from cpu-to-cpu. Even between Itanium releases the width changes. They don't want to get bound to a single implementation as techniques improve and new approaches are found. Otherwise, each time they discover something new they'd have to release a new ISA and backwards compatibility was the most commercially influential aspect of a chip. Now, it used to be that super-computer were made with custom chips, with custom ISAs, but the advantage of mass consumer parts is too high. So in general the decoupling of implementation and programming language allows for enough wiggle room to allow independent evolution without being rigidly coupled.
Not sure what is exactly your thought, since the optimizations you quote don't really takes advantage of any exposed optimization feature of the language.
Are your asking why we could not expose optimization feature (e.g. branch hint to replace branch-prediction) in the programming language ?
Are you asking if it's difficult for a compiler to optimize some type of high-level languages ?
Since "higher-level" language is C in your question, what the "language that already exposes the optimizations in a friendly way" ? Are you thinking the CPU µop as a language ?
The literal answer is that compilers are really easy to write when the source and destination language are the same and you don't want any optimisation. E.g. write the x64 machine code out as raw bytes and cat is good enough to turn it into x64 machine code.
Difficulty increases as the source and target languages become less similar, as more ambitious performance optimisations are attempted, as more comprehensive type/lint/warning style systems are implemented and as performance constraints on the compiler itself tighten.
So a compiler that takes imprecise scribblings, spots errors in them, and emits asymptotically perfect machine code for heterogenous distributed systems in real time is quite dramatically more complicated than cat.
same...I feel weird because I learned AT&T syntax since day 1. And even with that, I think Intel syntax is just another way of writing, period. No hard feeling at all. Don't quite understand why the author is so...pissed.
If you remember the Transmeta chips from the early 2000s they literally were compilers. Took in x86 binaries but JITed them to an internal RISC instruction set.
I can't recall the quote or source, but it went something like: A CPU is a compiler that transforms a serial instruction stream to a wide (acyclic) graph of data dependencies. This refers to concepts like out-of-order execution, superscalar processing, functional unit scheduling, and register renaming.
The merging of both compiler (cpu and software) is the main reason of the success of Nvidia.
Make the chip simpler and more parallel (way more cores)
Make the compiler smarter to better use the capabilities of the hardware.
Watching Jim Keller interview made me realise how much transistors are wasted because the cpu is trying to predict what the code is going to do.
There is an insane amount of complexity in chips trying to make single threaded code fast when what need the most cpu time in our code is usually parallels problem.
Maybe Triton will break that paradigm and will allow diverse parallels hardware to emerge and be used effectively.
But don't underestimate how much 'middleware' there is in Cuda/CuDNN, NCCL etc. A lot of it is not in the compiler, but much more in hand crafted, carefully optimised libraries.
As an example: there are so many low level ways to run a conv2D kernel on a SIMT machine, but CuDNN will pick the best option for you based on the card you have, and the tensor sizes you are using.
The failure of the Itanium highlights the danger of tilting too much complexity into the software / compiler space. It was very difficult to make a compiler which could generate parallelizable machine code and that lead to very disappointing performance for most software.
I'm not sure where in that article the re-write-microcode feature lies? That is, modern CPUs can write microcode for instruction sequences, not just single opcodes. Which is almost exactly what a compiler is, if you substitute 'op code sequence' for 'source code sequence'.
97 comments
[ 3.3 ms ] story [ 176 ms ] threadhttps://www.cs.princeton.edu/~appel/modern/
Every CPU manufacturing company have a compile team.
> This will never work
VLIW processors do work, and for a while now. This type of architecture performs better for data-intensive workloads, so you don't see them in the general-purpose world.
But if you are talking about Mill, yes it will never work.
Maybe Mill Computing won't pull it off, but why do you think the approach is bad? It seems sufficiently different from Itanium to not have the exact same problems.
The architecture itself looks very good. If it was built in a way similar to RISC-V, it would probably become very influential. (But then, I'm not sure you can create something that innovative by the same procedures RISC-V was created.)
And above all because there are too many choices that are too specific, outdated and too exotic. (e.g. the split-stream encoding is way too exotic)
I work in a small company that makes processors, and I know from experience that developing a processor is a very complicated subject, you have to go step by step (Mill does not). When you come up with a new design/idea, you try to simulate it, test it and implement it. You don't pile up new ideas without getting feedback on them.
Sure, but that doesn't help when all the binaries are compiled for AMD64 anyway.
Assuming you have access to the source code of course.
The one binary that does minimal to no self modification on boot is popular with users but intrinsically slower. Arm's variable length vector instructions are catering to that.
One binary that is specialised to hardware and expected arguments is the fastest you can do without optimising while the program is starting/running.
However hardware usually changes slower than software. Specifically if a program starts running on a specific x64 chip it's likely to stay on that chip until it finishes running. Linux used to patch itself on boot to pick a faster memcpy (may still do).
It seems obvious that fastest for sufficiently long running processes is to ship a compiler IR, specialise first to the hardware and second to patterns in the data. OpenCL/spir-v have a finaliser premise where you lower to a given GPU just before running on it. Specialising on program data is branded JIT compilation. I don't know of anything doing both yet.
Mill's idea for that is that compiler outputs a multi-target binary, which is specialized to the current CPU at install/first-run time, by fixing the size of the belt and other such hardware details.
> "genAsm is a dataflow language, essentially a programmable representation of a single-assignment compiler IR."
https://millcomputing.com/docs/compiler/
https://millcomputing.com/topic/on-the-lack-of-progress-repo...
and david bacon (et al) - https://files.catbox.moe/bipg79.pdf
When Sun brought out their SPARC hardware the language they run was ported to that, and ran about four times faster clock-for-clock.
You can gain some measure of the Rekursiv's success from the fact that the only complete machine known to still exist can be found on the bottom of the Forth and Clyde Canal, somewhere around the Possil Road Aqueduct.
https://www.slideshare.net/sebrose/rekursiv
The founders parents fled from Austria during Nazi times. In Austria we speak German. The English word "recursive" is "rekursiv" in German.
Fascinating guy.
(This whole thing also reminds me of the Intel 432... had some similar properties)
For instance there is the kind of simple interpreter that I know how to write off the top of my head which evaluates the nodes of an expression tree which is horribly inefficient.
Then there is something like Python which "compiles" code to bytecode which is then interpreted by a "virtual machine". That kind of system admits very complex optimizations about as far you as can imagine, including compiling some of the bytecode all the way to machine code the way PyPy or the JVM does it.
Note most interpretations of the Intel architectures break complex instructions up into RISC-like "micro-ops", which is a bit like bytecode interpretation.
One of the biggest concerns in a modern CPU is that memory accesses are very slow relative to a CPU cycle so you want to be executing a large number of instructions at a time to hide the latency of memory access. Intel's failed Itanium had the compiler try to explicitly schedule this but it didn't work because the compiler can't know ahead of time (for general purpose code) what is in what level of the cache and what isn't -- and in a worse case scenario this can hang up not only one instruction but many other instructions that depend on the result of that instruction, ether because they really depend on the result or because the CPU gets hung up. The CPU, on the other hand, does know, and can be opportunistic about taking advantage of available parallelism.
Isn't Apple M1 much wider than x86?
If there's a serious problem w/ the x86 architecture it's that the instructions are variable length from 1 to 14 bytes so if you wanted to build a decoder that fetches, say, 5 instructions at a time it would have to read 70 bytes. It has to run very quickly, ideally it doesn't consume a lot of power, so it is going to take up a lot of die area and if you want to make it wider still it is a challenge.
Intel and AMD do really well despite this and the long instructions mean you can build all sorts of acceleration into the CPU which can make up for this (some of why the double-pumped AVX512 is effective on AMD's latest is that even when it s getting work down at AVX256 speeds at the core, it is wasting fewer resources dealing with instructions.)
No you don't. Look at a block diagram of (say) Skylake: https://en.wikichip.org/wiki/intel/microarchitectures/skylak...
What you do is extract up to N instructions from a block of memory (in this case, 16 bytes). If there are fewer than N instructions, well, you can only issue as many as you have; if there are more than N instructions, well, you can only issue N instructions that cycle. Note that most instructions are only a few bytes length; I don't have hard data on the average instruction length of an x86-64 instruction in practice, but my guess is it's around 3-4 bytes.
The hard part about a variable-length ISA, as I understand it (hardware is not my expertise), is that you have to build essentially a mux that can steer from 16 source places to 5 outputs.
It's not just the mux, it's the control signals for the mux. If your first instruction in your 16-byte window is three bytes long, you can't realistically mux bytes 3-15 to the second decoder input, because you don't know that it needs to start decoding at byte 3 until /after/ the first instruction has decoded; so your gate delays would be the sum of the five decoders, plus muxing etc, and we're trying to do this at a single cycle.
The alternative is to have 16 decoders, each decoding what an instruction /would/ be if it started at a given byte. These all complete in parallel, but many of them might produce garbage. So we need to find the first five of these that have non-garbage outputs, and /then/ mux those sixteen possible outputs down to five channels. This is doable (and done), but it's a lot more hardware in both decoders and muxing than you might think at first.
Basically: To decode five instructions per cycle from a fixed-instruction-width stream takes five decoders. To decode up to five instructions per cycle from a variable-instruction-width stream takes number-of-possible-starts decoders and a mess of muxing. There really is a cost here.
The Thumb ISA is left as an exercise for the reader.
And of course every part of it has to be balanced. It makes no sense to decode instructions faster than the system downstream can handle it, particularly if you are wasting resources to do so.
The reason why Intel has so many different implementations of x86 is to meet the needs of different market segments.
Trade-offs are everywhere. But certainly fixed width instructions, or variable-width-but-trivial-to-determine-length (Thumb before Thumb2, RISC-V compressed) have real advantages.
I believe reading somewhere that that's pretty much how more or less recent Intel processors do that.
Well that just sounds hideously complex.
I don't think the x86 decoder is actually a particularly complex state machine (I haven't attempted to actually build it), so it's probably overall far less complex than most people assume it is.
And then add to that the complexity of speculative and out of order execution: you will want to very early decide, i.e. (pre)decode, where branch instructions are, in order to make sure your branch prediction unit has the right inputs in time, to decide where to fetch the next instructions from.
And after all that, on a branch mispredict earlier on (or pipeline flush for another reason), you might need to throw almost all of that expensively decoded instructions away and start fetching from elsewhere...
CPUs are fun :)
Section 2.2.1, Intel® 64 and IA-32 Architectures Software Developer’s Manual
Also, long instructions are infrequent, 96%+ are 7 bytes or less. That's static and dynamic is higher.
Throw in some more of context tracking (e.g. "did the left-hand side turn out to be a constant" or "are we in the (X+Y)+Z situation?" etc.) and you can start doing optimization such as constant folding and expression-tree rebalancing.
Then you can start emitting chunks of assembly instead of bytecode ("iconst X" turns into "push X", "add" turns into "pop eax; pop ecx; add eax, ecx; push eax" etc). Again, with enough context tracking (for example, what's in what registers), you can emit much less stupid assembly.
PyPI is the Python Package Index. https://en.wikipedia.org/wiki/Python_Package_Index
PyPy is the Python implementation with JIT. https://en.wikipedia.org/wiki/PyPy
(Yes, it is extremely confusing that there are two Python projects with homophonous, nearly-identical names.)
There's more than one way to name it! No, that's Raku.
https://pypi.org/help/#pronunciation
Interpreters operate sequentially in time.
They take the compiler output, combine it with parameters from the world outside the cpu, and sequentially produce results that affect the physical world in some way, even if it’s just writing a result to memory.
The interpreter may use the compiled text many times.
At some point, it’s interpreters all the way down, at first in object code, then microcode. The ALU itself is a sequential hardware interpreter.
There's a historical line from a CS great (I am not sure who) that goes something like:
When you first start writing software, you will not understand the difference between an interpreter and a compiler. After you've been writing software for a certain amount of time, you will never confuse an interpreter and a compiler. But after you've been writing software for a bit longer than that, you will again not understand what the difference between them really is.
I always thought of an interpreter as a translator, while a compiler was a translator and optimizer.
So my question - can LLMs do this? They are really good at contextualizing and generating code - so why not build a compiler that is basically an LLM?
I do wonder how this CPU code looks like
ML, Lisp, and Logic derived languages are all relatively easy.
Hence why on my degree their were forbidden for compiler assignments, even though we had a strong ML and Prolog set of lectures in programming languages I and II, LP II.
We were supposed to earn the compiler design assignment, from the professor´s point of view.
Although the year I took it, it was about the time Java was being introduced, so doing it with Java, SableCC while not as easy wasn't that harder, specially following alongside the Tiger book.
There is plenty of "cred" to be earned without that; you can still be pulling your hair out debugging a compiler written in Lisp, find years-old bugs in it and so on.
I don't know anything else about your ex-prof other than what you have in the comment, but based on that, my Ouija board's planchette is edging toward "insufferable asshole".
Mental note: be sure not to be that guy if you ever turn professor.
Our Physics III was even worse, it was one of those that was proud of hard it was to go through his final semester exam.
Thankfully they tend to be a minority, I also met several that became an a good example of how teaching should be like.
With sufficient dedication, you can even cut out the bodies from the binary the compiler of your high-level implementation language produced, to piggyback on its target support. Gforth[2] among others does this in the land of Forth, but the more well-known implementation is perhaps the dyngen code generator[3] used in Qemu before the switch to TCG in version 0.10.
Generating machine code isn’t difficult, and neither is modifying a (low-level) bytecode generator to do it[4]. Generaring good machine code is difficult.
[1] http://www.bradrodriguez.com/papers/moving1.htm
[2] https://www.complang.tuwien.ac.at/forth/gforth/Docs-html/Dyn...
[3] https://gitlab.com/qemu-project/qemu/-/blob/v0.9.1/qemu-tech..., rendered as https://web.archive.org/web/20081120011949if_/http://bellard...
[4] https://github.com/EarlGray/c4/blob/master/JIT.md
> Peephole optimisations, idioms | Idioms
From the software side, what is it exactly that makes it so difficult to write a higher-level language that must be optimized, instead of a language that already exposes the optimizations in a friendly way?
("higher-level language" meaning c, not python or something)
Are your asking why we could not expose optimization feature (e.g. branch hint to replace branch-prediction) in the programming language ?
Are you asking if it's difficult for a compiler to optimize some type of high-level languages ?
Since "higher-level" language is C in your question, what the "language that already exposes the optimizations in a friendly way" ? Are you thinking the CPU µop as a language ?
Difficulty increases as the source and target languages become less similar, as more ambitious performance optimisations are attempted, as more comprehensive type/lint/warning style systems are implemented and as performance constraints on the compiler itself tighten.
So a compiler that takes imprecise scribblings, spots errors in them, and emits asymptotically perfect machine code for heterogenous distributed systems in real time is quite dramatically more complicated than cat.
"Why no one should use AT&T syntax ever, for any reason, under any circumstances"
https://news.ycombinator.com/item?id=26122532
Make the chip simpler and more parallel (way more cores) Make the compiler smarter to better use the capabilities of the hardware.
Watching Jim Keller interview made me realise how much transistors are wasted because the cpu is trying to predict what the code is going to do.
There is an insane amount of complexity in chips trying to make single threaded code fast when what need the most cpu time in our code is usually parallels problem.
Maybe Triton will break that paradigm and will allow diverse parallels hardware to emerge and be used effectively.
As an example: there are so many low level ways to run a conv2D kernel on a SIMT machine, but CuDNN will pick the best option for you based on the card you have, and the tensor sizes you are using.
If x86 was Intel only, Itanium would have been eventually pushed everywhere no matter what.
A nice introduction to some similarities but the details and constraints are quite different.
Transmeta however...