Tuesday, October 9, 2012

Demonstrating usage of a Binary Search Tree in Java

What is a Binary Search Tree?

Binary Search Tree (BST) is a tree in which each node has up to two child nodes (subtrees).  If pointers are used, then each node contains references to the left, right, and parent nodes.  Otherwise, like the implementation I found for Java, each node contains a left and right subtree in the form of a left and right node (each of which have their own two subtrees and so on...) along with the data associated with the node.

A BST is said to have a binary-search-tree property:

Let x be a node in a binary search tree. If y is a node in the left subtree of x, then key[y] <= key[x]. If y is a node in the right subtree of x, then key[x] <= key[y].1

Since Java doesn't have pointers that we can use, we won't keep track of keys. We'll work directly with node data.

Cormen et-all mention that BSTs support the following operations:

Search trees are data structures that support many dynamic-set operations, including
SEARCH, MINIMUM, MAXIMUM, PREDECESSOR, SUCCESSOR, INSERT, and
DELETE. Thus, a search tree can be used both as a dictionary and as a priority
queue.


What are some applications of BST?

This StackOverflow question answers this well:
What are the applications of binary trees?

Apparently, it is also used in the solution to the Traveling Salesman Problem and the related Shortest Path Problem. I'll be checking these out soon.


How do I use a BST in Java?

I found a good Java BST impl here:
BST.java
BSTNode.java

