Exupery + Optimising Compiler = Damn Fast
Posted 12 Dec 2006 by mikevdgI don't believe that the Squeak compiler as it currently is does method inlining. Imagine if it could...
My understanding of Squeak compilation isn't complete, so take the following with a grain of salt.
As far as I'm aware, one of the slower operations in Squeak is doing a message send. There are 5 groups of bytecodes: Push/Pop, Store, Send, Return and Jump. Except for the Send bytecodes, these are all trivial operations. Send bytecodes, however, must do a method lookup. The Squeak implementation has a method cache where it stores recently looked up methods to prevent doing the expensive operation of doing the method lookup again.
Method inlining is where, instead of a message-send bytecode, the entire contents of the method that would be called is cut and pasted to where the message send would have been. Because Squeak is a dynamically typed language, it's a bit more complicated than this and a little bit of type-checking wrapper code would need to go around that inlined method.
If message sends could be inlined into code (at the bytecode level), there are significant speed-ups that could be made. However, if a method is updated with new code, anywhere that it is inlined will be out of sync. In other words, the compiler has no guarantee that the code it is working with won't change from underneath it.
But just imagine: if the compiler could be assured that the code is static, a programmer could run some profile tests to gather profiling information. The compiler could then use that profiling information to intelligently inline small, often-used methods. And then Exupery could do its magic and convert the now optimised code into seriously hard-core executable machine code. That would be very, very fast.
But then the problem remains: how can we assure the compiler that the CompiledMethods it's inlining won't change? Well, one way of doing this would be to do a "release" build where the compiler is effectively disabled or even removed from the image once it has done all it's hard work.
Another option would be to have some fancy updating scheme. The compiler (or some other part of Squeak) could have a Dictionary mapping Classes to lists of other Classes which have inlined CompiledMethods from that Class. If the compiler modifies any method, it will need to look up that method's class in that dictionary and iterate through the list of dependant classes, restoring their methods to the un-inlined versions. This way, the method which had an inlined method inside it will now use the new version of the inlined method.
Michael.
Why not add inlining to Exupery? , posted 15 Dec 2006 by willembryce
It's been planned since the beginning. The only reason I'm not working on it is it's not needed to provide a nice speed improvement to Squeak. You could think of the plan for Exupery 1.0 as everything needed to make use of inlining in a production Squeak environment except inlining.Exupery already needs to track changes because it's adding yet another representation for a method. Before Exupery there is CompiledMethod and the method source with Exupery there is also compiled machine code. That compiled machine code may be removed if the image is saved or a change invalidates the change.
Exupery already dynamically inlines primitives. The plan is to add dynamic method inlining as the big feature in 2.0. If nothing else this should provide motivation to finish 1.0.
Recommended resources, posted 15 Dec 2006 by kubetz
For anybody who is interested in this topic ..Strongtalk has some easy to understand notes/docs bundled with the distribution about adaptive method inlining and other speed optimization [1].There is also interesting material about Self optimalization on the same site [2].
For further resources look into strongtalk-general thread containing tips from VM/Compiler gurus [3].
There is also paper describing how Exupery is working [4].
[1] http://www.strongtalk.org/downloadCurrent.html
[2] http://www.strongtalk.org/documents.html
[3] http://groups.google.com/group/strongtalk-general/browse_thread/thread/83bda45b670b5a5b/2e2b63b0bf121f7a#2e2b63b0bf121f7a
[4] http://goran.krampe.se/exuperyDesign.pdfRE: Why not add inlining to Exupery?, posted 18 Dec 2006 by mikevdg
Hi Bryce :-).After some reflection, I realise that you're completely correct. I didn't realise that Exupery must track changes to code, which when you think about it should have been obvious.
My original hypothesis was that adding this optimisation at the bytecode compiler level (as opposed to the machine code compiler level that Exupery is) would allow the complexity to be managed in Smalltalk. That premise is useless because Exupery itself is written in Smalltalk and already has the framework (I assume) available for such optimisations.
I'd be very interested in how much of a speed-up Exupery can give by inlining small methods. I believe it would be quite phenomenal; Smalltalk methods are almost always tiny and many of them return a constant or instance variable.
[ Home | Articles | Login/Account | People | Projects ]