Computational complexity of a .size() method of set and map views in Java

Even though I’ve been programming in Java for many years, there are still some small bits that are new to me. Today I will write about the time complexity of a .size() method of set and map views in Java (based on OpenJDK implementation, which, in fact is a reference implementation).

In Java SE, we have an interface called SortedSet which according to the documentation is:

“A Set that further provides a total ordering on its elements. (...) Several additional operations are provided to take advantage of the ordering.”

Those additional operations let us get a view of some subset of the current set. There are 3 such methods available which names are self explanatory:

SortedSet headSet(E toElement)
SortedSet subSet(E fromElement, E toElement)
SortedSet tailSet(E fromElement)

An important part here is that the returned set is backed by the original set so changes to either of them are reflected in the other one as well.

So what about the time complexity of the .size() method of such returned set? Well, we may think it is the same as the .size() of a TreeSet, one implementation of the SortedSet interface, which is constant (O(1)):

public int size() {
       return size;
}

Source 

It turns out that in OpenJDK implementation that’s not the case. The time complexity of .size() method in such view set is linear to the number of elements in it (O(n)). The details can be found in the EntrySetView class:

abstract class EntrySetView extends AbstractSet

Source

So what is happening here? First condition checks if a view spans across entire original set and if true  delegates the call to its .size().
Later we check whether the size of the view hasn’t been calculated before or if the number of structural modifications in a view tree is different than in the original tree. If either of these conditions is true then we iterate over all the set elements and count them. Obviously that operation takes linear time to the number of elements.

How this could be solved? One possible solution would be to keep views and original sets linked to each other via references. I.e. a view set would maintain a reference to the set from which it has been derived and the original set would maintain references to all its views. Then a change in it or in any of the views could be propagated.
That would have solved the problem of the .size() time complexity but it would introduce a memory footprint and also affect the computational complexity of add/remove operations. That’s because we can have more than O(log n) unique views of a given set - in fact we can have n such views so now the add/remove operations would be O(n) as the size of all the views would have to be updated.

All in all, different approaches have different trade offs and the one chosen in OpenJDK seems sensible as the add/remove might be more common operation that .size() on a view and has smaller memory footprint than the solution depicted above but it’s still good to be aware of such details when developing high throughput and low latency applications.

UPDATE

After a while, I got curious about this case in different languages. I have decided to check C# as it has a class with similar functionality and in addition .NET Core has been open sourced so we can investigate the official code.
It turns out that they took a slightly different approach at solving this problem and ensure that getting a size of the view is a constant time operation when modifying it (but not when modifying the original set).

In C# we have a class called SortedSet which has a following method:

public virtual SortedSet GetViewBetween(
 T lowerValue,
 T upperValue
)

which corresponds to the subSet in Java SortedSet interface.

Source

In order to get a size of such SortedSet in C# we need to access a property, called "Count". According to the documentation retrievial of this value is an O(1) operation.

Source

If we dive into the code of SortedSet class we will quickly see that GetViewBetween() returns a subclass of SortedSet called TreeSubSet which only modifies the "count" variable and the "Count" property is unchanged from its super class SortedSet:

        public int Count {
            get {
                VersionCheck();
                return count;
            }
        }

Source

Now we should have a look at how the VersionCheck() is implemented in TreeSubSet:

            internal override void VersionCheck() {
                VersionCheckImpl();
            }
 
            private void VersionCheckImpl() {
                Debug.Assert(underlying != null, "Underlying set no longer exists");
                if (this.version != underlying.version) {
                    this.root = underlying.FindRange(min, max, lBoundActive, uBoundActive);
                    this.version = underlying.version;
                    count = 0;
                    InOrderTreeWalk(delegate(Node n) { count++; return true; });
                }
            }

Source

The key point here is the check if the version of a subset is different than the underlying set. The version of a set changes on any structural mutation of a set (add/remove operations). If the versions are different then this operation gets more expensive. First we find a new subset with FindRange which is O(log n) operation where n is the number of elements in the original set - thanks to Red-Black tree implementation - and then we perform an In-Order traversal which is O(n) operation where n is the size of the subset.

When the versions will be different? The modifying operations of TreeSubSet call already VersionCheck() therefore the versions will be the same so a consecutive call to Count will be a constant time operation.

Here is an example for add operation:

            internal override bool AddIfNotPresent(T item) {
 
                if (!IsWithinRange(item)) {
                    ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.collection);
                }
 
                bool ret = underlying.AddIfNotPresent(item);
                VersionCheck();
#if DEBUG
                Debug.Assert(this.versionUpToDate() && this.root == this.underlying.FindRange(min, max));
#endif
 
                return ret;
            }

Source

There is a possibility to optimize this method - to avoid O(n) (n - number of elements in the subset) counting in VersionCheck() we can update the count variable here right away - if ret is true we simply increase it by 1 as we already checked if a new value is in the subset range. Similar implementation is for a removal operation. Maybe I will submit a push request on github for that :)

Now, if we modify the original set, its version will also change. Then a consecutive call to its view's Count property will detect a version change so its expensive branch will be executed.

To summarize, the Java and C# implementations of subset size computation are very similar in terms of time complexity. Even though, in C# when modifying a subset we get a constant size operation, then the add/remove operations get more expensive. So it is all about shifting the additional cost of counting the elements from one method to another.
The shift in Java though looks more reasonable to me, especially for a case of massive modifications of a view, without a need to know its size in between. In C#, the size will be recalculated after each modification.

Memento design pattern in Java

Recently when recapping my design patterns I came across a Memento. In principle, it provides means for capturing and externalizing an object’s internal state without violating the encapsulation - only the Originator can manipulate the state saved in Memento. That would require a Memento class to implement two interfaces - a wide one for the Originator with appropriate get and set methods and a narrow one for other objects to be able to pass the Memento where necessary.

The GoF book presents one possible implementation of that pattern in C++ using a “friend” class. It defines two classes - an Originator and a Memento. The latter defines two methods marked as private - getState and setState. In addition to that it declares the Originator class as a friend thus letting it access its private members.

