Java Concurrency - Beyond Synchronized

Synchronized keyword is frequently used in Java. But, Synchronized cannot provide a method for threads to signal one another of conditions that others may be waiting on. Another thing is that synchronized does not act on a fairness policy. A thread that is starved for quite some time need not get access over others. i.e the fact that you have been waiting for some time may not be considered. 

An example for conditions is availability of elements in a shared data structure queue. Such a facility is provided by java.util.concurrent.locks.Condition. This allows threads to wait for a condition on a lock and relinquish the lock so that, other threads can full fill the condition that is needed for the waiting threads to continue. This logic can be programmed using locks but, Condition provides this off the shelf. Once the lock is acquired thread waits for the condition mandatory for it to continue. When the condition is true it continues. 

Fairness policy is allowed by a Reentrant lock where the thread waiting for quite sometime will get access. 

The intriguing part of threading in Java is that, the time (in ms) between a consumer / producer is able to regain access to a shared data structure is the same with Condition as it is without Condition. 

Example: Producers & consumers waiting on a lock & its condition. Both share a common queue where the producers put in integers for the consumers to take, contending for the queue access at the same time.  

Code Structure

Code with Synchronized keyword.

Condition creation code.

Code with Condition.

The consumer comes back on receiving the signal

Facade Pattern - Java Code Architecture

Object oriented programming involves instances of classes i.e objects interacting with one another towards a common goal. This interaction can be for services, control or data. Objects perform a particular function in a software. When there are a lot of objects the code becomes cumbersome to maintain and use; every time in the same piece of software. 

Facade pattern comes into action when you have a subsystem that performs a particular service for another subsystem or part of the code. A subsystem here in terms of software code means a group of objects interacting to get a job done. Facade pattern hides the objects underneath it and their interactions to object layers above the pattern. For example, information collected from the user interface in a java application may be used to create say, a user object, account object and the user interface may store this to the database by using an object that performs that database operation. Here a Facade object can expose an operation, i.e creating the objects from the data from UI and storing it to the database. This facade can be used by the UI without delving into the details of how it is done. 

If the interaction of the objects in the facade changes, it is contained within the facade and no layer of code outside the facade is affected. This is the most important aspect of the facade pattern that makes it so useful in Java Enterprise where this pattern is more frequently seen in popular Java Enterprise IDE's ready-made-code.

For example, suppose there is a table in the database that stores the details of attendees in a conference. Java enterprise wraps this with an Entity say, Attendee entity which would be part of the JPA ready-made-code. This entity will expose the database operations on the table. A facade would be created namely a session facade which exposes operations that are utilised by controller layers to update information.  The session facade will deal with the requests on the Attendee Entity. 

Here is an example of the code structure for a Tomcat based application that gets information in a table. Called from a servlet. i.e servlet is the controller in Model-View-Controller Application model. 

as you can see from this code, the facade is called to do the job. The code to get a job done becomes small as far a controller object is concerned. A lot of things may happen under the facade but, the higher layer object does not care about this. It is the Facade's responsibility. The code structure in eclipse web project is shown below. There are entity objects and Facade objects. Facade objects here share a common ancestor which declares common operations on entity-facades. In this example, entity objects simulate the JPA entity objects.

The abstract facade is not a must in the general facade pattern but, is used here as is further simplifies code with inheritance. A part of abstract facade is shown here 

A subclass of this called Attendee Facade used in our example is here 

A lot of object interactions and code is thus abstracted from a controller object / higher level object by using the Facade Pattern. It also makes the code more reusable, maintainable, predictable and beautiful.

Skip Lists Algorithm and Runtime Profiling

Skip List Runtime on dictionay operation compared to Splay Trees and Hash Tables. (Coded in Java)

Skip lists are a relatively new data structure. This is an ordered list where the nodes are connected together at multiple levels. Different levels of connected nodes need not be uniform. This allows the skip list to skip items during a search. Each level is an ordered list in itself.  Every node has a level and is connected to different nodes in the same level. This allows data structure operations to skip through the list. Example is the following list where there are two levels.

Level 1 connections                  E ----------> X
Level 0 connections A ->; B -> E -> F -> G->X -> Y -> Z

