How does method dispatch happen in Java?

 Have you ever wondered when you call a method like a list.add("Shamik"), How the actual method invoke in runtime?
If you want to discover the How part then you are in the right place else you can easily skip the article as it is not related to coding perspective. we know in Java we maintain two steps process
Compiler compiles and make the bytecodes
The interpreter takes bytecode and changes the instruction to machine code.
But think, When your code compiles to bytecode how the method call looks like and in the runtime how the dynamic linking happens, In a simple word how JVM find the actual method and call that method.
In this tutorial, we will discuss the same.
In java(till Java7) we have four types of method

1. Static methods.
2. private, package private or public methods
3. Interface methods declaration.
4. Some special methods like the constructor, super etc.

Now, as the actual method call happens at runtime, somehow at compile time(bytecode) we have to instruct JVM where to find the method or location of the method. But for some cases it is not possible to tell earlier(compile time) which method will be invoked( like in case of overriding, Polymorphism) so compiler has to defer the lookup of the method until runtime, so there are different types of opcodes are used by compiler to tell JVM what to do in runtime.
At runtime, JVM maintains a runtime table called vtable where each entry represents the precise location of the method. The help of this vtable, JVM actually dispatches the call to an actual method.
opcodes
In bytecode, java uses 4 opcodes still java6 but in java7 there is a new opcode introduced called invokedynamic, I will write a separate article on invokedynamic opcode but in this article, we will discuss the other opcodes.
invokestatic: invokestatic opcode is used at compile time to dispatch static methods.
invokevirtual: invokevirtual used to dispatch instance methods.
invokespecial: invokespecial is used to dispatch special methods like constructor or super or for the private method.
invokeinterface: invokeinterface is used to dispatch a method call via an interface.
Now, we will write a java example and try to see the bytecode representation of that example.

package com.example.methodcall;

import java.util.ArrayList;
import java.util.List;

public class MethodCall {

public void addCity() {
List<String> city = new ArrayList<String>();
city.add("Kolkata");

}


public void addState() {
ArrayList<String> state = new ArrayList<String>();
state.add("WestBengal");

}

public static void main(String[] args) {
MethodCall target = new MethodCall();
target.addCity();
target.addState();
}

}



Now I want to see the bytecode representation of the above java program so I will run the following command 

javap -c MethodCall.class 


Bytecode will look like following

 public class com.example.methodcall.MethodCall {
  public com.example.methodcall.MethodCall();
    Code:
       0: aload_0
       1: invokespecial #8                  // Method java/lang/Object."<init>":()V
       4: return

  public void addCity();
    Code:
       0: new           #15                 // class java/util/ArrayList
       3: dup
       4: invokespecial #17                 // Method java/util/ArrayList."<init>":()V
       7: astore_1
       8: aload_1
       9: ldc           #18                 // String Kolkata
      11: invokeinterface #20,  2           // InterfaceMethod java/util/List.add:(Ljava/lang/Object;)Z
      16: pop
      17: return

  public void addState();
    Code:
       0: new           #15                 // class java/util/ArrayList
       3: dup
       4: invokespecial #17                 // Method java/util/ArrayList."<init>":()V
       7: astore_1
       8: aload_1
       9: ldc           #31                 // String WestBengal
      11: invokevirtual #33                 // Method java/util/ArrayList.add:(Ljava/lang/Object;)Z
      14: pop
      15: return

  public static void main(java.lang.String[]);
    Code:
       0: new           #1                  // class com/example/methodcall/MethodCall
       3: dup
       4: invokespecial #39                 // Method "<init>":()V
       7: astore_1
       8: aload_1
       9: invokevirtual #40                 // Method addCity:()V
      12: aload_1
      13: invokevirtual #42                 // Method addState:()V
      16: return
}

Deep dive into the bytecode Representation :
In the above bytecode representation, except invokestatic all opcodes has been used.
If you noticed the bytecode minutely you can explore that for each method a section is entitled and each java line converted to a command. Let go through each method section

com.example.methodcall.MethodCall(): This is the constructor of MethodCall class, here you can find an invokespecial call because this opcode is used for calling a special method like constructor or super etc. if you pay attention to the commented line beside the invokespecial call you will find the method details
// Method java/lang/Object."<init>":() V: This says constructor can be found in java.lang.object which is detonated by a special symbol <init> and it takes nothing as an argument

 public void addCity():  In this section bytecode use invokeinterface opcode for  the line
