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

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

citeseerx.ist.psu.edu

56 pointstjalfi14 comments

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

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.

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

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

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

My basic education in computer science consisted of going to the university library starting about 1977 and reading dusty old ACM and IEEE journals. I already knew how to program, my initial interest was following up an academic reference on run length compression in Dr. Dobbs Journal. In the dark (and cool) Arizona State University library I discovered a wondrous web of scientific and engineering literature related to computing.

At some point in the 80's academia took a turn away from accessibility. While the boom in public internet did skew things back towards freely available, there are a multitude of forces attempting to conceal the lamp of knowledge, usually behind a paywall. This subtopic is worthy of independent discussion.

This also reminds me to remember Aaron Swartz.

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

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?

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 (Fast and flexible instruction selection with on-demand tree-parsing automata)

I expected the typical kerning/typesetting issues.

I want to note that it straight-up crashes Chromium's PDF reader.

Interesting... Chrome on macOS seems fine with it here.

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

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.

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

Reply on news.ycombinator.com