6 ms·

So. Programs that use Garbage Collection tend to be slow. Cause: Hardware don't like it. Solution: fix the hardware? Seriously, I'm afraid we're stuck in a

So. Programs that use Garbage Collection tend to be slow. Cause: Hardware don't like it. Solution: fix the hardware? Seriously, I'm afraid we're stuck in a local optimum here. It is as if machines are optimized for the two dominant C/C++ compilers out there, and we have then to optimize our program against that, closing the loop. Shouldn't compilers and hardware be designed hand in hand?

tlholaday 16y ago
Intel makes both processors and compilers.
- marshray 16y ago
  Yes, but their compiler doesn't have much market share, certainly not enough that it can drive the chip design. They do, of course, make a lot of popular chips, but even there they can't dictate the architecture single-handedly. The vast majority of software seems to be built with something other than Intel compilers and compiled for generic 32-bit x86/i386/ia32 and/or x64/x86_64/amd64 platforms. (whatever you want to call 'em)
rgoddard 16y ago
The design of the memory hierarchy is dictated by the fact that in general the faster your memory is, the more it costs. As a way to balance this you have a hierarchy of memory, with the fastest closest to the cpu and also in the smallest quantity. So the compilers are optimized for the hardware, not the other way around.
ciupicri 16y ago
There were a couple of machines optimized for LISP some years ago, but guess what? They were beaten by ordinary machines.
- jimwise 16y ago
  Sure -- but they were beaten by ordinary machines because the combination of better ordinary machines and better techniques for running lisp on ordinary machines improved to the point where lisp machines weren't better at running lisp. A lot of this is that a few small low-budget research groups were building lisp machines at a time when the big players suddenly started pouring all their efforts into developing commodity single-user graphical workstations. But it's also true that developments in GC technology -- developments which Torvalds seems unaware of in this 2002 post, even though they were 15-20 years old by then -- made GC really fast even on hardware not designed with GC in mind.
vog 16y ago
I think you're referring to the following paragraph: One fundamental fact on modern hardware is that data cache locality is good, and not being in the cache sucks. This is not likely to change. However, this did not happen to please the "two dominant C/C++ compilers". The reason is much more fundamental: One of the most expensive parts of the hardware is memory, and fast memory is a lot more expensive to produce than slower memory. So we have the choice between using the same (and thus slow) memory throughout the system, or combining different kinds of memory so that at software has at least the _chance_ to run faster. This is a fundamental issue, and the only thing you can do is trying to find the optimal share for each kind of memory. But no matter how well you choose: software will only be able to exploit this if it is designed for locality. If you can fix that (i. e. if you can find a cheap way to produce gigabytes of fast memory that makes chaches obsolete) the current compilers won't stop you from exploiting it: The code that is optimized for locality will still run as fast, and the code that can't be optimized for locality will run orders of magnitudes faster. So we aren't in a local optimum at all. You can still optimize further "just" by producing faster and cheaper hardware.
- kragen 16y ago
  One of the most expensive parts of the hardware is memory, and fast memory is a lot more expensive to produce than slower memory. So we have the choice between using the same (and thus slow) memory throughout the system, or combining different kinds of memory so that at software has at least the chance to run faster. This is a fundamental issue, and the only thing you can do is trying to find the optimal share for each kind of memory. Although all modern high-performance (edit: I mean non-embedded-microcontroller) computers work this way, it's not the only possible way. The Tera MTA takes a different, cacheless approach. First, the problem with modern RAM in desktop machines is not that it sucks at bandwidth. You can get your bandwidth arbitrarily high by multibanking. Multibanking requires more buses or point-to-point links, but that's a tolerable cost. The problem with modern RAM is that it sucks at latency, compared to what the CPU would like. Well, what do you do about latency? You make your requests earlier, and make sure you have other things to do in the meantime, when they get back. The Tera did this by having 128 sets of registers – 128 hardware threads — and switching to the next thread on every cycle. That means that, if all the thread slots were full, every thread only executed an instruction every 128 cycles, which is plenty of time to hide the latency of a slow memory fetch, as long as the memory bandwidth was adequate. So basically every thread gets to pretend that it's running on a machine with zero-latency RAM — memory that's as fast as the registers. And pointer-chasing becomes as fast as looping over an array. There are some other advantages to this design. Pipelining logic is very simple, because unless your pipeline gets insanely deep, you never have two instructions in the pipeline from the same thread, so you don't have register hazards. (Cache is still beneficial in such a design, since it reduces the bandwidth that the links to main memory need to support. But the Tera didn't use it.) I don't really understand why the Tera MTA failed in the market, and I suspect the problems were commercial rather than technical — customers had to take a big risk by porting their software to an unproven HPC platform, a platform whose performance characteristics were completely unlike anything else in the market (and unlike anything you can buy today). So customer uptake was insufficient to provide the cash flow needed to keep updating the design to keep up with Intel and AMD. The technical reason such a design might fail would be if the silicon resources needed to support an entirely independent core were comparable to the silicon resources needed to support a hardware thread. Consider the GreenArrays GA144 chip: 144 independent cores, each with a tiny amount of independent RAM, on the same chip. Such a chip will be at least as fast as a chip with 144 independent register sets, but a single execution pipeline — in the worst case, it's bottlenecked on getting data out of RAM, and only one of its cores is usable, making it just as fast, while in the best case, it runs 144 times as fast. So a chip with 144 register sets needs to be cheaper — i.e. smaller — than the GA144. (Well, or easier to program, but presumably you can use more mainstream multicore chips to prove the example instead.)