Level 0 list is the same as a linked list. E has connections has two levels. If a search was for say 'G'. The algorithms is as follows Start at Level 1, X > F so we move down at 'E' and then proceed at level 0 from E till G is found. Nodes A and B were skipped.

SkipList Search Algorithm:
1) Start from the top level proceed until level 0
    a) Move to the right until a node with node Key < search Key
    b) Jump to the next lower level.
2)  If 1a resulted in an exit in level 0, the next node could be the search node. else it is absent.

Here is a skip list implementation holding values A to Z. The nodes encountered during the search for H and M are shown.

Level 2 Skip List. 

Level 6 Skip List

In order for the list to be helpful level at each node needs to be decided at Random during the insert operation of that node. The maximum level that is useful in a skip list is ln N -1 where N is the number of items expected to go into the skip list. 

Algorithm Inserting in to the Skip List

1 Find the node as in search. This will return the node that will be to the left of the new node (L).

   a) While dropping down to the lower levels maintain the nodes in an update List.

2 Create the new node with a random level. 

3 Adjust the pointers from the existing L node to the new node.If the new level is greater than the existing level of the list, then the head of the list should be adjusted to point to the new node at the new level.

4 Set the next pointers of the new node to next pointers of L

5 Set next pointers of L to the new node at that level. This is done for each node where level was changed in step 1.

For example in the case of 

Level 1 connections                  E ----------> X
Level 0 connections A -> B -> E -> G->X -> Y -> Z. We need to insert H with level 3 then, at level 1 we drop down at E and also at G in level 0. So, G->next = H at level 0, E-> next = H at level 1, F -> next = X at level 1 and at level 2 H is linked to head and tail of the list.


Level 2 connections                                  *<-H->*
Level 1 connections                  E ----------->H-> X
Level 0 connections A -> B -> E -> F -> G->H->X -> Y -> Z

Runtime of Skip Lists: Dictionary operations on skip lists take O(Log(n)) time. Finding each new node's level is done in random as follows














Comparison of Skip List, Splay Binary Search Trees and Hash Table

For a serious input of 56000 word dictionary, the search operations on Skip lists, Splay Trees and Hash Table is as follows. Skip list took 40 comparisons at 11 levels to find the word 'Skip' in the dictionary.

Splay tree took less time than the skip list at

Hash Table left the above two way behind in run time

Result: In general skip lists and splay trees can't hold candle to hash tables. 

Ant Power : Build Automation

Ant is helpful in any java project involving large number of resources. Ant based on xml and java itself can help to compile java classes, put the classes in a jar or war, create file folders before building projects and interfacing with servers like tomcat to perform application installation. This is useful in java enterprise web applications and enterprise applications. Ant ships with popular IDEs like eclipse and Rational Application Developer.

Ant manual webpage  provides a sample build.xml file that can be customized by developers instead of writing it from scratch. This is a modification of that, file with modifications pertaining to ; building webapps for tomcat 7.0.26. For example a change is the compilations of classes and creating a war using war rather than jar (purpose!). Some changes were needed for tomcat 7.0.26 for example the manager url.

The sample folder structure used for eclipse dynamic web application is shown here.

The project tag is here. Base dir is .. since the ant build.xml is in 'Ant' folder. Multiple ant files can be grouped in this folder in a huge project.

The properties declaration that I use

The compile element with changes

The dist element which creates the distribution war file in the dist folder.

New elements to stop, remove, compile, install and start the web application.

The resulting WAR file contents

Java Authentication and Authorization Service JAAS - Java Security- Create a Login

How to create a custom Jaas Login Module?

Java Authentication and Authorization service allows applications to authenticate subjects independant of the underlying authentication mechanism. This is done by standard interfaces defined in the JAAS architecture. Any authentication mechanism that, conforms to these interfaces can be used by the application through JAAS without getting entangled in the fine details of the mechanism. This is typically used when applications need to authenticate subjects using a different mechanism than provided as part of an application framework. For example, custom database lookup to autheticate users rather than FORM authentication in a webapp under tomcat.