As Java being my primary programming language it made me think how we could implement the Memento using it. Especially given the fact that Java does not support the friend class concept.

The most straightforward solution is to put the Memento, its interfaces and the Originator in the same package. The wide interface will be package-private and the narrow one public:

package memento1;

public interface NarrowMemento {
}

interface WideMemento {
  int getState();
}

class MementoImpl implements WideMemento, NarrowMemento {

  private int state;

  MementoImpl(int state) {
    this.state = state;
  }

  @Override
  public int getState() {
    return state;
  }

}

public class Originator {
  private int state;

  public Originator(final int state) {
    this.state = state;
  }

  public NarrowMemento getMemento() {
    return new MementoImpl(state);
  }

  public void setMemento(NarrowMemento memento) {
    this.state = ((WideMemento) memento).getState();
  }
}

The important bits:

1. Originator class is public, can be used in any package. 
2. MementoImpl class is package private thus visible only within its package.
3. MementoWide interface is package private. 
4. MementoNarrow marker interface is public.

Therefore only Originator and MementoNarrow are visible outside of the package and as long as Originator encapsulates its state properly it won’t leak through Memento.
This solution works fine as long as we can ensure that the Originator is used in a different package. Otherwise, the MementoWide is visible and can be used to elicit the Originator state.

There is another approach to this problem that mitigates the packaging concerns. If we want to make sure that regardless of the packaging only the Originator can access (make a call) to methods defined in the wide interface we can use method signature security. We will alter the method from the MementoWide to include a dummy class which can be constructed only by the Originator:

package memento2;

import memento2.originator.Originator;

public interface Memento {
  int getState(Originator.Stamp stamp);
}

public class MementoImpl implements Memento {

  final int state;

  public MementoImpl(final int state) {
    this.state = state;
  }

  @Override
  public int getState(Originator.Stamp stamp) {
    Objects.requireNonNull(stamp);
    return state;
  }
}

And in a different package Originator:

package memento2.originator;

import memento2.Memento;
import memento2.MementoImpl;

public class Originator {
  private final static Stamp stamp = new Stamp();

  private int state;

  public Originator(final int state) {
    this.state = state;
  }

  public Memento getMemento() {
    return new MementoImpl(state);
  }

  public void setMemento(Memento memento) {
    this.state = memento.getState(stamp);
  }

  public static class Stamp {
    private Stamp() {
    }
  }
}

The first thing that you will probably notice is that Memento interface and an implementing class are public. Still, only the Originator will be able to make a call to the exposed method. That is because its parameter is an inner class of Originator but its constructor is private so only the Originator can create a Stamp instance and make a successful call. Of course it is possible to pass a null as an argument to the method but then such client will be smacked with an NPE.
The only way this solution can be broken is by publishing an instance of the Stamp by either Memento or Originator which requires modifying a class. Therefore it is less likely to be abused than the first approach which relies only on proper packaging.

The last solution gets as close as possible to the behaviour of the Memento implemented using C++ friend class - i.e. ensuring that only the class which state we externalize can access it.

Peterson’s locking algorithm in Java

Recently I started reading a new book - “The Art of Multiprocessor Programming”. At the very beginning the author brings up a topic of locks’ implementation and presents Peterson’s algorithm - an elegant two-thread mutual exclusion algorithm which can be generalized for n threads but lets start slow. After a short description, that can be found on the wikipedia as well, an implementation follows:

class Peterson implements Lock {
 private boolean[] flag = new boolean[2];
 private int victim;

 public void lock() {
  int i = ThreadID.get();
  int j = 1 - i;
  flag[i] = true;
  victim = i;
  while (flag[j] && victim == i) {};
 }

 public void unlock() {
  int i = ThreadID.get();
  flag[i] = false;
 }
}

Now, if we take that as a sample Java implementation then it is seriously flawed. We have 2 problems here. First is a data race (mentioned in my previous post) and a possibility of instructions reordering as there is no happens-before relationship established between different threads in this case.

How we can solve it? We have two possible ways:

1) Mark each shared variable as a volatile. But that is actually insufficient in the case of the ‘flag’ array since declaring it as a volatile will only ensure that the reference value will be visible to other threads. The values of the array may still land only in the CPUs cache and not be flushed to the main memory. To fix that we have 2 options. We can use either AtomicBoolean[] or AtomicIntegerArray (as there is no AtomicBooleanArray) and assume 0/1 for false/true. In the former case we will need an object per each array element and in the latter case only an object for AtomicIntegerArray and array object.
Here is a code using AtomicIntegerArray:

class Peterson1 implements Lock {
 private final AtomicIntegerArray flag = new AtomicIntegerArray(2);
 private volatile int victim;
 
 public void lock() {
  int i = ThreadID.get();
  int j = 1 - i;
  flag.set(i, 1);
  victim = i;
  while(flag.get(j) == 1 && victim == i) {};
 }

 public void unlock() {
  int i = ThreadID.get();
  flag.set(i, 0);
 }
}

2) Another approach is to use the technique that I have described in my article "Flushing with a volatile". In the code above (Peterson class) we can declare ‘victim’ as a volatile. It makes writes to the victim variable visible to other threads. Now what about visibility of writes to a ‘flag’ variable? If we ensure that each write to to the ‘flag’ is followed by a write to the volatile ‘victim’, then when a thread sees an up to date ‘victim’ value, it will also see an up to date ‘flag’ value.
There are 2 places where a write to a 'flag' happens:
In lock() method:

flag[i] = true;
victim = i;

Here a write to a flag is followed by a write to a volatile victim so all is good. Then in unlock() method we have:

int i = ThreadID.get();
flag[i] = false;

If we let the unlock() method as it is, the write of a false value to the ‘flag’ variable may not be seen by the other thread. To ensure the visibility, we should add a write to a ‘victim’ variable:
victim = 1 - i; // (this is the current victim value anyway)

