[Disclaimer: I wrote about this topic once before, but it was buried in a longer piece. Also, it was in one of the first posts on this blog and I don’t think anyone read it. Update: I checked the stats. Nobody read it.]
A hammer I like to use when reviewing papers and PhD proposals is one that (lacking a good name) I call the “squeeze technique” and it applies to research that optimizes something. To squeeze an idea you ask:
- How much of the benefit can be attained without the new idea?
- If the new idea succeeds wildly, how much benefit can be attained?
- How large is the gap between these two?
Though this is simple, surprisingly often people have failed to work it out for themselves. Let’s go through an example and then get back to the details.
In 2004 Markus Mock wrote a clever paper which squeezes the idea of programmer specified aliasing, as specified by the C99 language. The “restrict” qualifier added in that version of the language serves as a hint from developers to the compiler; it means that the qualified pointer will not be aliased by other pointers, permitting better code generation in some situations.
Mock’s idea was to instrument a collection of benchmarks to record actual pointer behavior and then use this information to add the maximum possible number of “restrict” qualifiers. In other words, he used dynamic information to optimistically add a restrict qualifier in every location where this was permissible for the inputs used during benchmarking. He then re-ran the modified benchmarks and found less than 1% average speedup.
This result means that for the given compilers and benchmarks, no conceivable human intervention or static pointer analysis can achieve more than 1% average speedup through the addition of restrict qualifiers. The conclusion was that since “restrict” is dangerous in practice (misplaced qualifiers will cause incorrect code to be generated) programmer-specified aliasing is not generally a good idea.
Squeezing a research idea has three elements. The first — left implicit in the list above — is to select a metric. In general this should be externally meaningful: something that people other than computer scientists would care about, perhaps because it has economic consequences. For example speedup, throughput, MTTF, or energy consumption might make a good metric (when coupled with good workloads, a good test platform, good experiment design, etc.). In contrast, the number of “restrict” qualifiers, the average size of an alias set, and the number of context switches are probably poor top-level metrics because they enjoy (at best) an indirect relationship with something a person on the street might be worried about.
The second important choice is the baseline: the amount of benefit achieved without the current idea. This can be tricky and there are many ways of going wrong (probably baseline selection deserves its own blog post). A pernicious mistake is to choose a straw man: an obviously primitive or defective baseline. For example, maybe I’ve created a highly parallelizable algorithm for coalescing hoovulators. Then, I choose the single-processor version of my algorithm as the baseline and go on to show that I can achieve near-linear scalability up to 512 processors. This is a great result unless I am ignoring Stickleback’s 1983 algorithm that is non-parallelizable but performs the same job 750 times faster than my single-processor version, on the same hardware.
The third important element of the squeeze technique is determining an upper bound on improvement. In many cases — as Mock showed — a little creativity is all that is required. Other examples:
- Amdahl’s Law bounds parallel speedup
- The power consumption of the disk, display, and memory often bound the increase in mobile device lifetime that can be attained by reducing processor power usage
- Time spent copying data can bound throughput improvements in networking
- Time spent traveling at 0.3c can bound latency improvements in networking
- CPU, memory, or I/O saturation can bound improvements in throughput due to better resource scheduling
In summary, no matter what we are trying to optimize, there is probably a component that we can improve and a component that we cannot. Understanding the relative magnitudes of these components is a powerful tool for helping to select a research problem to work on. I find myself extremely reluctant to sign off on a document like a PhD proposal that does not display evidence of this sort of thinking.
9 responses to “Squeezing a CS Research Idea”
It’s a good thought. I’ve seen a lot of work where it’s hopeless no matter how technically savvy the workers are. Of course, if you are just trying to show how technically savvy you are, you might not care about useful results.
The first item is close to the KISS principle. Start with the simplest solution, which is to do nothing, and gradually ratchet up the complexity until you have a sufficient solution. It only takes a few minutes to do this sort of mental exercise, and an impressive number of times you can save yourself weeks or months of work.
Great looking blog here. I’ll have to spend more time looking at it! I wanted to comment on your West Desert trilobite experience post, but it was locked, so I’m commenting here. We did a similar trip and had a great time. The book I referred to in the crinoid post is a great handbook for fun outings. And it’s pretty cheap.
It’s good to see someone who’s taking their kids out and helping them experience life.
A few good books I’d recommend for more local hikes & cool spots are:
Tales, Trails & Sites of the Centerville Mountains, by Royce Allen
Farmington Trails, by the Farmington Trails Committee
I do have to admit it’s great to be out of school! I didn’t know how political academia could be until I was working on my masters degree. I finished up last May.
I’ll read more later & post more comments if I can.
While it’s definitely a good step in determining if a line of research is worth pursuing, the kind of analysis done in Mock’s paper has a definite weakness in that it only considers changing the state of the world along a single axis.
Consider: Mock’s paper showed that, given the set of optimizations his compilers performed, it wasn’t beneficial to improved the accuracy of the alias analysis via restrict qualifiers. Thus, at first glance, it would seem that restrict qualifiers aren’t worthwhile.
However, this ignores the fact that the compilers he was using may have been engineered for a world in which restrict qualifiers were rare, and most aliasing queries were unresolvable. It would make sense, then, that such a compiler simply wouldn’t try very hard to perform perform aliasing-dependent optimizations. After all, why waste the compile time if it’s almost never going to succeed?
The point is that you can’t really change one part of the system _completely_ independently of the others. Making C pointers unaliased by default is unlikely to make a big difference on its own, but it would give C compiler writers the impetus to implement the kind of aggressive loop-transforming optimizations that are more common in Fortran compilers. Most C compilers simply don’t try very hard on that front, because it’s almost never possibly prove its safety, while most (good) Fortran compile do because they don’t have to worry about proving it.
TL;DR: It’s a good analysis, and certainly something to consider, but you also have to consider the whole-system impact of a change, not just its direct effects.
Of course you’re right Owen. But you are making a somewhat subtle point and I was only trying to make a blunt one.
On restrict, do you know of code bases that use it much? The version of the glibc header files on my home machine use it, but that’s just about the only real code I’ve seen. I think this usage makes sense: put “restrict” at module boundaries where they’re part of the contract, but within modules rely on pointer analysis to do the right thing.
[…] Embedded in Academia : Squeezing a CS Research Idea. […]
I’m not familiar with any code bases that use restrict heavily. It’s sort of a chicken-egg problem.
Compilers (except maybe MSVC) don’t implement aggressive alias analysis because it’s slow, and the efficient forms are patent encumbered. Because of this, very few aliases of this can be disambiguated. Thus it’s not worthwhile trying to implement aggressive restructuring optimizations that depend on aggressive AA. And then, since the compiler’s not going to do much them anyways, nobody actually bothers to write restrict qualifiers.
The article was about a much wider point but my feeling on the aliasing issue is that annotations are a big step backwards in terms of progress. It puts the complexity in the wrong place, and (at least in the case of the C annotations) opens another wormhole through which compiler optimizations mysteriously influence the behavior of programs.
My opinion as a compiler writer is that a compiler that is sufficiently advanced to be perform the kinds of code motion made possible by alias analysis should be capable of actually doing the analysis.
There’s another flaw in this kind of analysis. When programmers use restrict themselves, they tend to only place it in the small number of “important” places for their program (e.g. low-level function where a lot of time is spent, and disassembly shows that the compiler generates the wrong code without the restrict). In this way, they extract a lot of the potential value of manually-placed restrict even though they only place it in a few extra places. What I think this research really shows is that “putting restrict everywhere it could possibly be put, gains almost nothing over manually putting it in a SMALL number of sensible places”.
The rule for programmers should be “don’t use restrict unless you KNOW you need it, and be extremely careful when you do use it”.
By the way, I have the opposite opinion from Ben about manually-specified aliasing. Its too costly and in many cases undecidable for the compiler to find the right places where “restrict” can be used. As the programmer, I want the ability to declare to the compiler “I promise this thing does not alias with anything else”. I also want other types of programmer-annotation, such as “force-inline the called function at this specific call-site” and “assume this expression is true, and make whatever use of that you can to optimize”. Compilers cannot know all of the context that the programmer knows about how this code will be used. For example, maybe you have a code generator that generates thousands of similar methods and minimizing their code size (through controlling which things get inlined and which things don’t) is much more important to you than getting maximum speed out of them. As a game developer, I want a smart compiler that will make the right choice most of the time, but sometimes I definitely need to override its code-generation choices–game consoles have a fixed amount of RAM. (Its true that restrict has little effect on code size. I’ve seen cases where __assume can affect code size though, e.g. to eliminate NULL-checks generated by placement new)