Thoughts on GC friendly programmig

Garbage Collections in Java gets triggered automatically to reclaim some of the occupied memory by freeing up objects. Hotspot VM divides the Heap into different memory segments to optimize the garbage collection cycle. It mainly separates objects into two segments - young generation and old generation.

Objects get initially created into young gen. Young gen is quite small and thus minor garbage collection runs on it. If objects survive the minor GC; then they get moved to the old gen. So it's better to use short-lived and immutable objects than long-lived mutable objects.

Minor GC is quite fast (as its runs on smaller memory segment) and hence it's less disruptive. The ideal scenario will be that GC never compacts old gen. So if full GC can be avoided you will achieve the best performance.

So a lot depends on how you have configured your heap memory and another important factor is do you code keeping in mind these aspects.

http://www.ibm.com/developerworks/library/j-leaks/
http://stackoverflow.com/questions/6470651/creating-a-memory-leak-with-java/6471947#6471947

Graph DFS traversal

This post, I will be focusing on Depth-First traversal. 

The difference between BFS and DFS traversal lies in the order in which vertices are explored. And this mainly comes due to the data structure used to do traversal. BFS uses queue whereas DFS uses a stack data structure to perform traversal. Below diagram illustrates the order of traversal. 

DFS Progress

DFS Implementation

DFS implementation uses UndirectedGraph.java from the BFS post. Below class has two implementations of DFS traversals (recursive and iterative). Method, traverse(..) is stack based implementation whereas traverseRecur(..) is recursive implementation.

package graph.algo;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.Objects;
import java.util.Set;

/**
 * Depth-First Traversal of a graph represented as adjacency list
 * 
 * @author Siddheshwar
 * 
 */
public class DFS<V> {
 private Graph<V> graph; // graph on which DFS will be performed
 private Deque<V> stack; // Deque used to implement stack
 private Set<V> visited; // stores set of visited nodes

 public DFS(Graph<V> graph) {
  this.graph = graph;
  stack = new ArrayDeque<>();
  visited = new LinkedHashSet<>(); // to maintain the insertion order
 }

 /**
  * Iterative/stack based DFS implementation
  * 
  * @param source
  */
 public void traverse(V source) {
  Objects.requireNonNull(source, "source is manadatory!");
  if (this.graph == null || this.graph.isEmpty()) {
   throw new IllegalStateException(
     "Valid graph object is required !!!");
  }

  stack.push(source);
  this.markAsVisited(source);
  boolean pop = false;
  V stackTopVertex;
  System.out.print("  " + source);

  while (!stack.isEmpty()) {

   if (pop == true)
    stackTopVertex = stack.pop();
   else
    stackTopVertex = stack.peek();

   List<V> neighbors = graph.getAdjacentVertices(stackTopVertex);

   if (!neighbors.isEmpty()
     && hasUnvisitedNeighbor(neighbors, visited)) {
    for (V a : neighbors) {
     if (!this.isVertexVisited(a)) {
      System.out.print("  " + a);
      visited.add(a);
      stack.push(a);
      // break from loop if an unvisited neighbor is found
      break;
     }
    }
   } else {
    // if all neighbors are visited
    pop = true;
   }
  }
 }

 /**
  * Recursive implementation of DFS
  * 
  * @param source
  */
 public void traverseRecur(V source) {
  Objects.requireNonNull(source, "source is manadatory!");

  this.markAsVisited(source);
  System.out.print(" " + source);

  // get neighbors in sorted manner
  List<V> neighbors = this.graph.getAdjacentVertices(source);

  for (V n : neighbors) {
   if (!this.isVertexVisited(n)) {
    traverseRecur(n);
   }
  }
 }

 /**
  * checks if any of the neighbor is unvisited
  * 
  * @param neighbors
  * @param visited
  * @return
  */
 private boolean hasUnvisitedNeighbor(List<V> neighbors, Set<V> visited) {
  for (V i : neighbors) {
   if (!visited.contains(i))
    return true;
  }
  return false;
 }

 /**
  * Returns true if vertex is already visited
  * 
  * @param i
  * @return
  */
 private boolean isVertexVisited(V i) {
  return this.visited.contains(i);
 }

 /**
  * Mark a vertex visited
  * 
  * @param i
  */
 private void markAsVisited(V i) {
  this.visited.add(i);
 }

 // test method
 public static void main(String[] args) {
  Graph<Integer> graph = new Graph<>();
  graph.addEdge(1, 2);
  graph.addEdge(1, 5);
  graph.addEdge(1, 6);
  graph.addEdge(2, 3);
  graph.addEdge(2, 5);
  graph.addEdge(3, 4);
  graph.addEdge(5, 4);

  // for undirected graph
  graph.addEdge(2, 1);
  graph.addEdge(5, 1);
  graph.addEdge(6, 1);
  graph.addEdge(3, 2);
  graph.addEdge(5, 2);
  graph.addEdge(4, 3);
  graph.addEdge(4, 5);

  System.out.print("DFS -->");
  DFS<Integer> dfs = new DFS<>(graph);

  /**
   * stack based DFS traversal
   */
  dfs.traverse(1);

  /**
   * Recursive DFS traversal
   */
  // dfs.traverseRecur(1);

  // validation
  /**
   * after traversal; stack should be empty. And visited should have
   * vertices in DFS order
   */
  System.out.println("\nIs Stack is empty :"
    + (dfs.stack.isEmpty() ? "yes" : "no"));
  System.out.println("visited :" + dfs.visited);

 }

}

