Saturday, 7 July 2012

Item 6: Eliminate obsolete object references


When you switch from a language with manual memory management, such as C or C++, to a garbage-collected language, your job as a programmer is made much easier by the fact that your objects are automatically reclaimed when you’re through with them. It can easily lead to the impression that you don’t have to think about memory management, but this isn’t quite true.

Consider the following simple stack implementation:
// Can you spot the "memory leak"?
public class Stack {
private Object[] elements;
private int size = 0;
private static final int DEFAULT_INITIAL_CAPACITY = 16;
public Stack() {
elements = new Object[DEFAULT_INITIAL_CAPACITY];
}
public void push(Object e) {
ensureCapacity();
elements[size++] = e;
}
public Object pop() {
if (size == 0)
throw new EmptyStackException();
return elements[--size];
}

/**
* Ensure space for at least one more element, roughly
* doubling the capacity each time the array needs to grow.
*/
private void ensureCapacity() {
if (elements.length == size)
elements = Arrays.copyOf(elements, 2 * size + 1);
}
}

Loosely speaking, the program has a “memory leak,” which can silently manifest itself as reduced performance due to increased garbage collector activity or increased memory footprint. In extreme cases, such memory leaks can cause disk paging and even program failure with an
OutOfMemoryError, but such failures are relatively rare.

So where is the memory leak? If a stack grows and then shrinks, the objects that were popped off the stack will not be garbage collected, even if the program using the stack has no more references to them. This is because the stack maintains obsolete references to these objects. An obsolete reference is simply a reference that will never be dereferenced again.

The fix for this sort of problem is simple: null out references once they become obsolete. In the case of our Stack class, the reference to an item becomes obsolete as soon as it’s popped off the stack. The corrected version of the pop method looks like this:

public Object pop() {
if (size == 0)
throw new EmptyStackException();
Object result = elements[--size];
elements[size] = null; // Eliminate obsolete reference
return result;
}

Nulling out object references should be the exception rather than the norm.

Generally speaking, whenever a class manages its own memory, the programmer should be alert for memory leaks. Whenever an element is freed, any object references contained in the element should be nulled out.

Another common source of memory leaks is caches. Once you put an object reference into a cache, it’s easy to forget that it’s there and leave it in the cache long after it becomes irrelevant.

A third common source of memory leaks is listeners and other callbacks. If you implement an API where clients register callbacks but don’t deregister them explicitly, they will accumulate unless you take some action.

They are typically discovered only as a result of careful code inspection or with the aid of a debugging tool known as a heap profiler. Therefore, it is very desirable to learn to anticipate problems like this before they occur and prevent them from happening.

Reference: Effective Java 2nd Edition by Joshua Bloch

Item 5: Avoid creating unnecessary objects


It is often appropriate to reuse a single object instead of creating a new functionally equivalent object each time it is needed. Reuse can be both faster and more stylish. An object can always be reused if it is immutable (Item 15).

As an extreme example of what not to do, consider this statement:
String s = new String("stringette"); // DON'T DO THIS!

The statement creates a new String instance each time it is executed. The argument to the String constructor ("stringette") is itself a String instance

The improved version is simply the following:
String s = "stringette";

You can often avoid creating unnecessary objects by using static factory methods (Item 1) in preference to constructors on immutable classes that provide both. For example, the static factory method Boolean.valueOf(String).

you can also reuse mutable objects if you know they won’t be modified.

// DON'T DO THIS!
public boolean isBabyBoomer() {
// Unnecessary allocation of expensive object
Calendar gmtCal =
Calendar.getInstance(TimeZone.getTimeZone("GMT"));
gmtCal.set(1946, Calendar.JANUARY, 1, 0, 0, 0);
Date boomStart = gmtCal.getTime();
gmtCal.set(1965, Calendar.JANUARY, 1, 0, 0, 0);
Date boomEnd = gmtCal.getTime();
return birthDate.compareTo(boomStart) >= 0 &&
birthDate.compareTo(boomEnd) < 0;
}

The isBabyBoomer method unnecessarily creates a new Calendar, TimeZone, and two Date instances each time it is invoked.

static {
Calendar gmtCal =
Calendar.getInstance(TimeZone.getTimeZone("GMT"));
gmtCal.set(1946, Calendar.JANUARY, 1, 0, 0, 0);
BOOM_START = gmtCal.getTime();
gmtCal.set(1965, Calendar.JANUARY, 1, 0, 0, 0);
BOOM_END = gmtCal.getTime();
}
public boolean isBabyBoomer() {
return birthDate.compareTo(BOOM_START) >= 0 &&
birthDate.compareTo(BOOM_END) < 0;
}

