Java Data Structure - Part1

My dig at Java data structures -

Part1 -


How do hashtables/HashMap work ?

At the heart of the hash table algorithm is a simple array of items; this is often simply called the hash table. Hash table algorithms calculate an index from the data item's key and use this index to place the data into the array. The implementation of this calculation is the hash function

What happens if two keys have the same hashCode ?

Often termed as hash collision , hashtable implementations have to deal with it. One of the ways and the most common way to deal with this situation is to maintain a list of values
for keys with the same hashCode. HashCode of the keys would result into the same value and hence point to the same index in the array, containing mulitple key-values.
Run a equals on the key and return the appropriate value back to the caller.

What happens if the two keys have the same equals value ?

Pretty obvious duplicate keys cannot be stored and hence the original key/value is retained and new one being added is rejected

When implementing a LRU cache which datastructure would one use ?

LinkedHashMap would be an obvious choise for a couple of reasons -

1. This implementation differs from HashMap in that it maintains a doubly-linked list running through all of its entries. This linked list defines the iteration ordering, which is normally the order in which keys were inserted into the map (insertion-order).
2. The removeEldestEntry(Map.Entry) method may be overridden to impose a policy for removing stale mappings automatically when new mappings are added to the map.
3. A special constructor is provided to create a linked hash map whose order of iteration is the order in which its entries were last accessed, from least-recently accessed to most-recently (access-order)


How would one define a structural modification in a HashMap ?

A structural modification is any operation that adds or deletes one or more mappings; merely changing the value associated with a key that an instance already contains is not a structural modification.

How would one define a structural modification in a LinkedHashMap ?

A structural modification is any operation that adds or deletes one or more mappings or, in the case of access-ordered linked hash maps, affects iteration order.
In insertion-ordered linked hash maps, merely changing the value associated with a key that is already contained in the map is not a structural modification.
In access-ordered linked hash maps, merely querying the map with get is a structural modification.

Its important to understand structural modifications , since maps are not synchronized unlike a hashtable if a thread structurally modifies a map while another thread is iterating over the same there could be serious concurrency issues. Potentially resulting in ConcurrentModificationException

Please comment below with any interesting questions/discussions you might have come across with hashtables/maps

MORE STUFF-

Memory footprint of java primitives

Gretty - example - web-service

Sample code - Kilim

An actor framework for Java concurrency

Querying the memory usage of a Java object

Memory footprint of java primitives

Memory foot print of Java primitives

Java Primitive Data Types

Data Type	Description	Size	Default Value
boolean	true or false	1-bit	false
char	Unicode Character	16-bit	\u0000
byte	Signed Integer	8-bit (byte)	0
short	Signed Integer	16-bit (short)	0
int	Signed Integer	32-bit	0
long	Signed Integer	64-bit	0L
long	float	Real number	32-bit	0.0f
double	Real number	64-bit	0.0d

Next -- Garbage Collection explained
Prev -- Querying memory usage of a java object




ALSO READ
Java development 2.0: Ultra-lightweight Java web services with Gretty
An actor framework for Java concurrency
10 things you didn't know about java performance monitoring
Java collection performance - Chart view
The Clean Coder

Sample code - Kilim

A simple Calculator example -pretty naive but then demonstrates using Actor based model in java

In Kilim a thread must extend Task object and implement the execute method which should throw Pausable exception. Kilim weaver (read it as byte code enhancer) interprets classes containing operations throwing Pausable exception and weaves(enhances) it.

import java.math.RoundingMode;

import kilim.Mailbox;
import kilim.Pausable;
import kilim.Task;

public class Calculator extends Task{

 private Mailbox mailbox;

 public Calculator(Mailbox mailbox) {
  super();
  this.mailbox = mailbox;
 }

 @Override
 public void execute() throws Pausable, Exception {
  while (true) {   
   Calculation calc = mailbox.get(); // blocks
   if (calc.getAnswer() == null) {
    calc.setAnswer(calc.getDividend().divide(calc.getDivisor(), 8, 
      RoundingMode.HALF_UP));    
    System.out.println("Calculator determined answer");
    mailbox.putnb(calc);
   }
   Task.sleep(1000);
  }
 }
}

Thread2 - demonstrates sharing of data between Thread1 using a Mailbox

import java.math.BigDecimal;
import java.math.MathContext;
import java.util.Date;
import java.util.Random;

