Does method invoke cost remain constant with more interface implementions

Question

Lets say we have an interface "ISomething" with the method "DoSomething".
And we create multiple classes that implement it. Example 5/10/100/1000 new class definitions.

will iterating a List < ISomething > and calling DoSomething() take the same amount of time, regardless of #unique classes added to the list. Assumption that list contains the same number of objects. Comparison list of different types vs list of same type.

Essentially I am asking if an interface method call is always a "Constant" runtime cost, or it depends on # unique types behind it.

Why am I asking this? I need to realise how interface works behinds the scenes to not trigger unexpected overhead.

Edit: Can I make the question a little harder ?
Lets consider the opposite scenario, we now have only 1 class but N interfaces it implements(ISomething1...N). Is the performance the same regardless on the #interfaces that it implements. Lets say that most of the interfaces end up pointing to the same method.

Edit2: adjan's answer raises another potential issue:
he said that c# generates one v-table per interface => all its methods cost O(1).

Lets consider the following scenario.
A vertical inheritance chain: A0 extends A1 extends A2 ... extends AN.
All these classes we construct them with no variables inside.
We just created a performance bug.

A0.method() costs O(N).
I0.method() costs O(1).

If interfaces can do the job with a constant overhead, why pay variable cost if someone abuses the inheritance mechanism and creates a vertical tree branch of depth N.

Does A0 virtual method cost O(N) ? What about its constructor, or its destructor, are we 100% safe to assume that it takes constant runtime cost. Regarding the constructor, a call to A0's constructor triggers A1's parameter-less constructor, thus the invocation chain continues... therefore O(N) cost.

About your second edit: There is no invocation chain. No matter how deep the inheritance tree is, invocation will be always O(1). There is no search for the right pointer to the v-table. The pointer is already determined when you declare the variable. — adjan, Jun 03 '17 at 13:14

BradleyDotNET · Answer 1 · 2017-06-04T22:36:46.253

First off; this kind of premature optimization is crazy. The overhead involved with invoking through an interface just isn't significant enough to matter.

That said, mixed types will not have a runtime impact unless you are dealing with branch prediction. (See Why is it faster to process a sorted array than an unsorted array?).

The reason for this is that you are incurring the overhead of invoking through a virtual function pointer table regardless of whether it picks the same one over and over or not. Really; its just not something you need to worry about.

score 3 · Answer 2 · answered Jun 02 '17 at 19:11

There is no difference.

Languages like java and C# implement virtual method calls in a way which is quite similar to the way C++ does it. Roughly speaking, each class has a virtual method table, which is an array of pointers to methods. There is one entry in this table for each virtual method defined by the class or interface. A virtual method call simply consists of picking a pointer from a specific index within that table and calling the function pointed by it. It makes no difference whether you have a single implementation or a hundred implementations. The runtime cost is as constant as it gets.

There is no operation that I can think of whose runtime complexity is in any way a function of the number of existing class implementations in the (Java or .Net) virtual machine.

adjan · Accepted Answer · 2017-06-03T04:14:24.440

When calling an interface method, a so called v-table is used to determine the memory address of the called method. Each type has its own v-table that contains pointers to each implemented method, and every object of that type has a pointer to its type's v-table. Thus, during method invocation, there is no branching or searching for the right memory address, since the pointers will always uniquely point to the right v-table and method addresses.

Also see this diagram:

Edit: Regarding your second question. There is no difference. A call to a virtual method costs always the same, because you're only accessing the same number of pointers:

interface I1
{
   void DoIt();
}


interface I2
{
   void DoIt();
}


class A : I1, I2
{
   public void DoIt()
   {
      // do sth
   }
}

// Note: All v-tables point to the same implementation in A

I1 test1 = new A();
test1.DoIt(); // => lookup in I1's v-table

I2 test2 = (I2)test1;
test2.DoIt(); // => Lookup in I2's v-table

A a = (A)test2;
a.DoIt(); // => Lookup in A's v-table

Image source: https://www.codeproject.com/KB/recipes/com-interception/vtable.png

Does method invoke cost remain constant with more interface implementions

3 Answers3