5 ms·

Hard-Coding Bottom-Up Code Generation Tables to Save Time and Space (1991) [pdf]

56 points by tjalfi 6y ago

nsajko 6y ago
For some reason Chromium 81 is not able to handle this PDF. Works fine on MuPDF, though. Could somebody in the know please say if this BURS stuff is used in, e.g., GCC or Clang or LLVM? Or maybe something else that might be familiar?
- irogers 6y ago
  The issue with BURS is that lookup tables can be 10s to 100s of MB. Most code generators will use dynamic programming, but hybrids have been considered: https://dl.acm.org/doi/10.1145/1133255.1133988 https://dl.acm.org/doi/10.1145/1133255.1133988 (Fast and flexible instruction selection with on-demand tree-parsing automata)
- namibj 6y ago
  I expected the typical kerning/typesetting issues. I want to note that it straight-up crashes Chromium's PDF reader.
  - jfk13 6y ago
    Interesting... Chrome on macOS seems fine with it here.
reitzensteinm 6y ago
It's amazing how much cool stuff there is in old papers. I forget the details, but I once came up with a technique and was quite proud. A few months later I stumbled across a paper written in 1986, the year of my birth, that described everything I'd thought of and a few things I hadn't. Someone had my idea before I was born, and thought through the implications better than I did. Doesn't get much more humbling than that...
- ryan-allen 6y ago
  You still came up with it independently, and that's something. What is interesting is how someone in 1986 was thinking about the same problem and came to a similar conclusion. I used to think my ideas were unique, but then I realised that we're all absorbing similar information, and the likelihood of an idea being 100% unique is rare. But if you thought it up and someone somewhere else had a similar idea, you still thought it up on your own.
  - dspillett 6y ago
    > you still thought it up on your own Back in the very early 2000s I had an idea for efficient backups that was essentially rsync, while tinkering with the thought I hit a block and started looking around for implementations of, or papers about, rolling checksums and such, and found rsync. I wasn't put out that my idea wasn't original - I was glad twofold because not only had someone done it better already (so I could just use it for the task as hand), but it at least confirmed that my thinking was very much on the right track.
- throwaway_pdp09 6y ago
  People are very, very inventive and smart people were working with computers since they were invented. I'd say there were probably a higher proportion of smart people working with them then than now because they were so rare and expensive (although that may be survivor bias in that the less good people fade from history). Also there seemed to be a higher number of mathematicians involved in computers back then. One thing I've learnt is that principles matter more than code. Not deep I know, but take a look at the market...
  - no-s 6y ago
    >>smart people were working with computers since they were invented Smart people were working with computers before they were invented. Consider the Difference engine, or the Antikythera mechanism, Analog computers, and efforts to organize the production of results for tables used in calculation, or engineering. "Computer" was once a title for a person, too...
alexdowad 6y ago
Looks fascinating. I wish that in the first section, they would have shown which instructions (for a sample architecture) might have been generated for each application of the tree rewrite rules. It looks like the reader was expected to understand that as a prerequisite. It seems the authors' interest was more on how using their code generation tables could speed up the application of those tree rewrite rules.
- emmanueloga_ 6y ago
  It just blows my mind that an "Artifact Evaluation" process wasn't proposed until so recently [1]. "A paper consists of a constellation of artifacts that extend beyond the document itself: software, proofs, models, test suites, benchmarks, and so on. In some cases, the quality of these artifacts is as important as that of the document itself, yet our conferences offer no formal means to submit and evaluate anything but the paper." 1: https://www.artifact-eval.org/about.html https://www.artifact-eval.org/about.html
i_don_t_know 6y ago
Also highly recommended is „Engineering a simple, efficient code-generator generator“ (1992) by Fraser, Hansen and Proebsting. https://dl.acm.org/doi/pdf/10.1145/151640.151642 https://dl.acm.org/doi/pdf/10.1145/151640.151642
emmanueloga_ 6y ago
Describes an efficient way implementation of "Code generators based on bottom-up rewrite systems (BURS) automatically generated from machine description grammars". There's a short Wikipedia page for BURS [1]: "BURS (bottom-up rewrite system) theory tackles the problem of taking a complex expression tree or intermediate language term and finding a good translation to machine code for a particular architecture. Implementations of BURS often employ dynamic programming to solve this problem." 1: https://en.wikipedia.org/wiki/BURS https://en.wikipedia.org/wiki/BURS