But that’s not all. What about reading the ‘flag’ variable? It must be preceded by a read from a volatile field. In the lock() method we have the only read from the ‘flag’ variable:

while (flag[j] && victim == i) {};

To take the advantage of the Java memory model and to make the ‘flag’ value visible, we have to reorder the above condition to:

while (victim == i && flag[j]) {};

Here is the whole code:

class Peterson2 implements Lock {
 private final boolean[] flag = new boolean[2];
 private volatile int victim;
 
 public void lock() {
  int i = ThreadID.get();
  int j = 1 - i;
  flag[i] = true;
  victim = i;
  while (victim == i && flag[j]) {};
 }

 public void unlock() {
  int i = ThreadID.get();
  flag[i] = false;
  victim = 1 - i;
 }
} 

What about a microbenchmark? I have measured the execution of such task:

class IncrementingTask implements Runnable {
 Lock lock;
 int a;
 IncrementingTask(Lock lock) {
  this.lock = lock;
 }
 @Override
 public void run() {
  for(int i = 0; i < 50000000; i++) { // when 2 threads execute this task or 10^8 for 1 thread so that the amount of work and the end result are the same. The ‘a’ field must be equal to 10^8.
   lock.lock();
   a++;
   lock.unlock();
  }
 }
} 

with Peterson1 and Peterson2 implementations, both with only one and two threads executing it, on:

$ cat /proc/cpuinfo | egrep "core id|physical id" | tr -d "\n" | sed s/physical/\\nphysical/g | grep -v ^$ | sort | uniq | wc -l
12
$ java -version java version "1.6.0_26" Java(TM) SE Runtime Environment (build 1.6.0_26-b03) Java HotSpot(TM) 64-Bit Server VM (build 20.1-b02, mixed mode)
$ cat /proc/version Linux version 2.6.32-33-server (buildd@allspice) (gcc version 4.4.3 (Ubuntu 4.4.3-4ubuntu5) ) #72-Ubuntu SMP Fri Jul 29 21:21:55 UTC 2011 

Below are the average times (ns) for each case from 10 runs:

                   1 thread    2 threads
Peterson1    1840693030    42213715991
Peterson2    1836106908    35781376968

I find the results quiet interesting. First off, when there is no contention (column “1 thread”) the performance of both implementations is very similar with the Peterson2 being slightly ahead. When we introduce the second thread and thus increase the contention, the Peterson2 is significantly (15%) faster. But what surprises the most is the difference between the execution of the task on 1 versus 2 threads! 1 thread does the job more than 20 times faster than 2 threads! We can see clearly how expensive it is to coordinate 2 threads when they want to access the shared variable. And what if we use a Java synchronized mechanism and an intrinsic object lock? Then the average time (again from 10 runs) for 2 threads will be 2678088766 ns. It is way better than our lock implemenation but still it is slower than 1 thread with the Peterson lock acquisition overhead.

Ok, so that’s it for today. Hope you enjoyed the article and feel free to leave a comment!

Flushing with a volatile!

Core Java provides different ways of ensuring visibility of actions on memory performed by one thread to other threads. You probably can think of synchronization, marking a variable volatile or using a thread safe collection from java.util.concurrent package.

Today we will explore another, less obvious approach. We will use a volatile variable to ensure visibility of another non-volatile variable. Lets start with a simple but flawed example:

class BadTask implements Runnable {
 boolean keepRunning = true;
 
 @Override
 public void run() {
  while(keepRunning) {
  }
  System.out.println("Done.");
 }
}

public class VolatileExp {
 public static void main(String[] args) throws InterruptedException {
  BadTask r = new BadTask();
  new Thread(r).start();
  Thread.sleep(1000);
  r.keepRunning = false;
  System.out.println("keepRunning is false");
 }
}

The intention of this code is to let BadTask run for 1 second and after that to stop it by setting keepRunning boolean to false. As simple as it may look this code is doomed to fail - the BadTask won’t stop after 1 second and will run until you terminate the program manually. If it works fine in your environment try a different one. In my case the above code fails constantly on the following:

$ cat /proc/cpuinfo | egrep "core id|physical id" | tr -d "\n" | sed s/physical/\\nphysical/g | grep -v ^$ | sort | uniq | wc -l
12
$ java -version
java version "1.6.0_26"
Java(TM) SE Runtime Environment (build 1.6.0_26-b03)
Java HotSpot(TM) 64-Bit Server VM (build 20.1-b02, mixed mode)
$ cat /proc/version
Linux version 2.6.32-33-server (buildd@allspice) (gcc version 4.4.3 (Ubuntu 4.4.3-4ubuntu5) ) #72-Ubuntu SMP Fri Jul 29 21:21:55 UTC 2011

If the program does not stop you may wonder what happend. In short - the main thread and the thread running BadTask have been executed on different cores. Each core has its own set of registers and caches. The new value of keepRunning has been written to one of these without being flushed to the main memory. Thus it is not visible to the code running on a different core.

Ok, how we can fix it? The simplest and the most correct way is to mark this variable volatile. Another approach would be to acquire a common lock when accessing it but that would be definetly an overkill.

So what we will do today? We will introduce another variable marked with a volatile keyword! In the above code it does not make much sense and is only for demonstrating some aspects of Java memory model. But think about a scenario where there are more variables of keepRunning nature. Have a look at the below code that does not have visibility problem anymore:

class BadTask implements Runnable {
        boolean keepRunning = true;
        volatile boolean flush = true;

        @Override
        public void run() {
                while(keepRunning) {
                        if(flush);
                }
                System.out.println("BadTask is done.");
        }
}

public class VolatileExp extends Thread {

        public static void main(String[] args) throws InterruptedException {
                BadTask r = new BadTask();
                new Thread(r).start();
                Thread.sleep(1000);
                r.keepRunning = false;
                r.flush = false;
                System.out.println("keepRunning is false");
        }
}