List<String> city = new ArrayList<String>();
city.add("Kolkata");
and it is commented
as

// InterfaceMethod java/util/List.add:(Ljava/lang/Object;)Z which means add is an interface method  which is in java.util.List and it takes Object as an input argument.

Here invokeInterface opcode is used because, as we did the polymorphic assignment so at the compile time there is no way to know where is the actual add method implementation, so compiler has to put such opcode which will instruct JVM to dispatch the call to exact method from Vtable at runtime, so method resolution happens at runtime.

 public void addState():
In this section bytecode use invokevirtual opcode for  the line
ArrayList<String> state = new ArrayList<String>();
state.add("WestBengal");
and it is commented as

// Method java/util/ArrayList.add:(Ljava/lang/Object;)Z which means add can be found in java.util.ArrayList and it takes Object as an input argument.

There, is very subtle difference in coding -- we use ArrayList instead of List so it is not a polymorphic assignment so it creates a huge difference in bytecode now bytecode knows the exact class where to find the add method at compile-time but still call will be dispatched in runtime as if some other class can extend ArrayList. But it uses Invokevirtual opcode which is used for calling an instance method.

public static void main(java.lang.String[]): The last section is entitled to the main method where we call two instance methods addCity and addState so it uses invokevirtual opcode.

Conclusion : In this article we have a fair bit of an idea how method call is happened using different opcodes, But in Java7 an important opcode has been added that is invokeDynamic, which opens the door to allow dynamic type language in JVM, so other languages which run on top of JVM uses this invokeDynamic opcode to make them dynamic language certain extent also Lambda Expression in Java8 uses the invokedynamic opcode, In my next tutorial I will give a detailed overview on -- invokeDynamic opcode.

Read more

Oogways on Value Types(Project Valhalla)

Oogways promised us to give a demonstration on Project Valhalla, which is in roadmap of Oracle, Project Valhalla mainly focus on two features
1. Value types
2. Generic Specialization.
In this Article, I will cover the talk on Value type given by Oogways.let us get started what Oogways told us-- me and 5 Ninja warriors.
Oogways : we all know, to support primitives in Collection API--The Wrapper Object concept is created and java5 introduced autoboxing /unboxing feature, basically the motto of Autoboxing is to uplift primitives as an Object, so we can treat them as Object and Object's methods(equals, hashcode,toString) can be inherited to the Boxed Object so it can act as an Object and user(coder) does not have to bother about Boxing the primitives in a wrapper class, It will be done automatically and Vice versa.
So in developer's perspective, it is a huge improvement as you can play with collections and primitives and under the hood, all primitives get promoted to Object(Wrapper class, int->Integer). But in case of performance, it is not so good, to make developer happy Oracle compromised on the performance. Let us take a detailed look why the performance is degraded.

package com.example.valhalla;

public class PerformanceTest {

Integer[] boxedArray = new Integer[1000];

int[] primitiveArray = new int[1000];

public void insert() {

for (int i = 0; i < 1000; i++) {

boxedArray[i] = i;

primitiveArray[i] = i;

}

}

public void traveseBoxedArray() {

Long start = System.currentTimeMillis();

for(int i=0;i<boxedArray.length;i++) {

System.out.print(i);

}

System.out.println();

Long end = System.currentTimeMillis();

System.out.println("Time elapsed :: " + (end-start));

}

public void travesePrimitiveArray() {

Long start = System.currentTimeMillis();

for(int i=0;i<primitiveArray.length;i++) {

System.out.print(i);

}

System.out.println();

Long end = System.currentTimeMillis();

System.out.println("Time elapsed :: " + (end-start));

}

public static void main(String[] args) {

PerformanceTest test = new PerformanceTest();

test.insert();

test.traveseBoxedArray();

test.travesePrimitiveArray();

}

}

