Java Concurrency - Barrier

In this series we will discuss different concurrent structures provided in the new Java 5 Concurrent package. We will start with a simple parallel processing concept called "barrier" that we have all studied and forgotten. By definition if there are set of independent tasks (T1..Tn) that need to fully completed to initiate another task (Tx) which is dependent on all these tasks (T1...Tn) we can synchronize them using a barrier.


why is the barrier not more commonly used?
The functionality is simple enough that it can be accomplished with the low-level tools provided by Java. We can solve the coordination problem in two ways, without using a barrier.

First, we can simply have the threads wait on a condition variable. The last thread releases the barrier by notifying all of the other threads.

A second option is to simply await termination of the threads by using the join() method. Once all threads have been joined, we can start new threads for the next phase of the program

 However, in some cases it is preferable to use barriers. When using the join() method, threads are exiting and we're starting new ones. Therefore, the threads lose any state that they have stored in their previous thread object; they need to store that state prior to terminating. Furthermore, if we must always create new threads, logical operations cannot be placed together; since new threads have to be created for each subtask, the code for each subtask must be placed in separate run() methods. It may be easier to code all of the logic as one method, particularly if the subtasks are very small.

CyclicBarrier – a pair of threads computes the sum of all numbers in a
matrix by iterating over neighbour rows. Imagine you have a matrix (with an
even number of columns). You want to sum all its elements using 2 threads. The
simple way is to run 2 threads from inside main () to process rows 0 and 1, wait
(using busy-wait) until computation is complete; sum the resulting values; then
run 2 threads on rows 2 and 3, wait, sum and so on. This is demonstrated in
cyclsimple example

Below is the example:

package Barrier;
import java.util.concurrent.BrokenBarrierException;
import java.util.concurrent.CyclicBarrier;
public class CyclicBarrierExample
{
    private static int matrix[][] =
    {
        { 1 },
        { 2, 2 },
        { 3, 3, 3 },
        { 4, 4, 4, 4 },
        { 5, 5, 5, 5, 5 } };

    private static int results[];

    private static class Summer extends Thread
    {
        int row;

        CyclicBarrier barrier;

        Summer(CyclicBarrier barrier, int row)
        {
            this.barrier = barrier;
            this.row = row;
        }

        public void run()
        {
            int columns = matrix[row].length;
            int sum = 0;
            for (int i = 0; i < columns; i++)
            {
                sum += matrix[row][i];
            }
            results[row] = sum;
            System.out.println("Results for row " + row + " are : " + sum);
            // wait for others
            try
            {
                barrier.await();
            } catch (InterruptedException ex)
            {
                ex.printStackTrace();
            } catch (BrokenBarrierException ex)
            {
                ex.printStackTrace();
            }
           
           
        }
    }

    public static void main(String args[])
    {
        final int rows = matrix.length;
        results = new int[rows];
        Runnable merger = new Runnable()
        {
            public void run()
            {
                int sum = 0;
                for (int i = 0; i < rows; i++)
                {
                    sum += results[i];
                }
                System.out.println("Results are: " + sum);
            }
        };
        /*
         * public CyclicBarrier(int parties,Runnable barrierAction)
         * Creates a new CyclicBarrier that will trip when the given number
         * of parties (threads) are waiting upon it, and which will execute
         * the merger task when the barrier is tripped, performed
         * by the last thread entering the barrier.
         */
        CyclicBarrier barrier = new CyclicBarrier(rows, merger);
        for (int i = 0; i < rows; i++)
        {
            new Summer(barrier, i).start();
        }
        System.out.println("Waiting...");
    }
}

output :

Results for row 0 are : 1

Waiting...

Results for row 2 are : 9

Results for row 4 are : 25

Results for row 3 are : 16

Results for row 1 are : 4

Results are: 55

To access the source code:
https://bitbucket.org/nkancharla/javaexamples/src/bf0dcc13573e0782807788b99e934b64f592dd41/Barrier?at=master

Creating java objects without calling constructors

If the object is serializable, then it is created magically without having the constructor called. This means if a class implements Serializable interface then that class constructor wont be called while Deserialization process.

See below example for more details.


public class parent {
  public parent() {
    System.out.println("parent constructor called");
  }
}



import java.io.Serializable;

public class child extends parent implements Serializable {
   public child() {
      System.out.println("child constructor called");
   }
}


import java.io.*;
public class DeserializeTest {
  public static void main(String[] args) throws IOException, ClassNotFoundException {
    child ms = new child();
    // writing object to byte[]
    System.out.println("writing ms");
    ByteArrayOutputStream baos = new ByteArrayOutputStream();
    ObjectOutputStream oos = new ObjectOutputStream(baos);
    oos.writeObject(ms);
    oos.close();
    byte[] objectInBinaryForm = baos.toByteArray();

    // reading object from byte[]
    System.out.println("....Deserialization flow");
    System.out.println("reading ms2");
    ObjectInputStream ois = new ObjectInputStream( new ByteArrayInputStream(objectInBinaryForm) );
    child ms2 = (child) ois.readObject();
    System.out.println("ms == ms2 = " + (ms == ms2));
    System.out.println("ms = " + ms);
    System.out.println("ms2 = " + ms2);
  }
}

