[JVM-1] Byte code file structure

Java byte code has a structure so that the virtual machine knows where to look for which information. Usually, an assembly program has the following structure.
Data segment:
  //goes constant
  //array initialization and declaration
  //global variables
Code segment:
  //several sub routines that act on top of the data segment.

Byte Code File Structure:
Byte code has similar structure. It's Data segment follows a very specific format.
  Class_File_Format {
     u4 magic_number;

     u2 minor_version; 
     u2 major_version;

     u2 constant_pool_count; 
   
     cp_info constant_pool[constant_pool_count - 1];

     u2 access_flags;

     u2 this_class;
     u2 super_class;

     u2 interfaces_count; 
   
     u2 interfaces[interfaces_count];

     u2 fields_count; 
     field_info fields[fields_count];

     u2 methods_count;
     method_info methods[methods_count];

     u2 attributes_count; 
     attribute_info attributes[attributes_count];
  }

constant pool is one of the main parts of the bytecode file. It hold's the constants, variable names, method names, interfaces this class implements etc.

One interesting this is the magic number at the beginning for any java byte code file is always OxCAFEBABE. JVM won't read this file if this magic number is not found at the begin.

Constructors:
In byte code files, constructors are treated differently. All the constructors are replaced by a bytecode method <init> (parameters).

// In source packet in file init/ex8/CoffeeCup.java
class CoffeeCup {
    public CoffeeCup() {
        //...
    }
    public CoffeeCup(int amount) {
        //...
    }
    // ...
}
the compiler would generate the following two instance initialization methods in the class file for class CoffeeCup, one for each constructor in the source file:

// In binary form in file init/ex8/CoffeeCup.class:
public void <init>(CoffeeCup this) {...}
public void <init>(CoffeeCup this, int amount) {...}

Reading byte code
java Test.java  ==> produces Test.class
xxd Test.class  ==> reads byte codes of the class
javap -verbose Test.class ==> view the constant pool area
javap -c Test.class  ==> only shows the instructions