So as already mentioned we have introduced a new volatile variable “flush”. We do two things with it. First, we do a write operation in the main thread, right after modifying a non-volatile keepRunning variable. Second, in the thread running BadTask, we do a read operation on it.
Now, how come the value of keepRunning is flushed to the main memory? This is guaranteded by the current Java memory model. According to JSR133 “writing to a volatile field has the same memory effect as a monitor release, and reading from a volatile field has the same memory effect as a monitor acquire”. Thus, actions on memory done by one thread before writing to a volatile variable will be visible to another thread after reading that variable.

This is an advanced technique which should be used sparingly only when the performance has the highest priority. If you are looking for a real life adaptation of it, you can have a look at the ConcurrentHashMap from java.util.concurrent package.

Proxy and Adapter design patterns.

Recently, when speaking to some of my colleagues, I have noticed a lot of confusion between these two design patterns. Thus, today I'm going to clarify all the doubts :).

First off, both Proxy and Adapter belong to the same group of design patterns – structural one. What are structural design patterns? In simple words, they are patterns that describe ways of combining different entities with each other and thus forming larger structures.

And now a definition from Wikipedia:

“Structural design patterns are design patterns that ease the design by identifying a simple way to realize relationships between entities.”

Right. First we will scrutinize the adapter pattern. In a nutshell, it transforms an interface of one class into the interface that is expected. It enables two classes to work together even though their interfaces are not compatible with each other. There are two basic variations of the adapter design pattern: class adapter and object adapter.

• Class adapter.

In this case, the adapter's class subclasses the class we want to adapt and in the same time it implements the desired interface that the client expects. When the call is made, appropriate inherited methods are being invoked.

• Object adapter.

On the other hand, in the object adapter, the adapter's class does not subclass the adaptee but instead it holds a reference to it (composition). It also implements the expected interface.

There are pros and cons of each of these versions but in this article lets focus on more general concepts of the adapter pattern.

Now, what about the proxy pattern?

In general, it provides a surrogate of a given object in order to control the access to it in some way. Based on the way of controlling the access we can distinguish different types of proxy design pattern:

• Remote proxy – it handles the interaction between remote objects.
• Virtual proxy – it handles the situation when an object is expensive to create (lazy initialization).
• Protection proxy - based on who calls the proxy, it controls the access to different methods.
• Smart proxy – adds some extra operations when the objects is accessed.

Very important thing about the proxy pattern is the fact that the surrogate has the same interface as the real object.

To summarize. The adapter bridges the gap between two classes that are not compatible with each other. The proxy provides a surrogate to control the access to the real object.

Re-throwing exceptions.

Today we will talk about re-throwing exceptions. In many cases, after examining a caught exception, it doesn't fulfill some requirements and we must re-throw it. This is a very basic and simple action in C# but for the Java developers there is a trap. In the aforementioned scenario, in Java we would just write:

throw e;

were e is the exception we caught.
Why don't we do the same in C# and see what will happen. Below is a sample code that illustrates such situation:

   class Program
   {
       void m1() { m2(); }
       void m2() { m3(); }
       void m3() { m4(); }
       void m4()
       {
           throw new Exception("A sample exception.");
       }
       static void Main(string[] args)
       {
           try
           {
               new Program().m1();
           }
           catch(Exception e)
           {
               throw e;
           }
       }
   }

Now lets execute it and examine the stack trace:

System.Exception was unhandled
Message=A sample exception.
Source=LearningCsharp
StackTrace:
at ConsoleApplication1.Program.Main(String[] args) in C:\Path\Program.cs:line 220
…

What did happen here? We somehow lost the whole stack trace. Now it looks like the exception was created within the Main method – in a real life scenario that may cause many problems when troubleshooting.
How to do it correctly in C# and preserve the whole stack trace? Here is the answer:

   class Program
   {
       void m1() { m2(); }
       void m2() { m3(); }
       void m3() { m4(); }
       void m4()
       {
           throw new Exception("A sample exception.");
       }
       static void Main(string[] args)
       {
           try
           {
               new Program().m1();
           }
           catch(Exception e)
           {
               throw;
           }
       }
   }

Yes! Simple

throw;

solves the issue. Now our stack trace will look as follows:

System.Exception was unhandled
Message=A sample exception.
Source=LearningCsharp
StackTrace:
at ConsoleApplication1.Program.m4() in C:\Path\Program.cs:line 210
at ConsoleApplication1.Program.m3() in C:\Path\Program.cs:line 207
at ConsoleApplication1.Program.m2() in C:\Path\Program.cs:line 206
at ConsoleApplication1.Program.m1() in C:\Path\Program.cs:line 205
at ConsoleApplication1.Program.Main(String[] args) in C:\Path\Program.cs:line 220
...

Looks much better – we can see which method thrown the exception and thus find the source of the issue.
So Java developers – bear that difference in mind and avoid confusion when analyzing a half empty stack trace! :)

Exception handling – multiple catch.

Let's talk about the exception handling. Just to ensure that we are standing on the same planet – multiple catch of exception is a situation when we have a method that throws more than one checked exception and we want to handle some of them separetly. The following Java code shows such situation:

import java.util.ArrayList;
import java.util.List;

class Exception1 extends Exception {}
class Exception2 extends Exception {}
class Exception3 extends Exception {}

public class ExceptionHandling {
 public static void throwsExceptions() throws Exception1, Exception2, Exception3 {
  return;
 }
 
 public static void testMethod() {
  try {
   throwsExceptions();
  }
  catch(Exception1 e) {
   // handle Exception1
  }
  catch(Exception2 e) {
   // handle Exception2
  }
  catch(Exception e) {
   // handle other exceptions.
  }
 }
}

But what if the logic for handling Exception1 and Exception2 is the same? In this case we get a dirty code duplication. Although, there is a simple remedy for that. What we could do, is to catch a base Exception class and then branch appropriately with if-else statement as the below code snippet presents:

public static void testMethod2() {
 try {
  throwsExceptions();
 }
 catch(Exception e) {
  if(e instanceof Exception1 || e instanceof Exception2) {
   // Do the common handling logic for Exception1 and Exception2
  }
  else {
   // Handle other exceptions
  }
 }
}