If the improved version of the Person class is initialized but its isBabyBoomer method is never invoked, the BOOM_START and BOOM_END fields will be initialized unnecessarily. It would be possible to eliminate the unnecessary initializations by lazily initializing these fields (Item 71) the first time the isBabyBoomer method is invoked, but it is not recommended.

keySet method of the Map interface returns a Set view of the Map object, consisting of all the keys in the map. Naively, it would seem that every call to keySet would have to create a new Set instance, but every call to keyset on a given Map object may return the same Set instance. Although the returned Set instance is typically mutable, all of the returned objects are functionally identical.

There’s a new way to create unnecessary objects in release 1.5. It is called autoboxing.

// Hideously slow program! Can you spot the object creation?
public static void main(String[] args) {
Long sum = 0L;
for (long i = 0; i < Integer.MAX_VALUE; i++) {
sum += i;
}
System.out.println(sum);
}

Prefer primitives to boxed primitives, and watch out for unintentional autoboxing.

Conversely, avoiding object creation by maintaining your own object pool is a bad idea unless the objects in the pool are extremely heavyweight. The classic example of an object that does justify an object pool is a database connection. The cost of establishing the connection is sufficiently high that it makes sense to reuse these objects.


Reference: Effective Java 2nd Edition by Joshua Bloch

Item 4: Enforce noninstantiability with a private constructor


A class that is just a grouping of static methods and static fields. Such classes have acquired a bad reputation because some people abuse them to avoid thinking in terms of objects, but they do have valid uses.

Attempting to enforce noninstantiability by making a class abstract does not work. The class can be subclassed and the subclass instantiated.

A class can be made noninstantiable by including a private constructor:

// Noninstantiable utility class
public class UtilityClass {
// Suppress default constructor for noninstantiability
private UtilityClass() {
throw new AssertionError();
}
... // Remainder omitted
}

Because the explicit constructor is private, it is inaccessible outside of the class. The AssertionError isn’t strictly required, but it provides insurance in case the constructor is accidentally invoked from within the class.

Reference: Effective Java 2nd Edition by Joshua Bloch

Item 3: Enforce the singleton property with a private constructor or an enum type


A singleton is simply a class that is instantiated exactly once.

Making a class a singleton can make it difficult to test its clients, as it’s impossible to substitute a mock implementation for a singleton unless it implements an interface that serves as its type.

1)     // Singleton with public final field

public class Elvis {
public static final Elvis INSTANCE = new Elvis();
private Elvis() { ... }
public void leaveTheBuilding() { ... }
}

The main advantage of the public field approach is that the declarations make it clear that the class is a singleton: the public static field is final, so it will always contain the same object reference. There is no longer any performance advantage to the public field approach.

a privileged client can invoke the private constructor reflectively (Item 53) with the aid of the AccessibleObject.setAccessible method. If you need to defend against this attack, modify the constructor to make it throw an exception if it’s asked to create a second instance.

2)     // Singleton with static factory

public class Elvis {
private static final Elvis INSTANCE = new Elvis();
private Elvis() { ... }
public static Elvis getInstance() { return INSTANCE; }
public void leaveTheBuilding() { ... }
}

One advantage of the factory-method approach is that it gives you the flexibility to change your mind about whether the class should be a singleton without changing its API.

To make a singleton class that is implemented using either of the previous approaches serializable, it is not sufficient merely to add implements Serializable to its declaration. To maintain the singleton guarantee, you have to declare all instance fields transient and provide a readResolve method (Item 77). Otherwise, each time a serialized instance is deserialized, a new
instance will be created, leading, in the case of our example, to spurious Elvis sightings. To prevent this, add this readResolve method to the Elvis class:

// readResolve method to preserve singleton property
private Object readResolve() {
// Return the one true Elvis and let the garbage collector
// take care of the Elvis impersonator.
return INSTANCE;
}

As of release 1.5, there is a third approach to implementing singletons. Simply make an enum type with one element:

3)     // Enum singleton - the preferred approach

public enum Elvis {
INSTANCE;
public void leaveTheBuilding() { ... }
}

This approach is functionally equivalent to the public field approach, except that it is more concise, provides the serialization machinery for free, and provides an ironclad guarantee against multiple instantiation, even in the face of sophisticated serialization or reflection attacks. While this approach has yet to be widely adopted, a single-element enum type is the best way to implement a singleton.

Reference: Effective Java 2nd Edition by Joshua Bloch