Example:
  class Test{
    public static void main(String args[]){
      int i = 0;
      int j = 1;
      for(i = 0; i < 10; i++){
        j = j + 1;
      }
    }
  }

  javap -verbose Test.class output is following
    Classfile /Users/sa050870/Desktop/blog/javacompile/Test.class
    Last modified Oct 3, 2017; size 325 bytes
    MD5 checksum e48f946daadcae98c0ce5bcc07ac8094
    Compiled from "Test.java"
  class Test
    minor version: 0
    major version: 52
    flags: ACC_SUPER
  Constant pool:
     #1 = Methodref          #3.#13         // java/lang/Object."<init>":()V
     #2 = Class              #14            // Test
     #3 = Class              #15            // java/lang/Object
     #4 = Utf8               <init>
     #5 = Utf8               ()V
     #6 = Utf8               Code
     #7 = Utf8               LineNumberTable
     #8 = Utf8               main
     #9 = Utf8               ([Ljava/lang/String;)V
    #10 = Utf8               StackMapTable
    #11 = Utf8               SourceFile
    #12 = Utf8               Test.java
    #13 = NameAndType        #4:#5          // "<init>":()V
    #14 = Utf8               Test
    #15 = Utf8               java/lang/Object
  {
    Test();
      descriptor: ()V
      flags:
      Code:
        stack=1, locals=1, args_size=1
           0: aload_0
           1: invokespecial #1                  // Method java/lang/Object."<init>":()V
           4: return
        LineNumberTable:
          line 1: 0

    public static void main(java.lang.String[]);
      descriptor: ([Ljava/lang/String;)V
      flags: ACC_PUBLIC, ACC_STATIC
      Code:
        stack=2, locals=3, args_size=1
           0: iconst_0
           1: istore_1
           2: iconst_1
           3: istore_2
           4: iconst_0
           5: istore_1
           6: iload_1
           7: bipush        10
           9: if_icmpge     22
          12: iload_2
          13: iconst_1
          14: iadd
          15: istore_2
          16: iinc          1, 1
          19: goto          6
          22: return
        LineNumberTable:
          line 3: 0
          line 4: 2
          line 5: 4
          line 6: 12
          line 5: 16
          line 8: 22
        StackMapTable: number_of_entries = 2
          frame_type = 253 /* append */
            offset_delta = 6
            locals = [ int, int ]
          frame_type = 15 /* same */
  }
  SourceFile: "Test.java"
 

Reference
[0] object initialization in java. https://www.javaworld.com/article/2076614/core-java/object-initialization-in-java.html
[1] hacking java byte code. https://www.acloudtree.com/hacking-java-bytecode-for-programmers-part3-yes-disassemble-with-javap-all-over-the-place/
[2] Inside the Java 2 virtual machine. Bill Venners. http://www.artima.com/insidejvm/ed2/
[3] Java class file architecture, wikipedia. https://en.wikipedia.org/wiki/Java_class_file
[4] JVM specification. https://docs.oracle.com/javase/specs/jvms/se7/html/index.html

start from here https://www.javaworld.com/article/2076614/core-java/object-initialization-in-java.html?page=2

[Philosophy] In search of the true family

Today while walking through dense fog of Missouri, Kansas City a thought suddenly struck my mind. Why I keep running? I recalled my past. God knows, I worked as hard as hell to stand where I am standing today. Even when I was a young kid, I would wake up when it is still one or two hours for sun rise. I would wash my face with icy-cold water, I would pray to Almighty to show me path, to take me where I should go, then I would start my work. I would study and I stop only when it was time to go to school. If I wanted to do something, I never looked for a shortcut. I would always learn every material diligently, tried to think about them, understand them, never looked for memorizing something. I always wanted to go deep. Years after, even today I woke up at 5:30 in the morning, started looking at a MIT course material name "Hacking a Google code interview". During my undergrad days, I lost myself. I had a wrong thought that talent is all about something God-gifted. At this point of life, after realizing earnest and mindful work always beats a talent, I started educating myself again. I choose the topics that I felt I should be good at. So everyday, I would wake up at 5 am, educate myself on the knowledge I want to know. I would go to work, work for 9 hours, I would come back home take 2 hour of rest and from 7:30 pm I would start educating myself again. I have been doing this for days after days, months after months. I asked myself Why am I doing this?

Suddenly today my heart spoke. I have been living in several places. As I live in a place, I have to leave some of my parts there. With the help of that place, I transform some part of myself and become a modified person. I have to shed incompatible part of me that would not go with that place and let new parts grow in myself. May be, all I am looking for is a family. A family where members live under the shed of joy and respect. Their discussions are not trivial, their work is synergistic and solid. They don't take life for only merry-making. They work, think, reflect, invent, create necessity, fullfill the necessities and thus earn honest living. I believe, the members of true family do not grow up under the same roof. One member of the true family may be from Bangladesh, another may be from Africa, another may be from China, USA or Brazil. I have met many many people at many different parts of the world. I keep talking with them, I keep asking them what makes them happy. May be I do this because, someday, somewhere, some person will say something that will change my world forever. May be all these self modifications are taking me closer and closer to my family, to the people I truly belong. 

[JVM-0] Architecture of JVM

Java and Java Platform

Java has 4 core parts
  0. Language: a programmer uses it to write programs
  1. Class file format: java compiler translates it to byte codes to be executed by jvm
  2. JVM: an application that executes bytecode
  3. API: to interact with host machine

Java platform has 2 parts
  0. API
  1. JVM

A Java program runs on a Java platform.

Java program execution

Here are the steps to run a java program on a Java platform.

0. programmer writes java code

  class Test{
    public static void main(String args[]){
      int i = 0;
      int j = 1;
      for(i = 0; i < 10; i++){
        j = j + 1;
      }
    }
  }

1. Compile and produce byte code
              javac Test.java
bytecode has instruction that is targeted for a virtual architecture, java virtual machine.

javap -c Test.class produces the following output

class Test {
  Test();
    Code:
       0: aload_0
       1: invokespecial #1                  // Method java/lang/Object."<init>":()V
       4: return

  public static void main(java.lang.String[]);
    Code:
       0: iconst_0
       1: istore_1
       2: iconst_1
       3: istore_2
       4: iconst_0
       5: istore_1
       6: iload_1
       7: bipush        10
       9: if_icmpge     22
      12: iload_2
      13: iconst_1
      14: iadd
      15: istore_2
      16: iinc          1, 1
      19: goto          6
      22: return
}

2. user starts jvm by the command,

                java Test

Note: a jvm only runs a single application. jvm takes a class file as an agrument. the class file must have the main method with proper signature.

3. jvm loads, interprets the byte code and runs on host system.

Parts of JVM

0. Class loader: locates and imports byte code to jvm's memory.
    a. checks correctness of a type.
    a. on method area, loads byte code, initializes class variables. on heap creates Class object.
    b. links bytecode of method area with Class on heap.

there are two types of class loader
    a. bootstrap class loader: loads java api from installation location. this is part of jvm and written in c++ probably.
    b. user defined class loader: java classes created by user. these are objects in heap.

1. Method area: class loader loads byte code instructions to this place. For each class following information are stored
    a. fully qualified name of the type
    b. super class
    c. is it class or interface?
    d. modifier (public, abstract, final)
    e. constant pool: constants used by this type
        - string, int, float,
        - other classes used by this class (initially it holds only a symbolic link(fully qualified name), later when those classes are loaded to method area and in heap, those symbolic links are replaced by reference to class)
    f. field information (field name, type, modifier)
    g. method information
      0. name
      1. return type
      2. argument info
      3. modifier
      4. bytecode
      5. number of local variables
      6. size of operand stack
      7. exception table
    h.  class variable: all class's get a copy of static-final variable. static non-final are stored method area.
    i. class loader reference: reference to the loader that loaded this class.
    j. method table: instruction memory address for each method's start.

2. Java stack: each thread has separate java stack. only push and pop operations are allowed. contains stack frames for methods. each stack frame holds following information of a method
  a. parameters
  b. local variables
  c. operand stack
  d. return val
  e. return address
  f. exception table

      if an exception occurs and not catch clause found for that instruction, jvm causes the method return abruptly and re-throws the exception to the callers context.
one thread cannot access another thread's java stack.

3. Program counter: each thread gets one entry in the program counter (pc). pc remembers the next instruction to be run for a thread.

4. Heap: objects gets created in this area.

5. Execution engine: Fetches instructions from method area, translates and executes them. instructions acts on the data on java stack and heap. each thread is an execution engine. Interpreted byte code is cached and accessed if necessary.
2 popular techniques
  a. just in time compile: One by one, takes byte code, translates to native code, executes.
  b. adaptive: acts just like jit except as soon as it finds a code that is being used a lot of time(hot spot) it forks a thread. the thread heavily optimizes the code in hotspot and jvm in later time executes those optimized instructions.

6. Native method stack: holds frames for native methods. native methods works on the frame data and data in heap of JVM.

The following picture shows architecture of JVM

The following picture depicts Program counter and Java stack

** Object representation on JVM

** Thread Synchronization
Thread needs object locking and wait-notify mechanism to work.
calling the following methods on an object
  a. lock: a thread can access lock to an object. another thread has to wait to acquire the lock until the first thread unlocks the object.
  b. wait: a thread calls wait on an object. jvm puts the thread to the wait list of the object and makes it sleep. the thread sleeps until another thread calls notify or notify all
  c. notify and notify all: a thread calls this method on an object to notify the threads waiting on the object's wait list.

** Type of java threads
0. non-daemon thread: used by jvm. inital thread that starts a program, garbage collector.
1. daemon thread: created by running program.
As long as a non-daemon thread keeps running, the jvm would not stop unless exit method has not been called.

Atomic operations such as int, char operations makes sure a variable gets a value assigned either by one of the racing threads. if thread_1 tries to assign 0100 and thread_0 tries to assign 1011 to a variable x, it is guaranteed that x will have either 0100 or 1011 not any other values.

** Data types of jvm
a. reference type: holds object reference
b. primitive type: holds int, float. boolean false is stored as 0, any non-zero is stored as true. primitive types has same size and properties in all jvms. they don't depend on the host architecture.

As the jvm starts working, it's class loader loads byte codes to jvm's method area.

[Algorithms] Binary Search Tree (BST)

          parent
            / \
          /     \
        left    right

Binary search trees stores information (keys) holding some constraint. Each node holds some value. A left node holds value less than or equal to the parent node and right node holds value greater than parent node.

Motivation:
Interval scheduling problems can be solved efficiently with binary search trees. We will need to traverse left and right to see where a given interval should fit into. If that place is already taken or being overlapped by an existing interval, we discard the interval otherwise we insert it.

BST operations
0. insert : insert a key to the tree if the key does not already exist.
1. search : check if a key is present in the tree or not.
2. delete : delete a key if exist in the tree.

0. Insert
def insert (node, key):
  if node == null:
    return new Node(key)
  else if node.key == key:
    return node
  else if (node.key > key):
    node.left = insert(node.left, key)
  else:
    node.right = insert(node.right, key)

1. Search
def search(node, key):
  if node == null:
    return false
  if node.key == key:
    return true
  else if node.key > key:
    return search(node.left, key)
  else
    return search(node.right, key)

2. delete:
def delete(node, key):
  if node == null:
    return node
  if node.key == key:
    if node.left == null
      return node.right
    else if node.left.right == null
      return node.left
    else
      new_node = get_right_most(node.left)
      delete_right_most(node.left)
      new_node.left = node.left
      new_node.right = node.right
      return new_node
  else if node.key > key:
     node.left = delete(node.left, key)
  else
    node.right =  delete(node.right, key)
  return node

Augmented Binary Tree
When a binary tree holds information along with keys, it is called augmented binary tree. A common augmented BST is storing node counts of a subtree.

We will be discussing about the following binary search trees
0. avl tree
1 red-black tree
2. b-tree

AVL Tree
Self balancing binary trees. Balances herself using "rotate" operation. There can be log n number of rotations.
This tree is an augmented data structure. Every node contains the following information
  height of subtree
  left child
  right child
 
property:
  at any node, let h_left and h_right are left sub tree height and right sub tree height.
    |h_left - h_right| <= 1
  number of nodes, at worst case, N_h = 1 + N_(h-1) + N_(h-2) [because in best case both the left and right will be balanced]
  1 + N_(h-1) + N_(h-2) > 1 + 2 * N_(h-2) > 2 * N_(h-2)
  N_h > 2 * N(h-2)
  so number of nodes N = 2 ^ (h/2) => h = O(logn)

Rotation:
      x           <- left rotate                 y
    /   \         right rotate ->              /   \
   A     y                                    x     C
        / \                                  / \
       B   C                                A   B

in order traversal produces A x B y C for both the trees.

insert:
  simple bst insert
  fix avl property broken at any point of insertion. move up.

while insertion, the following cases can occur where AVL tree properties are broken at node x.
0. Right child is right heavy.

         x (h)          
       /   \      
(h-3) A     y (h-1)                                  
           / \                                
   (h-3)  B   C (h-2)                              

a left rotate against right child, y fixes the properties.

        y (h-1)
       / \
(h-2) x   C (h-2)
     / \
    A   B  [both A and B have h-3 height]

1. Right child is left heavy
                      x (h)          
                    /   \      
            (h-3) A     y (h-1)                                  
                       / \                                
               (h-2)  z   C (h-3)                              
                     / \
              (h-3) B   D (h-4)

              do a right rotate with respect to y

                  x (h)
                /   \
        (h-3)  A     z (h-1)
                    / \
            (h-3)  B   y (h-2)
                      / \
               (h-4) D   C (h-3)

        now we have the same situation as case 0. do as we did in case 0.

Mirror situation occurs for left heaviness.

[Algorithms] String search algorithms

String Matching Algorithms

problem: given two strings, s and t. does s occurs as a substring of t?

naive approach:

def substringSearch(t, s):
  for i in range(0..len(t)):
    matched = true
    for j in range(0..len(s)):
      if t[i+j] != s[j]:
        matched = false
        break
    if matched:
      return "String occurs"
  return "does not occur"

Runtime: O(m * n)

Rabin-Karp Algorithm:

def subStringSearch(t, s):
  len_s = len(s)
  pattern_hash = get_hash_val(s, 0, len_s)
  substr_hash = -1
  for i in range(0..len(t)-len(s)):
    substr_hash = get_hash(t, i, i+len_s, substr_hash)
    if substr_hash == pattern_hash:
      if t[i:i+len_s].matches(s):
        return true
  return false

def get_hash_val(s, start, end, prev_hash=-1):
  size_of_alphabet = SIZE_OF_ASCII_CHARS
  lowest_ascii_char = 'a'
  hash_val = 0
  if prev_hash == -1:
    for i in range(start..end):
      hash_val *= size_of_alphabet
      hash_val += (s[i] - lowest_ascii_char)
  else:
      start_char = s[start]
      hash_val = prev_hash * size_of_alphabet + (s[end] - lowest_ascii_char) - start_char * (size_of_alphabet ^ (end-start+1))

Analysis:
  if prev_hash = -1, hashing takes O(s)
  inside the for loop, hashing happens in O(1) time
  the hash function is designed in such a way that if two hash value equals then they are the same string.
  So for good hash function, O(n)
  for bad hash function O(m * n)

[Algorithms] Perfect Hashing: Guarantying constant time operation for hash function

For any hash function, it is possible to find a set of keys that will result O(n) time in search. In this article, I will talk about a scenario when we already know the keys, and we want to do the look up the keys in O(1) time even for the worst case.

Perfect Hashing Scheme:
We need two level hashing. In first level, we have n slots in hash table T where n = number of keys.
At level1, we use one hash function h_l1. Each slot of T contains 3 things
[number of items, hash function, pointer to array holding keys at level 2]

for any slot in T, size of key array in level 2 = (number of keys in level 2) ^ 2.

Index     Level-1         Level-2
0         [2 | 40 | ->]   [- | 40 | 37 | 27 ]
1         [1 | 01 | ->]   [- | 3 ]
2         [1 | 23 | ->]   [- | 25 ]
3         [0 | 19 | ->]   [ ]
4         [1 | 44 | ->]   [ 127 ]

at 0 index, level-1 slot has [2 | 40 | ->] this means, level-2 has 2 elements. So level-2 hash table will have size 2 ^ 2 = 4. the value 40 means universal hash function number 40, h_40 will be used to hash in level 2.

In level-1 there will be collision. We need to guarantee that in level-2 we can find hash functions that won't collide for m_i number of keys.

Proof:
x is a random variable that represents number of collisions in level-2 for a slot i. in i, level-2 has m_i number of keys. then hash table has size (m_i) ^ 2 slots. since, a universal hash function will be used probability of any two keys collide would be 1 / (m_i) ^ 2.

E[x] = sum (1/(m_i ^ 2)) for all keys x and y for given set of keys in level-2 at slot i.
we can make n Choose 2 combinations, so
E[x] = (m_i C 2) * (1/(m_i ^ 2)) < 1 / 2
E[x] <= 1/2

from Markov Inequality, P{x >= t} <= E[x] / t
P{x >= 1} <= E[x] / 2 <= 1/2    [0]
Equation [0], basically says, if we use universal hashing, at least half the cases there will be no collision. So randomly picking some hash functions from universal hashing should quickly yield a good hash function that does not do any collision for the given keys.

Space:
let x is a random variable denoting total space in level-2, then x = sum(n_i ^ 2), where n_0 + n_1 + ... + n_m  = n [n keys and m slots]
E[space] = n + E[x] = O(n)

Reference:
0. MIT OCW 6.046 : Introduction to Algorithms

[Algorithms] Keeping operations on a Hash table constant

In this article, I will discuss how to keep search operation's run time constant in a hash data structure.

Let the table T has m slots. If h is a universal hash function then, for key x and y where x != y
probability(x) = h(y)) = 1 / m
if the number of keys = n, on average every slot will have n / m keys. this is also known as load factor, alpha. So, alpha = n / m.
so each slot will have on average alpha number of keys. So expected number of searches would be O(1 + alpha).
To keep searching constant, we need to keep alpha constant.

