Monday, November 12, 2018

Micro Benchmarking with JMH - "Measure, don’t guess"


Java Micro Benchmark with JMH

  • Java Microbenchmark Harness (JMH) is a Java toolkit by OpenJDK for creating benchmarks.  
  • It is an open source framework provides benchmarking for measuring the performance of your Java code.

"Measure, don’t guess" :-


We’ve all faced performance problems in our projects and were asked to tune random bits in our source code and  hoping that performance will get improved. Instead, we should set up a stable performance environment  (operating system, JVM, application server, database), measure continuously, set some performance goals then, take action when our goals are not achieved. Continuous delivery, continuous testing is one thing,  but continuous measuring is another step.


What is JMH ?

  • JMH is a Java harness for building, running, and analyzing nano/micro/milli/macro benchmarks written in Java and other languages targeting the JVM.

When to use Micro Benchmarking ?


  • You identified the code segment that eats most of the resources in your application and the improvement can be tested by micro benchmarks.
  • You can not identify the code segment that will eat most of the resources in an application but you suspect it.

How to do a Micro Benchmark ?

  • We often do not worry about the performance requirements. We start with building functionality and concentrate on making things work and don’t focus on how. Once the software goes to production, we will be facing the inevitable. 
  • It is good to have the performance objectives written down before writing the code.
    We should weigh the importance of performance with respect to the functional requirements and should come up with a balance between them.
  • Just because your code runs in a certain way in an extremely isolated artificial situation does not mean it will run in the  same way inside your production code. To name but a few issues, in a real program the CPU caches will be subject to pressures from other parts of your code, any object creation will have a downstream effect on GC and the JIT may have inlined and compiled code from other parts of your code that conflict with the code you have benchmarked. 

Why are Java Microbenchmarks Hard ?

  • Writing benchmarks that correctly measure the performance of a small part of a larger application is hard. There are many optimizations that the JVM or underlying hardware may apply to your component when the benchmark executes that component in isolation. These optimizations may not be possible to apply when the component is running as part of a larger application. Badly implemented microbenchmarks may thus make you believe that your component's performance is better than it will be in reality.
  • Writing a correct Java microbenchmark typically entails preventung the optimizations the JVM and hardware may apply during microbenchmark execution which could not have been applied in a real production system. That is what JMH - the Java Microbenchmark Harness - is helping you do.  

Purpose

  • Benchmark is the process of recording the performance of a system.
  • JMH is a Java harness for building, running, and analyzing nano/micro/milli/macro benchmarks written in Java and other languages targeting the JVM.
  • it takes care of warm up iterations, forking JVM processes so that benchmarks don't interfere with each other, collating results and presenting then in a uniform manner.

Micro benchmarks are generally done for two reasons.

  • To compare different approaches of code which implements the same logic and choose the best one to use.
  • To identify any bottlenecks in a suspected area of code during performance optimization.

Benchmarking Modes:

At a basic level, JMH has two main types of measure:  throughput and time-based.

Throughput Measuring

  • Throughput is the amount of operations that can be completed per the unit of time. JMH maintains a collection of successful and failed operations as the framework increases the amount of load on the test.  
  • Ensure the method or test is well isolated and dependencies like test object creation is done outside of the method or pre-test in a setup method.  
  • With Throughput, the higher the value, the better as it indicates that more operations can be run per unit-time.

Time-Based Measuring

  • Time-based measuring is the counter-partner to throughput. 
  • The goal of time-based measuring is to identify how long a particular operation takes to run per unit-time.

JMH Commands

  • i - Number of measurement iterations to do. Measurement iterations are counted towards the benchmark score.
  • bs - Batch size: number of benchmark method calls per operation.
  • r - Minimum time to spend at each measurement iteration.
  • wi - Number of warmup iterations to do.
  • wbs - Warmup batch size: number of benchmark method calls per operation.
  • w - Minimum time to spend at each warmup iteration.
  • to - Timeout for benchmark iteration.
  • t - Number of worker threads to run with.
  • bm - Benchmark mode.
  • si - Should JMH synchronize iterations?
  • gc - Should JMH force GC between iterations?
  • foe - Should JMH fail immediately if any benchmark had experienced an unrecoverable error?
  • v - Verbosity mode.
  • f - How many times to fork a single benchmark. Use 0 to disable forking altogether.
  • wf - How many warmup forks to make for a single benchmark. 

 There are two way to run a benchmark:

  1. The recommended way is to generate a pom file and use that to create a jar. The mvn install uses the shade plugin to create a jar file so that you don't have create a main method.
  2. Add the JMH maven dependencies to your pom file and then add a main method to your code using the Runner object.This is useful if you want to run in your IDE. 

 Method 1 - Using command line argument


 Generate a pom file using this mvn command.

mvn archetype:generate
          -DinteractiveMode=false
          -DarchetypeGroupId=org.openjdk.jmh
          -DarchetypeArtifactId=jmh-java-benchmark-archetype
          -DgroupId=com.jenkov
          -DartifactId=first-benchmark
          -Dversion=1.0

  • This will create a project called test with an empty benchmark in it called MyBenchmark.
  • To build the project just use mvn clean install. This will build a jar called benchmark.jar
  • It is the benchmark.jar that should be run to run the benchmark not any other jars produced along the way that will be in your target folder.

To run use the command  java -jar target/benchmarks.jar JMHSample04 -wi 5 -t 1 -i 5 -f 1


 Method 2 - For running in your IDE


Add these dependencies to your Maven pom.xml file:

  org.openjdk.jmh
  jmh-core
  1.5.1


  org.openjdk.jmh
  jmh-generator-annprocess
  1.5.1


Then decide which methods you want benchmarked and add the annotation @Benchmark to them. If you need any initialisation code add it in a method which should be marked @Setup. 

The easiest way to run the benchmark is by adding by adding this implementation into your main method.
public static void main(String[] args) throws RunnerException {
        Options opt = new OptionsBuilder()
                .include(JMHSample04.class.getSimpleName()).
                warmupIterations(5).
                measurementIterations(5).
                threads(1).
                forks(1).
                build();
        new Runner(opt).run();
}


JMH benchmark Results :

As an example to see the format of a JMH benchmark, this is what my results looked like:

Example 1 : Arrays sort and Collection sort Benchmark Comparison