56 points by tjalfi 6y ago

For some reason Chromium 81 is not able to handle this PDF. Works fine on MuPDF, though. Could somebody in the know please say if this BURS stuff is used in, e.g., GCC or Clang or LLVM? Or maybe something else that might be familiar?

irogers 6y ago
The issue with BURS is that lookup tables can be 10s to 100s of MB. Most code generators will use dynamic programming, but hybrids have been considered: https://dl.acm.org/doi/10.1145/1133255.1133988 https://dl.acm.org/doi/10.1145/1133255.1133988 (Fast and flexible instruction selection with on-demand tree-parsing automata)
namibj 6y ago
I expected the typical kerning/typesetting issues. I want to note that it straight-up crashes Chromium's PDF reader.
- jfk13 6y ago
  Interesting... Chrome on macOS seems fine with it here.

reitzensteinm 6y ago

It's amazing how much cool stuff there is in old papers. I forget the details, but I once came up with a technique and was quite proud. A few months later I stumbled across a paper written in 1986, the year of my birth, that described everything I'd thought of and a few things I hadn't. Someone had my idea before I was born, and thought through the implications better than I did. Doesn't get much more humbling than that...

ryan-allen 6y ago
You still came up with it independently, and that's something. What is interesting is how someone in 1986 was thinking about the same problem and came to a similar conclusion. I used to think my ideas were unique, but then I realised that we're all absorbing similar information, and the likelihood of an idea being 100% unique is rare. But if you thought it up and someone somewhere else had a similar idea, you still thought it up on your own.
- dspillett 6y ago
  > you still thought it up on your own Back in the very early 2000s I had an idea for efficient backups that was essentially rsync, while tinkering with the thought I hit a block and started looking around for implementations of, or papers about, rolling checksums and such, and found rsync. I wasn't put out that my idea wasn't original - I was glad twofold because not only had someone done it better already (so I could just use it for the task as hand), but it at least confirmed that my thinking was very much on the right track.
throwaway_pdp09 6y ago
People are very, very inventive and smart people were working with computers since they were invented. I'd say there were probably a higher proportion of smart people working with them then than now because they were so rare and expensive (although that may be survivor bias in that the less good people fade from history). Also there seemed to be a higher number of mathematicians involved in computers back then. One thing I've learnt is that principles matter more than code. Not deep I know, but take a look at the market...
- no-s 6y ago
  >>smart people were working with computers since they were invented Smart people were working with computers before they were invented. Consider the Difference engine, or the Antikythera mechanism, Analog computers, and efforts to organize the production of results for tables used in calculation, or engineering. "Computer" was once a title for a person, too...

alexdowad 6y ago

Looks fascinating. I wish that in the first section, they would have shown which instructions (for a sample architecture) might have been generated for each application of the tree rewrite rules. It looks like the reader was expected to understand that as a prerequisite. It seems the authors' interest was more on how using their code generation tables could speed up the application of those tree rewrite rules.

emmanueloga_ 6y ago
It just blows my mind that an "Artifact Evaluation" process wasn't proposed until so recently [1]. "A paper consists of a constellation of artifacts that extend beyond the document itself: software, proofs, models, test suites, benchmarks, and so on. In some cases, the quality of these artifacts is as important as that of the document itself, yet our conferences offer no formal means to submit and evaluate anything but the paper." 1: https://www.artifact-eval.org/about.html https://www.artifact-eval.org/about.html

i_don_t_know 6y ago

Also highly recommended is „Engineering a simple, efficient code-generator generator“ (1992) by Fraser, Hansen and Proebsting. https://dl.acm.org/doi/pdf/10.1145/151640.151642 https://dl.acm.org/doi/pdf/10.1145/151640.151642

emmanueloga_ 6y ago

Describes an efficient way implementation of "Code generators based on bottom-up rewrite systems (BURS) automatically generated from machine description grammars". There's a short Wikipedia page for BURS [1]: "BURS (bottom-up rewrite system) theory tackles the problem of taking a complex expression tree or intermediate language term and finding a good translation to machine code for a particular architecture. Implementations of BURS often employ dynamic programming to solve this problem." 1: https://en.wikipedia.org/wiki/BURS https://en.wikipedia.org/wiki/BURS