I have been working on Scala recently and it has been a pure pleasure. I am in love with the language. And Yes! it indeed is a beast.

Generics/Parametrization is something that has always kept me on the hook even after good amount of experience in it. Thanks to Scala and lectures by Martin Odersky, I am much better now. There have been some realizations on the go, but to explain that I will first have to explain some basics. Though theoretical and boring at many places, I promise this will improve your architect skills if understood well

I have planned the post in 4 parts:

1. Brief overview of Co-variance & Contra-variance
2. Above paradigm behavior in Java, Python, C#
3. Overview and short-comings of Generics in Java. Design flaw with Arrays
4. A detailed theoretical explanation with help of Scala

Before starting, there is one very important theorem called Liskov Substitution principle in object oriented world. This should always be behind your mind while designing API’s. It states-

Let  be a property provable about objects  of type . Then  should be provable for objects  of type  where  is a subtype of .

The above means- If “A” extends “B” (A <: B), then all the things that one can do with “B” should also be legal with “A”.

Co-variance & Contra-variance

 Wiki will give you a formal definition. Crudely:

• Co-variance ( <: ) is converting type from wider type to narrow. In Java terms- ? extends E*
• Contra-variance (>: )is converting type from narrow to wider. In Java terms- ? super E*
• In-variant cannot be converted

class Animal {
}

class Dog extends Animal{
}

class Example{

  void run(){

     Dog dog = new Dog();
     getAnimal(dog);

}

void getAnimal(Animal animal){

.....

}

}

In the above example, one is ultimately doing

Animal animal = dog

So you are converting a dog type (narrow) to Animal type (wider). This is contra-variance. The reverse of it is Co-variance. The above paradigm is also followed in C# and python.

For co-variance:

class A{

  Animal getCreature(){
    return new Dog();
  }

}

class B extends A{

  Dog getCreature(){
    return new Dog();
  }

}

Check the return type of the getCreature function. getCreature() ultimately returns an Animal. But it returns type of Dog in class B. This is co-variance. The above is perfectly legal, because the code that invokes getCreature() of class A expects an Animal in return; which class B provides a Dog (ultimately dog is an animal. Vice-versa wont work, think!)

Invariance is when the type cannot be converted.

By default return types of functions in Java, C# and python are co-variant and argument types are invariant.

Points to Remember:

I will raise some points now and the explanation will be given by the end. The whole point of the post are the below points.

1. Contravariant types can only appear in places, where you write something (i.e. parameter types) and covariant types can only appear in places, where you read something. [P1]
2. Co-variance is only suitable when the data is immutable. More on it below. [P2]

I will first raise the issues caused in Java by not following [P1] i.e Arrays disaster for which Generics (type erasure) will be discussed. And then issues with [P2]. Finally improvements and how the issue was dealt successfully in Scala in the next post

This is  the first part of series of posts I plan to put-up on effective memory-centric cache implementations.

Well I have been working and going through different cache implementations in Java. Below is a discussion on some of them. The aim is to choose the perfect cache for a respective scenario. Below I have tried to explain the basics of Java dependencies to keep it language independent.

Now in general it is found out that LRU (Least Recently Used) is preferable for most of the scenarios. And it can be very easily be implemented in Java by extending a beautiful data structure “LinkedHashMap” and overriding removeEldestEntry(final Map.Entry<A, B> eldest).  More on it here. But the issue with it is the size. How will you set the size of the cache? If the cache size is too small, it would not solve the purpose. If it is too large, it might eat away applications required memory.

Fixing the size of the cache indeed is tough. Ideally you would want a cache that scales according to the application. Under low memory consumption by application, one wont mind cache taking too much of memory. Under high memory contention, one would want cache size to decrease (though it will create performance problems as cache might be non-existent then. But it is atleast better than repetitive Full GC’s).

Hence I have been in search for an effective implementation of Cache which is:

• LRU
• Size variant depending upon the available Memory.

Though it is still work in progress, I will be discussing about the second option above in this post and the next. And a culmination of both in the third post.

Scaling of Cache

The aim is be to generate specifications based on quantitative analysis to for a perfect outlook to implement such a scenario.

To implement such a case, we need some support from the language which shall timely give us input about the available memory; Better if it can itself remove objects from cache. Luckily Java gives us this flexibility be providing us with a java.lang.ref package which provides limited communication with Garbage Collector.