The LoginContext allows applications to login and out i.e authenticate(and also authorize). Applications don't interact with the security mechanism that provides the authentication mechanism. It may be a kerberos login or a login mechanism where you deal the user name and password. When you initialise the context you specify the LoginModule_Configuration you will use to login. You also specify the callback handlers which gets the information from the user(or someother place) and puts it in callbacks. Callback has the info needed by application. Callbackhandler implements interfaces which allow the application classes to get the information from the authentication mechanism. While the application is executing the login() method of the underlying
authentication mechanism, the handlers get the credentials and puts them in the callback. In the login() method the call backs can be polled to get the information they have.

Handler's handle method sample.

Login method in a class that extends LoginModule interface.

Loginmodule is an implementation of the jaas compatible security mechanism that, performs the authentication. A custome module can be coded by implementing the interface.The modules available are specified in a jaas configuration file and that module classes/jars should be available for the application to load.

Jaas configuration file.

You mention the options to be used with a loginmodule in the jaas configuration file. For example, do you want the loginmodule to be a mandatory success thing for applications to go through? requisite? failing ok? you mention the location of the jaas configuration file in  your java.security file. The java.security file is located in your_jre/lib/security/java.security. This is underlying login.config.url.= your_jaas_config_file here. if nothing is mentioned here it will look in you home folder for .java.login.config file. Sometimes a
behaviour noted is that, if you are running as a root user this will be accessed irrespective of anything else!!. This is the case when you run from eclipse as a root user. Simply put, this is the name of the class that implements the LoginModule interface. Standard providers like kerberos do this. You can also implement the
interface and put it here. The name at the top of the {} brackets is the 'name of the login configuration' you will refer to in your application.

Example jaas configuration specification in Java.Security file

Text Search: Boyer Moore Looking Glass Vs Hash

Text Search: a comparison of Boyer Moore Vs Hash. This experiment takes on 2 text search techniques to compare the output.

The first approach is Boyer Moore algorithm using the looking-glass approach. This is ok and has no side effects as a result of the technique used in the algorithm.

Input: A text file of 11,000 lines. The objective is to find the occurrences of a pattern.

Boyer Moore algorithms fares at 49.2 milli seconds.

Now the technique using super imposed coding to speed up the search by Malcolm C Harrison runs into problems and interesting observations when the text involved is English. The technique is to hash every two consecutive letter of every line of the
input to a superimposed code. Now, the same is done to the pattern and we need
to find only the line with the similar bits in the super imposed code.

This is pretty ok for small inputs but, on the huge input this gave a lot of additional outputs without any presence of the pattern in the text. This is mainly because the hashes to a range of 128 on English text is resulting in collisions. Too much that the out put is unusable. The number of collision is of the order of 1000. (10%).

As mentioned by Knuth, this collision can be brought down by removing all the
spaces in the input text and pattern since it contributing to the common noise. This does not help much but does bring the collision down a bit. But, the collision can be reduced to 240-280 collisions by applying the hash incrementally to the text pattern. i.e if 'software' is the term apply the hash to so, sof, soft, etc so that, the
incremental sub sequence is also caught in the superimposed code. This is good
but 200-250 collisions is still not good and not to mention the additional runtime incurred to perform the incremental hash. The time is 482ms.

 
Byer Moore although would take more time on much larger files wins for now.

Making Concurrent Software - Finding Concurrency with Lock Striping

In this post we see how planning software code with concurrency will save time.

At the basic level                    Software = Data structures + Algorithms. 

At an advanced level Faster Software = Data structures + Algorithms + Concurrency.

So, we can get more work done in the background or concurrently using multiple threads. But, more threads does not necessarily mean faster software. This is because as more thread are introduced we may be synchronizing the threads using single / multiple thread synchronization mechanisms such as locks. So multiple threads may be waiting on the same lock to do an operation on a data structure. This essentially makes the threads run sequentially. This is the case when ordinary data structures are wrapped using a single lock for thread synchronization in software programming. Not only will this make the data structure become a bottle neck in the performance but also, will introduce synchronization issues with composite operations. 

Most collections in Java concurrent package are thread safe and even employ a method known as lock striping. Lock striping stands for splitting a high contension lock into multiple locks with out adversely affecting the integrity of the protected data. 

An Example for Concurrency using Lock Striping