import kilim.Mailbox;
import kilim.Pausable;
import kilim.Task;

public class DeferredDivision extends Task {

 private Mailbox mailbox;

 public DeferredDivision(Mailbox mailbox) {
  super();
  this.mailbox = mailbox;
 }

 @Override
 public void execute() throws Pausable, Exception {
  Random numberGenerator = new Random(new Date().getTime());
  MathContext context = new MathContext(8);
  while (true) {
   System.out.println("I need to know the answer of something");
   mailbox.putnb(new Calculation(
     new BigDecimal(numberGenerator.nextDouble(), context), 
     new BigDecimal(numberGenerator.nextDouble(), context)));
   Task.sleep(1000);
   Calculation answer = mailbox.getnb(); // no block
   if (answer != null && answer.getAnswer() != null) {
    System.out.println("Answer is: " + answer.printAnswer());
   }
  }
 }
}

Using Ant invoke Kilim's weaver(byte code enhancer)

A simple test runner

import kilim.Mailbox;
import kilim.Task;

public class CalculationCooperation {
 public static void main(String[] args) {
  Mailbox sharedMailbox = new Mailbox();

  Task deferred = new DeferredDivision(sharedMailbox);
  Task calculator = new Calculator(sharedMailbox);

  deffered.start();
  calculator.start();

 }
}

Notice how the same Mailbox is shared between threads without a lock or synchronization

Your output will vary — actors are nondeterministic

[java] I need to know the answer of something
[java] Calculator determined answer
[java] Answer is: The answer of 0.36477377 divided by 0.96829189 is 0.37671881
[java] I need to know the answer of something
[java] Calculator determined answer
[java] Answer is: The answer of 0.40326269 divided by 0.38055487 is 1.05967029
[java] I need to know the answer of something
[java] Calculator determined answer
[java] Answer is: The answer of 0.16258913 divided by 0.91854403 is 0.17700744
[java] I need to know the answer of something
[java] Calculator determined answer
[java] Answer is: The answer of 0.77380722 divided by 0.49075363 is 1.57677330

Sequence Diagram -


Conclusion - As in Scala or Erlang , Actor model can be applied to java.



Also Read
Java development 2.0: Ultra-lightweight Java web services with Gretty
Instrumentation - Querying the memory usage of a Java object
10 things you didn't know about java performance monitoring
5 things you didn't know about java.util.concurrent
The Clean Coder

An actor framework for Java concurrency

Recently my curiosity towards learning something new , bumped me into a framework called Kilim. Ya that's right , not sure how many of you have heard about it.

Goal of this framework - to introduce Actor based concurrency to java ala. making the model similar to Erlang and Scala

Why do we need this switch from thread based model to Actor based model when it comes to concurrency - thread based model depends on using shared memory when it comes to communicating between threads. Actor based model takes a slightly different approach of using Mailboxes to communicate.

So whats the advantage ? - well when coded against Actor based model we don't need to worry about thread locks or use any kind of synchronization blocks. Actors are guaranteed to run on multi-core processors. Since there is no limitation or a dependency on shared memory actors can be scheduled on any core or a processor. Improves the overall performance and the scalability of system.

How to use Kilim? sample code - here








Also Read
Java development 2.0: Ultra-lightweight Java web services with Gretty
Instrumentation - Querying the memory usage of a Java object
10 things you didn't know about java performance monitoring
5 things you didn't know about java.util.concurrent
The Clean Coder

Querying the memory usage of a Java object

Creating the instrumentation agent class - would work with Jdk 5 and above



The JVM will pass to our method an implementation of the Instrumentation interface, defined in java.lang.instrument. In turn, this interface defines the method getObjectSize(). So for example, if we want to measure the memory usage of an instance of SomeClass, our agent code would look as follows:

import java.lang.instrument.*;
import com.somepackage.SomeClass;

public class MyAgent {
  public static void premain(String args, Instrumentation inst) {
    SomeClass obj = new SomeClass();
    long size = inst.getObjectSize(obj);
    System.out.println("Bytes used by object: " + size);
  }
}

Package the agent into a jar -

create manifest.txt with
Premain-Class: mypackage.MyAgent

execute this to create a jar -

jar -cmf manifest.txt agent.jar mypackage/MyAgent.class

Run the application with the agent -

java -javaagent:agent.jar -cp . com.mypackage.Main

