2 ms·
Lots of unexplored potential in this area. Also think about optimizing memory access by applying this to data structures: if you can prove there are at most 42
by fulafel 12y ago
Lots of unexplored potential in this area.
Also think about optimizing memory access by applying this to data structures: if you can prove there are at most 42000 foo objects, the compiler could reduce 64-bit foo pointers to 16-bit indices. And reorder object layout so that fields are in access order. Etc. With everything being limited by cache misses, reducing your cache footprint and miss frequency like this can provide big speedups. (also shrink your VM memory requirements).
Managed languages with capabilities to deopt when assumptions are violated can do optimizations like these more optimistically and based on profile feedback. In fact Hotspot already does in a more limited way (comperssed oops).
- userbinator 12y agoif you can prove there are at most 42000 foo objects, the compiler could reduce 64-bit foo pointers to 16-bit indices I think the main problem with doing this is that it requires a level of "intelligence" and insight that compilers currently are nowhere near; these types of optimisations are easy to see from the point of view of the (human) programmer, but due to their generality, compilers simply can't seem to "think" in this way. It's not quite at the level of "find an implicit O(n^2) algorithm in the code and replace it with an O(n log n) one", nor is it as simple as the common pattern-matching type of optimisation. The other aspect is that size-optimisation has traditionally been highly downplayed in academic research despite the techniques being well-known in e.g. the demoscene and some embedded systems development. Overlapping instructions, for example, is one optimisation that I don't think compilers will be able to do any time soon. This and other types of low-level optimisation are often applied by (human) Asm programmers, however.
- fulafel 12y agoLike I said, HotSpot already does a version of this. Doing doing the full version with deopt wouldn't appreciably harder analysis-wise: https://wikis.oracle.com/display/HotSpotInternals/CompressedOops https://wikis.oracle.com/display/HotSpotInternals/Compressed... For static compilation, generally proving <42000 by reasoning from code is probably too hard, but lots of room for cheating. For example profile feedback generates observation about <42000 and you put in an assertion to that effect. There's some attention deficit in academia, but there do exist papers about this stuff. Eg https://dl.acm.org/citation.cfm?id=1739033 https://dl.acm.org/citation.cfm?id=1739033 and its refs http://scholar.google.com/scholar?q=related:g11WX-h6J6cJ:scholar.google.com http://scholar.google.com/scholar?q=related:g11WX-h6J6cJ:sch... It's just not making its way to real-world production compilers/VMs. C/C++ don't really allow most of these optimizations, that's one problem.