The output is the following, note the number of times that each constructor is called:

parent constructor called

child constructor called

writing ms

....Deserialization flow

reading ms2

parent constructor called

ms == ms2 = false

ms = mySerialization.child@1a626f

ms2 = mySerialization.child@95fd19

While deserialization child constructor is not called. but still we got object after deserialzation.

Can you guess how it is done?

Below code will explain you in detail.

For example, to simulate what happens in the DeserializeTest, we could call it with

      SilentObjectCreator.create(child.class, parent.class)
    

Here is my SilentObjectCreator, used to instantiate objects without invoking any constructors:


import sun.reflect.ReflectionFactory;
import java.lang.reflect.Constructor;
public class SilentObjectCreator {

  public static <T> T create(Class<T> clazz) {
    return create(clazz, Object.class);
  }

  public static <T> T create(Class<T> clazz,
                             Class<? super T> parent) {
    try {
      ReflectionFactory rf =  ReflectionFactory.getReflectionFactory();
      Constructor objDef = parent.getDeclaredConstructor();
      Constructor intConstr = rf.newConstructorForSerialization( clazz, objDef );
      return clazz.cast(intConstr.newInstance());
    } catch (RuntimeException e) {
      throw e;
    } catch (Exception e) {
      throw new IllegalStateException("Cannot create object", e);
    }
  }
}


Lets test with our test class below


public class Creatiopublic class CreationTest {
   public static void main(String[] args) {
     // Creating child by calling parent no-args constructor, but not the child constructor.
    System.out.println("Creating child by calling parent no-args constructor, but not the child constructor");
    child ms = SilentObjectCreator.create( child.class, parent.class);
     System.out.println("ms = " + ms);
     // Creating child by not calling any constructors.
     System.out.println("Creating child by not calling any constructors");
     child ms2 = SilentObjectCreator.create( child.class );
     System.out.println("ms2 = " + ms2);
   }
}

In the output we see that in the first case, the NotSerializable constructor is called, but not in the second:

Creating child by calling parent no-args constructor, but not the child constructor

parent constructor called

ms = mySerialization.child@f9f9d8

Creating child by not calling any constructors

ms2 = mySerialization.child@112f614

We can use this mechanism to create just about any class, except abstract classes.

LinkedHashMap and IdentityHashMap

A LinkedHashMap is a combination of hash table and linked list. It has a predictable iteration order (a la linked list), yet the retrieval speed is that of a HashMap. The order of the iteration is determined by the insertion order.

We have a requirment say want to retrieve rows from a database table and convert these rows to Java Objects. Let us also imagine we are not using JDO. We need the elements in some order, and we need to search on keys quickly.

Before JDK 1.4, I would probably have made the objects Comparable and inserted them into a TreeMap. TreeMap works with a type of balanced binary tree, so the lookup would be O(log2n). If we have 1024 elements, it will take at most ten lookups. This is worse than a HashMap with a good hash function, which should only take one lookup. Keeping the tree balanced is expensive since it involves shuffling the nodes around whenever one side of the tree becomes too deep. Inserting the elements into a TreeMap is probably more expensive than sorting in your database, since the database is optimised for such things.

With the LinkedHashMap we get the best of both worlds. We can let the database do the sorting, retrieve the rows and insert them into the LinkedHashMap. This way we can retrieve them quickly via the HashMap mechanism, but we can still iterate through them in the sorted order.

To illustrate
Student class with roll number, name and DOB.

package LinkedHashMapTest;

import java.text.DateFormat;

import java.text.SimpleDateFormat;

import java.util.Date;

public class Student {

private final String id;

private final String name;

private final Date dateofbirth;

public Student(String id, String name, Date dateofbrith)

{      

               this.name = name;

this.id = id;

this.dateofbirth = dateofbrith;

}

private final static DateFormat df = 

   new SimpleDateFormat("yyyy/MM/dd");

 public String toString() {

   return name + " born on " + df.format(dateofbirth);

 }

public String getId() {

return id;

}

public String getName() {

return name;

}

public Date getDateofbirth() {

return dateofbirth;

}

public int hashCode(){

return id.hashCode();

}

public boolean equals(Object obj)

{

if(!(obj instanceof String))  return false;

String key = (String)obj;

return id.equals(key);

}

}

Now define Interface Department.
public interface Department
{
   Student[] getStudents();
}

Define ComputerScient Department with students