package org.sample;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.Random;
import java.util.concurrent.TimeUnit;
import org.openjdk.jmh.annotations.Benchmark;
import org.openjdk.jmh.annotations.BenchmarkMode;
import org.openjdk.jmh.annotations.Level;
import org.openjdk.jmh.annotations.Mode;
import org.openjdk.jmh.annotations.OutputTimeUnit;
import org.openjdk.jmh.annotations.Scope;
import org.openjdk.jmh.annotations.Setup;
import org.openjdk.jmh.annotations.State;

@State(Scope.Thread)
public class JMHSample02 {
 List arrayList;
 int[] array;
 Random random;

 @Setup(Level.Trial)
 public void init() {
  random = new Random();
  array = new int[150];
  arrayList = new ArrayList();
  for (int i = 0; i < 150; i++) {
   int randomNumber = random.nextInt();
   array[i] = randomNumber;
   arrayList.add(new Integer(randomNumber));
  }
 }

 @Benchmark
 @BenchmarkMode(Mode.Throughput)
 @OutputTimeUnit(TimeUnit.SECONDS)
 public void arraysSort() {
  Arrays.sort(array);

 }

 @Benchmark
 @BenchmarkMode(Mode.Throughput)
 @OutputTimeUnit(TimeUnit.SECONDS)
 public void collectionsSort() {
  Collections.sort(arrayList);
 }
}


JMH benchmark Results :



Example 2 : Java 8 Stream API (Parallel Stream vs Sequential Stream vs  for-each vs iterator )


Java 8 claimed that Stream API would employ multi-core CPUs  to process data in parallel fashion which would eliminate difficulties  of  dealing with multi-thread  codes , as well as gaining performance advantages obtained from  multicored CPUs. 
 
Stream parallel one is the slowest one among four approaches of summing  integers in array.

package org.sample;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.concurrent.TimeUnit;
import org.openjdk.jmh.annotations.Benchmark;
import org.openjdk.jmh.annotations.BenchmarkMode;
import org.openjdk.jmh.annotations.Mode;
import org.openjdk.jmh.annotations.OutputTimeUnit;
import org.openjdk.jmh.annotations.Scope;
import org.openjdk.jmh.annotations.Setup;
import org.openjdk.jmh.annotations.State;

@State(Scope.Benchmark)
public class JMHSample_01_HelloWorld {

 volatile int counts = 9999999;
 volatile List values = new ArrayList<>(counts);
 volatile int processors = Runtime.getRuntime().availableProcessors();

 @Setup
 public void setup() {
  populate(values);

 }

 public void populate(List list) {
  for (int i = 0; i < counts; i++) {
   if (i < counts / 2) {
    list.add(i, i);
   } else {
    list.add(i, i - counts);
   }
  }
 }

 @Benchmark
 @BenchmarkMode(Mode.Throughput)
 @OutputTimeUnit(TimeUnit.MICROSECONDS)
 public int iteratorSumIntegers() {
  int result = 0;
  Iterator ite = values.iterator();
  while (ite.hasNext()) {
   result += (int) ite.next();
  }
  return result;
 }

 @Benchmark
 @BenchmarkMode(Mode.Throughput)
 @OutputTimeUnit(TimeUnit.MICROSECONDS)
 public int fooEachSumIntegers() {
  int result = 0;
  for (Integer value : values) {
   result += value.intValue();
  }
  return result;
 }

 @Benchmark
 @BenchmarkMode(Mode.Throughput)
 @OutputTimeUnit(TimeUnit.MICROSECONDS)
 public int parallelSumIntegers() {
  int result = values.parallelStream().mapToInt(i -> i).sum();
  return result;
 }

 @Benchmark
 @BenchmarkMode(Mode.Throughput)
 @OutputTimeUnit(TimeUnit.MICROSECONDS)
 public int sequentialSumIntegers() {
  int result = values.stream().mapToInt(i -> i).sum();
  return result;
 }
}


JMH benchmark Results :


Example 3 : "Protobuf performs up to 6 times faster than JSON."


Protobuf, the binary format crafted by Google, surpasses JSON performance even on JavaScript environments like Node.js/V8 and web browsers.

Protocol buffers, or Protobuf, is a binary format created by Google to serialize data between different services. Google made this protocol open source and now it provides support, out of the box, to the most common languages, like JavaScript, Java, C#, Ruby and others. In our tests, it was demonstrated that this protocol performed up to 6 times faster than JSON.



package org.sample;

import java.io.FileInputStream;
import java.io.FileOutputStream;
import java.io.IOException;
import java.util.concurrent.TimeUnit;
import org.openjdk.jmh.annotations.Benchmark;
import org.openjdk.jmh.annotations.BenchmarkMode;
import org.openjdk.jmh.annotations.Level;
import org.openjdk.jmh.annotations.Mode;
import org.openjdk.jmh.annotations.OutputTimeUnit;
import org.openjdk.jmh.annotations.Scope;
import org.openjdk.jmh.annotations.Setup;
import org.openjdk.jmh.annotations.State;
import com.proto.StudentBookProtos;
import com.proto.StudentService;
import com.proto.model.StudentBook;

@State(Scope.Thread)
public class JMHSample04 {

 private byte[] studentBookAsJSON;
 private StudentBook studentBookObject;
 private StudentBookProtos.StudentBook.Builder studentBuilder;
 private StudentService studentService;

 @Setup(Level.Trial)
 public void init() {
  studentService = new StudentService();
  studentBookObject = studentService.getStudentBookObject();
  studentBuilder = studentService.getStudentBookProtoObject();
  studentBookAsJSON = studentService.studentBookAsJSONByte(studentBookObject);

  try (FileOutputStream output = new FileOutputStream("abc_proto.txt")) {
   studentBuilder.build().writeTo(output);
   output.close();
  } catch (IOException e) {
   e.printStackTrace();
  }

  try (FileOutputStream output = new FileOutputStream("abc_json.txt")) {
   output.write(studentBookAsJSON);
   output.close();
  } catch (IOException e) {
   e.printStackTrace();
  }

 }

 @Benchmark
 @BenchmarkMode(Mode.Throughput)
 @OutputTimeUnit(TimeUnit.SECONDS)
 public void writeProtoToFile() {
  try (FileOutputStream output = new FileOutputStream("abcd_proto.txt")) {
   studentBuilder.build().writeTo(output);
   output.close();
  } catch (IOException e) {
   e.printStackTrace();
  }
 }

