OSDev.org

I am currently working on a language and associated runtime (as part of my os project). It is managed and dynamically translated (somewhat in the spirit of the .NET platform, but a bit more focused on native performance when possible). In its development have run into an interesting dilemma regarding polymorphism and its implementation, which is best represented by an example.

Supposed you have a List class, which maintains an unordered list of elements. To increase performance in certain situations, you make a SortedList class that inherits from List, with an improved search algorithm and the necessary modifications to the methods of the List class.

But now you run into a problem. There are some functions you would like to pass a SortedList as a parameter, even though they are only designed to take a List. The obvious solution is using virtual functions in both classes, which would allow SortedList to be casted to List, no problem. However, requiring all uses of List to go through a VFT could be quite a performance hit.

I would like to resolve this problem inside my language, while generally sticking to OOP concepts. These are the soltuions I have come up with:

• Make the methods in classes like List virtual. This reduces the performance hit, but is still quite a serious problem when such basic classes require it. It also fails to solve the problem when a function external to your program requires a non-virtual type that you have inherited from as a parameter.
• Make all methods virtual, as Java does. This could create quite the performance hit, but it would resolve several other issues in the way I plan on using the language.
• Solve it at runtime. Simply allow programmers to cast types as they please and assure them that the correct function will be called, even if not explicitly flagged as virtual. VFTs will be used for methods that are explicitly virtual, and when a cast from an type to its ancestor occurs and some methods are not virtual, regenerate the functions that are not equipped to handle the inherited type. Having multiple copies of functions seems quite wasteful, especially if it is needed often, but this solution gives the programmer the most options and flexibility, especially when dealing with foreign code (under this system foreign code is generally in byte form and can handle this process just fine). It also raises an issue when types are casted to incompatible types and then stored.
• Make incompatible casts create temporary copies, and use these to simulate the previous solution. This can be very wasteful in both time and space. Storing is still an issue with this solution.
• Use either of the above two methods (or both in combination), but allow programmers to explicitly set up certain compatibilities when casting. For example, the SortedList could be temporarily allowed to be used as an unsorted List, and then resorted when the subroutine returns. Storing is still an issue with this solution.

I am leaning towards the second (make all methods virtual) solution. With proper compiler/runtime optimization, VFTs should have a minimum impact, and it nicely solves some other issues I was running into. The main place I see VFTs being a problem is when dealing with large arrays of types which be all / mostly the same. In that case, large arrays could store extra information about the type of the elements in them (for example, it could store the most derived type that all the elements in the array inherit from, and loops could check if the functions they use are overloaded past that type). This solution would also solve another issue I've been running into, namely how to allow classes inherit only the interface of a class, but none of the implementation (essentially in the manner of Java interfaces, except there is no separate interface construct).

I am open to any recommendations or alternate solutions. In particular, I am interested to hear those who are more familiar with the performance characteristics of VFTs have to say.

If you're going for a managed language, I'd go for the Java-C++ optimal mix.

C++ is good in that only the functions for which virtual function overhead is negligible and it adds something are virtual. Java is good in that you don't have to think about which to make virtual & you can't forget to.

Make your compiler find out which classes have subclasses and mark those functions as virtual-for-base in the objects. Then at "link time" convert those functions into actually virtual and the rest into actually-not-virtual. That makes the overhead equal to C++ (while removing the "new" option in C# terms) and the userland experience like Java.

Any cases where this would not work?

That sounds like a good idea, and after looking at my solutions it seems like I was over-complicating the issue . It would especially work well when certain programs don't require virtual methods for some virtual types (for example if a program uses the SortedList class only internally and does not cast it to List, and never accepts a reference to a List object from external code that might be casted as something else), and those programs can forgo VFTs.

JohnnyTheDon wrote:That sounds like a good idea, and after looking at my solutions it seems like I was over-complicating the issue . It would especially work well when certain programs don't require virtual methods for some virtual types (for example if a program uses the SortedList class only internally and does not cast it to List, and never accepts a reference to a List object from external code that might be casted as something else), and those programs can forgo VFTs.

That's a case I hadn't thought of. In those cases, you can statically resolve them to SortedList (as you know at link time that there will be no derivate of SortedList).

Do you support overload-after-link-time which iirc most languages do? If so, you can't do this until JIT time when you should know.

Yes, I do. Any kind of static vs virtual resolution would be done at JIT time, since my intermediate code will not have a concept of virtual vs non-virtual methods. At link time some analysis will be done, however, to see what types could possibly undergo such optimizations.