4 ms·

I've worked with a sufficiently smart compiler before: The HLSL (shader) compiler for the Xbox360. It truly is a grand experience. The general recommendation

I've worked with a sufficiently smart compiler before: The HLSL (shader) compiler for the Xbox360. It truly is a grand experience. The general recommendation was to not try to outsmart the compiler. Write everything as straight-forward as possible. Just watch out for work done on values that influence the result but aren't really necessary (ex: multiplying by an input that will always be 1). There were several occasions where I'd write out some elegant math and think "Yeah, that's pretty. But, it would run 30% faster if I transposed everything. But, then I'd have to hand-interleave the internals of all these functions..." Then I'd check the assembly output and Bam! the compiler was already producing exactly what I had in mind! The downside was that it took several minutes to compile <100 line sources that produce <1000 instruction programs. That's with a language completely specialized around small-scale linear algebra that maps very directly to hardware that is completely specialized around small-scale linear algebra; with branching highly discouraged, all functions calls expected to inline away completely, no recursion, no pointers, no heap, no imports, tiny-if-any headers and a tiny standard lib. It's my understanding that most of the smartness of the 360's HLSL compiler came from using O(n^3) analysis algorithms that were simply impractical at a larger scale. Our game had thousands of shader programs that were mechanically specialized for different situations. As a result, recompiling all of them after changing the tiny shared header took many hours. "Thankfully" the C++ of the game took so long to compile that we were already using Xoreax Incredibuild to distribute the compilation. We adapted that setup to distribute shader compilation and brought the turn-around time down to 15 minutes by leaching cycles from several dozen of my co-workers' machines.

deleted 13y ago
[deleted]
foobarbazqux 13y ago
Most optimizing compilers use data flow analyses which are cubic, so it's not just that it's O(n^3). http://dl.acm.org/citation.cfm?id=788019.788876 http://dl.acm.org/citation.cfm?id=788019.788876
- jevinskie 13y ago
  It becomes important to fast path the low hanging "can't optimize" condition checks and bail out as early as possible.
- larsberg 13y ago
  You can do pretty well for analyses where n is the number of variables instead of the number of program points / expressions. In those cases, the typical trick is to shorten the height of the tracked lattice, as you only get in trouble in a few places. To make that concrete, control-flow analysis (which answers "which possible functions could I call through this variable?") is cubic in general. But if you cut it off to only tracking N separate functions and then giving up to ANY when you hit that N, you can cut off the few bad cases (e.g., all of the bindings to the function passed to map, which you will probably just inline later anyway) that generate the cubic behavior and keep your execution time well-behaved, even for whole program compilers, at very small loss of precision in practice.
  - foobarbazqux 13y ago
    If your language has pointers or aliases, precise call graphs are exceedingly expensive (for large programs), because you need a precise pointer or alias analysis. Do you have a link to a publication about the technique you describe?
    - larsberg 13y ago
      There are meatier technical presentations around about the formal bounds, but I always recommend Manuel Serrano's early work, which is much more accessible than more modern presentations (my own included): http://dl.acm.org/citation.cfm?id=315891.315934 http://dl.acm.org/citation.cfm?id=315891.315934 A good survey of many of the tricks used in practice (and the formal techniques, as well) is available in Jan Midtgaard's tome, which was finally published in the last year or so: http://dl.acm.org/citation.cfm?id=2187671.2187672 http://dl.acm.org/citation.cfm?id=2187671.2187672
      - 13y ago
derleth 13y ago
> The downside was that it took several minutes to compile <100 line sources that produce <1000 instruction programs. This sounds like the Stalin Scheme compiler. Simple benchmark (vs C (gcc), Stalin wins): http://justindomke.wordpress.com/2009/02/23/the-stalin-compiler/ http://justindomke.wordpress.com/2009/02/23/the-stalin-compi... GUI addon: http://code.google.com/p/stalingui/ http://code.google.com/p/stalingui/ http://community.schemewiki.org/?Stalin http://community.schemewiki.org/?Stalin Download link: https://engineering.purdue.edu/~qobi/software.html https://engineering.purdue.edu/~qobi/software.html
- ANTSANTS 13y ago
  Stalin is very impressive, but > Simple benchmark (vs C (gcc), Stalin wins) Did you read the comments? > Nice, but part of the reason the C version is slow is that you are using abs instead of fabs. abs takes an int as an argument (this should be a compiler warning!) – passing a double other than zero always returns a large number. The C version is basically iterating till the error is below double’s resolution. > Excellent point! Making the switch to fabs brings the gcc-inline speed down almost exactly to what Stalin is getting.

deleted 13y ago

[deleted]

foobarbazqux 13y ago

Most optimizing compilers use data flow analyses which are cubic, so it's not just that it's O(n^3). http://dl.acm.org/citation.cfm?id=788019.788876 http://dl.acm.org/citation.cfm?id=788019.788876

jevinskie 13y ago
It becomes important to fast path the low hanging "can't optimize" condition checks and bail out as early as possible.
larsberg 13y ago
You can do pretty well for analyses where n is the number of variables instead of the number of program points / expressions. In those cases, the typical trick is to shorten the height of the tracked lattice, as you only get in trouble in a few places. To make that concrete, control-flow analysis (which answers "which possible functions could I call through this variable?") is cubic in general. But if you cut it off to only tracking N separate functions and then giving up to ANY when you hit that N, you can cut off the few bad cases (e.g., all of the bindings to the function passed to map, which you will probably just inline later anyway) that generate the cubic behavior and keep your execution time well-behaved, even for whole program compilers, at very small loss of precision in practice.
- foobarbazqux 13y ago
  If your language has pointers or aliases, precise call graphs are exceedingly expensive (for large programs), because you need a precise pointer or alias analysis. Do you have a link to a publication about the technique you describe?
  - larsberg 13y ago
    There are meatier technical presentations around about the formal bounds, but I always recommend Manuel Serrano's early work, which is much more accessible than more modern presentations (my own included): http://dl.acm.org/citation.cfm?id=315891.315934 http://dl.acm.org/citation.cfm?id=315891.315934 A good survey of many of the tricks used in practice (and the formal techniques, as well) is available in Jan Midtgaard's tome, which was finally published in the last year or so: http://dl.acm.org/citation.cfm?id=2187671.2187672 http://dl.acm.org/citation.cfm?id=2187671.2187672
    - 13y ago

derleth 13y ago

> The downside was that it took several minutes to compile <100 line sources that produce <1000 instruction programs. This sounds like the Stalin Scheme compiler. Simple benchmark (vs C (gcc), Stalin wins): http://justindomke.wordpress.com/2009/02/23/the-stalin-compiler/ http://justindomke.wordpress.com/2009/02/23/the-stalin-compi... GUI addon: http://code.google.com/p/stalingui/ http://code.google.com/p/stalingui/ http://community.schemewiki.org/?Stalin http://community.schemewiki.org/?Stalin Download link: https://engineering.purdue.edu/~qobi/software.html https://engineering.purdue.edu/~qobi/software.html

ANTSANTS 13y ago
Stalin is very impressive, but > Simple benchmark (vs C (gcc), Stalin wins) Did you read the comments? > Nice, but part of the reason the C version is slow is that you are using abs instead of fabs. abs takes an int as an argument (this should be a compiler warning!) – passing a double other than zero always returns a large number. The C version is basically iterating till the error is below double’s resolution. > Excellent point! Making the switch to fabs brings the gcc-inline speed down almost exactly to what Stalin is getting.