 @Benchmark
 @BenchmarkMode(Mode.Throughput)
 @OutputTimeUnit(TimeUnit.SECONDS)
 public void writeJSONToFile() {
  try (FileOutputStream output = new FileOutputStream("abcd_json.txt")) {
   output.write(studentBookAsJSON);
   output.close();
  } catch (IOException e) {
   e.printStackTrace();
  }
 }

 @Benchmark
 @BenchmarkMode(Mode.Throughput)
 @OutputTimeUnit(TimeUnit.SECONDS)
 public com.proto.StudentBookProtos.StudentBook deserialize_protobuf_to_student_object() {
  com.proto.StudentBookProtos.StudentBook studentBook = null;
  try (FileInputStream inputStream = new FileInputStream("abc_proto.txt")) {
   studentBook = com.proto.StudentBookProtos.StudentBook.parseFrom(inputStream);
   inputStream.close();
  } catch (IOException e) {
   e.printStackTrace();
  }
  return studentBook;
 }

 @Benchmark
 @BenchmarkMode(Mode.Throughput)
 @OutputTimeUnit(TimeUnit.SECONDS)
 public StudentBook deserialize_json_to_student_object() {
  StudentBook studentBook = null;
  try (FileInputStream inputStream = new FileInputStream("abc_json.txt")) {
   byte fileContent[] = new byte[(int) inputStream.available()];
   inputStream.read(fileContent);
   studentBook = studentService.getStudentBookFromJSONByte(fileContent);
   inputStream.close();
  } catch (IOException e) {
   e.printStackTrace();
  }
  return studentBook;
 }
}

JMH benchmark Results :

Sunday, July 8, 2018

Building a high performance Java application

Most of the time developers expect that performance optimization is a complicated topic that requires a lot of experience and knowledge.Optimizing an application to get the best performance possible isn’t an easy task. But that doesn’t mean that you can’t do anything if you haven’t acquired that knowledge. There are several easy ways to follow recommendations and best practices which help you to create a well-performing application.

System resources like threads, database connections, socket connections, File IO streams, Socket IO streams, JNI calls are the real bottleneck of a java application. If you will reuse them in a proper way then there will be a big performance impact into an application.

Java application bottleneck (CPU, IO, Heap usage) factors 

  • Excessive big data encryption/decryption with strongest algorithm 
  • Excessive remote web service call and creating/closing socket connections
  • Frequent File IO operations and Reading/Scanning a physical directory to lookup specific file
  • Huge loggers writing into log file (writing tons and tons of data to disk)
  • Regular expression and compiling regex Patterns
  • JNI Java Native method calls like C/C++/.Net
  • Too many application active threads
  • Excessive GC cycles going on & Large war size with maximum number of jars
  • Uncontrolled pooling (connections/objects/threads) &  complicated SQL query execution
  • Code problems for excessive back-end calls like 'infinite loops'




How would you improve performance of a Java application

  • Pool valuable system resources like threads, database connections, socket connections etc. Emphasize on reuse of threads from a pool of threads. Creating new threads and discarding them after use can adversely affect performance. Also consider using multi-threading in your single-threaded applications where possible to enhance performance. Optimize the pool sizes based on system and application specifications and requirements. Having too many threads in a pool also can result in performance and scalability problems due to consumption of memory stacks (i.e. each thread has its own stack.) and CPU context switching (i.e. switching between threads as opposed to doing real computation.)
  • Minimize network overheads by retrieving several related items simultaneously in one remote invocation if possible. Remote method invocations involve a network round-trip, marshaling and unmarshaling of parameters, which can cause huge performance problems if the remote interface is poorly designed.
  • Distributed cache(Infinispan  in-memory data grid platform for fast data access , In-memory data grids are commonly used as low-latency, highly available and elastic data storage backends, often as NoSQL solutions i,e for static data storage use 2nd level cache mechanism to avoid the network database round trips and db remote connections bottleneck.
  • High-performance asynchronous messaging libraryZeroMQ is used in distributed or concurrent applications. It provides a message queue, but unlike message-oriented middleware, a ZeroMQ system can run without a dedicated message broker.Connect your code in any language, on any platform.It carries messages across inproc, IPC, TCP, TIPC, multicast ,smart patterns like pub-sub, push-pull, and router-dealer and high-speed asynchronous I/O engines, in a tiny library.
  • Persistent connections (A persistent connection (HTTP persistent connection) is a network communication channel that remains open for further HTTP requests and responses rather than closing after a single exchange) , It also called HTTP keep-alive, or HTTP connection reuse, is the idea of using a single TCP connection to send and receive multiple HTTP requests/responses, as opposed to opening a new connection for every single request/response pair. The newer HTTP/2 protocol uses the same idea and takes it further to allow multiple concurrent requests/responses to be multiplexed over a single connection.
  • Non blocking Asynchronous IO(Log4j2) mechanism , LMAX Disruptor technology. Asynchronous Loggers internally use the Disruptor, a lock-free inter-thread communication library, instead of queues, resulting in higher throughput and lower latency.
  • Streams for IO Operation (Google Protocol Buffer for object serialization and deserialization) Protocol buffers, usually referred as Protobuf, is a protocol developed by Google to allow serialization and deserialization of structured data. this protocol even surpassed JSON with better performance, better maintainability and smaller size
  • Java Design Patterns to manage the objects efficiently - Flyweight design pattern to create a pool of shared objects , static factory methods instead of constructors to recycle immutable objects , visitor pattern to avoid “instanceof” constructs in frequently accessed methods. 
  • Choosing the Right Garbage Collector - However, the current generation of garbage collectors has mostly solved that issue and, with proper tuning and sizing, can lead to having no noticeable collection cycles. That being said, it does take an in-depth understanding of both GC on the JVM as a whole, but also the specific profile of the application – to get there
  • JDBC Performances - JDBC Connection pooling (The creation of a new connection takes time, which you can avoid if you reuse an existing connection.) ,JDBC Batching (we handle persistence is trying to batch operations wherever possible. JDBC batching allows us to send multiple SQL statements in a single database roundtrip.),Statement Caching (Depending on the underlying JDBC Driver, you can cache PreparedStatement both on the client-side (the Driver) or databases-side.
  • Architectural Improvements - If you write applications with poor architecture but performs well for the current requirements, what will happen if the requirements grow and your architecture is not flexible enough to extend and creates a maintenance nightmare where fixing a code in one area would break your code in another area. This will cause your application to be re-written.
Most applications need to retrieve data from and save/update data into one or more databases. Database calls are remote calls over the network. In general data should be lazily loaded (i.e. load only when required as opposed to pre-loading from the database with a view that it can be used later) from a database to conserve memory but there are use cases (i.e. need to make several database calls) where eagerly loading data and caching can improve performance by minimizing network trips to the database. Data can be eagerly loaded with a help of SQL scripts with complex joins or stored procedures and cached using third party frameworks or building your own framework.

How would you refresh Infinispan 2nd level remote cache?

  • Timed cache strategy where the cache can be replenished periodically (i.e. every 30 minutes, every hour etc). This is a simple strategy applicable when it is acceptable to show dirty data at times and also the data in the database does not change very frequently.
  • Dirty check strategy where your application is the only one which can mutate (i.e. modify) the data in the database. You can set a “isDirty” flag to true when the data is modified in the database through your application and consequently your cache can be refreshed based on the “isDirty” flag.

How would you refresh your cache(distributed data grid ) if your database is shared by more than one application ?

  • Database triggers: You could use database triggers to communicate between applications sharing the same database and write pollers which polls the database periodically to determine when the cache should be refreshed.
  • XML messaging (Enterprise – JMS) to communicate between other applications sharing the same database or separate databases to determine when the cache should be refreshed.
  • Distributed platform : Infinispan distributing data evenly across the cluster and use it from different language i,e language-independent service accessed remotely over a variety of protocols (Hot Rod, REST, Memcached and WebSockets),The purpose of Infinispan is to expose a data structure that is distributed, highly concurrent and designed ground-up to make the most of modern multi-processor and multi-core architectures. It is often used as a distributed cache, but also as a NoSQL key/value store or object database.

Optimize your I/O operations: 

Use buffering when writing to and reading from files and/or streams. Avoid writers/readers if you are dealing with only ASCII characters. You can use streams instead, which are faster. Avoid premature flushing of buffers. Also make use of the performance and scalability enhancing features such as non-blocking and asynchronous I/O, mapping of file to memory etc offered by the NIO (New I/O).

Establish whether you have a potential memory problem and manage your objects efficiently: 
1). Remove references to the short-lived objects from long-lived objects like Java collections etc to minimize any potential memory leaks. Also reuse objects where possible. It is cheaper to recycle objects than creating new objects each time. 

2). Avoid creating extra objects unnecessarily. For example use mutable StringBuffer/StringBuilder classes instead of immutable String objects in computation expensive loops  and use static factory methods instead of constructors to recycle immutable objects. 

