4 ms·
> You need a great inliner. You want common subexpression elimination (CSE), constant propagation and folding, strength reduction, and an excellent loop optimiz
by pcwalton 11y ago
> You need a great inliner. You want common subexpression elimination (CSE), constant propagation and folding, strength reduction, and an excellent loop optimizer. These days, you probably want to use static single assignment form (SSA), and some unique SSA optimizations like global value numbering (although you need to be careful about working set and compiler throughput when using SSA everywhere)…I hate to say it, but doing great at all of these things is "table stakes."
I'm not sure. It depends on the audience you're aiming for. Go has done very well with a compiler that essentially performs no compiler optimizations (by modern standards; certainly it doesn't do most of the above) by positioning itself appropriately.
> For example, there are ways to write the earlier loop that can easily "trick" the more basic techniques discussed earlier:
Yeah, bounds check elimination ends up nightmarish quickly. I think I prefer an approach that fixes the problem at its source, by just encouraging programmers to stop using for loops (which are bad for non-performance-related reasons as well). Note that all of the examples given use for loops; if they were rewritten using iterators, there wouldn't be a problem. C# has iterators, so the machinery is there; they just need to make it more painful to use a for loop than the iterator alternative. :)
> Imagine you have a diamond. Library A exports a List<T> type, and libraries B and C both instantiate List<int>. A program D then consumes both B and C and maybe even passes List<T> objects returned from one to the other. How do we ensure that the versions of List<int> are compatible?
I don't understand why this is a problem. Both separately compiled implementations of List<int> should monomorphize to bit-identical runtime value representations. Does the problem have to do with quirks of the compiler's RTTI implementation (e.g. making sure "foo instanceof List<int>" in package A works even if "foo" came from package B)?
> First, Go generates the interface tables on the fly, because interfaces are duck typed.
Does it really? That's interesting and seems extremely inefficient. I would have assumed that the Golang compiler would just statically determine the set of vtables that need to be used by the program and write them up front into rodata. Am I missing something?
- hencq 11y agoHere's a little more info on how and why Go does it: http://research.swtch.com/interfaces http://research.swtch.com/interfaces
- pcwalton 11y agoInteresting, thanks. The relevant part seems to be here: > Go's dynamic type conversions mean that it isn't reasonable for the compiler or linker to precompute all possible itables: there are too many (interface type, concrete type) pairs, and most won't be needed.
- cwzwarich 11y ago> I would have assumed that the Golang compiler would just statically determine the set of vtables that need to be used by the program and write them up front into rodata. Am I missing something? IIRC the Go compiler will generate the itables that it can determine are needed at compile time, but because you can dynamically request an interface conformance for a type there is also a runtime fallback. Swift does something similar; the compiler tries to generate protocol conformances as much as possible, but because there may be an unbounded number of types at runtime, clearly it can't generate all of them.
- pcwalton 11y ago> IIRC the Go compiler will generate the itables that it can determine are needed at compile time, but because you can dynamically request an interface conformance for a type there is also a runtime fallback. That would make more sense. But http://research.swtch.com/interfaces http://research.swtch.com/interfaces claims it's all runtime-based (though that document may well be out of date).
- cwzwarich 11y agoIt looks like the optimization I remember was implemented in gccgo, but maybe they never added it to the main compiler: http://www.airs.com/blog/archives/277 http://www.airs.com/blog/archives/277
- xenadu02 11y agoThey were trying to build the entire OS using a 100% memory-safe language. At one point they could elide process boundaries and protected memory (and the associated context switch overhead) because the loader could statically verify your program didn't do anything unsafe. The ultimate answer to Singularity/Midori/etc is yes, you can have an OS (including drivers and interrupt handlers) that is 100% provably memory safe and thread safe and is performance-competitive with existing systems. Unfortunately Microsoft basically sheleved most of the work and it doesn't look like anyone else is going to pick up the slack. I predict more heartbleeds and zero-day RCEs in our future. At least we'll all get 0wned with fast C code.