Accessing the Instrumentation object from within our application -

public class MyAgent {
  private static volatile Instrumentation globalInstr;
  public static void premain(String args, Instrumentation inst) {
    globalInstr = inst;
  }
  public static long getObjectSize(Object obj) {
    if (globalInstr == null)
      throw new IllegalStateException("Agent not initted");
    return globalInstr.getObjectSize(obj);
  }
}

Now, provided the agent is included in the JVM command line parameters as above, then from anywhere in our application we can call MyAgent.getObjectSize() to query the memory size of an object created by our Java application

Note that the getObjectSize() method does not include the memory used by other objects referenced by the object passed in.


Next -- Memory footprint of java datatypes

Also Read
Java development 2.0: Ultra-lightweight Java web services with Gretty
An actor framework for Java concurrency
Java Garbage Collection explained
Java collection performance - Chart view
The Clean Coder

Hello world with gretty

Gretty is a simple web framework for both building web servers and clients. Built on top of netty, it supports NIO style http server, asynchronous http client. It also supports both websocket server and client.

It's designed to be light weight and run as a standalone embedded solution.

It's written in Groovy++. But you can use it with pure Groovy, Scala or even Java.

Do bear with me for not being a fancy writer -

Sample code demonstrating a quick web-service implementation



Also Read
An actor framework for Java concurrency
Instrumentation - Querying the memory usage of a Java object
10 things you didn't know about java performance monitoring
The Clean Coder

CHART - Java collection framework perfromance

Also Read
The Clean Coder

How to get C like performance in Java

• The JVM does implicit bounds checking on array access and updates. This has a small overhead - you can unsafely eliminate this (and open yourself to buffer overflows and other problems) using the the Unsafe class or direct buffers.
• Use memory-minimized collections to reduce memory usage.
• You can use Direct memory to store data how you wish (this is what BigMemory uses).
• Use blocking IO in NIO (which is the default for a Channel) - don't use Selectors unless you need them.
• Most systems can handle 1K-10K threads efficiently. Scalability beyond 10K users/server doesn't buy you anything in the real world since the server resources will be consumed servicing 10k concurrent users.
• -XX:+UseCompressedStrings use byte[] instead of char[] for strings which don't need 16-bit characters - this saves memory but is 5%-10% slower.
• To reduce string space usage, you can use your own Text type which wraps a byte[], or get your text data from ByteBuffer, CharBuffer or use Unsafe or -XX:+UseCompressedStrings.
• To start the JVM faster, load fewer libraries.
• Use primitives instead of primitive wrapper objects.

My 2 cents on Hibernate

 Few hibernate experiences -

1. Implementing hashcode and equals on hibernate entities -
    Remember hibernate returns a set of entities when you have a one to many or a many to many relationships.
Accoring to Set rules - no two objects can be equal and hence it becomes all the more important to define the right equals implementation for your hibernate POJO's
Rule to thumb - equals should return true if the primary keys of the entities match.

2. Hibernate has dual caching layer -
    First level cache is stored at the hibernate SessionFactory level and the second level cache could be(if you choose to) a third party caching library.
Remember - enable second level cache only if your application has a high read to write ratio.

3. Hibernate transaction management -
    I am assuming in most cases you would use JTA. Hibernate sessions are stored on the transaction and hence if you use threadlocal to create and manage hibernate session ensure you clear the thread local once the session usage is over. Without this done explicity there is every chance that the session would not be garbage collected unless the transaction context is. Generally you would run into this issue if a transaction for some reason cannot be commited or rolledback and runs into a timeout.

One of the Most Powerful Debugging Practices

Dzone promoted a link called "One of the Most Powerful Debugging Practices," showing the use of a trap. The example is in C#, but a Java version is offered. Interesting thought - worth it?

Add Trap() instances all over the place to cover all the execution paths and have it throw a runtime exception so that the debugger would pick it up and help you step run through the immediate code path following the trap.

Once the debugging is done prefix the trap with a ** mark so that it can result in a compilation failure so that peice of code can be removed.

So essentially if you use a debugger this sure is handy in having all the execution paths tested, if not then there is little value addition.

5 java tips of the day

The decorator pattern is an alternative to subclassing. Subclassing adds behavior at compile time, and the change affects all instances of the original class; decorating can provide new behavior at runtime for individual objects