3). Automatic garbage collection is one of the most highly touted conveniences of Java. However, it comes at a price. Creating and destroying objects occupies a significant chunk of the JVM's time. Wherever possible, you should look for ways to minimize the number of objects created in your code:
  • For complex objects that are used frequently, consider creating a pool of recyclable objects rather than always instantiating new objects. This adds additional burden on the programmer to manage the pool, but in selected cases it can represent a significant performance gain. Use flyweight design pattern to create a pool of shared objects. Flyweights are typically instantiated by a flyweight factory that creates a limited number of flyweights based on some criteria. Invoking object does not directly instantiate flyweights. It gets it from the flyweight factory, which checks to see if it has a flyweight that fits a specific criteria (e.g. with or without GST etc) in the pool (e.g. HashMap). If the flyweight exists then return the reference to the flyweight. If it does not exist, then instantiate one for the specific criteria and add it to the pool (e.g. HashMap) and then return it to the invoking object.
  • If repeating code within a loop, avoid creating new objects for each iteration. Create objects before entering the loop (i.e. outside the loop) and reuse them if possible.
  • Use lazy initialization when you want to distribute the load of creating large amounts of objects. Use lazy initialization only when there is merit in the design. 

Where applicable apply the following performance tips in your code: 

  • Use ArrayLists, HashMap etc as opposed to Vector, Hashtable etc where possible. This is because the methods in ArrayList, HashMap etc are not synchronized. Even better is to use just arrays where possible. 
  • Using StringBuilder for String Concatenation String concatenation is a very common operation, and also an inefficient one. Simply put, the problem with using += to append Strings is that it will cause an allocation of a new String with every new operation.
  • Use + to concatenate Strings in in one statementWhen you implemented your first application in Java, someone probably told you that you shouldn’t concatenate Strings with +. And that’s correct if you’re concatenating Strings in your application logic. Strings are immutable, and the result of each String concatenation is stored in a new String object. That requires additional memory and slows down your application, especially if you’re concatenating multiple Strings within a loop.
  • Use primitives where possibleAnother quick and easy way to avoid any overhead and improve the performance of your application is to use primitive types instead of their wrapper classes. So, it’s better to use an int instead of an Integer, or a double instead of a Double. That allows your JVM to store the value in the stack instead of the heap to reduce memory consumption and overall handle it more efficiently.
  • Avoid RecursionRecursive code logic leading to StackOverFlowError is another common scenario in Java applications.If we cannot do away with recursive logic, tail recursive as an alternative is better.
  • Use Regular Expressions Carefully , Regular expressions are useful in a lot of scenarios, but they do, more often than not, have a very high performance cost. It’s also important to be aware of a variety of JDK String methods, which use regular expressions, such as String.replaceAll(), or String.split().
  • Avoid Creating and Destroying Too Many Threads (uses a pool of threads called the ForkJoinPool, which manages the worker threads)- Creating and disposing of threads is a common cause of performance issues on the JVM, as thread objects are relatively heavy to create and destroy.If your application uses a large number of threads, using a thread pool makes a lot of sense, to allow these expensive objects to be reused.To that end, the Java ExecutorService is the foundation here and provides a high-level API to define the semantics of the thread pool and interact with it.
  • Set the initial capacity of a collection (e.g. ArrayList, HashMap etc) and StringBuffer/StringBuilder appropriately. This is because these classes must grow periodically to accommodate new elements. So, if you have a very large ArrayList or a StringBuffer, and you know the size in advance then you can speed things up by setting the initial size appropriately.
  • Minimize the use of casting or runtime type checking like instanceof in frequently executed methods or in loops. The “casting” and “instanceof” checks for a class marked as final will be faster. Using “instanceof” construct is not only ugly but also unmaintainable. Look at using visitor pattern to avoid “instanceof” constructs in frequently accessed methods. 
  • Do not compute constants inside a large loop. Compute them outside the loop. For applets compute it in the init() method. Avoid nested loops (i.e. a “for” loop within another “for” loop etc) where applicable and make use of a Collection class. 
  • Exception creation can be expensive because it has to create the full stack trace. The stack trace is obviously useful if you are planning to log or display the exception to the user. But if you are using your exception to just control the flow, which is not recommended, then throw an exception, which is precreated. An efficient way to do this is to declare a public static final Exception in your exception class itself.
  • Avoid using System.out.println and use logging frameworks like Log4J2 etc, which uses Asynchronous I/O buffers.
  • Minimize calls to Date, Calendar, etc related classes.
  • Minimize JNI calls in your code