Item 2: Consider a builder when faced with many constructor parameters


Static factories and constructors share a limitation: they do not scale well to large numbers of optional parameters.

Consider Nutrition Facts label that appears on packaged foods.
required fields—serving size, servings per container, and calories per serving— and over twenty
optional fields—total fat, saturated fat, trans fat, cholesterol, sodium, and so on.

1)    Traditionally, programmers have used the telescoping constructor pattern, in which you provide a constructor with only the required parameters, another with a single optional parameter, a third with two optional parameters, and so on.

Telescoping constructor pattern - does not scale well!

public class NutritionFacts {
private final int servingSize; // (mL) required
private final int servings; // (per container) required
private final int calories; // optional
private final int fat; // (g) optional
private final int sodium; // (mg) optional
private final int carbohydrate; // (g) optional
public NutritionFacts(int servingSize, int servings) { //you know what is this }
public NutritionFacts(int servingSize, int servings, int calories) {//you know what is this }
public NutritionFacts(int servingSize, int servings, int calories, int fat) {//you know what is this }
public NutritionFacts(int servingSize, int servings, int calories, int fat, int sodium) {//you know what is this }
public NutritionFacts(int servingSize, int servings, int calories, int fat, int sodium, int carbohydrate) {//you know what is this }
}

When you want to create an instance, you use the constructor with the shortest parameter list containing all the parameters you want to set:

NutritionFacts cocaCola =
new NutritionFacts(240, 8, 100, 0, 35, 27);

the telescoping constructor pattern works, but it is hard to write
client code when there are many parameters, and harder still to read it.

If the client accidentally reverses two such parameters, the compiler won’t complain, but the program will misbehave at runtime (Item 40).

2)    the JavaBeans pattern, in which you call a parameterless constructor to create the
object and then call setter methods to set each required parameter and each
optional parameter of interest

JavaBeans Pattern - allows inconsistency, mandates mutability
NutritionFacts cocaCola = new NutritionFacts();
cocaCola.setServingSize(240);
cocaCola.setServings(8);
cocaCola.setCalories(100);
cocaCola.setSodium(35);
cocaCola.setCarbohydrate(27);

This pattern has none of the disadvantages of the telescoping constructor pattern. It is easy, if a bit wordy, to create instances, and easy to read the resulting code.

Unfortunately, the JavaBeans pattern has serious disadvantages of its own. Because construction is split across multiple calls, a JavaBean may be in an inconsistent state partway through its construction.

A related disadvantage is that the JavaBeans pattern precludes the possibility of making a class immutable (Item 15), and requires added effort on the part of the programmer to ensure thread safety.

3)      Builder pattern
Combines the safety of the telescoping constructor pattern with the readability of the JavaBeans pattern. Instead of making the desired object directly, the client calls a constructor (or static factory) with all of the required parameters and gets a builder object. Then the client calls setter-like methods on the builder object to set each optional parameter of interest. Finally, the client calls a parameterless build method to generate the object, which is immutable. The builder is a static member class (Item 22) of the class it builds.

// Builder Pattern
public class NutritionFacts {
private final int servingSize;
private final int servings;
private final int calories;
private final int fat;
private final int sodium;
private final int carbohydrate;
public static class Builder {
// Required parameters
private final int servingSize;
private final int servings;
// Optional parameters - initialized to default values
private int calories = 0;
private int fat = 0;
private int carbohydrate = 0;
private int sodium = 0;
public Builder(int servingSize, int servings) {
this.servingSize = servingSize;
this.servings = servings;
}
public Builder calories(int val)
{ calories = val; return this; }
public Builder fat(int val)
{ fat = val; return this; }
public Builder carbohydrate(int val)
{ carbohydrate = val; return this; }
public Builder sodium(int val)
{ sodium = val; return this; }
public NutritionFacts build() {
return new NutritionFacts(this);
}
}
private NutritionFacts(Builder builder) {
servingSize = builder.servingSize;
servings = builder.servings;
calories = builder.calories;
fat = builder.fat;
sodium = builder.sodium;
carbohydrate = builder.carbohydrate;
}
}

Here’s how the client code looks:

NutritionFacts cocaCola = new NutritionFacts.Builder(240, 8).
calories(100).sodium(35).carbohydrate(27).build();

The Builder pattern simulates named optional parameters.

A minor advantage of builders over constructors is that builders can have multiple varargs parameters.

The Builder pattern does have disadvantages of its own. In order to create an object, you must first create its builder. While the cost of creating the builder is unlikely to be noticeable in practice, it could be a problem in some performance critical situations.

In summary, the Builder pattern is a good choice when designing classes whose constructors or static factories would have more than a handful of parameters, especially if most of those parameters are optional. Client code is much easier to read and write with builders than with the traditional telescoping constructor pattern, and builders are much safer than JavaBeans.

Reference: Effective Java 2nd Edition by Joshua Bloch

Item 1: Consider static factory methods instead of constructors


A class can provide a public static factory method, which is simply a static method that returns an instance of the class.

public static Boolean valueOf(boolean b) {
return b ? Boolean.TRUE : Boolean.FALSE;
}

Providing a static factory method instead of a public constructor has both advantages and disadvantages.

Advantages:
1)    Unlike constructors, they have names.
2)    Unlike constructors, they are not required to create a new object each time they’re invoked.
3)    Unlike constructors, they can return an object of any subtype of their return type.
4)    They reduce the verbosity of creating parameterized type instances.