Output:
DFS -->  1  2  3  4  5  6
Is Stack is empty :yes
visited :[1, 2, 3, 4, 5, 6]

Time Complexity

Assuming above implementation of Graph i.e. Adjacency List, |V| is number of vertices and |E| is number of edges. 

So complexity is O(|V|+|E|)

--
happy learning !!!

Scalability - Getting hang of Seconds

This post list some of the most important numbers which are important for engineers to do back of envelope calculations. This post, I have focussed on seconds. If you hear someone telling that his service gets 1 million hits a day; don't get bogged down with the numbers, it just means he gets 10 requests per second.

Seconds

# Seconds in a day = 86400  (=24*60*60)

                                = 0.85*10^5

                                = 10^5

                                = 0.1 million

# Seconds in a month = 2592000 (=30*86400)

                                     =  2.5*10^6

                                     = 2.5 millions

If an online site gets 10 million hits per day then it means on an average it gets 100 requests/sec.

If an online site gets 10 million hits per month then it means on an average it gets 4 requests/sec.

# Seconds in a year = 31104000 (=12*259200)

                                  = 31 millions

                                  = Pie * 10^7

   If we treat a year as 365.25 days then also, # seconds in a year would be 3,155,7600 which would approximate to 31 million. 

# Seconds in a century = 3,155,760,000 seconds (considering 1 year = 365.25 days)

                                       = 3.15 billions 

                                     

Nanocentury is 1 billionth of a century. So, a nanocentry = 3.15 seconds.

i.e. Pie seconds are there in a nano century. This is also known as Duff's Rule. 

                    

Designing REST URI for supporting multiple content type

Resources can be represented in multiple formats - JSON, XML, Atom, Binary formats like png, text and even proprietary formats. If client request a resource the REST service transfers the state of a resource (and not the resource itself) in the appropriate format.

Assume that you are designing RESTful interface for providing metadata for Cars and your service gets consumed by many clients, some traditionals as well as few startups. So each one of them have their own requirements to provide response in the given format. Let's see what are available options-

Approach 1: One URI per representation

http://www.myservice.com/cars
http://www.myservice.com/cars/xml

The first URI is default representation of the resource and second one returns the response in xml format. Both URI are different so there will be different handlers (end point) and hence the response can be easily returned in appropriate format.

Approach 2: Use Parameter of URI

http://www.myservice.com/cars?format=xml

This approach is easy to read and understand.

Approach 3: Single URI for all representation

This approach comes from the fact that if client is essentially asking for the same resource then why do we need different URIs. Remember, REST uses HTTP; can we leverage HTTP ACCEPT header to get different representation of the same resource. This is process of selecting the best representation for a given resource- termed as Content Negotiation. 

Content Types

HTTP uses Internet media types (originally known as MIME types) in the content-type and accept header fields. Internet media types are divided into 5 top level categories: text, image, audio, video and application. And then these types are further divided into several subtypes:

• text/xml : default content type for text message
• text/html : commonly used type used in browsers 
• text/xml, application/xml: Format used for xml exchanges 
• image/gif, image/jpeg, image/png: image types
• application/json: language independent light weight data-interchange text format 

GET /cars/

Accept: application/json

So respect the HTTP headers and everything works out. 

This approach could be bit code intensive for some frameworks like Django as you need to dig into headers and decode what clients wants. But most of the Java frameworks handle it though annotation. 

Final Note

No matter which approach you use. It would be great if you stick to one across the services.  Prefer to be consistent even if that leads to not being very right!

References

https://www.ics.uci.edu/~fielding/pubs/dissertation/rest_arch_style.htm#sec_5_2_1_2

http://www.restapitutorial.com/lessons/restquicktips.html

http://www.informit.com/articles/article.aspx?p=1566460

PUT vs POST for Modifying a Resource

Debate around PUT vs POST for resource update is quite common; I have had my share as well. Debate is NOT un-necessary as the difference is very subtle. One simple line of defence by many people is that if the update is IDEMPOTENT then we should use PUT else we can use POST. This explanation is correct to a good extent; provided we clearly understand if a request is truly Idempotent or not. 

Also, lot of content is available online which causes confusion. So, I tried to see what the originators of REST architectural style themselves say. This post might again be opinionated, or have missed few important aspects. I have tried to be as objective as possible. Feel free to  post your comments/openions :)

Updating a Resource

For our understanding, let's take a case that we are dealing with an account resource which has three attributes: firstName, lastName and status. 

Updating Status field:

Advocates of PUT consider below request to be IDEMPOTENT. 

HTTP 1.1 PUT /account/a-123

{

   "status":"disabled"

}

Reality is that, above request is NOT idempotent as it's updating a partial document. To make it idempotent you need to send all the attributes. So that line of defence is NOT perfect. 

HTTP 1.1 PUT /account/a-123

{

   "firstName":"abc",

   "lastName":"rai",

   "status":"disabled"

}

Below article tells very clearly that, if you want to use PUT to update a resource, you must send all attributes of the resource where as you can use POST for either partial or full update. 

https://stormpath.com/blog/put-or-post

So, you can use POST for either full or partial update (until PATCH support becomes universal). 

What the originator of REST style says

The master himself suggest that we can use POST if you are modifying part of the resource. 

http://roy.gbiv.com/untangled/2009/it-is-okay-to-use-post

My Final Recommendation

Prefer POST if you are doing partial update of the resource. 
If you doing full update of the resource and it's IDEMPOTENT, use PUT else use POST.