3 ms·

Superoptimizer – A Look at the Smallest Program (1987) [pdf]

74 points by linggen 4mo ago

seritools 4mo ago
(1987)
- tomhow 4mo ago
  Updated, thanks!
gregdaniels421 4mo ago
Same author did the synthesis kernel with Carl Pu, I think? The Synthesis kernel was genius, but relied on self modifying code, so can't work with modern chips well.
- convolvatron 4mo ago
  yes. Calton Pu. is that really such a problem? JITs seem to work pretty well, I'm pretty sure synthesis was more about creating custom paths than being strictly self-modifying, but it's been a long time. update: oh, I just remembered why it _is_ an issue for modern processors, Massalin leaned very heavily on the general purpose double compare-and-swap that was present on some generations of the 68k architecture, and x86-64 only has double contiguous compare and swap
  - gregdaniels421 4mo ago
    Yeah for the Quajects to get the JIT-ing to work, which was outrageous cool sounding when I first read about it. It is a same we can't figure out how to have nice things like that go fast(cache flushing).
KentBeck 4mo ago
I love love love this paper. I wonder how a GPU would do with it?
smalltorch 4mo ago
Interesting to compare and contrast the human brain in the frame of reference of this superoptimzer paper. It constantly trys to do the most things with the least things. Take all the shortcuts to achieve the same outcome, often misconstrued with laziness, quality deficiency, or hard to understand. For example, something as simple as timing may superoptimize and minimize instruction sets. Using one resource to do all the things needed at once versus calling the resource multiple times at different times shrinks the overall program a lot.
petercooper 4mo ago
This has long been one of my favorite papers, if only for the opening example. When I walked through it, it was an eye opener to a different level of thinking about code, one that assembly and democoders are probably working in every day.
ashton314 4mo ago
A (relatively) new way to create a super optimizer is to use an egraph: https://egraphs-good.github.io/ https://egraphs-good.github.io/ These are nifty data structures that can quickly search the space of equivalent programs.

74 points by linggen 4mo ago

seritools 4mo ago

(1987)

tomhow 4mo ago
Updated, thanks!

gregdaniels421 4mo ago

Same author did the synthesis kernel with Carl Pu, I think? The Synthesis kernel was genius, but relied on self modifying code, so can't work with modern chips well.

convolvatron 4mo ago
yes. Calton Pu. is that really such a problem? JITs seem to work pretty well, I'm pretty sure synthesis was more about creating custom paths than being strictly self-modifying, but it's been a long time. update: oh, I just remembered why it _is_ an issue for modern processors, Massalin leaned very heavily on the general purpose double compare-and-swap that was present on some generations of the 68k architecture, and x86-64 only has double contiguous compare and swap
- gregdaniels421 4mo ago
  Yeah for the Quajects to get the JIT-ing to work, which was outrageous cool sounding when I first read about it. It is a same we can't figure out how to have nice things like that go fast(cache flushing).

KentBeck 4mo ago

I love love love this paper. I wonder how a GPU would do with it?

smalltorch 4mo ago

Interesting to compare and contrast the human brain in the frame of reference of this superoptimzer paper. It constantly trys to do the most things with the least things. Take all the shortcuts to achieve the same outcome, often misconstrued with laziness, quality deficiency, or hard to understand. For example, something as simple as timing may superoptimize and minimize instruction sets. Using one resource to do all the things needed at once versus calling the resource multiple times at different times shrinks the overall program a lot.

petercooper 4mo ago

This has long been one of my favorite papers, if only for the opening example. When I walked through it, it was an eye opener to a different level of thinking about code, one that assembly and democoders are probably working in every day.

ashton314 4mo ago

A (relatively) new way to create a super optimizer is to use an egraph: https://egraphs-good.github.io/ https://egraphs-good.github.io/ These are nifty data structures that can quickly search the space of equivalent programs.