All posts by Administrator

Threads – tips and tricks

Difference between notify and notifyAll

NotifyAll wakes up all the threads that are waiting on the specified object lock. Please note that it might be necessary to use notifyAll instead of notify in cases when a specific or a specific subset out of a set of threads need to be notified. For instance: in a producer – consumer scenario, the producer should use notifyAll to wake up all the consumers out of which only one would be able to utilize the product that the producer has available. The producer might have 2 quantities of products available for consumption and there might be consumers that require more than 2 and so just using notify might wake up those and there would be no progress.

Also note that notify will not relenquish the lock like wait does. Notify will only relenquish the lock once the synchronized section is exited. The thread invoking notify might continue to run although the thread that is waiting has been notified and is now in a RUNNABLE state ready to acquire the lock.


Thread Scheduling

Note that the round-robin scheduling might appear to be fair but it is not in the following case (in case of a single CPU machine):

  • Intermediate results from a calculation are not required – all that is required are the final results. For instance, if there are 5 threads started to do a calculation that provides a result in 5 seconds, then no matter what kind of time slicing is done, the average time for producing the final result is equal to or more than the average time in a non-timesliced version.

On the other hand, if intermediate results are required then the round-robin (timesliced) scheduling is the fairest. It the timeslice is 1 second, then the average time for each thread to produce an answer would be (1+2+3+4+5)/5 = 3 seconds. On the other hand, for a non-timesliced version, the average would be (1+6+11+16+21)/5 = 11 seconds.

 For a multiple CPU machine, it gets complicated.

If intermediate results are not required (on a 4 CPU machine), we have:

  • Average for a non-timesliced version = (5+5+5+5+10)/5 = 6 secs.
  • Average for a timesliced version = (5+5+5+7+8)/5 = 6 secs (for a timeslice of 2 secs)

If intermediate results are required:

  • Average for a non-timesliced version would be (1+1+1+1+6)/5 = 2 secs
  • Average for a timesliced version would be (1+1+1+1+2)/5 = 1.2 secs (for a timeslice of 1 sec)

Note that for intermediate results, the timesliced version of scheduling is the most fairest.

Dependency Inversion Principle


Depend upon abstraction. Code to interfaces and not to concrete implementations.

This is similar to the OO principle: "program to an interface and not to an implementation". However, the DIP makes an even stronger statement about abstraction. It means any component (high or low level) within an application should depend upon abstractions. A high level component is one whose behavior is defined in terms of other lower level components.

The following guidelines help in avoiding OO designs that violate the DIP:

  1. No variable should hold a reference to a concrete class. Do not use new, use factories.
  2. Do not derive from concrete classes. Derive from abstract or interfaces. If your are deriving from concrete classes then there is a dependence on the concrete class.
  3. Do not override base class methods. Those concrete methods in the base class are meant to be shared between all the derived classes.

Inverson of control:

This generic term is also synonymous with Dependency Injection.

The assembler injects the dependency and reduces tight coupling between classes.

Java Collections and Insertion Sort

Insertion Sort:

It is used for smaller size arrays. In Java Collections, insertion sort is applied to an array of size 7 or else. This cutoff is based on empirical studies. The best choice for the cutoff is actually machine ]dependent.

Method implementation:

public void insertionSort(int x[])


   int off = 0, len = x.length;

   for (int i = off; i < len; i++)

      for (int j = i; j > off && x[j-1] > x[j]; j–)

          swap(x, j, j-1);


public void swap (int x[]; int a, int b)


    int t = x[a]; x[a] = x[b]; x[b] = t;



The outer for loop runs n times (where n is the length of the array).

The inner for loop runs 0, 1, 2, 3 … (n-1) for the worst case scenario wherein the array is in descending order.

Therefore the worst case scenario = > n(n-1)/2

At every inner for loop step a decision is made whether to swap. If we assume that at each step there is a 50% chance of swapping, then the average case scenario would be: (n(n-1)/2 ) / 2 approx.

The best case behavior would be visible when the array is already sorted => insertion sort would be linear in n.

Bubble Sort:

Unlike insertion sort wherein the smaller element flows towards the beginning, here the larger element flows towards the end. Although the name might be catchy but it is not used industrially – there are other sorting algorithms that provide better perfomance.

Visitor Family of Design Patterns

Driver: The visitor family allows separation of concerns and allows functionality (basically one or more methods) to be added to a hierarchy of classes without modifying anything in the hierarchy.

For instance: in the visitor pattern, the visitable classes would just define a single method (accept) in the simplest case and within that a ploymorphic call would be made to the passed in Visitor instance’s visit() method.

OCP principal: (the Open Closed Principle): The visitor family allows changing the behavior of existing classes (for instance, in the case of the Visitor Pattern, these classes are termed as Visitable) without updating the existing codebase.

The main patterns of interest in this family are:

  • Visitor
  • Decorator

The Visitor Pattern:

There is a dual dispatch happening wherein the first dispatch is to invoke the correct accept method in case there are more than one.

The second dispatch is to invoke the correct visit() method on the Visitor instance.

One of the main benefits of the visitor pattern is that it is extremely fast as it involves only two polymorphic dispatches.

The Decorator Pattern:

This one is different from visitor although they are members of the same family of patterns – the Visitor family. It is primarily different  ’cause it does not require the interface of the Visitable to be updated with the addition of the accept() method. There are no dual dispatches.

This pattern is also called the toolkit pattern since new tools (new behavior) can be acquired at run time => the application therefore can be termed to be using new tools.

The SRP principle (Single Responsibility Principle) underlines the separation of concerns in a good design. This implies, in a decorator context, that a class (such as one representing the entity: CAR)  should not burden itself with a characteristic (such as the alloy wheels) that is not intrinsic to its behavior. In the case of the preceding example of a CAR, the decorator can implement the interface of the CAR and delegate all calls to the CAR instance but "decorate" the one for getPrice() by taking into account the presence of alloy wheels and adding that to the base price and thereafter delegating to the CAR instance.



Have been studying on Generics in Java and have evaluated the following:

  • Thinking in Java has a comprehensive chapter on Generics although towards the end, I found some inaccuracies.
  • The Generics tutorial linked from Java Docs is thorough but for someone who is hitting Generics aka templates in C++ for the first time, I would recommend starting with "Thinking in Java".
  • Any doubts that you might have can be quickly cast aside by checking out the immensely useful site:

Hopefully some of you might find this information useful.