For analysis here I have taken the code from from org.neo4j.kernel.impl.cache package of Neo4J graph database. I have slightly modified the code to generate statistics. The code is a property of NeoTechnologies and is used here only for educational purposes. It very well implements what we desire. The link to cache is here. Primarily it has 2 cache versions:

• SoftRefCache
• WeakRefCache

Cache & Performance – In Worst Case Scenario

I have carried some tests to decide which version should be used under what scenario. The below is analysis under high contention where all different objects are repeatedly added to cache. In reality, this can only happen under heavy stress.

The code to exhibit the above can be found out at CacheTest.java inside cache.neo4j package. Roughly it is:

private void go() {
SoftLruCache<EntityInteger> cache = new SoftLruCache<EntityInteger>(“Soft Cache”);
test(cache);
}

private void go2()
{
WeakLruCache<EntityInteger> cache2 = new WeakLruCache<>(“Weak Cache”);
test(cache2);
}

private void test(ReferenceCache<EntityInteger> cache) {
for (int i = 0; i < Integer.MAX_VALUE; i++) {
cache.put(new EntityInteger(i));
}
}

Below is individual analysis for each of the case. Though it is not true comparison of cache’s but rather SoftReference and WeakReference.
My configuration:

java version “1.7.0_05″
Java(TM) SE Runtime Environment (build 1.7.0_05-b05)
Java HotSpot(TM) Client VM (build 23.1-b03, mixed mode, sharing)
Windows 7.
intel i3 processor.
JVM arguments: -server  -Xmx200M -verbose:gc -XX:+PrintGCDetails (Xmx means JVM can at max hold 200 mb of RAM)

SoftLruCache

Below is a graph of size of cache vs time.

The memory behavior:

* Above the memory result is not correct as profiler itself might be consuming decent amount of memory. Without loss of generality, once can assume that it is consuming about 80-100 mb.

And the log.

Results:

• The memory expand to full 200mb allotted, after which results in repeated Full GC’s which frees up memory. During which, the cache size drastically reduces from ~1,700,000 to mere 400,000.
• The above cycle is repeated periodically. With the cache size increasing to 1,400,000 and then a drastic fall to less than 100,000. In some cases to even below 1000.
• On an average, around 75% of applications running time was spent in Garbage Collection.

Next post will be the same analysis on Weak Reference. Later repetition for a more realistic scenario

References:

For more on java.lang.ref:

1. http://docs.oracle.com/javase/7/docs/api/index.html

For one of the projects where Neo4J is being used, I have been working on implementing K-Shortest Path algorithm using Yen’s loopless improvised algorithm.

Now an issue in the algorithm is that; Say  in computing top 4 shortest path, what the algorithm does is that it when computing the 2nd shortest path; It removes arcs of the 1st shortest path from the graph. And so removes the 2nd while computing 3rd shortest path and so on. And later in the end, it adds back all the removed arcs.

The problem now is that when one thread is computing a kth shortest path, other threads cannot use the algorithm as the graph is not in its complete shape. i.e. because first thread in the computation has temporarily removed some arcs, and the same graph cannot be used for any other purpose till those arcs are again added. Hence multiple instances of the algorithm cannot be used in parallel. One can solve the problem by  instead of removing them, have a flag in the relationship for a particular par of nodes. Flag will be cleared once the computation is over. But when running many instances in parallel there shall be many  such key value pairs in the relationships.There is an extra load in teh end to clear the flags.

Now this would have been a problem while using any other graph library. But the transaction model in Neo4J solves the above issue.

Here is the crazy part which I am unsure of if at all its a good practice:
I will have the code inside a transaction, but not let the transaction succeed. i.e. I will implement the algorithm and remove the respective arcs in the process, when I have the desired output, I will call the transaction a failure. hence the arcs are never removed and the same instance of the algorithm can be used. Further there will be no need to later add those arcs as in reality they were never removed.

This is so cool. Though there is another issue with it as pointed out by Mattias Persson of NeoTechnologies-

The only problem I  see here is that removing relationships will grab write locks which will be held throughout the transaction and prevent any other shortest path algo to remove those relationships as long as the transaction is alive.

How big this issue is, I do not know. But if carefully crafted should behave well. In any case its way better than removing the arcs and halting all the other computations on the graph.

More on it here.

New Development:
Another reason why I use N3o4J is to reduce the development time.  Reason being had I used some graph service at expense of memory, rebuilding the graph even to test small things takes a lot of time. With Neo4J I dont have to worry about that. Though with JUNG the problem can be solved by using a custom class loader and using the test’ as plugins hence saving time. But all this requires effort.