import java.util.Date;

public class ComputerScienceDepartment implements Department {

private final static Student[] students = {

new Student("19", "Keerthi", new Date(88, 11, 25)),

new Student("01", "Kanish", new Date(99, 07, 27)),

new Student("22", "Naresh", new Date(81, 02, 07)),

new Student("11", "Avi", new Date(82, 05, 07)),

new Student("44", "Vedh", new Date(84, 03, 10)),

new Student(new String("44"), "Vedh", new Date(84, 03, 10)),

};

@Override

public Student[] getStudents() {

return students;

}

}

Note that the students are sorted by name. We assume that the students would be retrieved in that sort order from the database. We can see the difference between the HashMaps from this example: 

IdentityHashMap as name suggests uses the equality operator(==) for comparing the keys. So when you put any Key Value pair in it the Key Object is compared using == operator

import java.util.*;

public class LinkedHashMapTest {

  private static void fill(Map players, Department sd) {

    Student[] p = sd.getStudents();

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

      players.put(p[i].getId(), p[i]);

    }

  }  

  private static void test(Map players, Department sd) {

    System.out.println("Testing " + players.getClass().getName());

    fill(players, sd);

    for (Iterator it = players.values().iterator(); it.hasNext();) {

      System.out.println(it.next());

    }

    System.out.println();

  }  

  public static void main(String[] args) {

    Department sd = new ComputerScienceDepartment();

    test(new HashMap(), sd);

    test(new LinkedHashMap(), sd);

    test(new IdentityHashMap(), sd);

  }

}

When we run this code, we get the following output:

Testing java.util.HashMap

Vedh born on 1984/04/10

Hanuman born on 1988/12/25

Naresh born on 1981/03/07

Kanish born on 1999/08/27

Sairam born on 1982/06/07

Testing java.util.LinkedHashMap

Hanuman born on 1988/12/25

Kanish born on 1999/08/27

Naresh born on 1981/03/07

Sairam born on 1982/06/07

Vedh born on 1984/04/10

Testing java.util.IdentityHashMap

Hanuman born on 1988/12/25

Kanish born on 1999/08/27

Vedh born on 1984/04/10

Sairam born on 1982/06/07

Naresh born on 1981/03/07

Vedh born on 1984/04/10

LRU Cache
Another application for the LinkedHashMap is in building LRU caches. One of the constructors allows us to specify that we use access order instead of insert order. The order is from least-recently accessed to most-recently. You can override the removeEldestEntry(Map.Entry) method to impose a policy for automatically removing stale when new mappings are added to the map.

JAXB basic example

JAXB - Java to xml binding and vice versa.

This blog is helpful for those who are new to jaxb. It just helps you to start.

1) Create java classes from xsd(if you dont have xsd use trang to generate one.). To create java classes we can use xjc.
2) Annotated java classes will be created.
3) compile the java classes.
3) Modify java classes and write marshall(Java -> xml) code inside the main method of the class.
4) Now you will get xml from the java object as part of marshalling.
for unmarshalling( xml --> Java) modify code at step3 with unmarshalling code and run the java class.
See below code for more information.

Here I am giving simple startup example on windows.

1) Download the binary and execute the jar
http://jaxb.java.net/2.2.3u2/
> java -jar JAXB2_20110412.jar
After running above command you will get a folder with name "jaxb-ri-20101209"

2) set windows classpath to C:\jaxb-ri-20101209\bin. This is to get xjc on classpath. xjc is used to generate java classes from xml.

3) Use Employee.xsd as shown below

 <?xml version="1.0" encoding="UTF-8"?>
<xs:schema xmlns:xs="http://www.w3.org/2001/XMLSchema" elementFormDefault="qualified">
  <xs:element name="employee">
    <xs:complexType>
      <xs:sequence>
        <xs:element ref="firstName"/>
        <xs:element ref="middleName"/>
        <xs:element ref="lastName"/>
      </xs:sequence>
      <xs:attribute name="id" use="required" type="xs:integer"/>
    </xs:complexType>
  </xs:element>
  <xs:element name="firstName" type="xs:NCName"/>
  <xs:element name="middleName" type="xs:NCName"/>
  <xs:element name="lastName" type="xs:NCName"/>
</xs:schema>
4) run below command to genreate java classes from the xsd
     xjc Employee.xsd
5) Below Java Class will be generated

import javax.xml.bind.JAXBException;
import javax.xml.bind.annotation.XmlAccessType;
import javax.xml.bind.annotation.XmlAccessorType;
import javax.xml.bind.annotation.XmlAttribute;
import javax.xml.bind.annotation.XmlElement;
import javax.xml.bind.annotation.XmlRootElement;
import javax.xml.bind.annotation.XmlSchemaType;
import javax.xml.bind.annotation.XmlType;
import javax.xml.bind.annotation.adapters.CollapsedStringAdapter;
import javax.xml.bind.annotation.adapters.XmlJavaTypeAdapter;

