Prev: CFP: The 2010 International Conference on Frontiers in Education: Computer Science and Computer Engineering (FECS'10), USA, July 2010
Next: CFP: The 2010 International Conference on Software Engineering Research and Practice (SERP'10), USA, July 2010
From: Robin Holmes on 25 Jan 2010 08:33 Writing code with objects and virtual functions allows for faster program construction and often code with less bugs and code that is easier to change. But many virtual function calls can cause some performance degradation for some kinds of code. For JIT compilation, I have created this new technique, called ROD, that you can use to speedup performance of some virtual calls in some kinds of programs. http://www.pacificv.prophp.us/rod.php http://juke.googlecode.com/files/ROD_100.pdf If you understand VM and JIT, please get back to me with your thoughts . I would like to get some info on how you will integrate it with your own VM or if you think it would break your JIT code.
From: Dmitry A. Kazakov on 25 Jan 2010 14:57 On Mon, 25 Jan 2010 05:33:17 -0800 (PST), Robin Holmes wrote: > Writing code with objects and virtual functions allows for faster > program construction and often code with less bugs and code that is > easier to change. But many virtual function calls can cause some > performance degradation for some kinds of code. This is not an issue in a properly typed language, for example, in Ada, which statically distinguishes the class type (a closure of types derived from some root) and the concrete type (a member of the class). So dispatch never happens when the object's type is known. Especially no re-dispatch happens if not explicitly requested, because types of all arguments are known in the bodies. -- Regards, Dmitry A. Kazakov http://www.dmitry-kazakov.de
From: S Perryman on 25 Jan 2010 15:04 Dmitry A. Kazakov wrote: > On Mon, 25 Jan 2010 05:33:17 -0800 (PST), Robin Holmes wrote: >>Writing code with objects and virtual functions allows for faster >>program construction and often code with less bugs and code that is >>easier to change. But many virtual function calls can cause some >>performance degradation for some kinds of code. > This is not an issue in a properly typed language, for example, in Ada, > which statically distinguishes the class type (a closure of types derived > from some root) and the concrete type (a member of the class). So dispatch > never happens when the object's type is known. Especially no re-dispatch > happens if not explicitly requested, because types of all arguments are > known in the bodies. You can guarantee (for single dispatch) a fixed performance bound of one indirection before the op invocation. Which is a useful target env option for systems that do not have reams of object instances with reams of virtual ops. But not practical for the general case. Regards, Steven Perryman
From: Robin Holmes on 26 Jan 2010 11:02 Thanks for the replies. Go through the specification slowly at pacificv.prophp.us/rod.php . What I am talking about is much bigger for some purposes than static devirtualization based on class analysis. This object devirtualization is a specific attribute for specific functions like the root of a file parser, the process function of a VST etc... The actual devirt function itself is not inlined, but instead inlines just about as much as it can that is in the execution path of itself, because it knows the actual objects it will be using. You need to think here of massive inlining, like hundreds or thousands of inlined functions and direct memory references to fields. The output machine code for one properly devirted function can be huge(BUT RUN TWICE AS FAST IN SOME THEORYS). For example: class TObject { devirt void devirtFunction() { } } class TObjectA : public TObject { devirt void devirtFunction() { // } } class TObjectB { devirt TObjectA* fieldX; devirt void devirtFunction() { // because we know the allocated instance of the this parameter when we devirt // this function, we also know the allocated instance of fieldX, thus // allowing direct memory references to it and its children, as well as // being able to just inline any virtual functions on it because we already know // the type. fieldX->someVirtualMethod();// This can just be inlined no matter its class } } void callDevirt(TObject* obj) { // This call here on a type of TObject* is where the devirt happens. // It is not inlining this call itself, but instead building one massive function // that actually uses the runtime allocated instance of obj to do the JIT, instead // of normal JIT where method JIT is using static class types to do the JIT. In other // words one function per instance is JITTED for each different obj passed to // this function obj->devirtFunction(); // The point is that JIT compiling and knowing the exact object used for // the specific call will allow you to inline a lot more than you could with // static analysis of type information. The speedup of some code made // using normal OOP and some well placed devirt attributes can be enormous. } TObject* instanceA = new TObjectA(); TObject* instanceB = new TObjectB(); callDevirt(instanceA); callDevirt(instanceB); So if we have a VST plugin that must generate audio, or an SQL statement that must run quick, we can program as usual the things inside, such as string comparers, Select statements, DSP filters, rounding functions and so on. In other words program like with objects and virtual functions. Then by placing the devirt keywords carefully we can get the JIT to do all the inlining an optimization often better and much faster than could be done with hand optimized machine code. The main points are: Its Object devirtualization, not based on static type analysis Its not good for just any virtual function(except for once you are actually doing a devirt) Its good for code that uses lots of virtual functions and fields inside a repeated base function call like the process function of a VST plugin, or the compile function of an SQL statement object(or a C+ + parser or tokenizer object for example). By following all the virtual calls in such code constructs, and all the field references, it can be proven that large amounts of code can be removed, specifically stack frames, ret statements, double derefs to get at fields in objects, call statements etc... The trick to understanding it is thinking differently about the LDTHIS instruction in your JIT. When you encounter LDTHIS, dont load and work with only the static assumed type of the this parameter, but pass the JIT the actual runtime object of the this parameter and use that instead when you hit a LDTHIS. Once you have that on the pseudo stack, then go further and get the actual runtime object for fields of the this parameter and even fields of those fields. So once you get like a CALLVIRT instruction on the loaded LDTHIS result on the pseudo stack, you can inline the virtual function because you already know the exact object you will be using,.
From: Dmitry A. Kazakov on 26 Jan 2010 13:11
On Tue, 26 Jan 2010 08:02:46 -0800 (PST), Robin Holmes wrote: > Thanks for the replies. Go through the specification slowly at > pacificv.prophp.us/rod.php . What I am talking about is much bigger > for some purposes than static devirtualization based on class > analysis. This object devirtualization is a specific attribute for > specific functions like the root of a file parser, the process > function of a VST etc... I think the conventional naming for this is polymorphic vs. non-polymorphic object/type/operation. [...] > // because we know the allocated instance of the this parameter when we devirt > // this function, we also know the allocated instance of fieldX, thus > // allowing direct memory references to it and its children, as well as > // being able to just inline any virtual functions on it because we already know > // the type. > fieldX->someVirtualMethod();// This can just be inlined no matter its class > } > } This is the point, when the type is known it must be *properly* attributed. The problem you address simply does not exist in a properly typed language that *distinguishes* classes and types, thus polymorphic and non-polymorphic things become distinguishable as well. Your example written in Ada: type T is tagged private; procedure Foo (X : in out T; type S is new T with private; overriding procedure Foo (X : in out T); type Q is record X : S; end record; procedure Bar (Y : in out Q); procedure Bar (Y : in out Q) is begin Y.X.Foo; -- Or Foo (Y.X), no matter end Bar; Since the type of X is stated as S, it is statically known to be S and nothing else. A call to Y.X.Foo will be statically resolved and can be inlined if there is a desire to do so. BTW, no pointers are needed as the type and thus the object's size is known too. So you put S into Q and save overhead of memory and performance. This is possible because S and S'Class are distinct types. An instance of S is non-polymorphic, it is always S. An instance of S'Class is polymorphic and can "contain" S or any type derived from it. -- Regards, Dmitry A. Kazakov http://www.dmitry-kazakov.de |