When in the development process should you consider performance issues? 

Set performance requirements in the specifications, include a performance focus in the analysis and design and also create a performance test environment.

When designing your new code, what level of importance would you give to the following attributes? 

  • Performance
  • Maintainability
  • Extendibility
  • Ease of use
  • Scalability
You should not compromise on architectural principles for just performance. You should make effort to write architecturally sound programs as opposed to writing only fast programs. If your architecture is sound enough then it would allow your program not only to scale better but also allows it to be optimized for performance if it is not fast enough. So you should think about extendibility (i.e. ability to evolve with additional requirements), maintainability, ease of use, performance and scalability (i.e. ability to run in multiple servers or machines) during the design phase. List all possible design alternatives and pick the one which is conducive to sound design architecturally (i.e. scalable, easy to use, maintain and extend) and will allow it to be optimized later if not fast enough.

How would you detect and minimize memory leaks in Java?

In Java, memory leaks are caused by poor program design where object references are long lived and the garbage collector is unable to reclaim those objects.

Detecting memory leaks:

  • Use tools like JProbe, OptimizeIt etc to detect memory leaks.
  • Use operating system process monitors like task manager on NT systems, ps, vmstat, iostat, netstat etc on UNIX systems.
  • Write your own utility class with the help of totalMemory() and freeMemory() methods in the Java Runtime class. Place these calls in your code strategically for pre and post memory recording where you suspect to be causing memory leaks. An even better approach than a utility class is using dynamic proxies or Aspect Oriented Programming (AOP) for pre and post memory recording where you have the control of activating memory measurement only when needed.

Minimizing memory leaks:


In Java, typically memory leak occurs when an object of a longer lifecycle has a reference to objects of a short life cycle. This prevents the objects with short life cycle being garbage collected. The developer must remember to remove the references to the short-lived objects from the long-lived objects. Objects with the same life cycle do not cause any issues because the garbage collector is smart enough to deal with the circular references.

  • Design applications with an object’s life cycle in mind, instead of relying on the clever features of the JVM. Letting go of the object’s reference in one’s own class as soon as possible can mitigate memory problems. Example: myRef = null;
  • Unreachable collection objects can magnify a memory leak problem. In Java it is easy to let go of an entire collection by setting the root of the collection to null. The garbage collector will reclaim all the objects (unless some objects are needed elsewhere). 
  • Use weak references if you are the only one using it. The WeakHashMap is a combination of HashMap and WeakReference. This class can be used for programming problems where you need to have a HashMap of information, but you would like that information to be garbage collected if you are the only one referencing it. 
  • Free native system resources like AWT frame, files, JNI etc when finished with themExample: Frame, Dialog, and Graphics classes require that the method dispose() be called on them when they are no longer used, to free up the system resources they reserve.

Why does the JVM crash with a core dump or a Dr.Watson error?

Any problem in pure Java code throws a Java exception or error. Java exceptions or errors will not cause a core dump (on UNIX systems) or a Dr.Watson error (on WIN32systems). Any serious Java problem will result in an OutOfMemoryError thrown by the JVM with the stack trace and consequently JVM will exit. These Java stack traces are very useful for identifying the cause for an abnormal exit of the JVM. So is there a way to know that OutOfMemoryError is about to occur? The Java J2SE 5.0 has a package called java.lang.management which has useful JMX beans that we can use to manage the JVM. One of these beans is the MemoryMXBean. 

An OutOfMemoryError can be thrown due to one of the following 4 reasons:

  • JVM may have a memory leak due to a bug in its internal heap management implementation. But this is highly unlikely because JVMs are well tested for this.
  • The application may not have enough heap memory allocated for its running. You can allocate more JVM heap size (with –Xmx parameter to the JVM) or decrease the amount of memory your application takes to overcome this. To increase the heap space: java -Xms1024M -Xmx1024M Care should be taken not to make the –Xmx value too large because it can slow down your application. The secret is to make the maximum heap size value the right size.
  • Another not so prevalent cause is the running out of a memory area called the “perm” which sits next to the heap. All the binary code of currently running classes is archived in the “perm” area. The ‘perm’ area is important if your application or any of the third party jar files you use dynamically generate classes. For example: “perm” space is consumed when XSLT templates are dynamically compiled into classes, J2EE application servers, JasperReports, JAXB etc use Java reflection to dynamically generate classes and/or large amount of classes in your application. To increase perm space: java -XX:PermSize=256M -XX:MaxPermSize=256M
  • The fourth and the most common reason is that you may have a memory leak in your application when an object of a longer lifecycle has a reference to objects of a short life cycle.

So why does the JVM crash with a core dump or Dr.Watson error ? 