So far so good. We don't have code duplication anymore. Just a note: the above examples use Java language but they also apply to C# - we would face the same issue/remedy when coding in it.
Now you may wonder what more can be done. As for C# not much really. In Java though, there is still some room for improvement. In Java 7 there has been introduced a new multiple catch mechanism so that we can catch multiple exceptions in one catch block! The following code sample shows the solution using Java 7:

public static void testMethod3() {
 try {
  throwsExceptions();
 }
 catch(Exception1 | Exception2 e) {
  // Do the common handling logic for Exception1 and Exception2
 }
 catch(Exception e) {
  // Handle other exceptions.
 }
}

Here we can see how exceptions of type Exception1 and Exception2 are handled in one catch block using the '|' operator.
Summing up – a point for Java :)

Named arguments in C#.

So today is the day. I'm kicking off with a new series of articles in the category C# vs. Java. Let's start with a feature called named arguments. In a nutshell, it let us name arguments that we are passing when invoking some method. When it can be useful? There are a few different scenarios. First of all, it may happen that we have a method that takes many arguments of the same type. It comes as no surprise that they can get mixed easily and normally compiler won't help us as long as the passed variables' types match the ones from the method signature. Another thing is just code readability – it is much easier to go through it when we can see the variable name from the method signature next to the variable that we are passing.

    class NamedArgumentsExample
    {
        public static void AddStock(string companyShortName, int amount, double price)
        {
        }
        static void Main(string[] args)
        {
            AddStock("MSFT", 100, 150);
            AddStock("MSFT", amount: 100, price: 150);
        }
    }

In the above code we can see 2 method invocations – the first one without using named arguments. At first glance, it may be hard to get what are the values in the AddStock method invocation for. On the other hand, in the 9th line we can see with no problem that the first value is for the amount and the second for the price of a stock that we are adding.
As for Java, there is no such feature. I'm sure you can see, even from a very simple example above that it is useful. Of course, as with everything, one shouldn't overuse it but apply in a reasonable way, in cases where it will really add clarity.
That's it for today! Hope you enjoyed the post and have a happy Sunday!!

Back in the game!

Yeah, that's right lads – I'm back to the blogging!! I know, it's been a while since the last post, over half a year but believe me – there was lots of things going on – changed a job, moved to a different country, finished my master thesis and stuff like that. Luckily nobody died so no big deal.
But cutting to the chase, now again, you will have an occasion to read about my thrilling and breathtaking adventures in the code.
You may wonder, what you can expect exactly. In my professional career I have switched to C# and so I came up with an idea to create a new category called “Java vs. C#” where I will be writing down my remarks about interesting differences in those languages and also in the platforms and frameworks associated with them. I have used C# for about 5 months so far and spotted already a few really useful features that Java does not have. On the other hand, I haven't noticed anything that Java has but C# does not – here, speaking only about the language itself.
Other than that I will still continue to bring up topics about software engineering in general and things I find worth sharing with you!
So stay tuned – the next post coming up soon!

A tiny trick thanks to the autoboxing.

Today it will be short and tiny. The whole trick bases on the Java autoboxing feature. Let's say that we want to implement a method that checks whether a string that the passed reference points to, is evil. The first question that may pop up in your mind is when the string is evil? That mostly depends on you, in our example though, we will assume that it happens when it's equal to “666”. But wait, this article is not really about evilness. Let's go back to the way we should implement our method. The first important thing, is to check whether the reference is equal null. After that we can just invoke the equals() method inherited from the Object class and based on its result return true or false. A sample implementation could look like this:

public class StringTest {
 static boolean isEvil(String evil) {
  if(evil == null) {
   return false;
  }
  return evil.equals("666");
 }
}

But if we would like to get some advantage from the autoboxing feature in Java, we can easily get rid of the null check in our method. You probably ask why we can do that. It's simple – the null check is already done in the equals() method that the String class provides so why would we repeat it? To achieve the above, we have to force the “666” to be autoboxed and then invoke the equals() method on the new object against the passed reference. The following code shows the whole solution:

public class StringTest {
 static boolean isEvilEnhanced(String evil) {
  return "666".equals(evil);
 }
}

It's shorter, still easily readable and what's more important, faster! (The autoboxing in the first example has to be done anyway, since the equals method takes a reference to the Object class)

Parsing large XML files.

Today I will write about parsing XML files from the Java perspective. Recently I faced a task of reading and eliciting some certain data from a bigger than usually XML file – over half a GB. The most desirable approach when it's about parsing XML files is to use a parser that implements a DOM API interface. For those of you who are not familiar with this mechanism – in a nutshell, it's a tree based API which reads the entire document into memory and represents it as a tree of objects, to which we have random access. It makes a work with XML documents very convenient and easy thanks to the fact that we can easily retrieve any interesting node from the tree and read the data that we need. Unfortunately, there is a huge drawback with this solution – it requires lots of memory, depending on the implementation, up to a few times of the xml document's size which in my case, forced me to seek for another approach.

After a while, I came across to StAX, which stands for Streaming API for XML. It is much different API than the DOM. The first important thing – it does not convert the document into a tree. Instead, it treats it as it is – a stream. But that's not everything. The StAX is a pull streaming model which means that it is up to the programmer when he or she wants to start, pause or resume the parsing process.

Fine! I guess that's enough for an introduction. Let's have a look at the following example of parsing an xml file. First of all, here is how the xml file looks like:

<calendar>
 <event type = "party">
  <where>Club Mojito</where>
  <whom>My friends</whom>
 </event>
 <event type = "meeting">
  <where>A building</where>
  <whom>Project Manager</whom>
  <date>12/09/11</date>
 </event>
 <event type = "lunch">
  <where>Canteen</where>
 </event>
</calendar>

And the code that parses the file using StAX:

package stAX;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.InputStream;
import java.util.Iterator;