Problem: A hash table is used by multiple threads to insert and delete items from the hash table. This hash table has the option of lock striping by taking in the number of locks to protect the underlying data intergrity.

Case 1: Using only a single lock to protect the data structure operations. The time to execute 10000 inserts and 10000 deletes from two threads simultaneously takes runt time 7343811 nanotime for the system.

Case2:  Using only 10 lock to protect the data structure operations. i.e every N / 10 of the hashtable entries is protected by one of the 10 locks. The run time for this is 3067498 nanotime for the system. A savings of half the run time when there is only one lock.

The run times for the two cases in Netbeans profiler is shown below. Case 1

2

Lock striping demo shows that, striping can help the threads to wait on locks protecting narrow segments of the data. But, identifying such scenarios, updating and maintaining it can be challenging. Java uses the same technique in concurrency package.  (All coded in Java).

How to Code your own Search Engine Like Google, Bing or Yahoo - Part 2. Make the Search Engine run Faster or Better

In one of the previous posts, I coded up a small search engine with tries and the leaf nodes of the tries held the list of documents which had the specific word (path in the trie). The list of documents was maintained as binary search trees because, trees can help in set representation and finding set intersections pretty neat. But, not anymore in the case of search engines when we increase the size of the sets involved. Using binary search trees for the list of documents will utilize more memory for intersection and take more time than a sorted linked list. This is evident from the following profiling snapshots below with large amounts of data. More over search engines use sorted list to find the intersection faster by skipping through non-matching documents. This may seem a bit vague argument but, coding and profiling proves that this is better way.


New Algorithm for Set Intersection of the search engine:
So instead of binary search trees we use a sorted linked list to store the documents for a particular word. This list is sorted on the basis of the id of the documents. So every document
has to have an id. To find the intersection between two lists of documents we follow the algorithm as shown below. 


1. start from the beginning of the two sorted lists A & B


2. if the documents in the current positions of A and B match then we have a document which has both words add the document to the intersection list.


3. otherwise find which list A or B has the smaller document id at the current positions of mismatch.  if it is A then, skip through elements of A until you find a document with id >= current id at B. if it is B then, skip through elements of B until you find a document with id >= current id at A.


4. If you run off the end of any of the lists return the intersection list.


Example


List A 1, 4, 7, 9, 11, 31, 37, 56, 143, 200, 900, 3422
List B 1, 29, 37, 56, 142


Here in this example, we have a match at 1 and a mismatch at the second index. List A has smaller id of 4 compared to 29 of B. So we skip through A until we reach 31. Now, then
case is just the reverse B has 29 and A has 31 so we skip in B to 37. Then we skip in A to 37 a match! ok so the idea is to skip non-matching elements in the lists. We are also saved from having to go through the rest of A.


Run time Performance Profiling of implementing the Set intersection using, (a) Sorted Linked Lists (skipping using linked list iterators), (b) Sorted Linked List indices (age old ++ index for skipping), (c) Splay tree. The difference in the code for cases a and b are trivial in appearance but, is greatly different in efficiency.


Partial code snapshot of iterator based skipping.

Partial code Snapshot of Index ++ skipping

In both the above codes, the bulk of the time is used in "get(n)" type methods for the Java Linked List collection. But, it is far less for the iterator next() method!! This is evident here 

Performance Profiling snap shots for finding intersection of two lists with increasing sizes around the ranges 100, 1000, 10000, 100000, 1000000 in order.

The observation is that, when there are only a few items, skipping / jumping using indices is very fast. But, as we increase both the lists' size we will have to leave the splay tree / binary tree representation at around 10000. This is because getting each item of a tree and then comparing it will cost memory which is saved in both the list based scenarios. More over when two trees have M and N items, we try to find if each of M is similar to any of N. This takes M log N, as M and N are very large this can be bothersome. 


So, we are down with 2 contenders. The performance profiling of indices based skipping gives a shock as we again increase the lists' sizes, the Sorted Linked Lists (skipping using iterators) is way faster than indices (age old ++ index). For example, with a list sizes of 500000 and 150000, the sorted linked list algorithm finds the intersection in 3.45 minutes. Whereas, if we skip using integer indices and getAt(n) methods we get the set intersection in around 20 minutes. Again as mention before iterator Next() seems faster for the Iterator / Java LinkedList as opposed to a getIndex(n) for Lists. 