Both the core dump on UNIX operating system and Dr.Watson error on WIN32 systems mean the same thing. The JVM is a process like any other and when a process crashes a core dump is created. A core dump is a memory map of a running process. This can happen due to one of the following reasons:

  • Using JNI (Java Native Interface) code, which has a fatal bug in its native code. Example: using Oracle OCI drivers, which are written partially in native code or JDBC-ODBC bridge drivers, which are written in non Java code. Using 100% pure Java drivers (communicates directly with the database instead of through client software utilizing the JNI) instead of native drivers can solve this problem. We can use Oracle thin driver, which is a 100% pure Java driver.
  • The operating system on which your JVM is running might require a patch or a service pack. 
  • The JVM implementation you are using may have a bug in translating system resources like threads, file handles, sockets etc from the platform neutral Java byte code into platform specific operations. If this JVM’s translated native code performs an illegal operation then the operating system will instantly kill the process and mostly will generate a core dump file, which is a hexadecimal file indicating program’s state in memory at the time of error. The core dump files are generated by the operating system in response to certain signals. Operating system signals are responsible for notifying certain events to its threads and processes. The JVM can also intercept certain signals like SIGQUIT which is kill -3 < process id > from the operating system and it responds to this signal by printing out a Java stack trace and then continue to run. The JVM continues to run because the JVM has a special built-in debug routine, which will trap the signal -3. On the other hand signals like SIGSTOP (kill -23 ) and SIGKILL (kill -9 ) will cause the JVM process to stop or die. The following JVM argument will indicate JVM not to pause on SIGQUIT signal from the operating system.
          java –Xsqnopause

List of performance measurement tools in java:


No.
Tool  Name
Purpose
1
jVisualVM
JVM Profiler
2
GCeasy
Universal Garbage Collection Log Analysis
3
fastThread
Java Thread Dump Analyzer
4
HeapHero
Java Heap Dump Analyzer
5
sar
Real time monitoring Linux System Performance
6
ksar
Java based frontend tool which plots a nice easy to understand graph over a period of time
7
JMeter
A pure Java application designed to load test functional behavior and measure performance.
8
jvmtop
Provide JVM internals (e.g. memory information) of running JVMs / java processes.
9
MAT
Eclipse Memory Analyzer is a fast and feature-rich Java heap analyzer
10
jstack
Thread Dump - Java HotSpot VM to provide information about performance and resource consumption of running applications
11
jmap
Heap Dump - Take histogram and heap dump from running java process.
12
jstat
Runtime JVM statistics monitoring using command line
13
Visual GC + jstatd
Visual Garbage Collection Monitoring Tool using server side jstatd binding port
14
JMH
JMH is a Java harness for building, running, and analysing nano/micro/milli/macro benchmarks written in Java and other languages targetting the JVM


Reference URL’s:

  • http://gceasy.io/
  • http://fastthread.io/
  • http://heaphero.io/
  • https://www.eclipse.org/mat/
  • https://code.google.com/archive/p/jvmtop/
  • https://visualvm.github.io/
  • http://openjdk.java.net/projects/code-tools/jmh/

Saturday, June 23, 2018

Soundex algorithm for searching people name (Phonetic search)


Now a days search algorithms is a common feature in Artificial Intelligence.
If you want search for a specific word then you may get results along with similar words in various search engines like google.

If you will search a name from social media like "Facebook" or "Twitter" then it will get display a list of similar names but having slightly different spellings.

Phonetic search is a type of search where the string or words have the similar pronunciation. In many applications there will have a features to search any words or names where it will match exactly or similar word matches.

This search will be performed in a secure way i,e instead of using a plain text in searching process it will use the character encoded code.
For Soundex phonetic algorithm it will generate four characters encoded code and based on this encoded code the search will be performed.



Challenge:  
Suppose we have stored a customer name (last name,first name ,middle name ) into database and data in this column is in encrypted format and our application has a functionality for the operator to do a name search so that when the operation enters the customer name in the order last name ,first name and middle name, the database needs to search for it. The name would not be the exact match in last name, first name and middle name - so a like query is required.

Because the column has encrypted, you can not directly apply like operator on the concatenation of three names(last name,first name ,middle name) , Now the challenge is how can you search the names using like query from the encrypted data.

Solution 1: Create three different columns which will be used for storing encrypted values into them(last name,first name ,middle name) and provide three input search fields to the operator for searching the names. Encrypt the input text and search the encrypted value from the respective columns(last name,first name ,middle name).


Solution 2: Create six different columns , where three columns will be used for storing the encrypted values and three columns will be used to store the HMAC hash values for the names and provide three input search fields to the operator for searching the names. Get the HMAC hash value from provided input text and search that hash value from the respective columns(last name,first name ,middle name).

Solution 3: Create two different columns , where one column will be used for storing the encrypted value(last name + first name + middle name) and the second column will be used to store the Soundex code for the customer name (last name + first name + middle name)  

For Solution 1 and 2, You would have to encrypt the values while concatenating and then apply the like operator - which will be just too slow considering the size of the database (million rows),also you can not index encrypted columns. You need to provide three different input text fields to restrict the searching criteria(last name,first name ,middle name). 

For Solution 3, You need to provide a single text field to search a customer name and you only have to get the Soundex code for the input text and search it from the database,you have to use like operator if Soundex code of all the names(last name,first name ,middle name) have stored into a single column.


CustomerID
Surname
Phonic
1
SMITH
S530
2
JOHNSON
J525
3
WILLIAMS
W452
4
JONES
J520
5
BROWN
B650
6
DAVIS
D120

Note : Keyed hash(HMAC) value won't be searchable in like operator , encrypted column hash value will only be applicable for the exactly match condition not for like operator.

Before move into phonetic search ,we need to understand some words. lets get the knowledge about them before jumping into the algorithm.

Phonetic is a wing of linguistics that deals with the sounds of human speech. Basically it is more about the word that you pronounce. In the case of a phonetic search, it is a technique to look up a word with the exact spelling along with the words having similar sounds.
  •     Caret and Carat
  •     Nelson, Neilson and Neelson
  •     Neekita and Nikita
  •     Cup and Cop
Homophone is each of two or more words having the same pronunciation but different meanings, origins, or spelling (or) each of a set of symbols denoting the same sound or group of sounds.
  • Steal and  Steel
  • Some and  Sum
  • Suite and  Sweet
  • Sole and  Soul
  • Son and Sun








Phonetic Algorithm is an algorithm for indexing of words by their pronunciation. Most phonetic algorithms were developed for use with the English language
  • Soundex
  • Metaphone, Double Metaphone, Metaphone 3
  • Daitch–Mokotoff Soundex
  • Cologne phonetics
  • New York State Identification and Intelligence System (NYSIIS)
  • Match Rating Approach
  • Caverphone
Soundex is a phonetic algorithm for indexing names by sound, as pronounced in English. The goal is for homophones to be encoded to the same representation so that they can be matched despite minor differences in spelling. Soundex converts an alphanumeric string to a four-character code that is based on how the string sounds when spoken.
  • Robert and  Rupert - R163
  • Steal and  Steel - S340
  • Sridhar , Shridhar and Shreedhar - S636