import javax.xml.stream.XMLEventReader;
import javax.xml.stream.XMLInputFactory;
import javax.xml.stream.XMLStreamException;
import javax.xml.stream.events.Attribute;
import javax.xml.stream.events.StartElement;
import javax.xml.stream.events.XMLEvent;

public class StAXExample {
 public static void main(String[] args) {
  XMLInputFactory inputFactory = XMLInputFactory.newInstance();
  try {
   InputStream in = new FileInputStream("ourFile.xml");
   XMLEventReader eventReader = inputFactory.createXMLEventReader(in);
   String currentElement = "";
   while(eventReader.hasNext()) {
    XMLEvent event = eventReader.nextEvent();
    if(event.isStartElement()) {
     StartElement startElement = event.asStartElement();
     currentElement = startElement.getName().toString();
     System.out.println("Start element: " + startElement.getName());
     @SuppressWarnings("unchecked")
     Iterator<Attribute> it1 = startElement.getAttributes();
     while(it1.hasNext()) {
      Attribute attribute = it1.next();
      System.out.println(" Attribute name: " + attribute.getName() + ", value: " + attribute.getValue());
     }  
    }
    if(event.isEndElement()) {
     currentElement = "";
    }
    if(event.isCharacters()) {
     if(currentElement.equals("whom") && event.isCharacters()) {
      System.out.println(event.asCharacters().getData());
     }
    }
   }   
  } catch (FileNotFoundException e) {
   e.printStackTrace();
  } catch(XMLStreamException xse) {  
  }  
 }
}

In lines 17 – 20 we initialize our parser. The most important thing, is to get an implementation of an XMLEventReader interface. This is the top level interface for parsing xml files which gives an access to all methods that we need. In order to get this implementation we need XMLInputFactory and InputStream with the xml file we want to parse.

In the next part of code we can see the usage of an XMLEventReader interface. The methods that we take advantage of are as follows:

hasNext() It checks if there are more events

nextEvent() returns the next event

isStartElement() checks if the event is a start element, which means, for instance, an opening tag

isEndElement() as the previous method, just that it relates to an end element.

IsCharacters() checks if the event is the plain text, which means, the text between opening and closing tags.

Ok, so for now, we know how to get opening and closing tags, as well the content between them but let's say we would like to get the attributes of some tag and their values. In the lines 29-33 I achieve this with an iterator. The interface StartElement has a method getAttributes() that returns an iterator to the attributes which we can cast to the Iterator. After that the Attribute interface has the methods getName() and getValue() which we use to get the name and value of the tag's attributes.

It is that simple. So now on, if you have a large XML file you will know how big boys do handle it ;-).

Call me!

Today you will have a great occasion to call someone you would never expect to call... a thread. We talked already about the concurrency on the blog: Threads part 1: The basics and Threads part 2: functions overview. But the problem with the previous solution to achieve simultaneous computation is the lack of explicit mechanism to retrieve the result from a thread. As luck would have it, since Java 1.5 we have an access to a new interface – Callable. In comparison to Runnable there are a few significant differences:

• with Callable you can easily return a result of another execution thread.
• with Callable you can throw checked exceptions.
• with Callable you have to use a thread executor.

So far so good. Now, to get more familiar with it, let's have a look at some code:

import java.util.concurrent.Callable;
import java.util.concurrent.ExecutionException;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.Future;


class Computation implements Callable<Integer> {

@Override
public Integer call() throws Exception {
    int result = 0;
    for(int i = 0; i < 10000; i++) {
        for(int j = 0; j < 100000; j++) {
            // Some taught computation
            result += (i * j) - (i * j) + 1;
        }
    }
    return result;
}

}

public class CallableExample {
public static void main(String[] args) {
    ExecutorService pool = Executors.newFixedThreadPool(5);
    Future<Integer> f1 = pool.submit(new Computation());
    for(int i = 0; i < 10; i++) {
        System.out.println(i);
    }
    try {
        System.out.println(f1.get());
    } catch (InterruptedException e) {
        e.printStackTrace();
    } catch (ExecutionException e) {
        e.printStackTrace();
    }
    pool.shutdown();
}
}

Ok, there are a few new elements regarding Callable. First of all, if we implement the Callable interface, we have to implement T call() method. This is where the action takes place, it's a method corresponding to the run() method from Runnable interface. And the other important thing – it's the place where we can throw an exception (Exception or any subclass).
When the class implementing Callable interface is ready, we can instantiate it and run through a submit() method of a thread executor what happens in line 27. The submit() method will return some implementation of a Future interface. It represents the thread's computation and provides a few useful methods, among others:
boolean isDone();
which returns true if the task is completed.
T get()
which returns a result of a task of type T, or if the task is not completed yet it waits until it's finished. Actually this could be achieved with a wait() method using a Runnable interface and calling it on the instance of a thread from the main execution thread.

And that's it. I'm sure that the above information and the sample code will let you use the Callable interface in appropriate way.

Type erasure in Java.

Probably every Java developer knows what type erasure is. In Oracle tutorial on Type Erasure we can read:

When a generic type is instantiated, the compiler translates those types by a technique called type erasure — a process where the compiler removes all information related to type parameters and type arguments within a class or method. Type erasure enables Java applications that use generics to maintain binary compatibility with Java libraries and applications that were created before generics.

The generic types are only for the compile time - after the type checking they are removed and gone for good, for sake of legacy code. Are they really? Let's have a look at the code I just wrote:

import java.lang.reflect.Field;   
import java.lang.reflect.ParameterizedType;   
import java.lang.reflect.Type;   
  
class P1 {}   
class P2 {}   
class P3 {}   
  
class A<T1, T2, T3> { }   
  
public class Gen2 {    

    A<P1, Integer, P3> genTest = new A<P1, Integer, P3>();   
    public static void main(String[] args) throws Exception {      
        ParameterizedType genTestField = (ParameterizedType)Gen2.class.getDeclaredField("genTest").getGenericType();   
        for(Type type : genTestField.getActualTypeArguments() ) {   
            System.out.println(type);   
        }   
    }   
} 