The decorator pattern can be used to make it possible to extend (decorate) the functionality of a certain object at runtime, independently of other instances of the same class, provided some groundwork is done at design time

If an object is known to be immutable, it can be copied simply by making a copy of a reference to it instead of copying the entire object. Because a reference (typically only the size of a pointer) is usually much smaller than the object itself, this results in memory savings and a boost in execution speed.

Immutable objects can be useful in multi-threaded applications. Multiple threads can act on data represented by immutable objects without concern of the data being changed by other threads. Immutable objects are therefore considered to be more thread-safe than mutable objects.

All of the primitive wrapper classes in Java are immutable.

Proxy Pattern

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

A proxy object can take the responsibility that a client expects and forward requests appropriately to an underlying target object. This lets you intercept and control execution flow, providing many opportunities for measuring, logging, and optimizations.

A classic example of the Proxy pattern relates to avoiding the expense of loading large images into memory until they are definitely needed - avoid loading images before they are needed, letting proxies for the images act as placeholders that load the required images on demand.

Designs that use Proxy are sometimes brittle, because they rely on forwarding method calls to underlying objects. This forwarding may create a fragile, high-maintenance design.

Dynamic proxies let you wrap a java.lang.reflect.Proxy object around the interfaces of an arbitrary object at runtime. You can arrange for the the proxy to intercept all the calls intended for the wrapped object. The proxy will usually pass these calls on to the wrapped object, but you can add code that executes before or after the intercepted calls.

[Article provides an example of using the Proxy pattern to delay loading images until needed, for performance and memory optimization.]
[Article provides an example of using a dynamic java.lang.reflect.Proxy to measure execution times of method calls and log if this is too long.]

5 things you didn't know about ... java.util.concurrent

http://www.ibm.com/developerworks/java/library/j-5things4.html

CopyOnWriteArrayList is a thread-safe variant of ArrayList with all mutative operations (add, set, and so on) implemented to make a fresh copy of the array - ideal for the read-often, write-rarely scenario such as Listeners of a JavaBean event.










BlockingQueue is a first in, first out (FIFO) Queue which blocks the thread if it tries to get from an empty queue until an item is added by another thread; and for the bounded variety will block the thread on any attempt to insert an item into a full queue until space becomes available in the queue's storage.