Output :
Case of Boxed Time elapsed:: 9
Case of primitive Time elapsed:: 6
So, Just in case of traversing boxed version and primitive version, there is a 3 Ms lag for 1000 elements. Not only in traversal there is also the side effect of memory consumption.
Why this performance degradation in case of Boxed version?
The performance degradation occurs due to the following reasons
Memory consumption :  One of the differences between Java primitives and Object is --there is a cost associated with Object, just to box an int to Integer , it has to create a header(8-16 byte) and reference(4-8 bytes) in case of a reachable object, so instead of 4 bytes(int-4 bytes) it takes 4+8+4=16 bytes minimum. Imagine the same for 1000 elements each, so heap space is consumed rapidly as the elements in the array are increased (Not considering JIT optimization).
Traversing for Payload: When we wrap primitives into a wrapper class, it will act as Object so now array of Integers stores the pointers unlike the array of primitives where array store the value itself, so there is an unnecessary cost to traverse through the pointer to fetch the actual value/payload. It will certainly take much more time than storing the value directly in the array.
Lack of Inherent Locality : Think about the Java memory model map , in case of primitives , value will get stored in register and is pushed to stack memory. In case of array of primitives it will occupy same contiguous memory , so cache hits is bigger than cache miss and traversal will be optimized and faster. On the another hand in case of Object (Wrapper class) it will get stored in heap memory and we don't know where it belongs in heap memory as JVM there are different spaces like young generation, eden etc and Objects are moved to that spaces so there will no contiguous memory allocated for array of Objects. So the array of objects lacks the inherent locality and also cache miss is greater than cache hits, so traversing through pointer will take more time than directly find value from a contiguous location.
Due to the above reasons, Boxing is bad in terms of performance. But in Java, there are many use cases where we use Boxing to achieve some functionality which can't be achieved by only primitives.
I will tell you what are those areas where we use unnecessary boxing and compromise performance to achieve some programmatic design decision.
Value Types : In java, Often we design some Object which just carrier of some data, its primary goal represents a data structure nothing else, It does not hold any state so there is no identity check once the values are same we can say two objects are same , so they are only caring for value, not the reference and state. think about a Point object or a Money Object or a Pin Code Object, which are the associations of some primitives / Objects, If the value is same we can say those two objects are equal, think about Money Object, it is the combination of currency and value which is char and double respectively.

package com.example.valhalla;

public final class Money {

public final double value;

public final char currency;

public Money(double value,char currency) {

this.currency=currency;

this.value=value;

}

public final void display() {

System.out.println(value + currency);

}

}

So, Money is immutable in nature and we wrap the value and currency into a Money Object which acts as Wrapper Object, But this Money does not do anything apart from encapsulating the primitives values. So performance got affected as Money is an Object rather than a collection of primitives, and we can't store value and currency into an array as those are the heterogeneous types and array support homogeneous typing.To support heterogeneous type we have to opt for an object and compromise the performance.
Wrapper Object: All primitives Wrapper types are degrading the performance.
Iterator: Iterator creates a snapshot of the collections to be traversed so it wraps the collection into an Iterator Objects which is nothing but a wrapper and degrades the performance.
Multi valued returns : Some time we need to return more than one value and those are heterogeneous type( like int, char,Object etc)  from a method , in other languages we can do it by Tuples concept but in case of java we have to wrap the return   value in to an object and return that Object, say I have a method which returns Address of a customer, and Address contains flat number, location, zip code, city, country -- so we have to create a wrapper Object which contains all these properties and return the Address so here Address Object acts as wrapper/boxed Object.
In the all above cases, we see a common problem to associate heterogeneous types we have to wrap it into a Object which act as Boxed type and compromise the performance as there is no other way in Java we can achieve Class like behavior (tied data and behaviors) but act as primitive type so we can benefit local inherent, less memory and fast performance.
Java architects addressed these problems and came up with a remarkable idea called Value Type under Project Valhalla.
The slogan of the project is “Codes like a class, works like an int!”
Seeing this slogan we can understand what they want to achieve. They want to create a new Datatype -- From developer's perspective, this act as a class and they can tie data and method together but in JVM it will act as primitive-- means it has no reference and stays in Stack memory !!!
If they really build this new datatype, it will solve performance issue without compromising the encapsulation because all the heterogeneous types act as user-defined primitives and store into the register so no pointer traversing is needed for getting payload.
Although, it is a remarkable idea and solves all design issues stated earlier without compromising performance but the road is not smooth-- there are many assumptions  involved to create the new Value type-- which code like a class and act as an int.
I will try to give an overview of what considerations are needed to create a new Datatype.
Equality Check: As Value type does not has a pointer, so how you check the equality for two value Objects, As Value Object is a composite data Structure so a probable solution will call equals or == for all associated components.
Null keyword: We know for Object null is the default value, but Value type is not an Object so what will be its default value? Probable solution would be default Value of ValueObject is setting the default value to all is sub-fields/association that is the initial state of ValueObject and that is set when Value Object initialized. And the null keyword for ValueObject should be disallowed.
Reference Cast: Value type is not an Object so it is not Reference type and it is not pointed by a reference, But to support those APIs which play with  Reference casting is needed, Value type should able to upgrade to reference type and vice versa as we do in the case with primitive boxing and unboxing.
Polymorphism: One of the powerful features of java is Polymorphism where parent reference can hold all the subtypes, but this is valid for only reference types which have a pointer. So at runtime pointer points to the corresponding subclass implementation. As Value type is pointer less and immutable in nature so the question is, should Value type allow Polymorphism? The Answer is no, it is Just a Value type. Although you are coding it like a class, inheritance should be disallowed as Valuetype does not carry any header information and used for flattening the associated Objects.
Cloning: Value type carry only information so Cloning does not make sense but it can be used as Identity transformation.
Till now, we have found  various use cases for using Value types, Now we will see how a Value Type may look like