Class BST contains a root BSTNode node and provides most BST operations (as identified by Cormen et-all). The PREDECESSOR and SUCCESSOR operations are not implemented. Search is implemented, though not exposed directly (it's exposed as isInTree(T el)).

I've slapped together an Eclipse project that demonstrates the usage of this BST implementation. I added some code to BST.java (the one in the Eclipse project) borrowed from this Stanford CS Library page on BSTs. I also borrowed some inspiration from this SO page: How to print binary tree diagram. The class BTreePrinter in the project is pretty much directly from this SO page.

It would be worthwhile to study at least the BST.java and BSTNode.java.

>Download BST_Demo (Eclipse Project)

Here is the output:


>String arrays:
ACEG:  [Aliyah, Chris, Elijah, Gamal]
BDFH:  [Brian, Doug, Farah, Hasan]

>Insert ACEG:
Aliyah Chris Elijah Gamal 

>Insert BDFH:
Aliyah Brian Chris Doug Elijah Farah Gamal Hasan 

>Removing 'Aliyah':
Brian Chris Doug Elijah Farah Gamal Hasan Aliyah Brian Chris Chris Doug Elijah Elijah Farah Gamal Gamal Hasan 

>Clearing bst.

>Reinserting both arrays:
Aliyah Brian Chris Doug Elijah Farah Gamal Hasan 

>Search for 'Irene':
false

>Search for 'Aliyah':
true

>Postorder: 
Brian Doug Farah Hasan Gamal Elijah Chris Aliyah 
>Postorder (iterative): 
Brian Doug Farah Hasan Gamal Elijah Chris Aliyah 
>Postorder (Morris): 
Brian Doug Farah Hasan Gamal Elijah Chris Aliyah 

>Preorder: 
Aliyah Chris Brian Elijah Doug Gamal Farah Hasan 
>Preorder (iterative): 
Aliyah Chris Brian Elijah Doug Gamal Farah Hasan 
>Preorder (Morris): 
Aliyah Chris Brian Elijah Doug Gamal Farah Hasan 

>Size:
8

>Max depth:
5

>Min val:
Aliyah

>Max val:
Hasan

Aliyah Brian Chris Doug Elijah ElijahGamal Farah Gamal Hasan 

>Print all root-leaf paths:
Aliyah Chris Brian 
Aliyah Chris Elijah Doug 
Aliyah Chris Elijah Gamal Farah ElijahGamal 
Aliyah Chris Elijah Gamal Hasan 


>Mirroring bst:
Aliyah Brian Chris Doug Elijah ElijahGamal Farah Gamal Hasan 
Hasan Gamal Farah ElijahGamal Elijah Doug Chris Brian Aliyah 

>Doubling bst:
Hasan Hasan Gamal Gamal Farah Farah ElijahGamal ElijahGamal Elijah Elijah Doug Doug Chris Chris Brian Brian Aliyah Aliyah 

>bst:
Aliyah Brian Chris Doug Elijah Farah Gamal Hasan 
>bst2:
Aliyah Brian Chris Doug Elijah Farah Gamal Hasan 
>bst identical to bst2?:
true

>Possible unique trees given this bst's size: (8)
1430

>Check bst:
true

>Printing bst (bad spacing):
               Aliyah                               
                      \               
                       \              
                        \             
                         \            
                          \           
                           \          
                            \         
                             \        
                       Chris               
                      /      \       
                     /        \      
                    /          \     
                   /            \    
                   Brian       Elijah       
                          /       \   
                         /         \  
                         Doug   Gamal   
                            /      \ 
                            Farah Hasan 
                                                                

>Another bst print:
'- Aliyah
    '- Chris
        '- Brian
        '- Elijah
            '- Doug
            '- Gamal
                '- Farah
                '- Hasan

>Inst and init int bst (unbalanced because of ordered insert):
'- 1
    '- 2
        '- 3
            '- 4

Unbalanced integer tree:
       1               
        \       
         \      
          \     
           \    
           2       
            \   
             \  
             3   
              \ 
              4 
                                

Cleared and intBst.balance(intArr):
'- 2
    '- 1
    '- 3
        '- 4

>Balanced integer tree:
   2       
  / \   
 /   \  
 1   3   
      \ 
      4 
                


1 Introduction to Algorithms Second Edition (Cormen, Leiserson, Rivest, Stein), page 254

Posted by at No comments:

Thursday, October 4, 2012

Synchronization and Thread Safety in Hashtable, Hashmap, ConcurerntHashMap

Coming across blog entry "Who said Java Hashtable is thread safe?", I decided to run the code.  He's right in saying that Hashtable isn't thread safe, though, I don't think such a claim was ever officially made.  Maybe if there is allusion among some that it is, then I suppose it needs dispelling.  Thread safety is a design challenge.  Fully synchronized classes, and even completely thread-safe classes can be used inefficiently, or worse, incorrectly, in a concurrent system.

Here are three examples of thread unsafe usage, followed by three examples of safe usage:

1. Unsafe

package unsafe.demo;

import java.util.HashMap;
import java.util.Map;

import unsafe.threads.Unsafe_Hashmap_NoSynchronized_NotUsingContainsKey;

public class DemoThreadUnsafe {
  private Map<Integer, String> map = new HashMap<Integer, String>();

  public static void main(String[] args) throws InterruptedException {
    for (int j = 1; j < 200; j++) {
      DemoThreadUnsafe demoClass = new DemoThreadUnsafe();
      for (int i = 0; i < 5; i++) {
        new Thread(new Unsafe_Hashmap_NoSynchronized_NotUsingContainsKey(demoClass.map)).start();
      }
      Thread.currentThread().sleep(10);
      System.out.println(demoClass.map.keySet());
      demoClass.map.clear();
    }
  }
}

1. Unsafe cont.

package unsafe.threads;

import java.util.Map;

/**
 * put operation is not safe on the map because its impl in 
 * hashmap (used by calling thread) is not synchronized
 * based on: http://lovehasija.com/2012/08/16/who-said-java-hashtable-is-thread-safe/
 * 
 * @author sshakil
 *
 */
public class Unsafe_Hashmap_NoSynchronized_NotUsingContainsKey implements Runnable {
  private Map<Integer, String> map = null;

  public Unsafe_Hashmap_NoSynchronized_NotUsingContainsKey(Map<Integer, String> map) {
    this.map = map;
  }

  @Override
  public void run() {
    for (int i = 1; i <= 30; i++) {
      try {
        map.put(i, Thread.currentThread().getName());
      } catch (Exception e) {
        System.out.println(e);
      }

    }
  }
}


2. Unsafe
package unsafe.demo;

import java.util.Hashtable;
import java.util.Map;

import unsafe.threads.Unsafe_Hashtable_NoSynchronized_UsingContainsKey;

public class DemoThreadUnsafe2 {
  private static volatile Map<Integer, String> map = new Hashtable<Integer, String>();

  public static void main(String[] args) throws InterruptedException {
    for (int j = 1; j < 200; j++) {
      DemoThreadUnsafe2 demoClass = new DemoThreadUnsafe2();
      for (int i = 0; i < 10; i++) {
        new Thread(new Unsafe_Hashtable_NoSynchronized_UsingContainsKey(demoClass.map)).start();
      }
      Thread.currentThread().sleep(100);
      demoClass.map.clear();
    }
  }
}


2. Unsafe cont.

package unsafe.threads;

import java.util.Map;

/**
 * the sequence of map.containsKey(i) followed by the map.put sequence is not
 * safe because map's impl in hashmap (used by calling thread) is not
 * synchronized based on:
 * http://lovehasija.com/2012/08/16/who-said-java-hashtable-is-thread-safe/
 * 
 * @author sshakil
 * 
 */
public class Unsafe_Hashtable_NoSynchronized_UsingContainsKey implements Runnable {

  private static volatile Map<Integer, String> map = null;

  public Unsafe_Hashtable_NoSynchronized_UsingContainsKey(Map<Integer, String> map) {
    this.map = map;
  }

  @Override
    public void run() {

         for (int i = 1; i <= 30; i++) {
          synchronized(map) {
             if(!map.containsKey(i)) {
                 //some other thread can modify data between the execution of 
                 //above and below lines
                 //try to catch it:
                 if(map.containsKey(i)) {
                   try {
              throw new Exception ("Detected mofification by another thread.");
            } catch (Exception e) {
              // TODO Auto-generated catch block
              e.printStackTrace();
            }
                 }
                 //more modifications can occur any time in above block
                System.out.println( Thread.currentThread().getName() 
                    + "\tInserting new, Key exists: " + map.containsKey(i));
                map.put(i, Thread.currentThread().getName());
             }
             }
        }
    }
}


3. Unsafe

package unsafe.demo;

import java.util.concurrent.ConcurrentHashMap;

import safe.threads.Safe_Hashtable_Synchronized_UsingContainsKey;
import unsafe.threads.Unsafe_ConcurrentHashMap_NoSynchronized_UsingContainsKey;


public class DemoThreadUnsafe3 {

  // private Map<Integer, String> map = new Hashtable<Integer, String>();
  private ConcurrentHashMap<Integer, String> map = new ConcurrentHashMap<Integer, String>();

  public static void main(String[] args) throws InterruptedException {

    for (int j = 1; j < 2000; j++) {
      DemoThreadUnsafe3 demoClass = new DemoThreadUnsafe3();

      for (int i = 0; i < 15; i++) {
        new Thread(
            new Unsafe_ConcurrentHashMap_NoSynchronized_UsingContainsKey(demoClass.map))
              .start();
      }

      Thread.currentThread().sleep(1);
      demoClass.map.clear();
    }
  }

}

3. Unsafe cont.

package unsafe.threads;
import java.util.Map;


public class Unsafe_ConcurrentHashMap_NoSynchronized_UsingContainsKey implements Runnable {
 
    private Map<Integer, String> map = null;
 
    public Unsafe_ConcurrentHashMap_NoSynchronized_UsingContainsKey(Map<Integer, String> map) {
         this.map = map;
    }
 
    @Override
    public void run() {

         for (int i = 1; i <= 30; i++) {
           //synchronized(map) {
               if(!map.containsKey(i)) {
                   if(map.containsKey(i)){
                     System.out.println("TRUE?");
                     try {
                throw new Exception("this can't be!");
              } catch (Exception e) {
                e.printStackTrace();
              }
                   }
                  System.out.println( Thread.currentThread().getName() 
                      + "\tInserting new, Key exists: " + map.containsKey(i));
                  map.put(i, Thread.currentThread().getName());
              }
           //}
        }
    }
}


Examples of safe usage:

1. Safe

package safe.demo;

import java.util.Hashtable;

import safe.threads.Safe_Hashtable_NoSynchronize_UsingPut;

/**
 * Thread safe hashmap usage through the use of 'synchronized' keyword. Based
 * on: http://lovehasija.com/2012/08/16/who-said-java-hashtable-is-thread-safe/
 * 
 * @author sshakil
 * 
 */
public class PartiallySafe_BecauseOfHashtable {

  // private Map<Integer, String> map = new Hashtable<Integer, String>();
  private Hashtable<Integer, String> map = new Hashtable<Integer, String>();

  public static void main(String[] args) throws InterruptedException {

    for (int j = 1; j < 100; j++) {
      PartiallySafe_BecauseOfHashtable demoClass = new PartiallySafe_BecauseOfHashtable();

      for (int i = 0; i < 5; i++) {
        new Thread(new Safe_Hashtable_NoSynchronize_UsingPut(demoClass.map)).start();
      }

      Thread.currentThread().sleep(10);
      System.out.println(demoClass.map.keySet());
      demoClass.map.clear();
    }
  }
}


1. Safe cont.

package safe.threads;

import java.util.Map;

/**
 * put operation is not safe on the map because its impl in 
 * hashmap (used by calling thread) is not synchronized
 * based on: http://lovehasija.com/2012/08/16/who-said-java-hashtable-is-thread-safe/
 * 
 * @author sshakil
 *
 */
public class Safe_Hashtable_NoSynchronize_UsingPut implements Runnable {
  private Map<Integer, String> map = null;

  public Safe_Hashtable_NoSynchronize_UsingPut(Map<Integer, String> map) {
    this.map = map;
  }

  @Override
  public void run() {
    for (int i = 1; i <= 30; i++) {
      try {
        map.put(i, Thread.currentThread().getName());
      } catch (Exception e) {
        System.out.println(e);
      }

    }
  }
}

2. Safe


package safe.demo;

import java.util.concurrent.ConcurrentHashMap;

import safe.threads.Safe_ConcurrentHashMap_NoSynchronize_UsingPutIfAbsent;

public class Safe_ConcurrentHashMap {

  private ConcurrentHashMap<Integer, String> map = new ConcurrentHashMap<Integer, String>(
      80, 0.5f, 200);

  // private Map<Integer, String> map = new HashMap<Integer, String>();

  public static void main(String[] args) throws InterruptedException {

    for (int j = 1; j < 100; j++) {
      Safe_ConcurrentHashMap demoClass = new Safe_ConcurrentHashMap();
      for (int i = 0; i < 5; i++) {
        new Thread(
              new Safe_ConcurrentHashMap_NoSynchronize_UsingPutIfAbsent(demoClass.map))
                .start();
      }

      Thread.currentThread().sleep(10);
      System.out.println(demoClass.map.keySet());
      demoClass.map.clear();
    }
  }
}


2. Safe cont.


package safe.threads;

import java.util.Map;
import java.util.concurrent.ConcurrentHashMap;

/**
 * Thread safe hashmap usage through the use of 'synchronized' keyword based on:
 * http://lovehasija.com/2012/08/16/who-said-java-hashtable-is-thread-safe/
 * 
 * @author sshakil
 */
public class Safe_ConcurrentHashMap_NoSynchronize_UsingPutIfAbsent implements Runnable {

  //private Map<Integer, String> map = null;
  private ConcurrentHashMap<Integer, String> map = null;

  public Safe_ConcurrentHashMap_NoSynchronize_UsingPutIfAbsent(
      ConcurrentHashMap<Integer, String> map) {
  //public ThreadSafeMapUsage3(Map<Integer, String> map) {
    this.map = map;
  }

  @Override
  public void run() {
    for (int i = 1; i <= 30; i++) {
      //String result = map.put(i, Thread.currentThread().getName());
      String result = map.putIfAbsent(i, Thread.currentThread().getName());    
    }
  }
}


3. Safe

package safe.demo;

import java.util.concurrent.ConcurrentHashMap;

import safe.threads.Safe_ConcurrentHashMap_NoSynchronize_UsingPutIfAbsent;

public class Safe_ConcurrentHashMap {

  private ConcurrentHashMap<Integer, String> map = new ConcurrentHashMap<Integer, String>(
      80, 0.5f, 200);

  // private Map<Integer, String> map = new HashMap<Integer, String>();

  public static void main(String[] args) throws InterruptedException {

    for (int j = 1; j < 100; j++) {
      Safe_ConcurrentHashMap demoClass = new Safe_ConcurrentHashMap();
      for (int i = 0; i < 5; i++) {
        new Thread(
              new Safe_ConcurrentHashMap_NoSynchronize_UsingPutIfAbsent(demoClass.map))
                .start();
      }

      Thread.currentThread().sleep(10);
      System.out.println(demoClass.map.keySet());
      demoClass.map.clear();
    }
  }

}


3. Safe cont.

package safe.threads;

import java.util.Map;

/**
 * Thread safe hashmap usage through the use of 'synchronized' keyword based on:
 * http://lovehasija.com/2012/08/16/who-said-java-hashtable-is-thread-safe/
 * 
 * @author sshakil
 */
public class Safe_Hashtable_Synchronized_UsingContainsKey implements Runnable {

  private Map<Integer, String> map = null;

  public Safe_Hashtable_Synchronized_UsingContainsKey(Map<Integer, String> map) {
    this.map = map;
  }

  @Override
  public void run() {

    for (int i = 1; i <= 30; i++) {
      synchronized (map) {
        if (!map.containsKey(i)) {
          if (map.containsKey(i)) {
            System.out.println("TRUE?");
            try {
              throw new Exception("this can't be!");
            } catch (Exception e) {
              e.printStackTrace();
            }
          }
          System.out.println(Thread.currentThread().getName()
              + "\tInserting new, Key exists: "
              + map.containsKey(i));
          map.put(i, Thread.currentThread().getName());
        }
      }
    }
  }
}


 


Posted by at No comments:

Eclipse eclipse.ini memory params

I noticed a slight lag in my Eclipse (Juno) instance while working on some simple tutorials.  It could be: artificially low heap space in the eclipse.ini file, actual starvation due to too many user processes, or some bug in the way Eclipse handles project files. Realizing that I have dozens of links open in Chrome, some word docs, pdfs, photoshop, etc, it's probably the first two.  I'm not downloading or copy/pasting anything, so it can't be the OSX Spotlight indexing service (which has creeped up in the past after the completion of torrents with many files).  I'm using an i7 MacBook with 16 GB RAM, so I'm thinking Eclipse really shouldn't be lagging.  Time to investigate.

Like at work before, I thought of modifying the JVM args for Eclipse: Eclipse startup memory settings (Mac), specifically these:-
XX:MaxPermSize=512m
-Xms256m
-Xmx2048m
-XX:+UseParallelGC

Before saving it and moving on with life, I looked up Parallel GC, and found that it is one of a just a few garbage collectors, all of which behave slightly differently (how often they kick in [pause your application] and for how long) based on what part of JVM memory (generations: "memory pools holding objects of different ages") and how they collect it (internal algorithm), as listed on this (Jon Masamitsu's) Oracle blog article: Our Collectors:
  • Serial" is a stop-the-world, copying collector which uses a single GC thread.
  • "ParNew" is a stop-the-world, copying collector which uses multiple GC threads. It differs from "Parallel Scavenge" in that it has enhancements that make it usable with CMS. For example, "ParNew" does the synchronization needed so that it can run during the concurrent phases of CMS.
  • "Parallel Scavenge" is a stop-the-world, copying collector which uses multiple GC threads.
  • "Serial Old" is a stop-the-world, mark-sweep-compact collector that uses a single GC thread.
  • "CMS" is a mostly concurrent, low-pause collector.
  • "Parallel Old" is a compacting collector that uses multiple GC threads. Using the -XX flags for our collectors for jdk6,
  • UseSerialGC is "Serial" + "Serial Old"
  • UseParNewGC is "ParNew" + "Serial Old"
  • UseConcMarkSweepGC is "ParNew" + "CMS" + "Serial Old". "CMS" is used most of the time to collect the tenured generation. "Serial Old" is used when a concurrent mode failure occurs.
  • UseParallelGC is "Parallel Scavenge" + "Serial Old"
  • UseParallelOldGC is "Parallel Scavenge" + "Parallel Old"
The article also mentioned that if you want to use "GC Ergonomics" (further tuning params, mostly for large heaps spread accross many processors), then you should use UseParallelGC and UseParallelOldG, and that it will not work with useConcMarkSweepGC.

Quickly reading the list of GCs and their usable combinations (on Masamitsu's blog) leads me to believe that UseConcMarkSweepGC is a good general purpose candidate as it causes smaller pauses in your application, where as other concurrent collectors cause longer pauses after longer times (also mentioned here).

These are the params I went with:
-XX:MaxPermSize=512m
-Xms256m
-Xmx2048m
-XX:+UseConcMarkSweepGC

In activity monitor, double clicking Eclipse shows:

Note, the actual allocated VM to the Eclipse process is higher than 2048m. This was consistent when I increased Xmx to 4096m, observing 7.05GB allocated. In retrospect, the lag was likely due to 'too many windows open', though, with 16GB of RAM, I wonder why such lag would occur at all anymore. Its not like I'm working on a giant project in eclipse with some large amount of in-memory data. So far so good, though I did close many tabs in Chrome.

Links
Eclipse startup memory settings (Mac) - Finding eclipse.ini on OSX
Our Collectors - Jon masamitsu's blog at Oracle
GC Ergonomics - Oracle tutorial on fine tuning GCs
Java SE 6 HotSpot[tm] Virtual Machine Garbage Collection Tuning - Oracle's primer on GC; good read
FAQ How do I run Eclipse?
FAQ How do I increase the permgen size available to Eclipse?

Stackoverflow questions:
Java Concurrent and Parallel GC
Difference between -XX:UseParallelGC and -XX:+UseParNewGC


Posted by at No comments:
Subscribe to: Posts (Atom)