Ygor 16y ago
Not really directly connected, but in embedded systems you can actually see a lot of hardware software codesign approaches. There is an approach called NISC [1] (No Instruction Set Computer), where the instruction set is completely removed and the compiler generates control words directly for the architecture (which can also be designed from scratch and optimized). [1] http://en.wikipedia.org/wiki/NISC http://en.wikipedia.org/wiki/NISC
Jach 16y ago
You might enjoy reading this: http://www.thocp.net/biographies/papers/backus_turingaward_lecture.pdf http://www.thocp.net/biographies/papers/backus_turingaward_l... (I've been casually trying to implement an FFP Machine on an FPGA.)

tlholaday 16y ago

Intel makes both processors and compilers.

marshray 16y ago
Yes, but their compiler doesn't have much market share, certainly not enough that it can drive the chip design. They do, of course, make a lot of popular chips, but even there they can't dictate the architecture single-handedly. The vast majority of software seems to be built with something other than Intel compilers and compiled for generic 32-bit x86/i386/ia32 and/or x64/x86_64/amd64 platforms. (whatever you want to call 'em)

rgoddard 16y ago

The design of the memory hierarchy is dictated by the fact that in general the faster your memory is, the more it costs. As a way to balance this you have a hierarchy of memory, with the fastest closest to the cpu and also in the smallest quantity. So the compilers are optimized for the hardware, not the other way around.

ciupicri 16y ago

There were a couple of machines optimized for LISP some years ago, but guess what? They were beaten by ordinary machines.

jimwise 16y ago
Sure -- but they were beaten by ordinary machines because the combination of better ordinary machines and better techniques for running lisp on ordinary machines improved to the point where lisp machines weren't better at running lisp. A lot of this is that a few small low-budget research groups were building lisp machines at a time when the big players suddenly started pouring all their efforts into developing commodity single-user graphical workstations. But it's also true that developments in GC technology -- developments which Torvalds seems unaware of in this 2002 post, even though they were 15-20 years old by then -- made GC really fast even on hardware not designed with GC in mind.

vog 16y ago

I think you're referring to the following paragraph: One fundamental fact on modern hardware is that data cache locality is good, and not being in the cache sucks. This is not likely to change. However, this did not happen to please the "two dominant C/C++ compilers". The reason is much more fundamental: One of the most expensive parts of the hardware is memory, and fast memory is a lot more expensive to produce than slower memory. So we have the choice between using the same (and thus slow) memory throughout the system, or combining different kinds of memory so that at software has at least the _chance_ to run faster. This is a fundamental issue, and the only thing you can do is trying to find the optimal share for each kind of memory. But no matter how well you choose: software will only be able to exploit this if it is designed for locality. If you can fix that (i. e. if you can find a cheap way to produce gigabytes of fast memory that makes chaches obsolete) the current compilers won't stop you from exploiting it: The code that is optimized for locality will still run as fast, and the code that can't be optimized for locality will run orders of magnitudes faster. So we aren't in a local optimum at all. You can still optimize further "just" by producing faster and cheaper hardware.

kragen 16y ago
One of the most expensive parts of the hardware is memory, and fast memory is a lot more expensive to produce than slower memory. So we have the choice between using the same (and thus slow) memory throughout the system, or combining different kinds of memory so that at software has at least the chance to run faster. This is a fundamental issue, and the only thing you can do is trying to find the optimal share for each kind of memory. Although all modern high-performance (edit: I mean non-embedded-microcontroller) computers work this way, it's not the only possible way. The Tera MTA takes a different, cacheless approach. First, the problem with modern RAM in desktop machines is not that it sucks at bandwidth. You can get your bandwidth arbitrarily high by multibanking. Multibanking requires more buses or point-to-point links, but that's a tolerable cost. The problem with modern RAM is that it sucks at latency, compared to what the CPU would like. Well, what do you do about latency? You make your requests earlier, and make sure you have other things to do in the meantime, when they get back. The Tera did this by having 128 sets of registers – 128 hardware threads — and switching to the next thread on every cycle. That means that, if all the thread slots were full, every thread only executed an instruction every 128 cycles, which is plenty of time to hide the latency of a slow memory fetch, as long as the memory bandwidth was adequate. So basically every thread gets to pretend that it's running on a machine with zero-latency RAM — memory that's as fast as the registers. And pointer-chasing becomes as fast as looping over an array. There are some other advantages to this design. Pipelining logic is very simple, because unless your pipeline gets insanely deep, you never have two instructions in the pipeline from the same thread, so you don't have register hazards. (Cache is still beneficial in such a design, since it reduces the bandwidth that the links to main memory need to support. But the Tera didn't use it.) I don't really understand why the Tera MTA failed in the market, and I suspect the problems were commercial rather than technical — customers had to take a big risk by porting their software to an unproven HPC platform, a platform whose performance characteristics were completely unlike anything else in the market (and unlike anything you can buy today). So customer uptake was insufficient to provide the cash flow needed to keep updating the design to keep up with Intel and AMD. The technical reason such a design might fail would be if the silicon resources needed to support an entirely independent core were comparable to the silicon resources needed to support a hardware thread. Consider the GreenArrays GA144 chip: 144 independent cores, each with a tiny amount of independent RAM, on the same chip. Such a chip will be at least as fast as a chip with 144 independent register sets, but a single execution pipeline — in the worst case, it's bottlenecked on getting data out of RAM, and only one of its cores is usable, making it just as fast, while in the best case, it runs 144 times as fast. So a chip with 144 register sets needs to be cheaper — i.e. smaller — than the GA144. (Well, or easier to program, but presumably you can use more mainstream multicore chips to prove the example instead.)

Ygor 16y ago

Not really directly connected, but in embedded systems you can actually see a lot of hardware software codesign approaches. There is an approach called NISC [1] (No Instruction Set Computer), where the instruction set is completely removed and the compiler generates control words directly for the architecture (which can also be designed from scratch and optimized). [1] http://en.wikipedia.org/wiki/NISC http://en.wikipedia.org/wiki/NISC

Jach 16y ago

You might enjoy reading this: http://www.thocp.net/biographies/papers/backus_turingaward_lecture.pdf http://www.thocp.net/biographies/papers/backus_turingaward_l... (I've been casually trying to implement an FFP Machine on an FPGA.)