@XmlAccessorType(XmlAccessType.FIELD)
@XmlType(name = "", propOrder = {
    "firstName",
    "middleName",
    "lastName"
})
@XmlRootElement(name = "employee")
public class Employee {

    @XmlElement(required = true)
    @XmlJavaTypeAdapter(CollapsedStringAdapter.class)
    @XmlSchemaType(name = "NCName")
    protected String firstName;
    @XmlElement(required = true)
    @XmlJavaTypeAdapter(CollapsedStringAdapter.class)
    @XmlSchemaType(name = "NCName")
    protected String middleName;
    @XmlElement(required = true)
    @XmlJavaTypeAdapter(CollapsedStringAdapter.class)
    @XmlSchemaType(name = "NCName")
    protected String lastName;
    @XmlAttribute(name = "id", required = true)
    protected int id;

    /**
     * Gets the value of the firstName property.        
     */
    public String getFirstName() {
        return firstName;
    }

    /**
     * Sets the value of the firstName property.        
     */
    public void setFirstName(String value) {
        this.firstName = value;
    }

    /**
     * Gets the value of the middleName property.       
     */
    public String getMiddleName() {
        return middleName;
    }

    /**
     * Sets the value of the middleName property.    
     */
    public void setMiddleName(String value) {
        this.middleName = value;
    }

    /**
     * Gets the value of the lastName property.    
     */
    public String getLastName() {
        return lastName;
    }

    /**
     * Sets the value of the lastName property.        
     */
    public void setLastName(String value) {
        this.lastName = value;
    }

    /**
     * Gets the value of the id property.        
     */
    public int getId() {
        return id;
    }

    /**
     * Sets the value of the id property.     
     */
    public void setId(int value) {
        this.id = value;
    }
}
 

6) Add below jars to the project build path in the eclipse.

activation-1.1.jar
jaxb-api-2.0.jar
jaxb-impl-2.0.5.jar
jsr173_api-1.0.jar
jaxb-xjc.jar

7) Now modify your java class by adding main method for marshalling  i.e. java to xml.
public static void main(String args[]) throws JAXBException{
     Employee greg = new Employee();
     greg.setId(1);
     greg.setFirstName("Greg");   
     greg.setMiddleName("");
     greg.setLastName("Loyd");
   
     //java object to xml converstion    MARSHALLING
     JAXBContext jaxbContext = JAXBContext.newInstance(Employee.class);
     StringWriter stringWriter = new StringWriter();
     jaxbContext.createMarshaller().marshal(greg, stringWriter);   
     System.out.println("....Marshalling....."+  stringWriter.toString());
}

8) compile above java class. You will get xml in a string fromat.

9) Modify same java class for unmarshalling.

public static void main(String args[]) throws JAXBException{
Employee greg = new Employee();
greg.setId(1);
greg.setFirstName("Greg");
greg.setMiddleName("");
greg.setLastName("Loyd");
//java object to xml converstion MARSHALLING
JAXBContext jaxbContext = JAXBContext.newInstance(Employee.class);
StringWriter stringWriter = new StringWriter();
jaxbContext.createMarshaller().marshal(greg, stringWriter);
System.out.println("....Marshalling....."+ stringWriter.toString());
//End stringWriter is an xml
//xml to java object
Employee gregUnmarshal = (Employee)jaxbContext.createUnmarshaller().unmarshal(new StringReader(stringWriter.toString()));
if(greg.equals(gregUnmarshal)){
   System.out.println("....marshal and unmarshal objects are same");
}else{
   System.out.println("....marshal and unmarshal objects are not same");
}
}

package generated;
10) Run the java class and you get output for both marshalling and unmarshalling.

....Marshalling.....<?xml version="1.0" encoding="UTF-8" standalone="yes"?><employee id="1"><firstName>Greg</firstName><middleName></middleName><lastName>Loyd</lastName></employee>

....marshal and unmarshal objects are same

Find loop in a linked list

We have to maintain two pointers one slow pointer that moves one node at a time and a fast pointer that moves two nodes at  a time.

#include <stdio.h>
#include <stdlib.h>

struct linkedList{
    int number;
    struct linkedList* next;
};

typedef struct linkedList* NODE;

int FindLoop(NODE *head)
{
    NODE *fastPtr, *slowPtr;
    fastPtr = slowPtr = head;
    while(1)
    {
        if(!fastPtr || !fastPtr->next)
            return 0;
        else if(fastPtr == slowPtr || fastPtr ->next == slowPtr)
            return 1; // Loop Exist
        else{
            slowPtr = slowPtr->next;
            fastPtr = fastPtr->next->next;
        }
    }
    return 0;
}