Map<String, List<String>> m =
new HashMap<String, List<String>>();

With static factories, however, the compiler can figure out the type parameters for you. This is known as type inference. For example, suppose that HashMap provided this static factory:

public static <K, V> HashMap<K, V> newInstance() {
return new HashMap<K, V>();
}

Then you could replace the wordy declaration above with this succinct alternative:

Map<String, List<String>> m = HashMap.newInstance();

Disadvantages:
1)    Classes without public or protected constructors cannot be subclassed.
2)    They are not readily distinguishable from other static methods.

They do not stand out in API documentation in the way that constructors do, so it can be difficult to figure out how to instantiate a class that provides static factory methods instead of constructors.

Here are some common names for static factory methods:
• valueOf—Returns an instance that has, loosely speaking, the same value as its
parameters. Such static factories are effectively type-conversion methods.
• of—A concise alternative to valueOf, popularized by EnumSet (Item 32).
• getInstance—Returns an instance that is described by the parameters but
cannot be said to have the same value. In the case of a singleton, getInstance
takes no parameters and returns the sole instance.
• newInstance—Like getInstance, except that newInstance guarantees that
each instance returned is distinct from all others.
• getType—Like getInstance, but used when the factory method is in a different
class. Type indicates the type of object returned by the factory method.
• newType—Like newInstance, but used when the factory method is in a different
class. Type indicates the type of object returned by the factory method.

In summary, static factory methods and public constructors both have their
uses, and it pays to understand their relative merits. Often static factories are preferable,
so avoid the reflex to provide public constructors without first considering
static factories.

Reference: Effective Java 2nd Edition by Joshua Bloch

Tuesday, 3 July 2012

BloomFilter Crash Course

BloomFilters are essentially bit vectors. At a high level BloomFilters work in the following manner:
1.        Add the element to the filter.
2.        Hash it a few times, than set the bits to 1 where the index matches the results of the hash.
When testing if an element is in the set, you follow the same hashing procedure and check if the bits are set to 1 or 0. This process is how a BloomFilter can guarantee an element does not exist. If the bits aren’t set, it’s simply impossible for the element to be in the set. However, a positive answer means the element is in the set or a hashing collision occurred.
Google uses BloomFilters in BigTable to avoid disk lookups for non-existent items.
And Cassandra uses bloom filters to save IO when performing a key lookup: each SSTable has a bloom filter associated with it that Cassandra checks before doing any disk seeks, making queries for keys that don't exist almost free.

http://en.wikipedia.org/wiki/Bloom_filter
http://spyced.blogspot.sg/2009/01/all-you-ever-wanted-to-know-about.html

With Example: http://llimllib.github.com/bloomfilter-tutorial/

http://asemanfar.com/Using-a-bloom-filter-to-optimize-a-SQL-query


Sample Code

public class TestHashingString {

   static String testStringArray[] = { "Raja", "Vimal", "Sundar", "KaniKannan" };

   static String resultArray[] = new String[10];

   static Funnel<String> personFunnel = new Funnel<String>() {
      @Override
      public void funnel(String abc, Sink into) {
         into.putString(abc);
      }
   };

   public static void main(String... args) {
      BloomFilter<String> bloomFilter = BloomFilter.create(personFunnel, 1000);
      int resultCount = 0;

      String holder;
      for (int i = 0; i < 1000; i++) {
         for (int count = 0; count < testStringArray.length; count++) {
            holder = testStringArray[count];
            if (!bloomFilter.mightContain(holder)) {
               resultArray[resultCount++] = holder;
               bloomFilter.put(holder);
            }
         }
      }

      System.out.println(Arrays.deepToString(resultArray));
   }
}