Lazy evaluation

Recently i was writing log4j appender and wanted to use logger in it to log some diagnostic details during custom appender creation, but log4j initialization completes only after appender instance are created, so message logged during this phase are ignored.

I felt the need for lazy initialization in custom appender and started to look at options.

In this blog i will share things that i tried.

One of the thing that came to my mind was Singleton approach but now it is known fact that singleton causes problem with testing and make it impossible to extend it, so approach of mixing concurrency & object construction is not that good.

Incase if singleton is required then it is better to use Dependency Injection framework rather than spoiling your application code.

Lets get back to lazy initialization/eval.

Some programming language like scala/swift etc has support for lazy, so no custom code is required to do this but in java space we still have to write thread safe code to get it right.

Lets look at some options we have in java and what type of performance we get.

- Brute force using Synchronized
This is the most simple and inefficient one, scala is using this approach. Scala one is available @ ScalaLazy.java



- Double lock
This is little complex to write and gives good performance.

- Using Future task
This approach is simple to write and gives good performance.


Double lock approach gives the best performance and brute force one is worst. I did quick bench mark for 1 Million calls using different number of thread.

Single lock performance is very bad, lets have look at the number by removing single lock to see how Double Lock & Future Task performed.

These benchmark are done very quickly but detailed benchmark numbers should be close.

Code for this blog post is available @ github

Experiment with ConcurrentHashmap

I am investigating memory issue in one of my recent project where data is kept in memory for fast access, but memory footprint of application is very high.
This application was heavily using CHM(i.e Concurrenthashmap), so no brainier guess was required that CHM was the issue. I did memory profiling session to find how much really CHM was taking.
I was surprised with result that CHM was taking around 50% of the memory. So it was confirmed that CHM was the issue, it is fast but not memory efficient.

Why CHM is so fat ?

• Key/Values are wrapped by Map.Entry object , this create extra object per object. 
• Each segment is Re-entrant lock, so if you have lot of  small CHM and concurrency level is default then there will be lot of lock object and that will come in top list. 
• and many more states for house keeping activities.

All of above objects makes very good contribution to memory.

How can we reduce memory footprint
If is difficult to reduce memory footprint of CHM and possible reason that i can think of are

• It has to support old interface of Map 
• hash code collision technique used by java map are closed, closed hashing is based on creating Linklist on collision, closed hashing is very fast for resolution, but it is not CPU cache friendly, especially if nodes turns in big link list. There is interesting article about LinkList problem 

So we need alternate CHM implementation which is memory efficient.

Version 2 of CHM

I started to create version of CHM which has low memory foot print, target is come a close as array. I also used alternate hash code collision techniques to check the performance, their many options for Open_addressing.
I tried below options.

• Linear probing - performance was not that great, although this is most cpu cache friendly. Need to spend some more time to get it right.
• Double_hashing - Performance was in acceptable range.

Lets measure CHM V2 

• Memory footprint

There is big gain in terms of memory, CHM takes around 45%+ more than raw data , new implementation LCHM is very much close to Array type.

• Single thread PUT performance

CHM out performs in PUT test, new implementation is around 50 to 80 Millisecond slower for 1 Million items. 50 to 80 ms is not noticeable delay and i think it is good for application where latency requirement is  in seconds and in case if latency requirement is in millisecond/nanosecond then any way CHM will not be good choice.

Reason for slow performance of LCHM is hash collision technique, double hashing is used for resolving has code collision. 

• Concurrent Add performance 

New implementation perform slightly better when multiple threads are used to write to map.

• Get Performance

 Performance of get is slightly slower as compared to CHM.

Conclusion

New implementation out performs in memory test and it is bit slow in in get/put test, there are couple of things that can be done to improve performance of get/put and all the performance difference that we see is due to probing technique used.

•  Probing technique can be improved, linear probing technique can used to to get cache friendly access. 
• It is very easy to make probing technique parallel.