Time/space tradeoff [LWN.net]

Time/space tradeoff

Posted Apr 29, 2004 17:55 UTC (Thu) by jzbiciak (✭ supporter ✭, #5246)
Parent article: The cost of inline functions

There still is a time/space tradeoff of sorts, it's just that time as a function of space is not a monotonically decreasing function.

That's been true for a long time. The difference is that the crossover between negative slope (bigger space == less time) and positive slope (bigger space == more time) keeps moving closer and closer.

One of the benefits of inlining, aside from eliminating the call/return, is that it opens new optimization opportunities by optimizing across the caller/callee boundary. In effect, it allows the called function to be specialized for the context from which it was called. For instance, one of the operands to a function might be a flag that enables/disables some feature controlled by the function. If that flag is a constant in the call, entire codepaths from the callee might become dead code.

It would be interesting to see GCC start specializing functions in this manner without having to inline them, so we keep this secondary benefit while avoiding code bloat. Of course, this is relevant only if GCC can see multiple callers that would benefit from the same specializations. For instance, how many times is kmalloc called with "GFP_KERNEL"? Many. Would an automatic specialization for kmalloc(size, GFP_KERNEL) result in a performance benefit? Possibly.

(Log in to post comments)

Time/space tradeoff

Posted May 6, 2004 6:41 UTC (Thu) by joib (guest, #8541) [Link]

gcc 3.4 has some optimizations in this area. From http://gcc.gnu.org/gcc-3.4/changes.html:

# A new unit-at-a-time compilation scheme for C, Objective-C, C++ and Java which is enabled via -funit-at-a-time (and implied by -O2). In this scheme a whole file is parsed first and optimized later. The following basic inter-procedural optimizations are implemented:

* Removal of unreachable functions and variables
* Discovery of local functions (functions with static linkage whose address is never taken)
* On i386, these local functions use register parameter passing conventions.
* Reordering of functions in topological order of the call graph to enable better propagation of optimizing hints (such as the stack alignments needed by functions) in the back end.
* Call graph based out-of-order inlining heuristics which allows to limit overall compilation unit growth (--param inline-unit-growth).

Overall, the unit-at-a-time scheme produces a 1.3% improvement for the SPECint2000 benchmark on the i386 architecture (AMD Athlon CPU).
# More realistic code size estimates used by inlining for C, Objective-C, C++ and Java. The growth of large functions can now be limited via --param large-function-insns and --param large-function-growth.