For multiples sorted lists, we can find the intersection by taking the two smallest lists and finding the set intersection as above. Then doing the same with the next smallest list as so on until we end with only one list. So by using sorted lists for the documents we have, for a given word, we can speed up the set intersection part of our search engine by many order of magnitude. The thing is that, we need to maintain the documents for a particular word in the sorted order. Some housekeeping does help it seems!.

Splay tree (Super Search Tree) Vs Binary Search Tree

In one of the earlier posts I had called for the use of binary search trees for set representation and general search operations. I take it back. Now it is splay trees !. These are very similar to binary search trees but, these ones are balanced binary search trees. A binary search tree gives you log(n) of search and insertion theoretically. This is true only of the keys that are going into the tree are totally random. So if the set of keys { 10, 2, 38, 63, 21, 9, 1} go into a binary search tree then, the tree looks like 

This tree gives you log(n) time on its search. It is balanced too. But, if the application was putting in data in not-so random way then the tree can easily become unbalanced. This can lead to n time search. so if keys were to go in like { 1, 2, 9, 10, 21, 38, 63 }. Then the tree looks like

This seems ok with the defenition of the search tree but, if you were searching for 63 then, you need to do 7 comparisons compared to 3 in the previous tree. Also, recently accessed data may be frequently needed. Effectively this will turn into a list. In a splay tree, all operations are similar to a binary search tree but, you bubble up the recently accessed node up to the root or the first level from root. So next time you access it, the node will be available real fast. The bubble up will cost some time but, will compensate over a number of operations with the efficiency of balancing the tree. For splay tree the average of a collection of operations is always of the order of log(n) although some of these operations may be of n time complexity. Accessing a node means searching / inserting / deleting. In all these cases we bubble up the node / the node that replaced it in the case of deletion. 

The process of bubbling up the node consists of left rotations and right rotations. The algorithms to bubble up the node / balance the tree has three conditions.

1) If the node is a right child of a left child then you rotate the node left once and then rotate it right. (vice versa also for this case)

2) If the node is the right child of a right child then, you rotate the parent left once and then the node also once to left. (vice versa also for this case)

3) This has to be done until the node reaches the root or the first level from root.

So for a set of keys { 18, 12, 25, 4, 15, 26, 1, 13, 17, 30, 3, 14, 28, 29}  suppose the tree looks like this before any splay. We access 3 in 4 operations. 

For splaying, 3 is the right child of a left child so we rotate it left once and then right again. The left rotation gives a tree like this

Then a right rotation again gives

Again since 3 is the left child of a left child we do right rotations. one at 12 then at 3. This brings 3 to the root.

Next time we do a search for 3 we get a faster response. Also, the tree is better balanced so, we get a better time for any node than before. 

A run time profiling example: Tree is created with values from 0 - 99999 in order. Then 99999 is searched before and after splaying. The cpu runtime profiling results are shown below.

Another profiling result, to get a feel of the advantage, (constructing the same tree as before) 4 values near leaf and 1 value near mid section are searched together. Both before and after splaying. The run time results are shown below. 

Obviously, splay operation has an advantage on an average since, the tree is now balanced and we can find any value in less than  half time than before.

Code Design for Singleton / Lazy initialization Concurrency

This post is an experiment on the concurrency of the common Singleton design pattern and it memory profiling results. Singleton pattern is commonly used in coding and the objective of Singleton is to make sure that, only a single instance of the class is created. The common design with lazy initialization is present in most code. This is shown below (read with out the synchronized keyword).

This is fine as long as the code is executed by a single thread. If ever the code is executed by multiple threads, the 'check for null then act' part can result in multiple instances of the singleton class. If one thread A is checking the instance for null, returns true and it is moved out of processor for another thread B, B checks for null creates an instance. A comes back and creates another instance. So there will be 2 instances now as shown  in the run below. The class IamSingle has two instances without the synchronized keyword.

With the Synchronized keyword, the run profile is as follows. There is only one instance. 

This kind of bug can be difficult to reproduce as even getting the wrong scenario depends on the timing of the threads.