ArrayBlockingQueue can give reader and writer threads first in, first out access (it would be a more efficient to allow readers to run while other readers held the lock, but you'd risk a constant stream of reader threads keeping the writer from ever doing its job.)











BlockingQueue neatly solves the problem of how to "hand off" items from one thread to another thread without explicitly synchronizing.










Doing (if Map.get() == null) Map.put() is a race condition; ConcurrentMap supports putIfAbsent() that does the test first then does a put only if the key isn't already stored in the Map.










SynchronousQueue is a BlockingQueue in which each insert operation must wait for a corresponding remove operation by another thread and vice versa - i.e. the threads always operate synchronously across this queue

10 things you didn't know about - Java performance monitoring

JConsole is a built-in Java performance profiler that works from the command-line and in a GUI shell. It's not perfect, but it's an adequate first line of defense










The most effective response to a performance problem is to use a profiler rather than reviewing the code or JVM garbage collector flags.










Monitor the class count - if the count steadily rises, then you can assume that either the app server or your code has a ClassLoader leak somewhere and will run out of PermGen space before long.










com.sun.management.HotSpotDiagnostic has a "dumpHeap" mebean operation that allows a dump to be created (remotely) which can be analysed later.










jstat can monitor garbage collection and JIT compiler statistics

jstack will get a stack dump from any process










jmap can produce a dump of the heap, or a histogram of live classes and how many instances there are and the spaced used by them.










jhat supports analysing heap dumps obtained from jmap or jconsole or HotSpotDiagnostic.dumpHeap

Java Best Practices - High performance Serialization

• If you don't explicitly set a serialVersionUID class attribute the serialization mechanism has to compute it by going through all the fields and methods to generate a hash, which can be quite slow.
• With the default serialization mechanism, all the serializing class description information is included in the stream, including descriptions of the instance, the class and all the serializable superclasses.
• Externalization eliminates almost all the reflective calls used by Serialization mechanism and gives you complete control over the marshalling and demarshalling algorithms, resulting in dramatic performance improvements. However Externalization requires you to rewrite your marshalling and demarshalling code whenever you change your class definitions.
• Use simpler data representations to serialize objects where possible, e.g. just the timestamp instead of a Date object.
• You can eliminate serializing null values by serializing meta information about which fields are being serialized.
• Google protobuf is an alternative serialization mechanism with good size advantages when using compression.

Thousands of Threads and Blocking I/O

• For an NIO based server, the server notifies when some I/O event is ready to be processed, this is then processed; since all I/O is effectively multiplexed, it requires the server to keep track of where each client is within its i/o transaction, i.e. state must be maintained for all clients (unless a stateless protocol is used, e.g. all state is part of the request).
• NIO is not faster than IO, but it can be more scalable, though the scalability is an issue of how efficient the OS is at handling many threads.
• NIO transfers rate can be only 75% of a plain IO connection (several benchmark studies show this sort of comparative maximum rate).
• A multithreaded IO server tends to automatically takes advantage of multiple cores, where an NIO server may explcitly need to hand processing off to a pool of worker threads (though that is the common design)
• On modern OSs, idle threads have not much cost, context switching is fairly efficient, uncontended synchronization is cheap.

• Nonblocking datastructures scale well - ConcurrentLinkedQueue, ConcurrentHashMap, NonBlockingHashMap (&NonBlockingLongHashMap)
• A good architecture throttles incoming requests to the maximum rate the server can handle optimally, otherwise if the server gets overloaded overall request rates as well as individual request service times drop to unnacceptable levels.
• Avoid Executors.newCachedThreadPool as an unbounded number of threads tends to be bad for applications (e.g. more threads get created just when you are already maxxed on CPU).
• If you do mutliple sends per request, use a buffered stream. If one send per request, don't buffer (as you effectively already have).
• Try to keep everything in byte arrays if possible, rather than converting back and forth between bytes and strings.
• In a thread-per-request model, watch for socket timeouts.
• Multithreaded server coding is more intuitive than an event based server.

details - http://www.mailinator.com/tymaPaulMultithreaded.pdf

Fast and Safe concurrency - Actor framework for java
How to get C like performance in java
High Performance Serialization
How much time out if your day does ibm waste

JEDIT - lightweight powerful editor

jEdit

jEdit is a programmer's text editor written in Java. It can be configured as a rather powerful IDE through the use of its plugin architecture.

How are people using jEdit ?

• For developing jEdit
• As an IDE for various languages
• Partly embedded in other applications
• As a reverse engineering tool
• As a very powerful text editor
• As portable application
• As an excellent XML editor
• As an editor for KML files for Google Earth

What's on your project wish list?

• More spare time to work on it
• Regular release schedule
• Port jEdit to an OSGi framework
• The ability to create plugins in languages other than Java

Garbage collection in java

Global collections

An example of the output produced when a global collection is triggered is:

"gc type="global" id="6" totalid="6" intervalms="383.226"
compaction movecount="139926" movebytes="9478888"
refs_cleared soft="0" weak="0" phantom="0"
finalization objectsqueued="0"
timesms mark="33.391" sweep="1.760" compact="65.958" total="101.149"
tenured freebytes="1784720" totalbytes="11337472" percent="15"
gc"


Indicates that a garbage collection was triggered on the heap. Type="global" indicates that this was a global collection (mark, sweep, possibly compact). The id attribute gives the occurrence number of this global collection. The totalid indicates the total number of garbage collections (of all types) that have taken place. Currently this is the sum of the number of global collections and the number of scavenger collections. intervalms gives the number of milliseconds since the previous global collection.

Shows the number of objects that were moved during compaction, and the total number of bytes these objects represented. This line appears only if compaction occurred during the collection.

Provides information relating to the number of Java reference objects that were cleared during the collection. In this example, no references were cleared.

Provides information detailing the number of objects containing finalizers that were enqueued for VM finalization during the collection. Note that this is not equal to the number of finalizers that were run during the collection, because finalizers are scheduled by the VM.

Provides information detailing, respectively, times taken for each of the mark, sweep, and compact phases, as well as the total time taken. When compaction was not triggered, the number returned is zero. Note that if the VM being run is not compiled with compaction support, the compact field will not be displayed.

Indicates the status of the tenured area following the collection. If running in generational mode, there will also be a line output, showing the status of the active nursery area too.

ALSO READ
Java collection performance - Chart view
Java development 2.0: Ultra-lightweight Java web services with Gretty
An actor framework for Java concurrency
The Clean Coder