pervognsen, 25 days ago (edited 25 days ago)

Ershov also independently invents open-addressed linear probing in that short paper although Amdahl, et al, had the idea a few years earlier in 1954.

pervognsen, 25 days ago

Let's also invent the Sethi-Ullman algorithm 12 years early while we're at it.

pervognsen, 25 days ago

(I'm not sure how much credit he gets for that. I've always been amused that Sethi-Ullman gets to have a fancy name attached for something so simple and relatively limited in practice. Whereas value numbering/hash consing might be a simple idea but it's extremely powerful and far reaching. But it's nice to see him attack related parts of the problem at once in such a short paper, not just value numbering but instruction scheduling and register allocation, since they all affect each other.)