As number of keys, n grows alpha starts increasing. If we want to keep alpha ~ 1, we need to increase size of our table. If we can handle
resizing of the table in constant time, we will be able to do operations in hash table in constant time.

Idea is If alpha hits a certain threshold, then we double size of T. This way insertion will be in amortized O(1) time.

Example: Lets say initially T has size m = 1. Insertion has cost O(1) for a hash table as all it does is insert the element at the head.
When we double the table, the cost of insertion goes to O(n) from 1. Fortunately, this does not happen very often, which makes average insertion operation a O(n) time operation. Below I have shown the key number and the order of the operation. When there is only one key, the insertion time is 1. If we add another key, we need to increase size of our table and then copy all the data from old table to new table. This cause O(n) time.

Key#     cost
1             1
2             2
3             1
4             4
5             1
6             1
7             1
8             8
9             1
10           1
11           1
12           1
13           1
14           1
15           1
-----------------
total cost for n insertion  =  (1+1+1..) + (2+4+8) = O(n)  # as the bigger value gets scarce as you keep doubling the table
amortized cost = avg cost per insertion = O(n/n) = O(1)

for n = 1000, the following Haskel code snippet counts average cost of insert operation.
a = sum([2 ^ x | x <- [0..100], 2 ^ x < 1000] ++ take 1000 (repeat 1)) `div` 1000
print a # prints 2

Deletion
Table size = n, number of keys = k. Half the table size when k = n / 4

References:
0. MIT OCW 6.006 Introduction to Algortihms
1. MIT OCW 6.046J Introduction to Algorithms