In the above code, we define a generic class A that can be parametrized - in the line 13 we instantiate this class with parameters P1, Integer and P3. And now,
through a reflection of Gen2 class and methods getDeclaredField(String) and getGenericType() we can elicit the parameters used during instantiating generic class A!
The code will print:

class P1
class java.lang.Integer
class P3

So in this way we can get exactly the generic parameters that were used. How this can be accomplished? As I already wrote, through a reflection. When we open a compiled Gen2.class file we can see a section "Signature":

Signature LA<LP1;Ljava/lang/Integer;LP3;>;

which shows the types that we were interested in. So apparently it seems that this information is not completely removed after the compilation time. From the bytecode yes, but in the .class file the information is still available!
In my opinion it's a very interesting and important example especially when we can read in many places that after the compilation we can't get the parameters anymore! Hope it was at least a little bit inspiring and encouraged you to read more on the reflection mechanism.

String's split() method.

This will be short. Recently I had to use this simple String class method when developing a parser for some pdf documents. Everything was going well until one moment. In the document, among others I had to elicit a range value which was given in the format x..y (for instance, 1..32). After getting the string 1..32 I wanted to use split method to separate the bounds. So in the code it could look like this:

String range = "1..32";
String[] bounds = range.split("..");

But that didn't work! Why? The answer is very simple. The String's split method takes a regex expression as an argument! And in Java "." (a dot) in regex means any character. So that's why the returned array was empty! To solve it we have to use "\\" between any special regex character if we want it to be treated as a string character. So we should change the above code to:

String range = "1..32";
String[] bounds = range.split("\\.\\.");

That's simple! So remember: split's argument = regex expression! Wish all my readers remember this both on the exam and during the work with Java code.

Java 7, where are you?

That's right. On the December 11 it will be round 4 years since the first release of Java 6. And I have to admit that it's quiet a long time in comparison to the previous versions. Ok, why don't have a little history lesson right now? Let's go back in time to end of 90s. Right before Christmas period, in '98, on December 8 Java 1.2 is published. A year and a half (May 8, 2000) after this Java 1.3 kicks in. Then again, not even 2 years and we had the Java 1.4 (February 6, 2002). And it keeps going. September 30, 2004 – Java 1.5, December 11, 2006 – 1.6. And today we have November 28 2010 and there is still no Java 7! Nearly 4 years! Of course we had plenty updates to Java 6 (more precisely 22) but I still claim it's a long time. You may probably wonder that there are lots of new features and important changes coming up soon. The reality though, is a little bit different. Soon – yes, in the mid of 2011. Lots and important? Let's have a look. As for the Java 7 we got 2 major Java Specification Requests. JSR #334 Small Enhancements to the Java Programming Language and JSR #335 Lambda Expressions for the Java Programming Language. In a nutshell, the #334 introduces the following features:

• Strings in switch
• Binary integral literals and underscores in numeric literals
• Multi-catch and more precise rethrow
• Improved Type Inference for Generic Instance Creation (diamond)
• try-with-resources statement
• Simplified Varargs Method Invocation

I don't say these changes are not cool. They actually are. For instance the Diamond syntax will let you replace

 Map<String, ArrayList<Integer>> m = new LinkedHashMap<String, ArrayList<Integer>>();  

with this:

 Map<String, ArrayList<Integer>> m = new LinkedHashMap<>();  