Metaphone is a phonetic algorithm, published by Lawrence Philips in 1990, for indexing words by their English pronunciation.
  • Assistance and  Assistants - ASSTN 
  • Katherine and Catherine -  K0RN 
  • Steal and Steel - STL
  • Jena , Jina and  Jeena -  JN
Use of Phonetic Search
  • Phonetic Search is used in different types of word editors for spell checkers , so that an editor can show a list of relative other words (same or similar Metaphone)  whenever there will have any spelling mistakes.
  • Search functionality will use phonetic algorithms to find results that don't match exactly the term(s) used in the search. People can search their names that either contains only the identical elements like Wilson (or) Wylson, Katherine (or) Catherine,  Jena (or) Jina (or) Jeena.
There is a number of algorithms and tools or libraries that will help you for more advanced identical name matching.

Soundex
It is a standard and is very commonly used phonetic algorithm for indexing names by sound, as pronounced in English. The goal is for homophones (pronounced the same as another word but differs in meaning, and may differ in spelling) to be encoded to the same representation so that they can be matched despite minor differences in spelling.

Metaphone
This algorithm was developed by Lawrence Philips in 1990 for encoding words correspondng to English pronunciation rules. It is considered to be better than Soundex. In this case words are grouped and the resulting value is also a word unlikely in the case of soundex. This algorithm seems to be more complicated.

Double Metaphone
The developer of the Metaphone algorithm provided an improved version called "Doube Metaphone" in the year 2000 by providing support to other European languages. It is called "Double" because it provides both a primary and a secondary code for a word and code can be up to 4 characters. The Double Metaphone rule engine is a bit more complex than the others.

Metaphone 3
The same developer of Metaphone Lawrence Philips provided an improved version of an algorithm called Metaphone 3 in 2009. In this algorithm, various sounds like soft and hard were taken into consideration. It provided more support to Slavik languages like Russian.

Caverphone
The Caverphone algorithm was developed by David Hood in 2002 as part of a New Zealand project called "Caversham Project" to match the data in the old and new electoral lists. Although this algorithm is applicable for English words, it provides much more specific recognition of accents of words of New Zealand.

NYSIIS
This algorithm was developed in 1970 as part of the "New York State Identification and Intelligence System". It promises to provide better result and accuracy, up to 2.7%, over the Soundex algorithm. Again it is more specific to American names.

Daitch-Mokotoff
This algorithm was developed by two Jewish genealogists Gary Mokotoff and Randy Daitch in the year 1985. This algorithm is similar to Soundex but provides more accuracy for Russian and Jewish names.

Soundex Algorithim
This algorithm was developed by Robert Russell in 1910 for the words in English.As per this algorithm, words are compared based upon their index value. The main principle behind this algorithm is that consonants are grouped depending on the ordinal numbers and finally encoded into a value against which others are matched. It aims to find a code for every word by above process which is called soundex code.

The complete algorithm to find soundex code is as below:
  1. Retain the first letter of the name and drop all other occurrences of a, e, i, o, u, y, h, w.
  2. Replace consonants with digits as follows (after the first letter):
    b, f, p, v → 1
    c, g, j, k, q, s, x, z → 2
    d, t → 3
    l → 4
    m, n → 5
    r → 6
  3. If two or more letters with the same number are adjacent in the original name (before step 1), only retain the first letter; also two letters with the same number separated by ‘h’ or ‘w’ are coded as a single number, whereas such letters separated by a vowel are coded twice. This rule also applies to the first letter.
  4. Iterate the previous step until you have one letter and three numbers. If you have too few letters in your word that you can’t assign three numbers, append with zeros until there are three numbers. If you have more than 3 letters, just retain the first 3 numbers.

Java Implementation : Soundex
public class Soundex {
 public static String soundex(String s) {
  char[] x = s.toUpperCase().toCharArray();
  char firstLetter = x[0];

  // Step - 2 
  // convert letters to numeric code
  for (int i = 0; i < x.length; i++) {
   switch (x[i]) {

   case 'B':
   case 'F':
   case 'P':
   case 'V':
    x[i] = '1';
    break;

   case 'C':
   case 'G':
   case 'J':
   case 'K':
   case 'Q':
   case 'S':
   case 'X':
   case 'Z':
    x[i] = '2';
    break;

   case 'D':
   case 'T':
    x[i] = '3';
    break;

   case 'L':
    x[i] = '4';
    break;

   case 'M':
   case 'N':
    x[i] = '5';
    break;

   case 'R':
    x[i] = '6';
    break;

   default:
    x[i] = '0';
    break;
   }
  }

  // remove duplicates
  // Step - 1
  String output = "" + firstLetter;

  // Step - 3
  for (int i = 1; i < x.length; i++)
   if (x[i] != x[i - 1] && x[i] != '0')
    output += x[i];

  // Step - 4
  // pad with 0's or truncate
  output = output + "0000";
  return output.substring(0, 4);
 }

 public static void main(String[] args) {
  System.out.println("Soundex Code for Wilson is: " + soundex("Wilson"));
  System.out.println("Soundex Code for Wylson is: " + soundex("Wylson"));

  System.out.println("Soundex Code for beer is: " + soundex("beer"));
  System.out.println("Soundex Code for bear is: " + soundex("bear"));
  System.out.println("Soundex Code for bearer is: " + soundex("bearer"));
 }
}
Output :
Soundex Code for Wilson is: W425
Soundex Code for Wylson is: W425
Soundex Code for beer is: B600
Soundex Code for bear is: B600
Soundex Code for bearer is: B660

Apache "commons-codec" provides the implementations for the following algorithms.
  •     Metaphone
  •     Double Metaphone
  •     Soundex
Above three algorithms are packed into apache commons codec JAR, declared as Maven dependency:  commons-codec-1.5.jar

    commons-codec
    commons-codec
    1.5

Full Example :

package com.sjena.helloswitch;

import org.apache.commons.codec.StringEncoderComparator;
import org.apache.commons.codec.language.DoubleMetaphone;
import org.apache.commons.codec.language.Metaphone;
import org.apache.commons.codec.language.Soundex;

public class LanguageCodecTest {