package com.example.valhalla;

public final _ByValue class Money {

public final double value;

public final char currency;

public Money(double value,char currency) {

this.currency=currency;

this.value=value;

}

public final void display() {

System.out.println(value + currency);

}

 public boolean equals(Money that) {

     return this.currency == that.currency && this.currency == that.currency;

  }

}

Here, a new keyword _ByValue is used to instruct JVM to treat the class as a Value type so instead of pointing the Money Object it extracts Money's all component and create a space in the stack.
Next Question will come How we instantiate Value types.
Probably in the following way

Money money = __MakeValue(100, '$')

It will create a value type and store the currency and value properties into a stack.
So it flattens the Money Value type.

As Value type is neither Object and nor primitive we have still some questions about equality check. Let's see How Valuetype treats equality check.

Money money1 = __MakeValue(100, '$);

Money money2 = __MakeValue(100, '$);

now 

money1 == money2 (Do the Value equality check)

money1.equals(money2) (Do the Value equality check)

Object moneyWrapper1 = money1// Reference type

Object moneyWrapper2 = money2// Reference type 

moneyWrapper1 == moneyWrapper2 // Refrence check

moneyWrapper1.equals(moneyWrapper2)  // call Money Value types equals

Ok, we are got a fair bit of idea what are the challenges and how Oracle architects are trying to deal with the same to offer Value type in Java.

But if it ends here that would be fine but still, it has some advanced things to deal with and the probable answer to those questions are.

 Subtyping:
Value type can extends Reference type? No, because it is not an Object this is a new type.
Reference type extends a value type? No, because Valuetype does not have reference/pointer.
 Can a Value type class extend another value type? No, because  value types are final.)
 Can a value type be abstract or non-final? No abstract value type seems not worthwhile
 Can a value type implement interfaces? Yes. Boxing may occur when we treat a value type as an interface instance.
 Can values participate in inheritance-based subtyping? No, polymorphism not allowed.
Containment :
 Can a value class contain a field of the reference type? Yes because of a value type code like a class.
  Can a reference class contain a field of value type? Yes because it is just another type.
  Can a value type contain a component field of value type? Yes it is work like a class
  Can an array contain elements of value type? Yes works like an int. And the array itself is an object.
  Can a value class contain a non-final field? No as Value type is immutable.     
  Can values have member types? Yes. Non-static member types have hidden fields that record containing values.
 Can values be member types? Yes. If non-static, they have hidden fields that point to containing objects.

Compatibility
        Are values objects? No, although they can be boxed into objects.
        Are primitives values? Possibly. (Value classes named int, boolean, etc., would provide good successors to the existing wrapper types.
        Can value types be serialized? Not by default, since that would violate encapsulation.
          
Conclusion: Value type is a rich concept, Oracle is working hard to release this concept to efficiently manage the memory wasted for tiny objects which are acting as a wrapper or as the data carriers.

Read more