Another interesting feature is “try-with-resources statement”. You may wonder what this is. Have a look at the following example (sorry for the lack of proper code formatting but for some reason it doesn't work with this code):

BufferedReader br = new BufferedReader(new FileReader(path));

try {

return br.readLine();

} finally {

br.close();

}

With the automatic resource management statement it will look like this:

try (BufferedReader br = new BufferedReader(new FileReader(path)) {

return br.readLine();

}

This new enhanced try clause will automatically close the resource after the try block so in this case it will never happen that the programmer forgets about it. Oh, and any sorts of streams are welcome in the new try plus you can have more than one.

And my most favourite – the second point. You will be able to use underscores in numeric literals, like this:

int howCoolIsThis = 1_000_000;

No kidding. That's one of the points proposed for the Java 7 specification.

Ok. Let's go to the big one. Lambda expressions! Present in the huge rival of Java – C# and also in other languages like PHP or Javascript. And now very likely to be introduced to Java 7. Here is the glimpse of the request:

• Lambda Expressions
• SAM Conversion
• Method References
• Virtual Extension Methods

As for me, this is a real boost of Java 7 and the feature that will make an actual difference. Because let's be honest, the changes from the JSR #334 are really minor. Of course, they all are very useful (maybe except the underscore thing...), especially the Diamond syntax and will lead to the better quality of code but aren't these too few changes for 4 years?

And here it is - certification summary!

Well, I must admit that it's been some time since the last article but I was really overwhelmed recently – I had to accommodate in a new apartment, settle down all the things at university and finally I have started to work as a Java Software Developer. But anyway, now all the issues are resolved and I'm back to blogging again!

So today I would like to make a summary of OCPJP certification. First of all, I'm really glad that I've taken upon this endeavor. I have learnt many new things about Java that I didn't use before. Actually I'm not sure if I will ever use it but it's good to know it anyway ;-). And as luck would have it, I already have noticed how has my marked value increased. I did mention that I got a job, didn't I? ;-) Alright but you might probably want to know what I did in preparation for this exam. So obviously on the first place there is a book, the only one, don't even think about getting any other - SCJP Sun Certified Programmer for Java 6 Exam. I read it twice. The first time was a quick review of the book and getting familiar with some completely new areas. The second time though was much more careful and full of experiments with the code. And that is really vital! Experiment with the code – without this you will score much lower than you could if you did it. I know, it takes some time but trust me on that, it's really worth it. Ok, so let's assume that you already read the book, as many times as you wanted and you are wondering what next... Well, in my case it was a series of mock tests. Mostly by Whizlab (http://www.whizlabs.com/scjp/certification-exam.html). But in this place I have one more important tip. After solving a mock test also do some experiments with the code in exercises, especially the ones that were not correct. And I guess that's all! If you do more or less what I've described I'm sure you will do well on the exam!

As for me, my next goal on the Oracle Certification path is Oracle Certified Professional, Java EE 5 Web Component Developer! Soon, you will be able to follow my preparation's activities to this exam!

Oracle Certified Professional Java SE 6 Programmer exam passed!

Yes, that's it! On the 6th of September I made it with 95% score. Not bad at all! It means 57 out of 60 questions answered correctly! Frankly speaking, the exam didn't seem to be easy - many questions required me to think deeply not as it was with the Whizlabs' tests. Even though, I had had some spare time left at the end to review all the questions and afterwards could hit the magic button "end" which surprisingly... ended the exam! But don't worry! The fact that I passed the exam doesn't mean that I will stop posting the articles related to it. I have a list of topics that I want to bring up here and after my short holidays that I'm on right now I will resume writing! I will also say something more about my scores of the exam and add some important notes that might be helpful for other people preparing to become certified!

Utility methods of wrapper classes.

Wrapper classes basically have two purposes: to wrap a primitive and to provide a set of utility functions dealing with some conversions. In this article I will focus on the latter objective.

The first function that I will cover here is a static valueOf() method. It takes as an argument a string and converts it to the desired wrapper object. In most cases you can also provide a second parameter that is an int radix which indicates the base of the first parameter. The valueOf() method is provided in most of the wrapper classes (except Character). It throws a NumberFormatException (it is not checked so you don't have to declare it) if the string provided can't be converted. Here are some legal uses of it:

Integer i1 = Integer.valueOf("3");
Integer i2 = Integer.valueOf(123);
Float f = Float.valueOf("2.2");

The second method is xxxValue() where in the place of xxx we can put any primitive. This function converts the value of a wrapped object to a primitive. The following code shows a few examples of how we should use it:

Float f = Float.valueOf("5.5");
byte b = f.byteValue();
short s = f.shortValue();
double d = f.doubleValue();

The next function that is important to remember is parseXXX(). It is static and takes a string as an argument and parses it into an appropriate primitive. It also throws NumberFormatException in case when the string arument is not well formated. Let's have a look at the following demonstration code:

double d = Double.parseDouble("123.456");
int i = Integer.parseInt("345");
byte b = Byte.parseByte("127");

And that's it! Three useful and important methods that we should know for the exam!

No more Sun Certified Java Programmer!

Erm... nearly. If you want to become one you should simply hurry up. You have 7 days for that and starting on 1st September you will be named Oracle Certified Professional Java SE 6 Programmer. That's another outcome of the acquisition Sun by Oracle that has had place at the beginning of this year.

As for me the name of the certificate doesn't really matter but what actually pops up in my mind is the question whether and when the employers will become familiar with the new name. Let's be honest - one of the reasons of why we become certified is the fact that it adds a new valuable element to our CV. But for this, the potential employer must be familiar with the title. Recently I read on a forum that Oracle sends some newsletters about the naming changes for the interested people (you probably need an account in the Oracle's Education Center) but for sure it will take some time to spread the word.

Nevertheless, below is the link to Oracle's website with additional information and names of the other exams. Yes! All the names has been changed!

Oracle Certification Program

Assignments.

By the title I actually mean the 3rd chapter of the K&B SCJP book. I have to admit that it was really surprising. I have learnt many new things that I was completly unaware of. Of course, in the real projects, when you use some IDE it's nearly impossible to make mistakes of this sort but on the exam they can be very savage. So below you will find some important points from this chapter that you really should pay attention to, during the exam.

First, we'll talk about the literals. Remember that every integer literal is an int. So there is no problem if we want to do the following assignments:

int a = 5; (fits well)
long b = 6; (fits well since long is bigger than int)

but what if we try to assign the integer literal (so an int) to the smaller type? Let's have a look!

byte c = 7;

And yeah, there is still no problem. That's of course good for us but basing on the above that shouldn't work. Well, that happens because the compiler makes an implicit cast so in fact, it looks like this:

byte c = (byte)7;

Alright. That's very convenient for us. But this implicit cast is applied only to literals! So this is not going to work:

int a = 5;
byte b = a;

To compile the code consisting of the above assignments you need to do an explicit cast:

int a = 5;
byte b = (byte)a;

Also keep in mind the following rule. The result of any expression involving an int or anything smaller, like byte and short will result in an int! So the following will... not compile!

byte a = 5;
byte b = 1;
byte c = a + b;

You need to put an explicit cast! One more thing about the floating points literals. They are always doubles. And here the compiler won't make an implicit cast, the following code will not compile:

float d = 2.5;

Instead you should write:

float d = (float)2.5;

Or mark that what you mean is really a float by adding and f or F at the end of the literal:\

float d = 2.5f;

Ok, that's it for the literals! Now let's move on to the primitive casting.
First of all, it's important to remember that the implicit cast happens when we assing a smaller to a bigger. So for instance:

int a = 5;
byte b = (byte)a;
long c = 'a' + 'b';
 
a = b;
c = a;
c = b;

These are all legal assignments. But the followings are not:

b = a;
b = c;
a = c;

And what do we need? An explicit cast!

b = (byte)a;
b = (byte)c;
a = (int)c;

Et voila monsieur! Also the same thing happens with floating points. All the following are legal:

double d = 2.5;
float f = 3.4f;
int i = 12;
long l = 45;
     
d = l; // assigning long to double
d = f; // assigning float to double
f = i; // assigning integer to float

But in case when a truncation may occur we have to make an explicit cast otherwise our code will produce an error.
The followings are legal but the cast is necessary:

double d = 2.5;
float f = 3.4f;
int i = 12;
long l = 45;
     
f = (float)d;
i = (int)f;
l = (long)d;

That's a piece of cake but I'm sure that you've found here something new and interesting for you!