 public static void main(String args[]) {

  Soundex sndx = new Soundex();

  System.out.println("Soundex Code for Erickson is: " + sndx.encode("Erickson"));
  System.out.println("Soundex Code for Erikson is: " + sndx.encode("Erikson"));
  System.out.println("Soundex Code for Ericson is: " + sndx.encode("Ericson"));
  System.out.println("Soundex Code for Ericksen is: " + sndx.encode("Ericksen"));
  System.out.println("Soundex Code for Ericsen is: " + sndx.encode("Ericsen"));

  System.out.println("Soundex Code for Wilson is: " + sndx.encode("Wilson"));
  System.out.println("Soundex Code for Wylson is: " + sndx.encode("Wylson"));

  System.out.println("Soundex Code for Sridhar is: " + sndx.encode("Sridhar"));
  System.out.println("Soundex Code for Shridhar is: " + sndx.encode("Shridhar"));
  System.out.println("Soundex Code for Shreedhar is: " + sndx.encode("Shreedhar"));

  System.out.println("Soundex Code for Jena is: " + sndx.encode("Jena"));
  System.out.println("Soundex Code for Jeena is: " + sndx.encode("Jeena"));
  System.out.println("Soundex Code for Jina is: " + sndx.encode("Jina"));

  System.out.println("Soundex Code for OBrien is: " + sndx.encode("OBrien"));
  System.out.println("Soundex Code for O'Brien is: " + sndx.encode("O'Brien"));
  System.out.println("Soundex Code for OBr'ien is: " + sndx.encode("OBr'ien"));
  System.out.println("Soundex Code for OBrie'n is: " + sndx.encode("OBrie'n"));
  System.out.println("Soundex Code for OB'rien is: " + sndx.encode("OB'rien"));

  // Use the StringEncoderComparator to compare these two Strings
  StringEncoderComparator comparator1 = new StringEncoderComparator(sndx);
  System.out.println("Wilson and Wylson are same :" + comparator1.compare("Wilson", "Wylson"));
  System.out.println("Erickson and Ericson are same :" + comparator1.compare("Erickson", "Ericson"));
  System.out.println("Sridhar and Shreedhar are same :" + comparator1.compare("Sridhar", "Shreedhar"));

  Metaphone metaphone = new Metaphone();
  System.out.println("Metaphone Code for Wilson is: " + metaphone.encode("Wilson"));
  System.out.println("Metaphone Code for Wylson is: " + metaphone.encode("Wylson"));

  System.out.println("Metaphone Code for Sridhar is: " + metaphone.encode("Sridhar"));
  System.out.println("Metaphone Code for Shridhar is: " + metaphone.encode("Shridhar"));
  System.out.println("Metaphone Code for Shreedhar is: " + metaphone.encode("Shreedhar"));

  DoubleMetaphone doubleMetaphone = new DoubleMetaphone();
  System.out.println("DoubleMetaphone Code for Wilson is: " + doubleMetaphone.encode("Wilson"));
  System.out.println("DoubleMetaphone Code for Wylson is: " + doubleMetaphone.encode("Wylson"));

  System.out.println("DoubleMetaphone Code for Sridhar is: " + doubleMetaphone.encode("Sridhar"));
  System.out.println("DoubleMetaphone Code for Shridhar is: " + doubleMetaphone.encode("Shridhar"));
  System.out.println("DoubleMetaphone Code for Shreedhar is: " + doubleMetaphone.encode("Shreedhar"));

  // Use the StringEncoderComparator to compare these two Strings
  StringEncoderComparator comparator2 = new StringEncoderComparator(doubleMetaphone);
  System.out.println("Auto and Otto are same :" + comparator2.compare("Auto", "Otto"));
  System.out.println("Double Metaphone primary code for Sridhar: " + doubleMetaphone.doubleMetaphone("Sridhar"));
  System.out.println("Double Metaphone secondary code for Sridhar: " + doubleMetaphone.doubleMetaphone("Sridhar", true));

 }
}

Output :
Soundex Code for Erickson is: E625
Soundex Code for Erikson is: E625
Soundex Code for Ericson is: E625
Soundex Code for Ericksen is: E625
Soundex Code for Ericsen is: E625
Soundex Code for Wilson is: W425
Soundex Code for Wylson is: W425
Soundex Code for Sridhar is: S636
Soundex Code for Shridhar is: S636
Soundex Code for Shreedhar is: S636
Soundex Code for Jena is: J500
Soundex Code for Jeena is: J500
Soundex Code for Jina is: J500
Soundex Code for OBrien is: O165
Soundex Code for O'Brien is: O165
Soundex Code for OBr'ien is: O165
Soundex Code for OBrie'n is: O165
Soundex Code for OB'rien is: O165
Wilson and Wylson are same : 0
Erickson and Ericson are same :0
Sridhar and Shreedhar are same :0
Metaphone Code for Wilson is: WLSN
Metaphone Code for Wylson is: LSN
Metaphone Code for Sridhar is: SRTH
Metaphone Code for Shridhar is: XRTH
Metaphone Code for Shreedhar is: XRTH
DoubleMetaphone Code for Wilson is: ALSN
DoubleMetaphone Code for Wylson is: ALSN
DoubleMetaphone Code for Sridhar is: SRTR
DoubleMetaphone Code for Shridhar is: XRTR
DoubleMetaphone Code for Shreedhar is: XRTR
Auto and Otto are same :0
Double Metaphone primary code for Sridhar: SRTR
Double Metaphone secondary code for Sridhar: SRTR

Database Feature : SOUNDEX

It is now a standard feature of major database like Oracle,PostgreSQL,DB2,MySQL, Ingres, MS SQL Server and some major word editors.

Oracle : The SOUNDEX function can be used in the following versions of Oracle/PLSQL:
Oracle 12c, Oracle 11g, Oracle 10g, Oracle 9i, Oracle 8

Query: SELECT last_name, first_name FROM employees WHERE SOUNDEX(last_name) = SOUNDEX('SMYTHE');

Output :

LAST_NAME  FIRST_NAME
Smith                  Lindsey
Smith                  William

  • SOUNDEX('tech on the net') = 'T253'
  • SOUNDEX('TECH ON THE NET') = 'T253'
  • SOUNDEX('apples') = 'A142'
  • SOUNDEX('apples are great') = 'A142'
  • SOUNDEX('applus') = 'A142'