Vanilla #Java

"Java Sucks" revisited

2012-01-26T09:07:00.003Z

Overview

An interesting document on Java's short comings (from C developer's perspective) was written some time ago (about 2000? ) but many of the arguments issues are as true (or not) today as they were ten years ago.

The original Java Sucks posting.

Review of short comings

Java doesn't have free().

The author lists this as a benefit and 99% of the time is a win. There are times when not having it is a downside, when you wish escape analysiswould eliminate, recycle or free immediately an object you know isn't needed any more (IMHO the JIT / javac should be able to work it out in theory)

lexically scoped local functions

The closest Java has is anonymous methods. This is a poor cousin to Closures (coming in Java 8), but it can be made to do the same thing.

No macro system

Many of the useful tricks you can do with macros, Java can do for you dynamically. Not needing a macro system is an asset because you don't need to know when Java will give you the same optimisations. There is an application start up cost that macros don't have and you can't do the really obfuscated stuff, but this is probably a good thing.

Explicitly Inlined functions

The JIT can inline methods for you. Java can inline methods from shared libraries, even if they are updated dynamically. This does come at a run time cost, but its nicer not to need to worry about this IMHO.

I find lack of function pointers a huge pain

Function pointers makes in lining methods more difficult for the compiler. If you are using object orientated programming, I don't believe you need these. For other situations, I believe Closures in Java 8 is likely to be nicer.

The fact that static methods aren't really class methods is pretty dumb

I imagine most Java developers have come across this problem at some stage. IMHO: The nicest solution is to move the "static" functionality to its own class and not use static methods if you want polymorphism.

It's far from obvious how one hints that a method should be inlined, or otherwise go real fast

Make it small and call it lots of times. ;)

Two identical byte[] arrays aren't equal and don't hash the same

I agree that its pretty ugly design choice not to make arrays proper objects. They inherit from Object, but don't have useful implementation for toString, equals, hashCode, compareTo. clone() and getClass() are the most useful methods. You can use helper methods instead, but with many different helper classes called Array, Arrays, ArrayUtil, ArrayUtils in different packages its all a mess for a new developer to deal with.

Hashtable/HashMap does allow you to provide a hashing function

This is also a pain if you want to change the behaviour. IMHO, The best solution is to write a wrapper class which implements equals/hashCode, but this adds overhead.

iterate the characters in a String without implicitly involving half a dozen method calls per character

There is now String.toCharArray() but this creates a copy you don't need and is not eliminated by escape analysis. When it is, this is the obvious solution.

The same applies to "The other alternative is to convert the String to a byte[] first, and iterate the bytes, at the cost of creating lots of random garbage"

overhead added by Unicode support in those cases where I'm sure that there are no non-ASCII characters.

Java 6 has a solution to this which is -XX:+UseCompressedStrings. Unfortunately Java 7 has dropped support for this feature. I have no idea why as this option improves performance (as well as reducing memory usage) in test I have done.

Interfaces seem a huge, cheesy copout for avoiding multiple inheritance; they really seem like they were grafted on as an afterthought.

I prefer a contract which only lists functionality offered without adding implementation. The newer Virtual Extension Methods in Java 8 will provide default implementations without state. In some cases this will be very useful.

There's something kind of screwy going on with type promotion

The problem here is solved by co-variant return types which Java 5.0+ now supports.

You can't write a function which expects and Object and give it a short

Today you have auto-boxing. The author complains that Short and short are not the same thing. For efficiency purposes this can make surprisingly little difference in some cases with auto-boxing. In some cases it does make a big difference, and I don't foresee Java optimising this transparently in the near future. :|

it's a total pain that one can't iterate over the contents of an array without knowing intimate details about its contents

Its rare you really need to do this IMHO. You can use Array.getLength(array) and Array.get(array, n) to handle a generic array. Its ugly but you can do it. Its one of the helper class which should really be methods on the array itself IMHO.

The only way to handle overflow is to use BigInteger (and rewrite your code)

Languages like Scala support operators for BigInteger and it has been suggested that Java should too. I believe overflow detection is also being considered for Java 8/9.

I miss typedef

This allows you to use primitives and still get type safety. IMHO, the real issue is that the JIT cannot detect that a type is just a wrapper for a primitive (or two) and eliminate the need for the wrapped class. This would provide the benefits of typedef without changing the syntax and make the code more Object Orientated.

I think the available idioms for simulating enum and :keywords are fairly lame

Java 5.0+ has enum which are first class objects and are surprising powerful.

there's no efficient way to implement `assert'

assert is now built in. To implement it yourself is made efficient by the JIT. (Probably not tens years ago)

By having `new' be the only possible interface to allocation, ... there are a whole class of ancient, well-known optimizations that one just cannot perform.

This should be performed by the JIT IMHO. Unfortunately, it rarely does, but this is improving.

The finalization system is lame.

Most people agree its best avoided. Perhaps it could be more powerful and reliable. ARM (Automatic Resource Management) may be the answer.

Relatedly, there are no ``weak pointers.''

Java has always had weak, soft and phantom references, but I suspect this is not what is meant here. ??

You can't close over anything but final variables in an inner class!

There is true of anonymous inner classes, but not nested inner classes referring to fields. Closures might not have this restriction but its likely to be just as confusing. Being used to the requirement for final variables, I don't find this problem esp. as my IDE will correct the code as required for me.

The access model with respect to the mutability (or read-only-ness) of objects blows

The main complaint appears to be that there are ways of treating final fields as mutable. This is required for de-serialization and dependency injectors. As long as you realise that you have two possible behaviours, one lower level than the other, it is far more useful than it is a problem.

The language also should impose the contract that literal constants are immutable.

Literal constants are immutable. It appears the author would like to expand what is considered a literal constant.

It would be useful IMHO, to support const in the way C++ does. const is a keyword in Java and the ability to define immutable versions of classes without creating multiple implementations or read only wrappers would be more productive.

The locking model is broken.

The memory overhead of locking concern is really an implementation detail. Its up to the JVM to decide how large the header is and whether it can be locked. The other concern is that there is no control over who can obtain a lock. The common work around for this is to encapsulate your lock, which is what you would have to do in any case.

In theory the lock can be optimised away. Currently this only happens when the whole object is optimised way.

There is no way to signal without throwing

For this, I use a listener pattern with an onError method. There is no support in the language for this, but I don't see the need to.

Doing foo.x should be defined to be equivalent to foo.x(),

Perhaps foo.x => foo.getX() would be a better choice, rather like C# does.

Compilers should be trivially able to inline zero-argument accessor methods to be inline object+offset loads.

The JIT does this, rather than the compiler. This allows the calling code to be changed after the callee has been compiled.

The notion of methods "belonging" to classes is lame.

This is a "cool" feature which some languages support. In a more dynamic environment, this can look nicer. The down side is that you can piece of code for a class all over the place and you would have to have some way of managing duplicates in different libraries. e.g. library A defines a new printString() method and library B also defines a printString method for the same class. You would need to make each library see its own copy and have some way of determining which version library C would want when it calls this method.

Libraries

It comes with hash tables, but not qsort

It comes with an "optimised merge sort" which is designed to be faster.

String has length+24 bytes of overhead over byte[]

That is without considering that each of the two objects are aligned to an 8 byte boundary (making it higher). If that sounds bad, consider that malloc can be 16-byte aligned with a minimum size of 32 bytes. If you use a shared_ptr to a byte[] (to give you similar resource management) it can be much larger in C++ than Java.

The only reason for this overhead is so that String.substring() can return strings which share the same value array.

This is not correct. The problem is that Java doesn't support variable sized objects (apart from arrays). This means that String object is a fixed size and to have variable sized field, you have to have another object. Its not great either way. ;)

String.substring can be a source of "memory leak"

You have to know to take an explicit copy of you are going to retain a substring of a larger string. This is ugly, however the benefits usually out weight the down side. What would be a better solution is to be able to optimise the code so that a defensive copy was taken by default, except when the defensive copy is not needed (it is optimised away)

The file manipulation primitives are inadequate

The file system information has been improved in Java 7. I don't think these options are available, but can be easily inferred if you need to know this.

here is no robust way to ask ``am I running on Windows'' or ``am I running on Unix.'

There are System properties os.name, os.arch, os.version which have always been there.

There is no way to access link() on Unix, which is the only reliable way to implement file locking.

This was added in Java 7 Creating a Hard Link

There is no way to do ftruncate(), except by copying and renaming the whole file.

You can use RandomAccessFile.truncate(). Adding in Java 1.4.

Is "%10s %03d" really too much to ask?

It was added in Java 5.0

A RandomAccessFile cannot be used as a FileInputStream or FileOutputStream

RandomAccessFile supports DataInput and DataOutput, FileInputStream and FileOutputStream can be wrapped in DataInputStream and DataOutputStream. They can be made to support the same interfaces. I have never come across a situation where I would want to use both classes in a single method.

markSupported is stupid

True. There are a number of stupid methods which are only there for historical purposes. Another being Object.wait(millis, nanos) on every object (even arrays) and yet the nanos is never really used.

What in the world is the difference between System and Runtime?

I agree it appears arbitrary and in some cases doubled up. System.gc() actually calls Runtime.getRuntime().gc() and yet is called System GC even in internal code. In hind site they should really be one class with monitoring functionality moved to JMX.

What in the world is application-level crap like checkPrintJobAccess() doing in the base language class library

So your SecurityManager can control whether you can perform printing. (Without having to have an Application level Security Manager as well) Not sure is this really prevents the need to have Application level security. ;)

Demonstrating when volatile is required

2012-01-23T08:32:00.002Z

Overview

In many cases volatile is required when you need a guarantee about visibility of changes between threads. i.e. All threads see a consistent view of the same field. Demonstrating a consistent failure when you don't use volatile is tricky, and likely to be platform specific.

An example

The following example show that each thread starts by flipping the value and then stops as each thread has a different view of the field value This works on Java 7 update 2 on Centos 5.7 (x64).

Even incidental change to the code, change the behaviour showing how brittle the example is. I would be interested if others can reproduce this behaviour

The code


public class RequiresVolatileMain {
    static boolean value;

    public static void main(String... args) {
        new Thread(new MyRunnable(true), "Sets true").start();
        new Thread(new MyRunnable(false), "Sets false").start();
    }

    private static class MyRunnable implements Runnable {
        private final boolean target;

        private MyRunnable(boolean target) {
            this.target = target;
        }

        @Override
        public void run() {
            int count = 0;
            boolean logged = false;
            while (true) {
                if (value != target) {
                    value = target;
                    count = 0;
                    if (!logged)
                        System.out.println(Thread.currentThread().getName() + ": reset value=" + value);
                } else if (++count % 1000000000 == 0) {
                    System.out.println(Thread.currentThread().getName() + ": value=" + value + " target=" + target);
                    logged = true;
                }
            }
        }
    }
}

As you can see, each thread tries to flip the value whenever it doesn't match the target. When you attempt to run this fails, perhaps not in the way you might expect. If you run this with -XX:+PrintCompilation


Sets true: reset value=true
Sets false: reset value=false
....
Sets true: reset value=true
Sets false: reset value=false
     44    1 %           com.google.code.java.core.threads.RequiresVolatileMain$MyRunnable::run @ 4 (129 bytes)
Sets true: reset value=true
Sets false: reset value=false
....
Sets true: reset value=true
Sets false: reset value=false
Sets true: value=false target=true
Sets false: value=true target=false
...
Sets true: value=false target=true
Sets false: value=true target=false

Not long after the code is compiled, the code starts acting as if it doesn't detect a change even though the value printed is clearly not the target. Exactly why it fails this way is not clear. esp. as the value in the same thread appears to be inconsistent.

The only explanation I can come up with is that if (value != target) has been incorrectly optimised away. Possibly because the only branch which sets this value is not run most of the time.

Just caching the value stops it failing for me, but this is not a proper fix and might fail on a different platform


                // caching the value stops the failure.
                boolean value = RequiresVolatileMain.value;
                if (value != target) {
                    RequiresVolatileMain.value = target;

The solution

The solution is to use a volatile variable, in which case it keeps printing that the value is reset as expected.

Why does this fail

The values are boolean. This is like a game of ping-pong. The ball is only on one side, either true or false (if you use volatile) It doesn't matter which values it is, only one thread will change the value.

Without volatile, this breaks down in a number of possible ways. One way is that the two threads each think they have changed the value and are waiting for the other i.e. each has its own cached copy of the value.

The way it breaks down in the example above is that the compiler detect that the value is not changed if it is the target value already and the thread is not going to set it to any other value. It then assumes the check isn't required and even though both thread print the value as needing changing (the opposite of the previous case) it stops changing the value.

Another Shifty Challenge

2012-01-22T10:52:00.001Z

Overview

Shifting has lots of edge cases. Some particular to Java.

Over shifting

In C the expression n << 64 and n >> 64 would always be 0, but in Java it will always be n This is because the shifted value is mod'ed by the number of bits.

A puzzle

If the following program


for (int i = -200; i < 200; i++)
    if (i >>> i == 1)
        System.out.print(i+" ");

prints


-193 -161 -129 -97 -65 -33 -1 37 70 102 135 167 199

What do you get if you change the type to long?

See if you can work it out without running the code.

Shifting Challenge

2012-01-19T08:59:00.000Z

Overview

Using shift in Java and some surprising edge cases.

Getting the sign

For the following program, what is the values for n so that I can change the type of x without having to change the code.


// sign is 1 if negative and 0 if non-negative
long sign = x >>> n;

There is a value you can replace n such that you don't need to know the type of x

Similarly, I want to shift the lowest bit to be the highest without knowing what type I am shifting


// sign is MIN_VALUE if odd otherwise 0
long sign = x << n;

For bonus points, write formula for all the possible solutions of n (there is more than one)

Is a power of two

How do you determine an integer is a power of 2.

This is a fairly common interview question. Its pretty hard to figure out in an interview I imagine. To save you googling, you can write this in C with


x&&!(x&(x-1))

In Java, you can write this using just 0 ~ - & == != . Complete this expression using those operators


long x = 
boolean isPow2 = x != 0 .....

Unsigned Challenge

2012-01-18T20:58:00.001Z

Overview

Its easy to assume that because Java doesn't support unsigned primitives that you need a complex wrapper to using unsigned numbers.

The challenge

Modify the following class which has been written to use signed int as unsigned value. The starting code works for signed values. You need to change the methods so it treats them as unsigned 32-bit int values. The aim is to add/change a minimum of lines. (You can't change the tests or turn them off)


public enum Unsigned {;
    public static int add(int i, int j) {
        return i + j;
    }

    public static int subtract(int i, int j) {
        return i - j;
    }

    public static int multiply(int i, int j) {
        return i * j;
    }

    public static int shiftLeft(int i, int n) {
        return i << n;
    }

    public static int shiftRight(int i, int n) {
        return i >> n;
    }

    public static int parseUnsignedInt(String text) {
        return Integer.parseInt(text);
    }

    public static String toString(int n) {
        return Integer.toString(n);
    }

    public static void main(String... args) {
        assert "2500000000".equals(toString(subtract(add(2000 * 1000 * 1000, 1750 * 1000 * 1000), 1250 * 1000 * 1000)));
        assert "4000000000".equals(toString(multiply(1000 * 1000, 4000)));
        assert "3200000000".equals(toString(shiftLeft(100 * 1000 * 1000, 5)));
        assert "1000000000".equals(toString(shiftRight(parseUnsignedInt("4000000000"), 2)));

        ByteArrayOutputStream baos = new ByteArrayOutputStream();
        DataOutputStream dos = new DataOutputStream(baos);
        writeUnsignedInt(dos, multiply(1000 * 1000, 4000));
        writeUnsignedInt(dos, parseUnsignedInt("3210000000"));
        dos.close();
        DataInputStream dis = new DataInputStream(new ByteArrayInputStream(baos.toByteArray()));
        assert "4000000000".equals(toString(readUnsignedInt(dis)));
        assert "3210000000".equals(toString(readUnsignedInt(dis)));
        dis.close();
    }
}

Hint: The solutions are surprisingly simple (which is the point of this article) If you are adding many lines of code, you are heading down the wrong path.

Java Thread Affinity support for ExecutorService

2012-01-16T16:52:00.000Z

Overview

The Java Thread Affinity version 1.4.1 library has support for the concurrency library through an AffinityThreadFactory.

This follows my previous article on HyperThreading support in the library which give mroe detail on what it does and how it works.

Example

In the AffinityThreadFactoryMain example,


private static final ExecutorService ES = Executors.newFixedThreadPool(4,
        new AffinityThreadFactory("bg", SAME_CORE, DIFFERENT_SOCKET, ANY));

public static void main(String... args) throws InterruptedException {
    for (int i = 0; i < 12; i++)
        ES.submit(new Callable() {
            @Override
            public Void call() throws InterruptedException {
                Thread.sleep(100);
                return null;
            }
        });
    Thread.sleep(200);
    System.out.println("\nThe assignment of CPUs is\n" + AffinityLock.dumpLocks());
    ES.shutdown();
    ES.awaitTermination(1, TimeUnit.SECONDS);
}

by changing the ThreadFactory, you can decide how threads in the factory should be laid out. The default behaviour is to allocate from highest CPU id to lowest, however by changing the AffinityStrategy you can make it try to minimise the number of cores it uses.


Assigning cpu 7 to Thread[bg,5,main]
Assigning cpu 6 to Thread[bg-2,5,main]
Assigning cpu 3 to Thread[bg-3,5,main]
Assigning cpu 2 to Thread[bg-4,5,main]

The assignment of CPUs is
0: General use CPU
1: General use CPU
2: Thread[bg-4,5,main] alive=true
3: Thread[bg-3,5,main] alive=true
4: General use CPU
5: General use CPU
6: Thread[bg-2,5,main] alive=true
7: Thread[bg,5,main] alive=true

Releasing cpu 7 from Thread[bg,5,main]
Releasing cpu 6 from Thread[bg-2,5,main]
Releasing cpu 3 from Thread[bg-3,5,main]
Releasing cpu 2 from Thread[bg-4,5,main]

In this case, the second thread is allocated to the SAME_CORE as the first, the third cannot get one on the same core so it tries to get on on a DIFFERENT_SOCKET, but there is only one so it takes ANY available core which can be reserved.

Java Thread Affinity support for hyper threading.

2012-01-16T13:00:00.000Z

Overview

A benefit of hyper-threading is the ability to support more threads without incurring the overhead of context switches. If your threads spend a high proportion of their time waiting for resources e.g. busy waiting on a data source, accessing main memory or waiting for short periods of time for IO, hyper threading can improve performance at little cost.

However, hyper threading can impact performance when the two threads on the same core start competing for resources, such as the FPU, Level 1 cache, or CPU pipeline. For these reasons, hyper-threading is often turned off in high performance systems.

A solution to get the best of both worlds

The Java Thread Affinity version 1.4 library attempts to get the best of both worlds, by allowing you to reserve a logical thread for critical threads, and reserve a whole core for the most performance sensitive threads. Less critical threads will still run with the benefits of hyper threading.

Example

Say you have a system e.g. an Intel i7 with four core and two logical threads per core.

You want to reserve two cores to dedicate to critical threads. On Linux you can do this but using isolcpus= in grup.conf

Say you have two critical thread which are busy waiting for resources and can share a core called "reader" and "writer" and you have an "engine" thread you want to dedicate a whole core to (so it doesn't have to compete for resources) You can assign the threads as follows.

The "engine" only uses "CPU 3" and "CPU 7" is reserved as idle.

How does this look in code

Sample code to allocate these thread/cores is as follows


AffinityLock al = AffinityLock.acquireLock();
try {
    // find a cpu on a different socket, otherwise a different core.
    AffinityLock readerLock = al.acquireLock(DIFFERENT_SOCKET, DIFFERENT_CORE);
    new Thread(new SleepRunnable(readerLock, false), "reader").start();

    // find a cpu on the same core, or the same socket, or any free cpu.
    AffinityLock writerLock = readerLock.acquireLock(SAME_CORE, SAME_SOCKET, ANY);
    new Thread(new SleepRunnable(writerLock, false), "writer").start();

    Thread.sleep(200);
} finally {
    al.release();
}

// allocate a whole core to the engine so it doesn't have to compete for resources.
al = AffinityLock.acquireCore(false);
new Thread(new SleepRunnable(al, true), "engine").start();

Thread.sleep(200);
System.out.println("\nThe assignment of CPUs is\n" + AffinityLock.dumpLocks());

This code declares that the "main" thread uses a cpu (it gets 7). The "reader" thread should use a different socket or a different core. It get a different core as there is no second socket. The "writer" thread tries to get a thread on the same core, or the same socket, or any thread. The AffinityStrategy is an interface which allows you to create your own thread allocation strategies.

The "engine" thread tries to allocate a whole core to the thread. (It finds a core where it can allocate all the threads for that core)

When run on an i7 with isolcpus=2,3,6,7 you get the following output


Assigning cpu 7 to Thread[main,5,main]
Assigning cpu 6 to Thread[reader,5,main]
Assigning cpu 2 to Thread[writer,5,main]
Releasing cpu 7 from Thread[main,5,main]
Assigning core 3: cpus 3, 7 to Thread[engine,5,main]

The assignment of CPUs is
0: General use CPU
1: General use CPU
2: Thread[writer,5,main] alive=true
3: Thread[engine,5,main] alive=true
4: General use CPU
5: General use CPU
6: Thread[reader,5,main] alive=true
7: Thread[engine,5,main] alive=true

Surprising results of autoboxing

2012-01-16T09:20:00.005Z

Overview

There are a number of surprising consequences of auto-boxing. Some are more widely known than others. Most of them are due to the effect of caching of some auto boxed objects.

== and equals may or may not match

If you run the program AutoboxEqualsMain with default options.


All Boolean are cached.
All Byte are cached.
The first auto-boxed char is 0 and the last is 127
The first auto-boxed short is -128 and the last is 127
The first auto-boxed int is -128 and the last is 127
The first auto-boxed long is -128 and the last is 127
No Float are cached.
No Double are cached.

For those that know that == compares references, for Integer or any Object type.

Run the program again with -XX:+AggressiveOpts on Java 7 and you get almost the same result.


All Boolean are cached.
All Byte are cached.
The first auto-boxed char is 0 and the last is 127
The first auto-boxed short is -128 and the last is 127
The first auto-boxed int is -128 and the last is 20000
The first auto-boxed long is -128 and the last is 127
No Float are cached.
No Double are cached.

Note: This option has increased the maximum for the Integer cache.

The performance improvements

The memory size for an int[] and an ArrayList<Integer> can be almost the same size for cached values. If you run this program which builds a collection of both using the numbers 1 to 16,000 with -XX:-UseTLAB and -XX:+AgressiveOpts you can get this result.


The int[16000] took 64592 bytes and new ArrayList() with 16000 values took 65048 bytes

This result is surprising for two reasons. Firstly, it is run in a 64-bit JVM. The ArrayList is an array of references, however the JVM can use 32-bit reference for up to 32 GB of heap memory. Note: You can use direct memory and memory mapped files to use much more than 32 GB, but as long as your heap is smaller than 32 GB it can use 32-bit references.
Secondly, the objects themselves don't appear to take any space. This is because all the values are cached before the program starts so you don't see the space they occupy.

Note: being such a short test the values for size you get vary with each run. I ran this test a few times and took the lowest result. The highest results were not that much higher (within 20%)

Auto-boxed objects don't get garbage collected

If you use auto-boxed objects as keys, they might never be unloaded.


Map<Long, String> keyValueMap = new WeakHashMap<Long, String>(10000);
for (long i = 1; i <= 8192; i *= 2)
    keyValueMap.put(i, "key-" + i);
System.out.println("Before GC: " + keyValueMap);
System.gc();
System.out.println("After GC: " + keyValueMap);

The keys of the map are not being held so you would expect them to be cleaned up on a GC. What might be surprising is that not all keys are cleaned up.


Before GC: {8192=key-8192, 4096=key-4096, 2048=key-2048, 1024=key-1024, 512=key-512, 256=key-256, 
    128=key-128, 64=key-64, 32=key-32, 16=key-16, 8=key-8, 4=key-4, 2=key-2, 1=key-1}
After GC: {64=key-64, 32=key-32, 16=key-16, 8=key-8, 4=key-4, 2=key-2, 1=key-1}

Note: I increased the initial capacity of the WeakHashMap so that the keys would appear in a predictable order.

Don't use auto-boxed object for as locks

This goes up there with not using string literals for locks


synchronized("lock one") { // DON'T do this.

But what can make using auto-boxed values worse is that your program can work fine when tested, provided the objects locked are small. When you program happens to use a larger value, the locking suddenly fails.


Object o = 
Integer lock = o.hashCode() & 255;
synchronized(lock)  { // DON'T do this either.

This could look like a clever way to have locks for all objects which are equal. However, its very brittle and obtuse and you could find your program fails unexpectedly in ways which are difficult to reproduce e.g. depending on whether you have use -XX:+AggressiveOpts If you have more than one library or section of code which does this, you could get bizarre deadlocks between unrelated code.

The code

Java Thread Affinity supports groups of threads.

2012-01-12T15:01:00.001Z

Overview

The Java Thread Affinity Library version 1.3, supports assigning groups of threads together by Socket, Core, or a custom strategy.

Determining the grouping of threads

The following Affinity Lock binding example, shows how you can choose to take either different sockets or cores, or share the same sockets or cores.

It creates a thread lock for "main". For the reader and writer threads it tries to get a different socket or core to "main", and reserve a cpu on the same core or socket as each other.


AffinityLock al = AffinityLock.acquireLock();
try {
    // find a cpu on a different socket, otherwise a different core.
    AffinityLock readerLock = al.acquireLock(DIFFERENT_SOCKET, DIFFERENT_CORE);
    new Thread(new SleepRunnable(readerLock), "reader").start();
    // find a cpu on the same core, or the same socket, or any free cpu.
    AffinityLock writerLock = readerLock.acquireLock(SAME_CORE, SAME_SOCKET, ANY);
    new Thread(new SleepRunnable(writerLock), "writer").start();
    Thread.sleep(200);
} finally {
    al.release();
}
// re-use the same cpu for the engine.
new Thread(new SleepRunnable(al), "engine").start();

When this runs you can see that reader gets cpu 6 which is on a different core to main on cpu 7, however writer is on cpu 2 which is another thread on the same core as reader.


Jan 12, 2012 2:58:56 PM vanilla.java.affinity.AffinityLock bind
INFO: Assigning cpu 7 to Thread[main,5,main]
Jan 12, 2012 2:58:56 PM vanilla.java.affinity.AffinityLock bind
INFO: Assigning cpu 6 to Thread[reader,5,main]
Jan 12, 2012 2:58:56 PM vanilla.java.affinity.AffinityLock bind
INFO: Assigning cpu 2 to Thread[writer,5,main]
Jan 12, 2012 2:58:56 PM vanilla.java.affinity.AffinityLock release
INFO: Releasing cpu 7 from Thread[main,5,main]
Jan 12, 2012 2:58:56 PM vanilla.java.affinity.AffinityLock bind
INFO: Assigning cpu 7 to Thread[engine,5,main]

The assignment of CPUs is
0: General use CPU
1: General use CPU
2: Thread[writer,5,main] alive=true
3: Reserved for this application
4: General use CPU
5: General use CPU
6: Thread[reader,5,main] alive=true
7: Thread[engine,5,main] alive=true

Jan 12, 2012 2:58:57 PM vanilla.java.affinity.AffinityLock release
INFO: Releasing cpu 6 from Thread[reader,5,main]
Jan 12, 2012 2:58:57 PM vanilla.java.affinity.AffinityLock release
INFO: Releasing cpu 2 from Thread[writer,5,main]
Jan 12, 2012 2:58:57 PM vanilla.java.affinity.AffinityLock release
INFO: Releasing cpu 7 from Thread[engine,5,main]

Generating every combination without duplicates

2012-01-10T14:04:00.000Z

Overview

Generating every combination where there is no duplicates is pretty simple. Handling the situation where there can be more than one value which is the same is trickier.

The problem

In this problem you have a list, with duplicates. e.g. [1, 1, 2, 3, 3, 3] Find all the combinations of this list, is a way which doesn't create any duplicates. e.g. if you swap the 1s around, its the same list.

You can do this with brute force by creating every combination and adding them to a Set to remove duplicates. The Set grows with the number of solutions. You can avoid the need to do this, by using a strategy to generate all possible lists which don't result in duplicates.

A solution

When building a collection to describe the problem all elements which are the same are equal and the order doesn't matter, only the number of times that element appears. e.g. 2 of 1, 1 of 2, 3 of 3.

This collection can also be used to determine how many of each time is still left. For the first number there is only three possibilities, 1, 2, 3 (not six if you were to use brute force) If you choice a 1, there is still three possibilities because you can still have another 1. After you choice 1 again, there is only two possibilities as there can only be one 2, and three 3's left.

In this post, I use a recursion and a Bag which keep a count of the values remaining. This ensures the number of options for an element is the number of unique values which have no appeared already.


import java.util.*;
import java.util.concurrent.atomic.AtomicInteger;

public class Main {
    public static void main(String... args) {
        Bag<Integer> b = new Bag<>();
        b.countFor(1, 2);
        b.countFor(2, 1);
        b.countFor(3, 3);
        Set<String> set = new LinkedHashSet<>();
        for (List<Integer> list : b.combinations()) {
            System.out.println(list);
            String s = list.toString();
            if (!set.add(s))
                System.err.println("Duplicate entry " + s);
        }
    }
}

class Bag<E> {
    final Map<E, AtomicInteger> countMap = new LinkedHashMap<>();

    void countFor(E e, int n) {
        countMap.put(e, new AtomicInteger(n));
    }

    void decrement(E e) {
        AtomicInteger ai = countMap.get(e);
        if (ai.decrementAndGet() < 1)
            countMap.remove(e);
    }

    void increment(E e) {
        AtomicInteger ai = countMap.get(e);
        if (ai == null)
            countMap.put(e, new AtomicInteger(1));
        else
            ai.incrementAndGet();
    }

    List<List<E>> combinations() {
        List<List<E>> ret = new ArrayList<>();
        List<E> current = new ArrayList<>();
        combinations0(ret, current);
        return ret;
    }

    private void combinations0(List<List<E>> ret, List<E> current) {
        if (countMap.isEmpty()) {
            ret.add(new ArrayList<E>(current));
            return;
        }
        int position = current.size();
        current.add(null);
        List<E> es = new ArrayList<>(countMap.keySet());
        if (es.get(0) instanceof Comparable)
            Collections.sort((List) es);
        for (E e : es) {
            current.set(position, e);
            decrement(e);
            combinations0(ret, current);
            increment(e);
        }
        current.remove(position);
    }
}

prints


[1, 1, 2, 3, 3, 3]
[1, 1, 3, 2, 3, 3]
[1, 1, 3, 3, 2, 3]
[1, 1, 3, 3, 3, 2]
[1, 2, 1, 3, 3, 3]
[1, 2, 3, 1, 3, 3]
[1, 2, 3, 3, 1, 3]
[1, 2, 3, 3, 3, 1]
[1, 3, 1, 2, 3, 3]
[1, 3, 1, 3, 2, 3]
[1, 3, 1, 3, 3, 2]
[1, 3, 2, 1, 3, 3]
[1, 3, 2, 3, 1, 3]
[1, 3, 2, 3, 3, 1]
[1, 3, 3, 1, 2, 3]
[1, 3, 3, 1, 3, 2]
[1, 3, 3, 2, 1, 3]
[1, 3, 3, 2, 3, 1]
[1, 3, 3, 3, 1, 2]
[1, 3, 3, 3, 2, 1]
[2, 1, 1, 3, 3, 3]
[2, 1, 3, 1, 3, 3]
[2, 1, 3, 3, 1, 3]
[2, 1, 3, 3, 3, 1]
[2, 3, 1, 1, 3, 3]
[2, 3, 1, 3, 1, 3]
[2, 3, 1, 3, 3, 1]
[2, 3, 3, 1, 1, 3]
[2, 3, 3, 1, 3, 1]
[2, 3, 3, 3, 1, 1]
[3, 1, 1, 2, 3, 3]
[3, 1, 1, 3, 2, 3]
[3, 1, 1, 3, 3, 2]
[3, 1, 2, 1, 3, 3]
[3, 1, 2, 3, 1, 3]
[3, 1, 2, 3, 3, 1]
[3, 1, 3, 1, 2, 3]
[3, 1, 3, 1, 3, 2]
[3, 1, 3, 2, 1, 3]
[3, 1, 3, 2, 3, 1]
[3, 1, 3, 3, 1, 2]
[3, 1, 3, 3, 2, 1]
[3, 2, 1, 1, 3, 3]
[3, 2, 1, 3, 1, 3]
[3, 2, 1, 3, 3, 1]
[3, 2, 3, 1, 1, 3]
[3, 2, 3, 1, 3, 1]
[3, 2, 3, 3, 1, 1]
[3, 3, 1, 1, 2, 3]
[3, 3, 1, 1, 3, 2]
[3, 3, 1, 2, 1, 3]
[3, 3, 1, 2, 3, 1]
[3, 3, 1, 3, 1, 2]
[3, 3, 1, 3, 2, 1]
[3, 3, 2, 1, 1, 3]
[3, 3, 2, 1, 3, 1]
[3, 3, 2, 3, 1, 1]
[3, 3, 3, 1, 1, 2]
[3, 3, 3, 1, 2, 1]
[3, 3, 3, 2, 1, 1]

Project Euler

2012-01-09T11:58:00.001Z

Project Euler has a good list of interesting puzzles to solve for any language. I worked on a quite a few at one point but haven't for a while until someone mentioned Problem 303

I suggest you try a few if you haven't already Project Euler Problems.

For extra difficulty you can try to make the program shorter, or faster. e.g. My solution to Problem 303 runs in 1.524 seconds solving all values (without guessing) When you solve a problem you can look at how some people solved the problem in different languages which is pretty cool IMHO.

Generic class names to avoid

2012-01-09T09:00:00.001Z

Overview

Java (Oracle Java update 2) has many classes with the same generic name. To avoid further confusion, I suggest avoiding these names if you can.

Most repeated

The following class names are repeated, 19 Handler, 16 Messages, 13 Util, 10 Element, 8 Attribute, 7 SecuritySupport, 7 Node, 6 Provider, 6 Header, 6 FactoryFinder, 6 Document. 5 SOAPBinding, 5 Repository, 5 Ref, 5 ORB, 5 Name, 5 Constants, 5 Connection, 5 Comment, 5 Binding, 5 Attributes,
This excludes the Apache XML library which repeats many names. If you include these libraries there are 26 classes called SecuritySupport.

Four times

Window, Version, Utility, Timer, Text, State, Signature, ServiceName, ServiceConfigurationError, Service, ResourceLoader, Queue, Policy, Parser, Operation, NativeLibLoader, Message, Label, JSObject, GetPropertyAction, FactoryFinder$ConfigurationError, Event, ConstantPool, AppletAudioClip, Action,

Three times

XMLWriter, Wrapper, WildcardTypeImpl, Visitor, Validator, Types, TypeMismatch, TypeInfo, Type, Trace, Token, Timestamp, Target, Symbol, StyleSheet, SOAPFault, SOAPConstants, Scope, Schema, ResourceManager, Resource, Resolver, Request, Reference, Properties, ProgressMonitor, PrincipalImpl, Principal, Port, PooledConnection, Pool, Pipe, Patcher, ParseException, OutputStream, ObjectStreamField, Navigator, NamespaceSupport$Context, NamespaceSupport, MimeType, MemoryCache, MarshalException, Manifest, Main, Location, List, JarVerifier, IOR, Invoker, InvalidName, Introspector, InputStream, Import, ImageCache, HTMLDocument, HTMLCollection, Headers, FinalArrayList, Filter, FileSystem, FactoryImpl, Extension, EventListener, ErrorHandler, Entity, EncryptedPrivateKeyInfo, Delegate, DataSource, CurrentOperations, CurrentHelper, Current, Counter, Context, ContentType, Config, Code, CharacterData, Certificate, CacheTable, Cache, Bridge, Base64, Authenticator, AttributeList, ArrayType, Array, AppletAudioClip$1, Annotation,

Appearing twice

Too many to mention.

String.valueOf(int) vs "" + int

2012-01-05T11:30:00.001Z

Overview

There are a number of reason prefer either

int i = ...
String s = "" + i;
String s = String.valueOf(i);

These include

simplicity
clarity
efficiency
performance

Personally I prefer efficiency for the developer as the performance difference is very, very small. IMHO, "" + i is also simpler and clearer, but that is a matter of taste.

Comparing the performance difference


public static void main(String... args) throws IOException {
    for (int i = 0; i < 3; i++) {
        long svo = perfStringValueOf();
        long qqp = perfQuoteQuotePlus();
        System.out.printf("String.valueOf took an average of %.3f us and \"\"+ took an average of %.3f us%n", svo / 1e3, qqp / 1e3);
    }
}

private static long perfStringValueOf() {
    long start = System.nanoTime();
    final int runs = 100000;
    String s;
    for (int i = 0; i < runs; i++) {
        s = String.valueOf(i * i);
        // ensure s is not optimised away
        if (s.length() < 1) throw new AssertionError();
    }
    long time = System.nanoTime() - start;
    return time / runs;
}

private static long perfQuoteQuotePlus() {
    long start = System.nanoTime();
    final int runs = 100000;
    String s;
    for (int i = 0; i < runs; i++) {
        s = "" + i * i;
        // ensure s is not optimised away
        if (s.length() < 1) throw new AssertionError();
    }
    long time = System.nanoTime() - start;
    return time / runs;
}

prints


String.valueOf took an average of 0.140 us and ""+ took an average of 0.243 us
String.valueOf took an average of 0.063 us and ""+ took an average of 0.058 us
String.valueOf took an average of 0.044 us and ""+ took an average of 0.058 us

This suggest that using String.valueOf will save 0.014 micro-seconds. However, using "" + will save you, the developer far, far more than that in time. (possibly a million times over)

As I have mentioned in previous article, if performance is really critical, you are better off writing the number as text to the direct ByteBuffer which will be written to the device where the text will be going. This creates no objects at all and is clearly OTT for 99% of use cases.

An odd case of initialization

2012-01-04T09:32:00.001Z

Overview

You might assume that once a variable has been initialized it stays that way. However, the javac compiler, treats a variable as initialized only when it can determine a variable has been set, and exception handling can confuse the compiler.

But I know its initialised because I used it

In the following example, a variable is treated as initialized but after a catch block, the compiler isn't sure, and the variable can assigned again and used later.


int a;
try {
    a = 1;
    // a is initialised and can be read.
    System.out.println(a); // compiles ok.
} catch (RuntimeException ignored) {
}
// a is not considered initialised as the compiler 
// doesn't know the catch block couldn't be thrown before a is set.
System.out.println(a); // Variable 'a' might not have been initialized

a = 2;
// a is definitely initialised.
System.out.println(a); // compiles ok.

The problem here is that you know that the variable cannot throw an exception before the variable a is set, but the compiler doesn't know this. The simplest solution is to move the initialization out of the try/catch block.

Note: If you make the variable a final, the second a = 2 gets an error "Variable 'a' might have been initialized"

Java Puzzler, double chars

2012-01-03T10:31:00.000Z

A teaser which uses char and double

The following compiles and produces an output. Can you explain why?


char ch = 'A';
ch *= 1.5;
System.out.println(ch); // prints 'a'

Here is a hint for a simpler example.


byte b = 100;
b /= 2.5;
System.out.println(b); // prints 40

Regex vs IndexOf in Java.

2012-01-02T18:11:00.001Z

Overview

The author of these articles Are C# .Net Regular Expressions Fast Enough for You? and .Net Regex: Can Regular Expression Parsing be Faster than XmlDocument or Linq to Xml? recently pointed out to me that he had found that Regular expressions were at least as fast or faster than the alternatives in C#. However it has been my experience that regular expressions in Java were slower. It is hard for me to say why this might be different in Java and C# or even if these are fair comparisons but here is what I found in Java.

Searching XML for the start of a field

This test searches for the expression "\\s*" in short section of text.


Performing 1 loops, regex took 323.389 us and indexOf took 73.026 us on average, ratio=4.4
Performing 10 loops, regex took 61.513 us and indexOf took 42.480 us on average, ratio=1.4
Performing 100 loops, regex took 84.899 us and indexOf took 8.134 us on average, ratio=10.4
Performing 1,000 loops, regex took 16.307 us and indexOf took 5.851 us on average, ratio=2.8
Performing 10,000 loops, regex took 3.751 us and indexOf took 1.321 us on average, ratio=2.8
Performing 100,000 loops, regex took 3.586 us and indexOf took 1.260 us on average, ratio=2.8

Using indexOf is somewhat faster, but more complex to code. You would only optimise this example if you really needed to as even one million searches takes a fraction of a second.

Code for Search XML example

Searching for a value= expression in a short string

This test search for the {value} in value="{value}" of a short string.


Performing 1 loops, regex took 227.029 us and indexOf took 9.387 us on average, ratio=24.2
Performing 10 loops, regex took 11.141 us and indexOf took 1.195 us on average, ratio=9.3
Performing 100 loops, regex took 9.631 us and indexOf took 1.108 us on average, ratio=8.7
Performing 1,000 loops, regex took 14.993 us and indexOf took 2.491 us on average, ratio=6.0
Performing 10,000 loops, regex took 2.472 us and indexOf took 0.254 us on average, ratio=9.7
Performing 100,000 loops, regex took 0.583 us and indexOf took 0.097 us on average, ratio=6.0
Performing 100,000 loops, regex took 0.465 us and indexOf took 0.032 us on average, ratio=14.5
Performing 100,000 loops, regex took 0.467 us and indexOf took 0.032 us on average, ratio=14.6

Since the times keep improving even after 100K iterations, I suspect the JIT is able to optimise indexOf more than the relatively complex code supporting regular expressions.

Code for Searching a short string example

Happy New Year all

2011-12-31T19:04:00.000Z

Thank you everyone who read my blog, especially those who gave feedback. It encourages me to write me more.

I hope everyone has a Happy New Year.

Using a memory mapped file for a huge matrix

2011-12-30T12:54:00.000Z

Overview

Matrices can be really large, sometimes larger than you can hold in one array. You can extend the maximum size by having multiple arrays however this can make your heap size really large and inefficient. An alternative is to use a wrapper over a memory mapped file. The advantage of memory mapped files is that they have very little impact on the heap and can be swapped in and out by the OS fairly transparently.

A huge matrix

This code supports large matrices of double. It partitions the file into 1 GB mappings. (As Java doesn't support mappings of 2 GB or more at a time, a pet hate of mine ;)


import sun.misc.Cleaner;
import sun.nio.ch.DirectBuffer;

import java.io.Closeable;
import java.io.IOException;
import java.io.RandomAccessFile;
import java.nio.MappedByteBuffer;
import java.nio.channels.FileChannel;
import java.util.ArrayList;
import java.util.List;

public class LargeDoubleMatrix implements Closeable {
    private static final int MAPPING_SIZE = 1 << 30;
    private final RandomAccessFile raf;
    private final int width;
    private final int height;
    private final List mappings = new ArrayList();

    public LargeDoubleMatrix(String filename, int width, int height) throws IOException {
        this.raf = new RandomAccessFile(filename, "rw");
        try {
            this.width = width;
            this.height = height;
            long size = 8L * width * height;
            for (long offset = 0; offset < size; offset += MAPPING_SIZE) {
                long size2 = Math.min(size - offset, MAPPING_SIZE);
                mappings.add(raf.getChannel().map(FileChannel.MapMode.READ_WRITE, offset, size2));
            }
        } catch (IOException e) {
            raf.close();
            throw e;
        }
    }

    protected long position(int x, int y) {
        return (long) y * width + x;
    }

    public int width() {
        return width;
    }

    public int height() {
        return height;
    }

    public double get(int x, int y) {
        assert x >= 0 && x < width;
        assert y >= 0 && y < height;
        long p = position(x, y) * 8;
        int mapN = (int) (p / MAPPING_SIZE);
        int offN = (int) (p % MAPPING_SIZE);
        return mappings.get(mapN).getDouble(offN);
    }

    public void set(int x, int y, double d) {
        assert x >= 0 && x < width;
        assert y >= 0 && y < height;
        long p = position(x, y) * 8;
        int mapN = (int) (p / MAPPING_SIZE);
        int offN = (int) (p % MAPPING_SIZE);
        mappings.get(mapN).putDouble(offN, d);
    }

    public void close() throws IOException {
        for (MappedByteBuffer mapping : mappings)
            clean(mapping);
        raf.close();
    }

    private void clean(MappedByteBuffer mapping) {
        if (mapping == null) return;
        Cleaner cleaner = ((DirectBuffer) mapping).cleaner();
        if (cleaner != null) cleaner.clean();
    }
}

public class LargeDoubleMatrixTest {
    @Test
    public void getSetMatrix() throws IOException {
        long start = System.nanoTime();
        final long used0 = usedMemory();
        LargeDoubleMatrix matrix = new LargeDoubleMatrix("ldm.test", 1000 * 1000, 1000 * 1000);
        for (int i = 0; i < matrix.width(); i++)
            matrix.set(i, i, i);
        for (int i = 0; i < matrix.width(); i++)
            assertEquals(i, matrix.get(i, i), 0.0);
        long time = System.nanoTime() - start;
        final long used = usedMemory() - used0;
        if (used == 0)
            System.err.println("You need to use -XX:-UsedTLAB to see small changes in memory usage.");
        System.out.printf("Setting the diagonal took %,d ms, Heap used is %,d KB%n", time / 1000 / 1000, used / 1024);
        matrix.close();
    }

    private long usedMemory() {
        return Runtime.getRuntime().totalMemory() - Runtime.getRuntime().freeMemory();
    }
}

With the following test, which writes to each of the diagonal values of a one million * one million matrix. This is too large to hope to create on the heap.


Setting the diagonal took 314,819 ms, Heap used is 2,025 KB

$ ls -l ldm.test
-rw-rw-r-- 1 peter peter 8000000000000 2011-12-30 12:42 ldm.test
$ du -s ldm.test 
4010600 ldm.test

That's 8,000,000,000,000 bytes or ~7.3 TB in virtual memory, in a Java process! This works because it only allocates or pages in the pages which you use. So while the file size is almost 8 TB, the actual disk space and memory used is 4 GB.

With a more modest file size of 100K * 100K matrix you see something like the following. Its still an 80 GB matrix, which uses trivial heap space. ;)


Setting the diagonal took 110 ms, Heap used is 71 KB

$ ls -l ldm.test
-rw-rw-r-- 1 peter peter 80000000000 2011-12-30 12:49 ldm.test
$ du -s ldm.test 
400000 ldm.test

Thread Affinity library for Java supports JNA

2011-12-29T11:38:00.001Z

Java Thread Affinity library 1.1

BegemoT has provided same code to allow the Thread Affinity library can use JNA if its available. This means you don't have to have the JNI library.

The latest version is available HERE Click on the ZIP button to download the whole thing as a zip file.

What skills should a Core Java Developer have?

2011-12-27T15:42:00.002Z

Overview

I have been trying to put together a list of basic skills a Java developer should have to move on to being an advanced Core Java programmer.

Skills

You;

can write code on paper which has a good chance of compiling.
can use a debugger to debug programs and profile an application.
are familiar all the primitives types and operators in Java.
understands the class loading process and how class loaders work
can use multiple threads both correctly and can prove this improve performance or behaviour. e.g. wait/notify/notifyAll, SwingUtils.invokeLater, the concurrency library
can use checked exceptions, generics and enums
can time a small benchmark and get reproducible results
can write a very simple client server TCP service
have an understanding of garbage collection, when is it triggered, what can you do to minimise it
understand when to use design patterns such as Singleton, Factory, Fly-weight, Builder, Object Pool, Iterator, Strategy, Visitor, Composite

Suggestions on how to get these skills

read Java Concurrency in Practice (http://jcip.net/)
write a simple client server TCP service such as chat
read up on Design Patterns and try to use them. http://www.oodesign.com/ so you can learn when they help and don't help

Solution: What is this broken code doing

2011-12-22T13:38:00.002Z

Following my earlier blog, here is my solutions to these puzzles.

Loop every second value


List list = new ArrayList<>();
for (int i = 0; i < 10; i++) list.add(i);

for (int i = 0; i < list.size(); i++) {
    System.out.println(list.get(i));
    list.remove(i);
}

When you call remove(i) it shifts all the elements down one AND i++ shifts the index up one. This means, you see every second value.

A work around is as follows.


while(!list.isEmpty) 
    System.out.println(list.remove(0));

Endless loop

This prints all the characters which have value


for(char ch = Character.MIN_VALUE; ch<= Character.MAX_VALUE; ch++) {
    int i = Character.getNumericValue(ch);
    if (i >= 0)
        System.out.println("char "+ch + ' ' + (int) ch+" = "+i);
}

As many realised, this doesn't stop because a char is always less than or equals to the maximum value. (Which is why its called the maximum ;)

Some suggested avoiding this difficult value and have the loop iterate one less. However, another approach is to use a do/while loop which most developers don't use much AFAIK.


char ch = Character.MIN_VALUE;
do {
    int i = Character.getNumericValue(ch);
    if (i < 0) continue;
    System.out.println("char "+ch + ' ' + (int) ch+" = "+i);
} while(ch++ < Character.MAX_VALUE)

The difference is that the check is at the end of the loop instead of the start. This means its stops after ch = MAX_VALUE instead of before it iterates with this value.

What am I waiting for?

This "program" deadlocks. The main method is optional ;)


class Main {
    static int value;
    
    static {
        final Thread t = new Thread() {
            @Override
            public void run() {
                value = 1; // attempts to set Main.value
            }
        };
        t.start();
        System.out.println("Dead locking");
        try {
            t.join();
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
        System.out.println("Released");
    }
}

The problem here is that class initialization is single threaded and implicitly locked. This means another thread cannot use or access the class or its fields or method while another thread is initialising it. Using pseudo-Java it looks like this.


class Main {
    static int value;
    
    static {
      // synchronized(Main.class) {
        final Thread t = new Thread() {
            @Override
            public void run() {
             // deadlocks as the thread initialising Main has not finished.
             // synchronized(Main.class) { 
                value = 1; // attempts to set Main.value
             // }
            }
        };
        t.start();
        System.out.println("Dead locking");
        try {
            t.join();
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
        System.out.println("Released");
      // }
    }
}

What is this broken code doing

2011-12-21T09:22:00.000Z

Overview

Here are some examples of broken code. I find the interesting to understand what they don't do what they appear to.

Can you work out why these don't work? ;)

Loop every second value


List list = new ArrayList<>();
for (int i = 0; i < 10; i++) list.add(i);

for (int i = 0; i < list.size(); i++) {
    System.out.println(list.get(i));
    list.remove(i);
}

prints

Endless loop

This prints all the characters which have value


for(char ch = Character.MIN_VALUE; ch<= Character.MAX_VALUE; ch++) {
    int i = Character.getNumericValue(ch);
    if (i >= 0)
        System.out.println("char "+ch + ' ' + (int) ch+" = "+i);
}

However it doesn't stop. Can you change the code to use a do/while loop so that every char is considered but it does stop? (Without using a larger type)

What am I waiting for?

This "program" deadlocks. The main method is optional ;)


class Main {
    static int value;
    
    static {
        final Thread t = new Thread() {
            @Override
            public void run() {
                value = 1;
            }
        };
        t.start();
        System.out.println("Dead locking");
        try {
            t.join();
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
        System.out.println("Released");
    }
}

Can you see why it deadlocks?

The last two puzzles are based on puzzles from Java Puzzlers by Joshua Bloch and Neal Gafter If you liked these, you will love this book. ;)

Sample Solutions

Solutions: Testing an Anagram of a Palindrome

2011-12-19T18:55:00.000Z

There are many solutions to this problem. However, it is made simpler if you determine the number of letter with an odd number occurrences. As long as the text has no more than 1 odd numbered letter, you can make a palindrome from it.

A straight forward solution


public static boolean isPalindromeAnagram(String text) {
    BitSet bs = new BitSet(27);
    for (int i = 0; i < text.length(); i++) {
        char ch = text.charAt(i);
        if (('A' <= ch && ch <= 'Z') || ('a' <= ch && ch <= 'z'))
            bs.flip(ch % 32);
    }
    return bs.cardinality() <= 1;
}

A trickier solution


public static boolean isPalindromeAnagram(String text) {
    int count = 0;
    for (int i = 0; i < text.length(); i++) {
        char ch = text.charAt(i);
        if (ch + Integer.MIN_VALUE - 'A' <= 'z' + Integer.MIN_VALUE - 'A')
            count ^= 1 << ch;
    }
    return Integer.bitCount(count % (1 << 'z') & ~1) <= 1;
}

synchronized is slower but not worth worrying about

2011-12-15T15:32:00.000Z

Overview

Often developer jump through hoops to avoid synchronization. There are justifications like; the application does lots of writes or reads. Without a clear idea of what "lots" means, they have no idea whether the optimisations they are using will help or just add complexity (and possibly make it slower)

Vector is slower than ArrayList, but that's not a good reason to avoid it

I prefer to use lock free objects and collections in a single threaded context. This is more for clarity than performance. It makes it obvious this code was designed to be single threaded. The performance difference by comparison is often trivial.


public static void main(String... args) throws IOException {
    for (int i = 0; i < 5; i++) {
        perfTest(new ArrayList());
        perfTest(new Vector());
    }
}

private static void perfTest(List objects) {
    long start = System.nanoTime();
    final int runs = 100000000;
    for (int i = 0; i < runs; i += 20) {
        // add items.
        for (int j = 0; j < 20; j+=2)
            objects.add(i);
        // remove from the end.
        while (!objects.isEmpty())
            objects.remove(objects.size() - 1);
    }
    long time = System.nanoTime() - start;
    System.out.printf("%s each add/remove took an average of %.1f ns%n", objects.getClass().getSimpleName(),  (double) time/runs);
}

prints


ArrayList each add/remove took an average of 3.0 ns
Vector each add/remove took an average of 38.5 ns
ArrayList each add/remove took an average of 2.0 ns
Vector each add/remove took an average of 4.4 ns
ArrayList each add/remove took an average of 2.4 ns
Vector each add/remove took an average of 4.6 ns
ArrayList each add/remove took an average of 2.0 ns
Vector each add/remove took an average of 4.6 ns
ArrayList each add/remove took an average of 2.3 ns
Vector each add/remove took an average of 4.5 ns

Using Vector is several times slower, and if all you application does is access the Vector it would make sense to use an ArrayList (and be glad you only have a trivial program to write) For real-world applications, a number of operations are needed and the cost of any one of these is relatively small.

The difference in time is only 2 ns (possibly more on some systems). If you have a task which takes a micro-second (called one million times per second) that operation will take 0.5% slower. If you have an operation which is used only 100,000 times per second, you might find you can't even measure the difference.

In summary, don't worry about performance problems until you have measured the difference you believe it would make. Otherwise you can waste a lot of time "optimising" something which won't make any difference or worse, is slower but you don't know it. (Due to the added complexity in "optimising" the solution)

DZone adds page view summary.

2011-12-13T15:18:00.004Z

DZone have added page views to the summary of articles an individual has posted. My articles on DZone This is interesting to me as the articles which are most popular on blogger and are not the same as those on DZone. (A factor for 2 one way or the other in many cases)

Its is also interesting that the total number of pages views is currently 173K compared with on blogger its 163K page views. (Surprisingly similar)

Java Interview Question; Anagram of a Palindrome

2011-12-13T11:28:00.003Z

Overview

In many interview questions, what they are looking for is a simple solution to an apparently complex problem. Unfortunately, the solutions are usually obvious if you know the solution, but very hard to come up with in an interview situation. ;)

Anagram of Palindrome

Write a method to test if a String is an anagram of a palindrome. The method should have O(n) time complexity and O(1) space complexity. You can assume all letters are between ' ' (space) and 'z'. Assume only letters matter and case is ignored.

e.g.
"kayak"
"Rats live on no evil star"
"A man, a plan, a canal, Panama"
"Doc, note: I dissent. A fast never prevents a fatness. I diet on cod."

The solution

A brute force approach is to generate anagrams and test if they are a palindromes. This is not required. All you need to test is if the String is the sort of string which can be turned into a palindrome.

Sample solution available HERE

Thread Affinity library for Java.

2011-12-13T08:16:00.001Z

Overview

Locking critical thread to a CPU can improve throughput and reduce latency. It can make a big difference to 99%, 99.9% and 99.99%tile latencies.

Unfortunately there is no standard calls in the JDK to do this, so I wrote a simple library so you can manage and see how CPUs have been assigned.

What does it look like running?

In the following example, there are four threads main, reader, writer and engine. The main thread finishes before the engine starts so they end up using the same CPU.


Estimated clock frequency was 3400 MHz
Assigning cpu 7 to Thread[main,5,main]
Assigning cpu 6 to Thread[reader,5,main]
Assigning cpu 3 to Thread[writer,5,main]
Releasing cpu 7 from Thread[main,5,main]
Assigning cpu 7 to Thread[engine,5,main]

The assignment of CPUs is
0: General use CPU
1: General use CPU
2: Reserved for this application
3: Thread[writer,5,main] alive=true
4: General use CPU
5: General use CPU
6: Thread[reader,5,main] alive=true
7: Thread[engine,5,main] alive=true

Releasing cpu 6 from Thread[reader,5,main]
Releasing cpu 3 from Thread[writer,5,main]
Releasing cpu 7 from Thread[engine,5,main]

The code which produces this looks like


public class AffinitySupportMain {
    public static void main(String... args) {
        AffinityLock al = AffinityLock.acquireLock();
        try {
            new Thread(new SleepRunnable(), "reader").start();
            new Thread(new SleepRunnable(), "writer").start();
            new Thread(new SleepRunnable(), "engine").start();
        } finally {
            al.release();
        }
        System.out.println("\nThe assignment of CPUs is\n" + AffinityLock.dumpLocks());
    }

    private static class SleepRunnable implements Runnable {
        public void run() {
            AffinityLock al = AffinityLock.acquireLock();
            try {
                Thread.sleep(1000);
            } catch (InterruptedException e) {
            } finally {
                al.release();
            }
        }
    }
}

This library has been tested on Linux, and I believe it can be adapted to Windows and other OSes.

The Java Thread Affinity Library

Java Puzzle operator confusion

2011-12-07T12:26:00.001Z

Why does this


int _=1, __=2;
int j = __ ^_^ __, k = __-- -+- _ -+- --__;
System.out.println(j + " " + k);

print the following?

1 3

Java puzzle System.exit and locks.

2011-12-06T08:25:00.001Z

When you call System.exit() it will stop the execution of the thread at that point and not call any finally blocks.


private static final Object lock = new Object();

public static void main(String... args) {
    Runtime.getRuntime().addShutdownHook(new Thread(new Runnable() {
        @Override
        public void run() {
            System.out.println("Locking");
            synchronized (lock) {
                System.out.println("Locked");
            }
        }
    }));
    synchronized (lock) {
        System.exit(0);
    }
}

What does this program print?

Replace System.exit(0) with Thread.currentThread().stop() and run again for comparison.

Test a complete failure of the JVM

2011-12-05T14:53:00.001Z

Say you want to test that your application behaves correctly on restart even after the application crashes. One approach is to trigger a crash in test code and check that data is in a correctable state on restart.


Unsafe unsafe = getUnsafe(); // use reflection
unsafe.setMemory(0, 1, (byte) 0);

This triggers a SIGSEGV


#
# A fatal error has been detected by the Java Runtime Environment:
#
#  SIGSEGV (0xb) at pc=0x00000032b967ae09, pid=17870, tid=1082034496
#
# JRE version: 7.0_01-b08
# Java VM: Java HotSpot(TM) 64-Bit Server VM (21.1-b02 mixed mode linux-amd64 compressed oops)
# Problematic frame:
# C  [libc.so.6+0x7ae09]  memset+0x9
#

If your tests still pass, you can be reasonably confident it is recoverable even on a complete failure of the JVM.

For the code for getUnsafe().

Warning: This class is appropriately named and misuse can result in a crash of the JVM. It can also change in future versions (It is more likely new methods will be added rather than removed)


public static Unsafe getUnsafe() {
    try {
        Field field = Unsafe.class.getDeclaredField("theUnsafe");
        field.setAccessible(true);
        return (Unsafe) field.get(null);
    } catch (Exception e) {
        throw new AssertionError(e);
    }
}

Java puzzle, low latency queue

2011-11-28T20:45:00.001Z

There a number of ways to use queues. A simple and very fast queue is to use AtomicReference. (It stores 0 or 1 element)

1. Write a producer and consumer thread which communicates via an AtomicReference. [Click for sample solution]

Took an average of 48 ns per object


public class Main {
    public static void main(String... args) throws InterruptedException {
        AtomicReference<Long> queue = new AtomicReference<Long>();
        final Consumer<Long> consumer = new Consumer<Long>(queue);
        Thread t = new Thread(new Runnable() {
            @Override
            public void run() {
                while(consumer.take() >= 0);
            }
        });
        t.start();

        Producer<Long> producer = new Producer<Long>(queue);

        long start = System.nanoTime();
        int runs = 10*1000*1000;
        for(long i=0;i<runs;i++)
            producer.push(i);
        producer.push(-1L); // poison pill
        t.join();
        long time = System.nanoTime() - start;
        System.out.printf("Took an average of %,d ns per object%n", time/runs);
    }
}

class Producer<T> {
    final AtomicReference<T> queue;

    public Producer(AtomicReference<T> queue) {
        this.queue = queue;
    }

    public void push(T l) {
        while (!queue.compareAndSet(null, l)) ;
    }
}

class Consumer<T> {
    final AtomicReference<T> queue;

    public Consumer(AtomicReference<T> queue) {
        this.queue = queue;
    }

    public T take() {
        T t;
        do {
            t = queue.getAndSet(null);
        } while(t == null);
        return t;
    }
}

2. Have the consumer send messages back to the producer using another AtomicReference. [left as an exercise]
The average round trip time taken was 156 ns if you have one message at a time, or 98 ns if you have two messages at a time.

3. Time the throughput for one second repeatedly. What variation do you see?

4. Pad the AtomicReference to make sure they are at least 64 bytes apart in memory and measure again.

Low Latency Slides

2011-11-28T18:45:00.001Z

Last weekend was LJC Open Conference #4, and like many people I got a lot out of it.

My talk was up first which meant I could relax for the rest of the day.

Here are the slides

Note: the message size was 16 longs or 128 bytes. This makes a difference at higher throughputs.

In answer to @aix's questions

On slide 12; what are we measuring here, elapsed time from the message hitting the buffer to the "echo" reply showing up on the client socket?

In each message I add a timestamp as it is written. When each message is read, I compare the timestamp with the current time. I sort the results and take the middle / 50%tile as typical timings and the worst 0.01% as the 99.99%tile.

What's causing the large difference between "nanoTime(), Normal" and "RDTSC, Normal" in the bottom half of the slide (2M/s)?

The reason for taking the RDTSC directly (9 ns) is that System.nanoTime() is quite slow on Centos 5.7 (180 ns) and the later is a system calls which may disturb the cache. At modest message rate 200K/s (one message every 5000 ns) the difference is minor however as the message rates increase 2M/s (one message every 500 ns) the addition to latency is significant. Its not possible to send messages over 5 M/s if I was using System.nanoTime() where as with RDTSC I got up to 12 M/s. Without timing each message, I got a throughput of 17 M/s.In answer to @Matt's questions

Is that a safe way to call tsc on a multicore machine? Is it consistent across cores?

Calling RDTSC on a multi-core system is safe as there is one counter per socket. However, calling TSC on a multi-socket system is not safe and there will be difference and possibly a drift between sockets.

This is not a problem if you have only one socket, or you do all you timing on one socket. e.g. You have used thread affinity and know the timings will all be on the same socket.

Don't you need some sort of serialisation in the instruction stream to avoid out of order behaviour?

This is a potential problem. However, the total time taken with JNI is around 9 ns which is more than 40 instructions. This is longer than the CPU pipeline can re-order. (typically around 32 instructions) If this instruction were embedded the way the some Unsafe methods are, it could be re-ordered with Java instruction. However, provided this re-ordering is not random, the difference is likely to be a bias of << 10 ns. If the re-ordering was random this could add up to 10 ns jitter.

Given I am timing latencies to an accuracy of 100 ns, I decided it wasn't a problem for me. It could be a problem if you want 10 ns accuracy.

On the "reproducible results" theme, to be completely anal you need to repeat the test n times (20-30?) and examine the distribution of results.

What I do is repeatedly run the test for 5 seconds and print the results. This will consist of a minimum of one million individual messages. This is repeated 30 times and I print an aggregate distribution. I compare the individual distributions with the aggregate to see if they are "close".

I will try to document how the test are done in more detail when I am happy with the reproducibility of the 99.99%tile values. :|

Ever decreasing cost of main memory

2011-11-25T08:47:00.001Z

I have blogged about the relative cost of memory to the cost of your time. Memory in servers is so cheap that for small amounts of memory, it just isn't worth your time to introduce complexity into your application to try to save it.

The average salary for a developer in the UK is £40,000 and the average cost of memory is £5 per GB. The cost to your organisation for both is higher and if you have many machines saving a 1 MB on 1000 machines saves 1 GB, however memory is so divisible you can quickly run into small amounts of memory which are not worth your time saving.

Hard disk space is even cheaper and most people get its not worth keeping your disks completely clean all the time, because the cost of deleting a file you later need is high, but also the value of the space you save is not worth your time. A typical 2 TB of mirrored disk in a network appliance costs about £300.

Your time	Main memory to save in total	Disk space to save
Blink of an eye (20 ms)	20 KB	1.7 MB
One second	1 MB	33 MB
One line of tested code (2 mins)	120 MB	3.5 GB
A small sized well tested library, 100 lines (0.5 days)	14 GB	500 GB
A medium sized well tested, documented library, 1000 lines (1 week)	140 GB	5 TB

For self learning, interest or fun you might think about ways of saving small amounts of memory or disk. But for work, the most efficient way to program may be to save your time and those who have to maintain your code, and waste some hardware resources in the process. BTW: hardware resources are more re-usable than your time.

Stupid performance trick in Java

2011-11-23T10:54:00.001Z

ByteBuffer has a compact() method which is useful for re-using a buffer if it is not full consumed. However, in the likely case it is consumed, it can perform surprising badly.


while (in.read(buf) >= 0 || buf.position != 0) {
     buf.flip();
     out.write(buf);
     buf.compact();    // In case of partial write
}

In my application, the throughput increased by 6% by replacing compact() with this method.


public static void compact(ByteBuffer bb) {
    if (bb.remaining() == 0)
        bb.clear();
    else
        bb.compact();
}

Note: this is not the increase in a micro-benchmark, but across the entire application!

Your Mileage May Vary of course

Java puzzle (Single threaded client server)

2011-11-22T08:39:00.001Z

Without creating additional threads, create a ServerSocket on a random unused port, a client Socket connecting to localhost and a server Socket.

Part 1) Send messages from client to server and back again. (This can be useful in unit tests)[Click for sample solution]


ServerSocket ss = new ServerSocket(0);
Socket c = new Socket("localhost", ss.getLocalPort());
Socket s= ss.accept();
ss.close();
// sends one byte.
c.getOutputStream().write(1);
int num = s.getInputStream().read();
s.getOutputStream().write(num+1);
int num2 = c.getInputStream().read();

s.close();
c.close();

Part 2) Do the same with blocking NIO.[Click for sample solution]


ServerSocketChannel ss = ServerSocketChannel.open();
ss.socket().bind(new InetSocketAddress(0));
SocketChannel c = SocketChannel.open(new InetSocketAddress("localhost", ss.socket().getLocalPort()));
SocketChannel s = ss.accept();
ss.close();
// sends one byte.
ByteBuffer bb1 = ByteBuffer.allocateDirect(1);
c.write(bb1);
// read one byte.
ByteBuffer bb2 = ByteBuffer.allocateDirect(1);
int num = s.read(bb2);

// sends it back.
bb2.flip();
s.write(bb2);

// reads one byte.
bb1.clear();
c.read(bb1);

s.close();
c.close();

Part 3) Benchmark how many GB/s per second you can transfer this way.[Click for sample solution]


ServerSocketChannel ss = ServerSocketChannel.open();
ss.socket().bind(new InetSocketAddress(0));
SocketChannel c = SocketChannel.open(new InetSocketAddress("localhost", ss.socket().getLocalPort()));
SocketChannel s = ss.accept();
ss.close();

final int bufferSize = 64 * 1024;
final int runs = 10000;

for (int j = 0; j < 3; j++) {
    ByteBuffer bb1 = ByteBuffer.allocateDirect(bufferSize);
    ByteBuffer bb2 = ByteBuffer.allocateDirect(bufferSize);
    long start = System.nanoTime();
    for (int i = 0; i < runs; i++) {
// sends one buffer.
        bb1.clear();
        c.write(bb1);
// read one buffer.
        bb2.clear();
        int num = s.read(bb2);

// sends it back.
        bb2.flip();
        s.write(bb2);

// reads one byte.
        bb1.clear();
        c.read(bb1);
    }
    long time = System.nanoTime() - start;
    long rate = (long) (1e9 * bufferSize * runs / time / 1e6);
    System.out.println("Transfer rate " + rate + " MB/s");
}

s.close();
c.close();

Prints on my machine


Transfer rate 1963 MB/s
Transfer rate 2330 MB/s
Transfer rate 2365 MB/s

Part 4) Measure the typical and 99.99% round trip latency, and estimate how much garbage is produced.

For bonus points try the same with Async NIO2 in Java 7.

I will add a solution Nov 29th (after a week)

Java puzzle (Sum of even Fibonacci numbers)

2011-11-22T08:22:00.001Z

Write a function which calculates the sum of even Fibonacci numbers.


public static void main(String... args) {
    for(int i=1;i<22;i++)
        System.out.print(sumEvenFibonacci(i) + " ");
}

public static long sumEvenFibonacci(int n) {
    // add code here.
    return sum;
}

prints


0 0 2 2 2 10 10 10 44 44 44 188 188 188 798 798 798 3382 3382 3382 14328

For bonus points, optimise the sumEvenFibonacci method so it contains only one condition and doesn't test for even or odd.

[Click for sample solution]


public static long sumEvenFibonacci(int n) {
  long a = 1, b = 1, sum = 0;
  for (int i = n; i > 2; i -= 3) {
    long c = a + b;
    sum += c;
    a = b + c;
    b = a + c;
  }
  return sum;
}

How arbitary is the start of System.nanoTime()?

2011-11-21T09:42:00.001Z

System.nanoTime() is defined as having an arbitrary start time. However, there is no reason to make it random and it is based on an unspecified system call. On Centos 5.7 and other Linuxes I have tried, this appears to be based on the uptime.


System.out.println("/proc/uptime    " + new Scanner(new FileInputStream("/proc/uptime")).next());
System.out.println("System.nanoTime " + System.nanoTime() / 1e9);

prints


/proc/uptime    265671.85
System.nanoTime 265671.854834206

Why Concurrency examples are confusing

2011-11-07T11:04:00.000Z

Overview

I was recently at a talk were the audience was asked who used concurrency and who found it confusing. Nearly all who use concurrency found it confusing.

This was a little surprising to me, and I was left wondering what the reason might be.

I have been thinking about writing a book, so I have been watching a number of web talks and reading a number of books which talk about concurrency and I think I know at least one reason.

Bad Examples

The problem is; in a talk or a book you need a simple, easily understood example. Unfortunately, simple and easily understood examples almost always make very BAD examples for concurrency.

What makes them bad examples is that concurrency code comes with an overhead both to the developer in terms of complexity of the code and in CPU performance. Simple examples are likely to have far more overhead than the work done making the performance of the concurrent example far worse than just writing it single threaded and also the code more confusing.

Account transfer example

A common example used to illustrate how to avoid dead lock between two objects, is the account transfer problem. The problem is that to transfer between two accounts, you must lock both accounts (assuming you lock individual accounts). However, unless you lock them in the same order, you can get a deadlock where two threads hold the one of the accounts the other thread needs.


Took an average of 30.7 ns to transfer money with a lock on each Account.

Using synchronized improves performance synchronized is marginally faster for un-contended locks. (i.e. the same threadkeep acquiring the lock)


Took an average of 28.9 ns to transfer money with a lock on each Account.

This is the speed of using a thread safe account with one thread. In theory, this should scale very well and using two threads would halve this time. You might get good scalability up to the number of cores you have.

But the awkward question is, what if we didn't have one lock per account and just had one global lock. The code would be simpler, but not as scalable. But what is the cost of scalability?

What if I used just one global lock


Took an average of 9.7 ns to transfer money with a one global lock.

This means we would need to have at least 7 threads trying to transfer money to be as fast as using one global lock. (Assuming we achieved the theoretically best scalability) Given a real application has a lot other things to do, it is highly unlikely that you will average more than 7 thread in this section of code.

What if I just make the code single threaded?


Took an average of 1.8 ns to transfer money, single threaded

This implies that we need to average over 56 cores (not just threads) in the account transfer block of code, to break even. In this unlikely scenario, I would suggest you need to rethink your application. e.g. if you are working for an Uber-Bank performing one billion transfers per second, why are you using just one machine to do it?

A Really Bad Example

A pet hate of mine is using the Fibonacci series in examples of concurrency. This example has the advantage of being easy to define recursively and translate the code to being concurrent. It also an amazingly, staggeringly BAD idea.

This is run on a 4.6 GHz i7 2600K with 16 GB of memory. The code stops when there isn't enough resources to start any more threads.


Fibonacci 2 was 2, took 1,665 us, Time ratio=832.5 
Fibonacci 3 was 3, took 123 us, Time ratio=41.0 
Fibonacci 4 was 5, took 126 us, Time ratio=25.2 
Fibonacci 5 was 8, took 154 us, Time ratio=19.3 
Fibonacci 6 was 13, took 291 us, Time ratio=22.4 
Fibonacci 7 was 21, took 359 us, Time ratio=17.1 
Fibonacci 8 was 34, took 646 us, Time ratio=19.0 
Fibonacci 9 was 55, took 544 us, Time ratio=9.9 
Fibonacci 10 was 89, took 471 us, Time ratio=5.3 
Fibonacci 11 was 144, took 1,417 us, Time ratio=9.8 
Fibonacci 12 was 233, took 3,516 us, Time ratio=15.1 
Fibonacci 13 was 377, took 3,120 us, Time ratio=8.3 
Fibonacci 14 was 610, took 2,143 us, Time ratio=3.5 
Fibonacci 15 was 987, took 7,949 us, Time ratio=8.1 
Fibonacci 16 was 1,597, took 17,539 us, Time ratio=11.0 
Fibonacci 17 was 2,584, took 7,639 us, Time ratio=3.0 
Fibonacci 18 was 4,181, took 28,766 us, Time ratio=6.9 
Fibonacci 19 was 6,765, took 28,838 us, Time ratio=4.3 
Fibonacci 20 was 10,946, took 18,460 us, Time ratio=1.7 
Fibonacci 21 was 17,711, took 85,533 us, Time ratio=4.8 
Fibonacci 22 was 28,657, took 67,250 us, Time ratio=2.3 
Fibonacci 23 was 46,368, took 194,481 us, Time ratio=4.2 
Fibonacci 24 was 75,025, took 122,891 us, Time ratio=1.6 
Fibonacci 25 was 121,393, took 283,110 us, Time ratio=2.3 
Fibonacci 26 was 196,418, took 403,611 us, Time ratio=2.1 
Fibonacci 27 was 317,811, took 2,476,695 us, Time ratio=7.8 
Fibonacci 28 was 514,229, took 7,661,490 us, Time ratio=14.9 
Exception in thread "main" java.lang.AssertionError: java.util.concurrent.ExecutionException: java.lang.AssertionError: java.util.concurrent.ExecutionException: java.lang.AssertionError: java.util.concurrent.ExecutionException: java.lang.AssertionError: java.util.concurrent.ExecutionException: java.lang.OutOfMemoryError: unable to create new native thread

The time ratio is the ratio of the time taken in micro-seconds and the solution. This is interesting because the time taken is proportional to the final value, something which rises exponentially. Unfortunately it also consumes more resources, exponentially.

Now compare this with the single threaded looping solution with -XX:+PrintCompilation turned on.


     30    1             java.lang.String::hashCode (67 bytes)
     36    2             sun.nio.cs.UTF_8$Encoder::encode (361 bytes)
Fibonacci 2 was 2, took 1 us
Fibonacci 3 was 3, took 1 us
Fibonacci 4 was 5, took 1 us
Fibonacci 5 was 8, took 1 us
Fibonacci 6 was 13, took 1 us
Fibonacci 7 was 21, took 1 us
Fibonacci 8 was 34, took 0 us
Fibonacci 9 was 55, took 0 us
Fibonacci 10 was 89, took 1 us
Fibonacci 11 was 144, took 1 us
Fibonacci 12 was 233, took 1 us
Fibonacci 13 was 377, took 1 us
Fibonacci 14 was 610, took      42    3             java.lang.String::indexOf (87 bytes)
1 us
Fibonacci 15 was 987, took 1 us
Fibonacci 16 was 1,597, took 1 us
Fibonacci 17 was 2,584, took 0 us
     42    4             java.lang.String::charAt (33 bytes)
Fibonacci 18 was 4,181, took 1 us
Fibonacci 19 was 6,765, took 1 us
Fibonacci 20 was 10,946, took 1 us
Fibonacci 21 was 17,711, took 1 us
Fibonacci 22 was 28,657, took 1 us
Fibonacci 23 was 46,368, took 1 us
Fibonacci 24 was 75,025, took 1 us
Fibonacci 25 was 121,393, took 0 us
Fibonacci 26 was 196,418, took 1 us
Fibonacci 27 was 317,811, took 1 us
Fibonacci 28 was 514,229, took 1 us
Fibonacci 29 was 832,040, took 1 us
Fibonacci 30 was 1,346,269, took 0 us
Fibonacci 31 was 2,178,309, took 1 us
Fibonacci 32 was 3,524,578, took 1 us
Fibonacci 33 was 5,702,887, took 1 us
Fibonacci 34 was 9,227,465, took 1 us
Fibonacci 35 was 14,930,352, took 1 us
Fibonacci 36 was 24,157,817, took 0 us
Fibonacci 37 was 39,088,169, took 1 us
Fibonacci 38 was 63,245,986, took 1 us
Fibonacci 39 was 102,334,155, took 1 us
Fibonacci 40 was 165,580,141, took 3 us
Fibonacci 41 was 267,914,296, took 0 us
Fibonacci 42 was 433,494,437, took 1 us
Fibonacci 43 was 701,408,733, took 1 us
Fibonacci 44 was 1,134,903,170, took 1 us
Fibonacci 45 was 1,836,311,903, took 1 us
Fibonacci 46 was 2,971,215,073, took 1 us
Fibonacci 47 was 4,807,526,976, took 1 us
Fibonacci 48 was 7,778,742,049, took 1 us
Fibonacci 49 was 12,586,269,025, took 1 us
Fibonacci 50 was 20,365,011,074, took 1 us
Fibonacci 51 was 32,951,280,099, took 1 us
Fibonacci 52 was 53,316,291,173, took 1 us
Fibonacci 53 was 86,267,571,272, took 1 us
Fibonacci 54 was 139,583,862,445, took 1 us
Fibonacci 55 was 225,851,433,717, took 1 us
Fibonacci 56 was 365,435,296,162, took 1 us
Fibonacci 57 was 591,286,729,879, took 1 us
Fibonacci 58 was 956,722,026,041, took 1 us
Fibonacci 59 was 1,548,008,755,920, took 1 us
Fibonacci 60 was 2,504,730,781,961, took 1 us
Fibonacci 61 was 4,052,739,537,881, took 1 us
Fibonacci 62 was 6,557,470,319,842, took 2 us
Fibonacci 63 was 10,610,209,857,723, took 2 us
Fibonacci 64 was 17,167,680,177,565, took 2 us
Fibonacci 65 was 27,777,890,035,288, took 1 us
Fibonacci 66 was 44,945,570,212,853, took 1 us
Fibonacci 67 was 72,723,460,248,141, took 1 us
Fibonacci 68 was 117,669,030,460,994, took 2 us
Fibonacci 69 was 190,392,490,709,135, took 2 us
Fibonacci 70 was 308,061,521,170,129, took 1 us
Fibonacci 71 was 498,454,011,879,264, took 1 us
Fibonacci 72 was 806,515,533,049,393, took 1 us
Fibonacci 73 was 1,304,969,544,928,657, took 1 us
Fibonacci 74 was 2,111,485,077,978,050, took 1 us
Fibonacci 75 was 3,416,454,622,906,707, took 1 us
Fibonacci 76 was 5,527,939,700,884,757, took 1 us
Fibonacci      49    5             java.util.regex.Matcher::77reset (83 bytes)
 was 8,944,394,323,791,464, took 1 us
Fibonacci 78 was 14,472,334,024,676,221, took 1 us
Fibonacci 79 was 23,416,728,348,467,685, took 1 us
Fibonacci 80 was 37,889,062,373,143,906, took 2 us
Fibonacci 81 was 61,305,790,721,611,591, took 3 us
Fibonacci 82 was 99,194,853,094,755,497, took 2 us
Fibonacci 83 was 160,500,643,816,367,088, took 1 us
Fibonacci 84 was 259,695,496,911,122,585, took 2 us
Fibonacci 85 was 420,196,140,727,489,673, took 2 us
Fibonacci 86 was 679,891,637,638,612,258, took 1 us
Fibonacci 87 was 1,100,087,778,366,101,931, took 2 us
Fibonacci 88 was 1,779,979,416,004,714,189, took 2 us
Fibonacci 89 was 2,880,067,194,370,816,120, took 1 us
Fibonacci 90 was 4,660,046,610,375,530,309, took 1 us
Fibonacci 91 was 7,540,113,804,746,346,429, took 2 us

Note: the method calculating Fibonacci values is not even compiled and is still running in the relatively slow interpreter.Yet it barely uses more than 2 micro-seconds. When compiled to native code it takes around 40 nano-seconds.

If the multi-threaded Fibonacci took 2 micro-second per result value, implying "Fibonacci 91" might take around 180 million years. Unfortunately, the number of threads required is also proportional to the result value, requiring in the order of a trillion trillion threads.

Conclusion

When considering multi-threading a section of an application, you should take a single threaded, lock free implementation as a base line. If you can't make the multi-threaded, thread safe implementation faster, don't make it multi-threaded.

Put another way, if you are using concurrency to improve performance, make sure you are dealing with a problem which can be made concurrent and a solution which is faster than using one thread.

The Code

For Accounts, look at the ThreadedAccountMain, ThreadedAccountLockMain, ThreadedAccountOneLockMain and UnthreadedAccountMain.

For Fibonaccii, look at the ThreadedFibonacciMain and UnthreadedFibonacciMain

Threads code

I would like to thank Roger Lindsjö for his suggestions on DZone.

Recycling objects to improve performance

2011-10-30T12:06:00.000Z

Overview

In a previous article I stated that the reason the deserialisation of objects was faster was due to using recycled objects. This is potentially surprising for two reasons, 1) the belief that creating objects is so fast these days, it doesn't matter or is just as fast as recycling yourself, 2) None of the serialisation libraries use recycling by default.

This article explores deserialisation with and without recycling objects. How it not only is slower to create objects, but it slows down the rest of your program by pushing data out of your CPU caches.

While this talks about deserialisaton, the same applies to parsing text or reading binary files, as the actions being performed are the same.

The test

In this test, I deserialise 1000 Price objects, but also time how long it takes to copy a block of data. The copy represents work which the application might have to perform after deserialising.

The test is timed one million times and those results sorted. The X-Axis shows the percentile timing. e.g. the 90% values is the 90% worst value. (or 10% of values are higher)

As you can see, the deserialisation take longer if it has to create objects as it goes, however sometimes it takes much much long. This is perhaps not so surprising as creating objects means doing more work and possibly being delayed by a GC. However, it is the increase in the time to copy a block of data which is surprising. This demonstrates that not only is the deserialisation slower, but any work which needs the data cache is also slower as a result. (Which is just about anything you might do in a real application)
Performances tests rarely show you the impact on the rest of your application.

In more detail

Examining the higher percentile (longest times) you can see that the performance consistently bad if the deserialisation has to wait for the GC.

And the performance of the copy increases significantly in the worst case.

The code

Recycling example code

Serialization using ByteBuffer and recycled objects

2011-10-27T14:51:00.000+01:00

Overview

I have always been of the view that using recycled objects is faster for serialization.

So I wrote a test based on Thrift Protobuf Compare to see where it does well or poorly.

The benchmark suggest that serialization/deserialization is fast with ByteBuffer and recycled objects, but creating new objects is relatively expensive.

This suggests that provided you have a simple strategy for reusing objects, it may be worth using this approach. However, if you can't recycle objects I suspect it won't be worth the extra effort.

Total Serailization time

All results

Note: the creation time for a recyclable object is much higher, but the serialization/deserialization times are much better.


Starting
                        ,   Object create,       Serialize,  /w Same Object,     Deserialize, and Check Media,   and Check All,      Total Time, Serialized Size
ByteBuffer-specific     ,       154.98000,       242.50000,       303.00000,       132.00000,       132.00000,       132.00000,       374.50000,        213
avro-generic            ,       791.64500,      1675.00000,      1024.00000,       890.00000,       890.00000,       890.00000,      2565.00000,        211
avro-specific           ,       460.89500,      1089.00000,       756.50000,      1055.00000,      1055.00000,      1055.00000,      2144.00000,        211
activemq protobuf       ,        49.61000,      1203.50000,       186.00000,         7.00000,       612.50000,       934.00000,      2137.50000,        231
protobuf                ,        61.55500,      1130.50000,       762.50000,       579.00000,       797.00000,       839.50000,      1970.00000,        231
thrift                  ,        62.97000,      1401.00000,      1502.00000,      1530.00000,      1530.00000,      1530.00000,      2931.00000,        353
hessian                 ,        34.69000,      3208.00000,      3186.00000,      5597.00000,      5597.00000,      5597.00000,      8805.00000,        526
kryo                    ,        35.33000,       988.50000,      1132.50000,       957.00000,       957.00000,       957.00000,      1945.50000,        226
kryo-optimized          ,        36.00000,       887.50000,      1051.00000,       915.00000,       915.00000,       915.00000,      1802.50000,        207
MessagePack (buggy)     ,        34.93000,       873.50000,       960.00000,       674.00000,       674.00000,       674.00000,      1547.50000,        216
java                    ,        38.50000,      5012.50000,      4705.50000,     23918.50000,     23918.50000,     23918.50000,     28931.00000,        919
java (externalizable)   ,        38.99000,       707.00000,       839.50000,       610.00000,       610.00000,       610.00000,      1317.00000,        264
scala                   ,        33.98000,     11184.50000,     10630.50000,     63917.00000,     63917.00000,     63917.00000,     75101.50000,       2024
json (jackson)          ,        37.69000,      1934.50000,      2196.00000,      1738.00000,      1738.00000,      1738.00000,      3672.50000,        378
json/jackson-databind   ,        38.55500,      8888.00000,      9277.00000,      9537.50000,      9537.50000,      9537.50000,     18425.50000,       1815
JsonMarshaller          ,        40.04500,      4856.00000,      5127.00000,      8456.00000,      8456.00000,      8456.00000,     13312.00000,        370
protostuff-json         ,        67.91000,      2153.00000,      2361.00000,      2139.00000,      2139.00000,      2139.00000,      4292.00000,        448
protostuff-numeric-json ,        65.95000,      2171.00000,      2220.50000,      2188.50000,      2188.50000,      2188.50000,      4359.50000,        359
json/google-gson        ,        40.13000,    102987.00000,    103714.00000,    123158.00000,    123158.00000,    123158.00000,    226145.00000,        470
stax/woodstox           ,        39.84500,      2357.50000,      2651.00000,      3576.50000,      3576.50000,      3576.50000,      5934.00000,        475
stax/aalto              ,        37.01500,      2008.50000,      2220.00000,      3104.50000,      3104.50000,      3104.50000,      5113.00000,        475
binaryxml/FI            ,        40.43000,      5322.00000,      5639.50000,      5092.50000,      5092.50000,      5092.50000,     10414.50000,        300
xstream (stax with conv),        41.80500,      4512.50000,      4276.50000,      8374.50000,      8374.50000,      8374.50000,     12887.00000,        399
javolution xmlformat    ,        36.89000,      3197.00000,      3309.00000,      3769.00000,      3769.00000,      3769.00000,      6966.00000,        419
sbinary                 ,        33.50000,      1510.00000,      1690.00000,       972.00000,       972.00000,       972.00000,      2482.00000,        264

The main advantage over Java Externalizable is the option to re-use objects rather than create them each time. There is also a small advantage in being able to read/write a long as a single native read/write instead or 8 bytes with bit shift operations. (Similar for int)

The Code

Note: You have to write more code yourself if you are going to use ByteBuffers, but not much more than custom Java Externalisable. The main shift of thinking required is creating recycleable structures. In a multi-threaded context this ia made additionally difficult, however if you use these with care or model you application as a series of independant single threaded processes, this doesn't have to be a problem.

ByteBuffers are builtin to Java so no additional library is required to use them, however a small number of helper methods are useful.

Using ByteBuffers for serialization can also improve IO performance as the data is in the "C" space already. A byte[] is not required.

ByteBuffer serialization example code

Serialization benchmarks and charts

2011-10-27T09:24:00.000+01:00

I was looking at this serialization benchmark Thrift Protobuf Compare and saw at the end oif the report it spits out a series of HTML. One of these reads.

Which when displays looks like.

A simple way to generate charts in web pages.

BTW: The application was run using Java 7 update 1 64-bit on an i7 2600K 4.6 GHz.

Strine translator

2011-10-26T13:58:00.002+01:00

Translating to Strine ;)


    public static void main(String... args) {
        System.out.println("Hello World");
    }

    static {
        try {
            Field value = String.class.getDeclaredField("value");
            value.setAccessible(true);
            value.set("Hello World", value.get("G'Day Mate."));
        } catch (Exception e) {
            throw new AssertionError(e);
        }
    }

prints


G'Day Mate.

BTW: Strine is the Australian Dialect of English.

Randomly not so random

2011-10-26T13:25:00.001+01:00

In a random sequence, all sequences are equally likely, even not so random ones.


    Random random = new Random(441287210);
    for(int i=0;i<10;i++)
        System.out.print(random.nextInt(10)+" ");
    }

prints


1 1 1 1 1 1 1 1 1 1

and


    Random random = new Random(-6732303926L);
    for(int i=0;i<10;i++)
        System.out.println(random.nextInt(10)+" ");
    }

prints


0 1 2 3 4 5 6 7 8 9

Lastly


public static void main(String ... args) {
    System.out.println(randomString(-229985452)+' '+randomString(-147909649));
}

public static String randomString(int seed) {
    Random rand = new Random(seed);
    StringBuilder sb = new StringBuilder();
    for(int i=0;;i++) {
        int n = rand.nextInt(27);
        if (n == 0) break;
        sb.append((char) ('`' + n));
    }
    return sb.toString();
}

prints


hello world

Java plus

2011-10-26T11:36:00.003+01:00

A confusing piece of code here for you to parse. ;)


int i = (byte) + (char) - (int) + (long) - 1;
System.out.println(i);

prints

Later discussed on Stack Overflow here.

HugeCollections moved to github

2011-09-26T13:05:00.001+01:00

HugeCollections has been moved to github. to support easier forking and collaboration.

https://github.com/HugeCollections/Collections

Its a pain to setup, but once that is done it makes working on the code and merging changes much easier.

New Contributors to HugeCollections

2011-09-20T08:53:00.001+01:00

What is the HugeCollection library

The objectives of HugeCollections for the first release are fairly ambitious.

Scale to massive collections i.e. sizes much larger than 2 billion without significant heap foot print or GC impact. i.e. using heap-less memory
Be faster and more efficient that using plain JavaBeans with an ArrayList or Map and a vector or unordered_map in C++.
Support durability (transparently saved and loaded from disk)
Support thread safety (with no overhead if not required) and using multiple threads implicitly. i.e. large operations are automatically distributed.
Be faster and more efficient than using a database. Transactions will NOT be in this release.
Support in one application what might have to be distributed otherwise.
Dynamic code generation as required (no need to pre-generate code in the build)

A prototype has been built which shows these objectives are possible, however to turn this library in to a usable release, will take some help.

Note: I am open to people working on the things they find most interesting, even if this means some areas are more developed than others.

To have a look at the code start with http://vanilla-java.googlecode.com/svn/sandbox/ which you can also checkout.

Myself

Peter Lawrey - I have been working with Java for 12 years and on high performance systems for 15 years. I have worked at Investment Banks, a prop trading firm and Sun Microsystems.

Two new contributors

Rob Austin currently contracting for a large investment bank, working on a low latency pricing and trading platform. Over 10 years of Java experience.

Costantino Cerbo is a certified Java developer (SCJP and SCBCD) and software consultant with more than 6 years experience. He has worked for one of the Italy's largest banks. He is an Italian native speaker, fluent in German and strong in English (TOEFL: 607 points).

More contributors welcome

I am looking for additional contributors to....
- document the high level approach used and its advantages.
- proper documentation and pier review of the design.
- code review of the hand coded collections for list and hash map (These are templates for the auto-generated classes)- tool to assist the conversion of the template into the code generation.
- Test cases for correct functionality.
- Performance and scalability tests.
- Comparison tests for performance and scalability.
- a comparison with the features of similar products like ehCache BigMemory, javolution, trove4j (also find other products worth comparing) and C++.

- Documentation and blog of the comparison.
- Examine thread safety support and tests.
- Auto multi-threading for filter() and visit() methods.
- Examine integration and examples of use in JVM languages like Scala, Groovy, Jython, JRuby and see what support can be given. i.e. are there simple things which can be done to make it simpler/more natural to use.
- Produce a JTable GUI demo with one billion rows.

Later
- Add queue/dispatcher support.
- Add sorted index (a la TreeMap or map in C++) support.
- Add non-unique indexes.
- Simple remote support. RMI/RPC
- Distributed copies of data and partitioning.

Any suggestions welcome.

My email

You can contact me as peter.lawrey on gmail.

Forum for ideas

2011-09-17T15:53:00.000+01:00

Someone recently asked me if had a forum to include suggestions for articles to add.

Does anyone have

a forum to work well with blogger.
suggestions for articles.

Please comment with your ideas.

The Exchanger and GC-less Java

2011-09-12T17:37:00.001+01:00

Overview

The Exchanger class is very efficient at passing work between thread and recycling the objects used. AFAIK, It is also one of the least used Concurrency classes.
As @Marksim Sipos points out, if you don't need GC less logging using an ArrayBlockingQueue is much simpler.

Exchanger class

The Exchanger class is useful for passing data back and forth between two threads. e.g. Producer/Consumer. It has the property of naturally recycling the data structures used to pass the work and supports GC-less sharing of work in an efficient manner.
Here is an example, passing logs to a background logger.
Work (a log entry) is batched into LogEntries and passed to a background thread which later passes it back to the thread so it can add more work. Provided the background thread is always finished before the batch is full, it is almost transparent. Increasing the size of the batch reduces how often the batch is full but increase the number of unprocessed entries waiting at any one time. Calling flush() can push out the data.
The key line is the following which exchanges the batch in the current thread with the batch in the other thread. The producer fills up the batch while the consumer is emptying it.
The exchange when it occurs typically takes 1-4 micro-seconds. In this case, once every 64 lines.

entries = logEntriesExchanger.exchange(entries);

How does this compare to the LMAX disruptor pattern

This approach has similar principles to the Disruptor. No GC using recycled, pre-allocated buffers and lock free operations (The Exchanger not completely lock free and doesn't busy wait, but it could)
Two keys difference are:

there is only one producer/consumer in this case, the disruptor supports multiple consumers.
this approach re-uses a much smaller buffer efficiently. If you are using ByteBuffer (as I have in the past) an optimal size might be 32 KB. The disruptor library was designed to exploit large amounts of memory on the assumption it is relative cheap and can use medium sized (MBs) to very large buffers (GBs). e.g. it was design for servers with 144 GB. I am sure it works well on much smaller servers. ;)

Thank you @Doug, for reminding me to mention the Disruptor pattern.

If you have dozen logs files (for different purposes) and you want to minimise memory foot print and you prefer the consuming thread to be blocking rather than busy waiting which consumes 100% of a thread (which adds a small latency of up to 10 us) then the Exchanger is better suited.

Exchanger example

import java.util.concurrent.Exchanger;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;

public class BackgroundLogger implements Runnable {
  static final int ENTRIES = 64;

  static class LogEntry {
    long time;
    int level;
    final StringBuilder text = new StringBuilder();
  }

  static class LogEntries {
    final LogEntry[] lines = new LogEntry[ENTRIES];
    int used = 0;
  }

  private final ExecutorService executor = Executors.newSingleThreadExecutor();
  final Exchanger<LogEntries> logEntriesExchanger = new Exchanger<LogEntries>();
  LogEntries entries = new LogEntries();

  BackgroundLogger() {
    executor.submit(this);
  }

  public StringBuilder log(int level) {
    try {
      if (entries.used == ENTRIES)
        entries = logEntriesExchanger.exchange(entries);
      LogEntry le = entries.lines[entries.used++];
      le.time = System.currentTimeMillis();
      le.level = level;
      return le.text;

    } catch (InterruptedException e) {
      throw new RuntimeException(e);
    }
  }

  public void flush() throws InterruptedException {
    if(entries.used > 0)
        entries = logEntriesExchanger.exchange(entries);
  }

  public void stop() {
    try {
      flush();
    } catch (InterruptedException e) {
      e.printStackTrace(); // use standard logging.
    }
    executor.shutdownNow();
  }

  @Override
  public void run() {
    LogEntries entries = new LogEntries();
    try {
      while (!Thread.interrupted()) {
        entries = logEntriesExchanger.exchange(entries);
            for (int i = 0; i < entries.used; i++) {
              bgLog(entries.lines[i]);
              entries.lines[i].text.delete(0, entries.lines[i].text.length());
        }
        entries.used = 0;
      }
    } catch (InterruptedException ignored) {

    } finally {
      System.out.println("Warn: logger stopping."); // use standard logging.
    }
  }

  private void bgLog(LogEntry line) {
    // log the entry to a file.
  }
}

Is making Boost more like Java a good idea?

2011-09-12T12:54:00.000+01:00

Overview

I was reading a question StackOverflow about What is Boost missing? and I was wondering how many of these features are available in Java already and whether making boost more like Java is good idea.

Top suggestions

Suggestion	What is in Java
SQL support	JDBC
JSon	Requires an additional library like XStream, Possibly should be in core Java
Audio	Java has basic support. Don't know if it much good.
logging	Logger
callstack, a standard API	Throwable.getStackTrace() and Thread.getStackTrace()
Support for archives	Support ZIP and JAR
Redeveloped collections	The same could be said for Java Collections
Standard XML parsing for UTF-8 text	SAX (event driven) and DOM (Document object model) parsers for XML
Platform independent GUI	Swing
Concurrency with lock free collections and atomic operations	Concurrency library
Arbitrary precision floating point and decimal	BigDecimal and BigInteger
Python, Ruby and Lua support	Not built in, but there is Jython, JRuby and LuaJava
High performance (sub micro-second) timers	System.nanoTime()
Better concept support	This looks like staticly defined duck typing and Java is a long way from having anything like this. ;)
Atomic	AtomicBoolean, AtomicInteger, AtomicLong, AtomicReference, AtomicIntegerArray and AtomicLongArray
Thread pools	ExecutorService and ScheduledExecutorService
RPC	RMI
Character encoding	CharSet
GPU support	I would love Java to have this as well. There is JoCL but its not exactly transparent or close to the Write One, Run Anywhere model.
Hashing/Checksums	MessageDigest and CRC32
OS performance measures	This is poor in Java. You can get the load average but its always 0 on windows.
Co-routines	The closest is fork/join with anonymous classes. In Java 8 methods will become first class objects which is a little closer.
Fixed size strings	You can have this in Java. However I assume the point of this is efficiency, which Java is unlikely to match, ever.
Message Queues	JMS
cryptography	Java SE Security
Extend GC to trigger a GC and handle when an object is cleaned up.	System.gc(), finaliser() and PhantomReferences
A overflow/underflow safe integer	This would be useful if language support was included, but I doubt that will happen, (like unsigned int)
unification and backtracking	This could be added in the far future. I imagine after Java 8
Singletons	An enum with one instance (enum are Objects in Java not int values)
A Persistent Collections Library.	Java doesn't have much support for functional programming. This is something which it could have, but I don't imagine it being any time soon.

IMHO, The best suggestions which are missing or could be better in Java are

persisted collections
JSon serializaton/deserialization
GPU support
Good OS performance measures

Even more useful would be a common interface and basic support for collections which are distributed and persisted. e.g. standardised/simplified Hazelcast, Terracotta and Hibernate. @Vyadh points out this is not what is meant by a persisted collection in functional programming

Last thoughts

While I really like Java, but I have never looked at C++ & Boost and thought; if only it were more like Java. (Some of the limitations of the C syntax are a bit backward IMHO) I have thought this about the refactoring tools in IDEs e.g extracting a method from a body of code (and have it replace any duplicates)

Is making C++ & Boost more like the relatively heavy weight Java a good thing? Or is it better to use a language for it strengths?

Memory alignment in C, C++ and Java

2011-09-10T11:41:00.000+01:00

Overview

You might assume that reducing the size of a struct or class saves the same amount of memory. However due to memory alignment in memory allocators it can make no difference, or perhaps more difference than you might expect. This is because the the amount of memory reserved is usually a multiple of the memory alignment. For Java and C this can 8 or 16 bytes.

Size of memory reserved

These tests were performed in a 64-bit C program (gcc 4.5.2) and a 64 JVM (Oracle Java 7) In Java, direct memory is largely a wrapper for malloc and free.

Bytes	C malloc() reserved	Java ByteBuffer.allocateDirect()
0 to 24	32 bytes	32 bytes + a ByteBuffer
25 to 40	48 bytes	48 bytes + a ByteBuffer
41 to 56	64 bytes	64 bytes + a ByteBuffer
57 to 72	80 bytes	80 bytes + a ByteBuffer

Constructing objects is a similar story

Number of fields	C class of int (heap/stack)	C class of void * (heap/stack)	Java class with int	Java class with Object references
1	32/16 bytes	32/16 bytes	16 bytes	16 bytes
2	32/16 bytes	32/16 bytes	24 bytes	24 bytes
3	32/16 bytes	32/32 bytes	24 bytes	24 bytes
4	32/16 bytes	48/32 bytes	32 bytes	32 bytes
5	32/32 bytes	48/48 bytes	32 bytes	32 bytes
6	32/32 bytes	64/48 bytes	40 bytes	40 bytes
7	48/32 bytes	64/64 bytes	40 bytes	40 bytes
8	48/32 bytes	80/64 bytes	48 bytes	48 bytes

Using a C struct/class on the stack is more efficient than the other approaches for a number of reasons, two of them being that there is no memory management header and no additional pointer/reference (not shown in the table).

Sun/Oracle and OpenJDK 6 and 7 JVMs will use 32-bit references and the 8 byte memory aligned and to support up to 32 GB (8 * 4 G) Most JVMs are less than 32 GB in size making this a useful optimisation. Note: Part of the reason that JVMs are usually 1 to 4 GB in size is that the worst case Full GC time is typically 1 second per GB of heap and a 30 second full CG time is to long for most applications. The typical way around this full GC time problem is to keep the working size of the heap to a few GB and use an external database or heapless "direct" and "memory mapped" memory.

Another solution for Java is to use a pause less concurrent collector such as that provided by Azul. They claim excellent scalability beyond 40 GB of heap, but don't openly list their costs ;)

Why does this matter?

Say you have a class like this


class MyClass {
    int num;
    short value;
}

In C, how much memory is saved by changing num to a short or how much more is consumed of with make it long long. The answer is likely to be none at all (unless you have an array of these)In Java, it could make a difference as the alignment size is different.Conversely, if the C class/struct is 16 or 17 bytes, it can make the size on the stack be 16 or 32 bytes. Similarly being 24 or 25 bytes can make the malloc'ed size used 32 or 48 bytes long.

The code

MemoryAlignment/main.cpp and MemoryAlignment.java

Why thread priority rarely matters

2011-09-08T18:33:00.002+01:00

Overview

Its is tempting to use the Thread.setPriority() option in Java. However for many applications this is more a comment for the developer than something which will make a measurable difference. esp. with multi-core systems.

Why it usually doesn't matter

If you have plenty of free CPU, every thread which can run will run. The OS has no reason not to run a low priority thread or process when it has free resources.

If your system is close to 100% of CPU on every core, the OS has to make a choice as to how much time each thread or process gets on the CPU and it is likely to give favour to higher priority threads over lower priority threads, (many OSes ignore the hint) and other factors are likely to matter as well.

This priority only extends to raw CPU. Threads compete equally for CPU cache, heap space, CPU to memory bandwidth, file cache, disk IO, network IO and everything else. If any of these resource are in competition, they are all equal.

To set a high priority on Windows you need to be an administrator and on Linux you need to be root to set the priority of a thread. Different Implementations and OSes can ignore this hint.

Summary

If your application is heavily CPU bound, using every core, not using any other system resources significantly like IO or memory and your OS doesn't ignore the hint, the thread priority might make a difference.

If in doubt, I wouldn't bother setting it because someone might think it does something. ;)

Order of elements in a hash collection

2011-09-07T14:26:00.002+01:00

Overview

While is it generally understood that keys or elements in a HashMap or HashSet occur in a pseudo random order, what is not obvious is that two collections with the same elements can be in different orders. This is because the capacity of the collection also determines the order the elements appear.

This can be important if you have only an Iterator to a Set. It is easy to assume the order will be the same and most of the time it will work (you can write unit tests with this assumption which will pass) However, if the Set has a different capacity (something you don't normally know or worry about) the order will change.

Find what order elements can appear in

The following test adds the same 11 elements to a HashSet, each time with a different collection and prints out all the combinations it finds.


@Test
public void testSetOrder() {
  Set<String> order = new HashSet<String>();
  Collection<String> elements = Arrays.asList(
                     "zero, one, two, three, four, five, six, seven, eight, nine, ten".split(", "));

  try {
  for(int i=1;i > 0;i*=2) {
    Set set = new HashSet<String>(i, 100.0f);
    set.addAll(elements);
    String str = set.toString();
    if (order.add(str))
      System.out.println("HashSet("+i+") order was "+str);
  }
  } catch(OutOfMemoryError ignored) { }
}

prints this output


HashSet(1) order was [ten, nine, eight, seven, six, five, four, three, two, one, zero]
HashSet(2) order was [eight, three, zero, ten, nine, seven, six, five, four, two, one]
HashSet(4) order was [three, zero, ten, two, eight, nine, seven, six, five, four, one]
HashSet(8) order was [three, ten, two, seven, five, four, zero, eight, nine, six, one]
HashSet(16) order was [ten, two, seven, five, nine, one, three, four, zero, eight, six]
HashSet(32) order was [ten, five, nine, one, zero, eight, six, two, seven, three, four]
HashSet(64) order was [ten, nine, one, zero, eight, six, three, four, five, two, seven]
HashSet(128) order was [ten, nine, zero, eight, three, one, six, four, five, two, seven]
HashSet(256) order was [nine, zero, six, ten, eight, three, one, four, five, two, seven]
HashSet(512) order was [six, four, five, seven, nine, zero, ten, eight, three, one, two]
HashSet(1024) order was [six, five, nine, eight, two, four, seven, zero, ten, three, one]
HashSet(2048) order was [eight, seven, zero, six, five, nine, two, four, ten, three, one]
HashSet(4096) order was [eight, seven, zero, six, five, nine, three, one, two, four, ten]
HashSet(8192) order was [eight, seven, zero, six, nine, four, five, three, one, two, ten]
HashSet(16384) order was [eight, zero, nine, five, three, two, ten, seven, six, four, one]
HashSet(32768) order was [zero, six, one, eight, nine, five, three, two, ten, seven, four]
HashSet(65536) order was [zero, eight, five, seven, four, six, one, nine, three, two, ten]
HashSet(131072) order was [nine, zero, eight, five, seven, four, six, one, three, two, ten]
HashSet(262144) order was [nine, five, seven, six, one, two, ten, zero, eight, four, three]
HashSet(524288) order was [nine, seven, six, one, two, ten, zero, four, five, eight, three]
HashSet(1048576) order was [nine, seven, six, one, two, ten, four, eight, three, zero, five]
HashSet(2097152) order was [seven, six, one, two, ten, five, nine, four, eight, three, zero]
HashSet(4194304) order was [six, one, two, ten, eight, seven, five, nine, four, three, zero]
HashSet(8388608) order was [six, one, two, ten, eight, five, nine, four, zero, seven, three]
HashSet(16777216) order was [six, one, two, ten, five, nine, four, zero, eight, seven, three]
HashSet(33554432) order was [six, one, two, ten, five, nine, four, zero, seven, three, eight]

As you can see almost every initial capacity has a different order (even for a relatively small number of elements)

Single note: with a capacity of 1 and a large load factor (to prevent it resizing the capacity), the HashSet becomes a linked list which shows object in reverse order. i.e. as there is 100% collisions.

As @Alex Zhang, notes, if you have small positive numbers (Byte, Short, Integer, Long) and you allow the capacity to grow naturally, you will get those numbers in order. However if you vary this a little the pattern breaks up.


Collection<Integer> col = Arrays.asList(-1, 1, 10, 100, 1000, 10000, 100000, 1000000);
for (int i = 1; i < 5000000; i *= 2) {
    Set<Integer> set = new HashSet<Integer>(i, 100f);
    set.addAll(col);
    System.out.println("HashSet(" + i + ") " + set);
}

prints


HashSet(1) [1000000, 100000, 10000, 1000, 100, 10, 1, -1]
HashSet(2) [1000000, 100000, 100, 10, 10000, 1000, 1, -1]
HashSet(4) [10000, 1000, 1, 1000000, 100000, 100, 10, -1]
HashSet(8) [1000, 1, 1000000, 100, 10, 10000, 100000, -1]
HashSet(16) [1000, 1, 100, 1000000, 10, 10000, 100000, -1]
HashSet(32) [1, 100, 10, 10000, 1000, 1000000, 100000, -1]
HashSet(64) [1, 10, 1000, 1000000, 100000, -1, 100, 10000]
HashSet(128) [1, 10, 1000000, -1, 10000, 1000, 100000, 100]
HashSet(256) [1, 10, 1000000, -1, 10000, 100, 1000, 100000]
HashSet(512) [1, 10, 1000000, 100, -1, 10000, 1000, 100000]
HashSet(1024) [1, 10, 1000000, 100, 10000, 100000, -1, 1000]
HashSet(2048) [1, 10, 1000000, 100, 1000, 10000, 100000, -1]
HashSet(4096) [1, 10, 100, 1000, 10000, 1000000, 100000, -1]
HashSet(8192) [1, 10, 100, 1000, 10000, 1000000, -1, 100000]
HashSet(16384) [1, 10, 100, 1000, 100000, 10000, 1000000, -1]
HashSet(32768) [1, 10, 100, 1000, 100000, 10000, 1000000, -1]
HashSet(65536) [1, 10, 100, 1000, 10000, 100000, 1000000, -1]
HashSet(131072) [1, 10, 100, 1000, 10000, -1, 100000, 1000000]
HashSet(262144) [1, 10, 100, 1000, 10000, -1, 100000, 1000000]
HashSet(524288) [1, 10, 100, 1000, 10000, -1, 100000, 1000000]
HashSet(1048576) [1, 10, 100, 1000, 10000, -1, 100000, 1000000]
HashSet(2097152) [1, 10, 100, 1000, 10000, 100000, 1000000, -1]
HashSet(4194304) [1, 10, 100, 1000, 10000, 100000, 1000000, -1]

The Code

The importance of innovation

2011-09-02T10:33:00.000+01:00

Overview

In a recent article I wrote about how you do things can make a big difference. Java can be significantly faster than C

The aim was to show how you can use the same algorithm (the what), implemented with a different approach (the how) and make significant improvement in performance.

What I have learnt

I now understand that the purpose of the web site is compare languages and remove the developer from the equation by making "the how" as similar to what has been written before as possible. I see this is legitimate approach to have a fair comparison of languages.

The Importance of Innovation

To me it shows you what can happen when you deliberately limit innovation, even if you have good reasons to do so. If you prescribe one way of implementing a requirement, it can make a big difference to the solution you can achieve.

In the case of this benchmark, following the requirements as closely as I could, but admittedly disregarding how these requirements had been achieved before resulted in a solution which was 2.2x faster than the previous C solutions and 4.6x faster than the previous Java solution.

Java can be significantly faster than C

2011-08-31T21:19:00.007+01:00

Preface

When I wrote this article it was to comment on how writing the same algorithm implement a different way can make a major difference. I now believe this is not the point of the web site perhaps shouldn't be the point of this article either. I have written a follow up article.

The importance of innovation

Overview

Whether you use Java or C is not always as important as the approach you use. By "approach" I mean; algorithms not specified in the requirements or "the how" to do something.

You might not see this as a fair test of Java vs C, but in the real world human factors are matter. There is no point saying C is faster in theory but there isn't anyone available to make it so. Its like getting a very cheap price on an item which is not in stock. ;)

Benchmark Shootout

Java is temporarily the fastest for this particular knucleotide benchmark. It is quite likely that if the algorithm I used is translated to C it would be faster again. But for the moment Java is fastest because it uses a different approach in a number of key places.

Benchmark results at Wed 31st August 2011.

If anyone is interested in translating it to C, I would like to know how much faster it is. ;)

Making it faster again

On my home PC it only takes 0.684 ms, a gain of 2.5x. My PC uses newer hardware (and an over clocked CPU)

The code

MethodHandle performance in Java 7

2011-08-30T16:49:00.001+01:00

Overview

A new feature in Java 7 provides a MethodHandle which "is a typed, directly executable reference to an underlying method, constructor, field, or similar low-level operation, with optional transformations of arguments or return values"

This supports currying methods and many other features lambda based languages take for granted.

Note: this method compares invoke() in reflections and MethodHandles. I couldn't get invokeExact to work when returning a primitive (it got confused between int and Integer) However another benchmark Using Method Handles by Andrew Till indicated using invokeExact is much faster than using Method.invoke() with reflections.Thank you wensveen for the link.

Example

Say you have two method

public static int multiply(int i, int j) {
    return i * j;
}

public static int subtract(int i, int j) {
    return i - j;
}

With MethodHandle you can not only get a reference to the Method (like in reflection) but you can construct new MethodHandles. For example, you can bind the Object concerned or one of the arguments.

final Lookup lookup = lookup();
MethodHandle multiply = lookup.findStatic(MethodHandleMain.class, 
                          "multiply", methodType(int.class, int.class, int.class));
MethodHandle quadruple = insertArguments(multiply, 1, 4);

System.out.println(multiply.invoke(3, 2)); // prints 6
System.out.println(quadruple.invoke(5)); // prints 20

MethodHandle subtract = lookup.findStatic(MethodHandleMain.class, 
                         "subtract", methodType(int.class, int.class, int.class));
MethodHandle subtractFromFour = insertArguments(subtract, 0, 4);
MethodHandle fourLess = insertArguments(subtract, 1, 4);
System.out.println(subtract.invoke(10, 5)); // prints 5
System.out.println(subtractFromFour.invoke(10)); // prints -6
System.out.println(fourLess.invoke(10)); // prints 6

Performance

This is very cool, but how does it perform? ;)

There is a lot of potential for it to perform very well and the interface is cleaner than plain reflections however when comparing the alternatives, it doesn't perform as well as the alternatives in Java 7 (update 0)

Call method	Average time per call
Direct Method calls	31 ns
Reflections	353 ns
MethodHandle.invoke()	5,378 ns

It is a very cool API and hopefully it will perform much better in the future. ;)

The code

MethodHandleTest.java

Added Memory Mapped support to HugeCollections

2011-08-30T14:00:00.005+01:00

Overview

The Huge collections library is designed to support large collections on data in memory efficiently without GC impact. It does this using heap less memory and generated code for efficiency.

One of the benefits of this approach is memory mapped files can be larger than the available memory, use trivial heap and no direct memory.

Memory mapping

Loading large amounts of data is time consuming so being able to re-use a store persisted to disk can improve efficiency. With the use of SSD drives the amount of "memory" a Java system can access is effectively extended provided it can be used.

How does it perform

Adding an object with 12 fields and reading objects sequentially takes about 110 ns for one billion elements. It takes less than two minutes to add all the entries, and the same to read all the elements.

Random access is much more expensive until all the data is in memory, with a fast SSD drive it takes about 600 ns when most of the data is in cache, slower if this is not the case.

Java has a collection with one billion elements. (Top)

As you can see the machine has only 24 GB and yet it the Java process is using 37.6G of virtual memory as this includes 33 GB of mapped files. The actual memory used is 3.4 GB as this is how much is kept in memory.

The shared memory is the same as the memory mapped files can be shared with other processes (however writing to them in a safe manner is not supported)

Creating the huge collection

Like previous huge collections, an anonymous sub-class of the builder is used to create the collection. The baseDirectory is the base directory of where the list is stored.

HugeArrayList list = new HugeArrayBuilder() {{

    baseDirectory = TEMPORARY_SPACE;

    capacity = length;

    allocationSize = 32 * 1024 * 1024;

}}.create();



// update or lookup the collection

list.add(...);



MutableType mt = list.get(900*1000*1000);



// close to flush the data, close files and un-map the collection.

list.close();

Links

Wiki
Downloads
Unit Tests and examples

To follow

Support for a Huge Map with one index under development. Additional non-unique indexes also planned.

Writing to stdin

2011-08-28T18:08:00.001+01:00

Overview

System.in or stdin is usually used as an InputStream. However on Linux you can access this stream in other ways.

Accessing file descriptor 0

In linux, each file descriptor is accessible via /proc/{process-id}/fd/{file-id} You can use this to see what files a process has open but also see the contents of a file.

Writing and memory mapping

Getting the process id in Java is obscure, but once you have this you can re-open existing file descriptors such as stdin, file descriptor 0.

int processId = Integer.parseInt(ManagementFactory.getRuntimeMXBean().getName().split("@")[0]);

RandomAccessFile raf = new RandomAccessFile("/proc/" + processId + "/fd/0", "rw");

final FileChannel fc = raf.getChannel();

final MappedByteBuffer bb = fc.map(FileChannel.MapMode.READ_WRITE, 0, fc.size());

bb.putLong(System.nanoTime());

bb.force();

raf.close();

This opens the System.in is a read-write mode and memory maps it before changing its contents.

When you run this program it looks like

$ echo "        " > file.dat

$ od -xc file.dat

0000000    2020    2020    2020    2020    000a

                                         \n

0000011

$ java -cp . Main < file.dat

$ od -xc file.dat

0000000    0000    5522    11a9    79c6    000a

         \0  \0   "   U 251 021 306   y  \n

0000011

At first is rather surprising you can write to stdin or even memory map it. What happens if stdin is not a real file.

$ echo "        " | java -cp . Main

Exception in thread "main" java.io.FileNotFoundException: /proc/7935/fd/0 (Text file busy)

	at java.io.RandomAccessFile.open(Native Method)

	at java.io.RandomAccessFile.(RandomAccessFile.java:233)

	at java.io.RandomAccessFile.(RandomAccessFile.java:118)

	at Main.main(Main.java:10)

Avoiding Java Serialization to increase performance

2011-08-18T12:07:00.011+01:00

Overview

Many frameworks for storing objects in an off-line or cached manner, use standard Java Serialization to encode the object as bytes which can be turned back into the original object.

Java Serialization is generic and can serialise just about any type of object.

Why avoid it

The main problem with Java Serialization is performance and efficiency. Java serialization is much slower than using in memory stores and tends to significantly expand the size of the object. Java Serialization also creates a lot of garbage.

Access performance

Say you have a collection and you want to update a field of many elements. Something like

for (MutableTypes mt : mts) {

   mt.setInt(mt.getInt());

}

If you update one million elements for about five seconds how long does each one take.

Collection	Fast PC	Labtop
Huge Collection	5.1 ns	33 ns
List<JavaBean>	6.5 ns	54 ns
List<byte[]> with Externalizable	5,841 ns	17,508 ns
List<byte[]> with Serializable	23,217 ns	60,947 ns

If you update ten million elements for five seconds or more

Collection	Fast PC	Labtop
Huge Collection	5.4 ns	33 ns
List<JavaBean>	6.6 ns	60 ns
List<byte[]> with Externalizable	6,073 ns	71,691 ns
List<byte[]> with Serializable	22,943 ns	failed

* Fast PC - 3.8 GHz i7 with 24 GB of memory.
* Labtop - 2.3 GHz Core Duo with 4 GB of memory.

Huge Collection stores information in a column based based, so accessing just one field is much more CPU cache efficient than using JavaBeans. If you were to update every field, it would be about 2x or more times slower.

Using an optimised Externalizable is much faster than the default Serializable, however is it 400x slower than using a a JavaBean

Memory efficiency

The per object memory used is also important as it impacts how many object you can store and the performance of accessing those objects.

Collection type	Heap used per million	Direct memory per million	Garbage produced per million
Huge Collection	0.09 MB	34 MB	80 bytes
List<JavaBean>	68 MB	none	30 bytes
List<byte[]> using Externalizable	140 MB	none	5,941 MB
List<byte[]>	506 MB	none	16,746 MB

This test was performed on a collection of one million elements.

To test the amount of garbage produced I set the Eden size target greater than 17 GB so no GC would be performed.

-mx22g -XX:NewSize=20g -XX:-UseTLAB -verbosegc

Conclusion

Having an optimised readExternal/writeExternal can improve performance and the size of a serialised object by 2-4 times, however if you need to maximise performance and efficiency you can gain much more by not using it.

Generating ASCII Banners

2011-08-18T10:06:00.000+01:00

Overview

Generating ASCII banners can be tedious. However there is a simple short cut, use an image to display the text.

Creating an invisible image

You don't have to have a GUI to create images. The following code creates an image in memory without a GUI.

BufferedImage image = new BufferedImage(144, 32, BufferedImage.TYPE_INT_RGB);

Graphics g = image.getGraphics();

g.setFont(new Font("Dialog", Font.PLAIN, 24));

Graphics2D graphics = (Graphics2D) g;

graphics.setRenderingHint(RenderingHints.KEY_TEXT_ANTIALIASING,

        RenderingHints.VALUE_TEXT_ANTIALIAS_ON);

graphics.drawString("Hello World!", 6, 24);

ImageIO.write(image, "png", new File("text.png"));



for (int y = 0; y < 32; y++) {

    StringBuilder sb = new StringBuilder();

    for (int x = 0; x < 144; x++)

        sb.append(image.getRGB(x, y) == -16777216 ? " " : image.getRGB(x, y) == -1 ? "#" : "*");

    if (sb.toString().trim().isEmpty()) continue;

    System.out.println(sb);

}

it display the image

By scanning this image you can create text like.

##         ##                 ##    ##                      *#*      *##**      *#*                       ##            ##     ##       

##         ##                 ##    ##                      *#*      *###*      *#*                       ##            ##     ##       

##         ##                 ##    ##                      *#*      *#*#*      *#*                       ##            ##     ##       

##         ##                 ##    ##                      *#*     *******     *#*                       ##            ##     ##       

##         ##     *******     ##    ##     *******           *#*    *#* *#*    *#*    *******     ##****  ##     ****** ##     ##       

##         ##    **#####**    ##    ##    **#####**          *#*    *#* *#*    *#*   **#####**    ##*##*  ##    **#####*##     ##       

##         ##   **#*****#**   ##    ##   **#** **#**         *#*   **#* *#*    *#*  **#** **#**   ##****  ##   **#** ***##     ##       

#############   *#*     *#*   ##    ##   *#*     *#*         *#*   *#*   *#*   *#*  *#*     *#*   ##*     ##   *#*     *##     ##       

#############   *#*     *#*   ##    ##   *#*     *#*         ****  *#*   *#*  ****  *#*     *#*   ##*     ##   *#*     *##     ##       

##         ##   *#########*   ##    ##   *#*     *#*          *#*  *#*   *#*  *#*   *#*     *#*   ##      ##   *#*     *##     ##       

##         ##   *#########*   ##    ##   *#       #*          *#* *#*     *#* *#*   *#       #*   ##      ##   *#       ##     ##       

##         ##   *#*           ##    ##   *#*     *#*          *#* *#*     *#* *#*   *#*     *#*   ##      ##   *#*     *##     ##       

##         ##   *#*           ##    ##   *#*     *#*          *****#*     *#*****   *#*     *#*   ##      ##   *#*     *##     ##       

##         ##   *#*     *#*   ##    ##   *#*     *#*           *#*#*       *#*#*    *#*     *#*   ##      ##   *#*     *##              

##         ##   **#** *****   ##    ##   **#** **#**           *#*#*       *#*#*    **#** **#**   ##      ##   **#** ***##              

##         ##    **######*    ##    ##    **#####**            *###*       *###*     **#####**    ##      ##    **#####*##     ##       

##         ##     *******     ##    ##     *******             *##**       **##*      *******     ##      ##     ****** ##     ##

change to BOLD

###       ###                 ###    ###                        *##*     *###*     *##*                          ###            ###    #

###       ###                 ###    ###                        *##*     *###*     *##*                          ###            ###    #

###       ###                 ###    ###                        *##*     *###*     *##*                          ###            ###    #

###       ###                 ###    ###                        **##*   **###**   *##**                          ###            ###    #

###       ###     *******     ###    ###      *******            *##*   *##*##*   *##*     *******      ###****  ###     ****** ###    *

###       ###    **#####**    ###    ###    **#######**          *##*   *##*##*   *##*   **#######**    ###*##*  ###    **#####*###    *

###       ###   **#######**   ###    ###    *#########*          *##**  *#* *#*  **#**   *#########*    #####**  ###   **##########    *

#############   *##** **##*   ###    ###   *###** **###*          *##* *##* *##* *##*   *###** **###*   ###**    ###   *##******###    *

#############   *##*   *##*   ###    ###   *##*     *##*          *##* *##* *##* *##*   *##*     *##*   ###*     ###   *##*    *###    *

#############   *#########*   ###    ###   *##*     *##*          *##* *##* **#* *##*   *##*     *##*   ###*     ###   *##*    *###    *

###       ###   *#########*   ###    ###   ###       ##*           *##*##*   *#**##*    ###       ##*   ###*     ###   *##      ###    *

###       ###   *##*          ###    ###   *##*     *##*           *##*##*   *##*##*    *##*     *##*   ###      ###   *##*    *###    *

###       ###   *##*          ###    ###   *##*     *##*           *#####*   *#####*    *##*     *##*   ###      ###   *##*    *###    *

###       ###   *##*****##*   ###    ###   *###** **###*           **###**    *###**    *###** **###*   ###      ###   *##******###     

###       ###   **########*   ###    ###    *#########*             *###*     *###*      *#########*    ###      ###   **##########    #

###       ###    **######*    ###    ###    **#######**             *###*     *###*      **#######**    ###      ###    **#####*###    #

###       ###     *******     ###    ###      *******               *###*     *###*        *******      ###      ###     *******###    #

in ITALIC

*#*        *#*                *#*   *#*                      *#*       *##*      **#*                      *#*          *#*  *#*      

   *#*        *#*                *#*   *#*                      *#*      *###*      *#*                       *#*          *#*  *#*      

   *#*        *#*                *#*   *#*                      *#*      *###*     **#*                       *#*          *#*  *#*      

   *#*        *#*                *#*   *#*                      *#*     *#**#*     *#*                        *#*          *#*  *#*      

  ****       *#*    *******     ****  ****   *******            *#*     *#**#*    ****   *******    *#* **#* ****   ********#*  *#*      

  *#*        *#*   **######*    *#*   *#*   **######*           *#*    *#***#*    *#*   **######*   *#**###* *#*   **####**#**  **       

  *#*        *#*  **#******#*   *#*   *#*  **#******#*          *#*   **#* *#*   ****  **#******#*  *#****   *#*  *##** **##*  *#*       

  *############* **#*     *#*   *#*   *#* **#*     *#*          *#*   *#*  *#*   *#*  **#*     *#*  *#**     *#* **#*    **#*  *#*       

 **###########** *#*       #*  ****  **** *#*      *#*          *#*  **#*  *#*  ****  *#*      *#* **#*     **** *#*      *#*  *#*       

 *#*        *#*  *##########*  *#*   *#*  *#*       #*          *#*  *#*   *#*  *#*   *#*       #* *#**     *#*  *#*      *#*  **        

 *#*        *#*  *##########*  *#*   *#*  *#*      *#*          *#* ****   *#* *#**   *#*      *#* *#*      *#*  *#*      *#*  **        

 *#*        *#*  *#            *#*   *#*  *#       *#*          *#* *#*    *#* *#*    *#       *#* *#*      *#*  *#      ***   **        

 *#*        *#*  *#*           *#*   *#*  *#*     **#*          *#**#**    *#**#**    *#*     **#* *#*      *#*  *#*     *#*   **        

*#*        *#*   *#*     **** *#*   *#*   *#*     *#**          *#**#*     *#**#*     *#*     *#***#*      *#*   *#*    **#*             

*#*        *#*   *#*******#*  *#*   *#*   *#*** **##*           *###**     *###**     *#*** **##* *#*      *#*   *#******##*             

*#*        *#*    *######**   *#*   *#*    *######**            *###*      *###*       *######**  *#*      *#*   **#####**#*  *#*        

*#*        *#*     *******    *#*   *#*     *******              ##*       *##*         *******   *#*      *#*    ********#*  *#*

Change the Font to SERIF BOLD

#######   #######             ####   ####                   *######* *######*   ####*                       ####         ####    ***     

 *###*     *###*              *###   *###                    **##**   **##**    ****                        *###         *###    *#*     

  ###       ###                ###    ###                     *##**    **##*     **                          ###          ###    *#*     

  ###       ###                ###    ###                      *##*     *##*    ***                          ###          ###    *#*     

  ###       ###                ###    ###                      *##*     **#**   **                           ###          ###    *#*     

  ###       ###      ******    ###    ###     ******           **##*   ***##*   **     ******    #### ****   ###     *****###    *#*     

  ###       ###     *#***#**   ###    ###    *#****#*           *##*   ***##*   **    *#****#*   *###*###*   ###    *#****###    *#*     

  #############    *##* *##*   ###    ###   *##*  *##*          *##*   ****#** **    *##*  *##*   ###*****   ###   *##*  *###    *#*     

  ###       ###    *##   ##*   ###    ###   *##*  *##*           *##* **  *##* **    *##*  *##*   ###*       ###   *##*   ###    *#*     

  ###       ###    *#######*   ###    ###   *##    ##*           *##* **  *##* **    *##    ##*   ###*       ###   *##    ###    *#*     

  ###       ###    *##*        ###    ###   *##    ##*           *##***   **##**     *##    ##*   ###        ###   *##    ###    *#      

  ###       ###    *##*        ###    ###   *##    ##*            *##**    *##**     *##    ##*   ###        ###   *##    ###            

  ###       ###    *##*   **   ###    ###   *##*  *##*            *##**    *###*     *##*  *##*   ###        ###   *##*   ###            

  ###       ###    *##** ***   ###    ###   *##*  *##*            **#*      *#*      *##*  *##*   ###        ###   *##*  *###*   ***     

 *###*     *###*    *#####*   *###*  *###*   *#****#*              *#*      *#*       *#****#*   *###*      *###*  **#****####   *#*     

#######   #######   ******    #####  #####    ******               ***      *#*        ******    #####      #####   **********   ***

Double your money again

2011-08-17T10:42:00.004+01:00

Overview

A long time ago I wrote an article on using double for money. However, it is still a common fear for many developers when the solution is fairly simple.

Why not use BigDecimal

@myfear (Markus) asks a good question, doesn't BigDecimal do rounding already, (and with more options)

IMHO, There are two reason you may want to avoid BigDecimal

Clarity. This may be a matter of option but I find x * y / z clearer than x.multiply(y).divide(z, 10, BigDecimal.ROUND_HALF_UP)
Performance. BigDecimal is often 100x slower.

Took an average of 6 ns for rounding using cast

Took an average of 17 ns for rounding using Math.round

Took an average of 932 ns for rounding using BigDecimal.setScale

You might like to test the difference on your machine.

The code

RoundingPerformanceMain.java

When to use BigDecimal

The better question is why would you ever use BigDecimal?

Arbitary precision. If you want more than 15 decimal places of precision, use BigDecimal.
Precise rounding. If you need to have full control over rounding options, it will be simpler using BigDecimal
The project standard is to use BigDecimal. Human factors can be more important than technical arguments.

The problem with using double for money

double has two types of errors. It have representation error. i.e. it cannot represent all possible decimal values exactly. Even 0.1 is not exactly this value. It also has rounding error from calculations. i.e. as you perform calculations, the error increases.

double[] ds = {

        0.1,

        0.2,

        -0.3,

        0.1 + 0.2 - 0.3};

for (double d : ds) {

    System.out.println(d + " => " + new BigDecimal(d));

}

prints

0.1 => 0.1000000000000000055511151231257827021181583404541015625

0.2 => 0.200000000000000011102230246251565404236316680908203125

-0.3 => -0.299999999999999988897769753748434595763683319091796875

5.551115123125783E-17 => 5.5511151231257827021181583404541015625E-17

You can see that the representation for 0.1 and 0.2 is slightly higher than those values, and -0.3 is also slightly higher. When you print them, you get the nicer 0.1 instead of the actual value represented 0.1000000000000000055511151231257827021181583404541015625

However, when you add these values together, you get a value which is slightly higher than 0.

The important thing to remember is that these errors are not random errors. They are manageable and bounded.

Correcting for rounding error

Like many data types, such as date, you have an internal representation for a value and how you represent this as a string.

This is true for double. You need to control how the value is represented as a string. This can can be surprise as Java does a small amount of rounding for representation error is not obvious, however once you have rounding error for operations as well, it can some as a shock.

A common reaction is to assume, there is nothing you can do about it, the error is uncontrollable, unknowable and dangerous. Abandon double and use BigDecimal

However, the error is limited in the IEE-754 standards and accumulate slowly.

Round the result

And just like the need to use a TimeZone and Local for dates, you need to determine the precision of the result before converting to a String.

To resolve this issue, you need to provide appropriate rounding. With money this is easy as you know how many decimal places are appropriate and unless you have $70 trillion you won't get a rounding error large enough you cannot correct it.

// uses round half up, or bankers' rounding

public static double roundToTwoPlaces(double d) {

    return Math.round(d * 100) / 100.0;

}

// OR

public static double roundToTwoPlaces(double d) {

    return ((long) (d < 0 ? d * 100 - 0.5 : d * 100 + 0.5)) / 100.0;

}

If you add this into the result, there is still a small representation error, however it is not large enough that the Double.toString(d) cannot correct for it.

double[] ds = {

        0.1,

        0.2,

        -0.3,

        0.1 + 0.2 - 0.3};

for (double d : ds) {

    System.out.println(d + " to two places " + roundToTwoPlaces(d) + " => " + new BigDecimal(roundToTwoPlaces(d)));

}

prints

0.1 to two places 0.1 => 0.1000000000000000055511151231257827021181583404541015625

0.2 to two places 0.2 => 0.200000000000000011102230246251565404236316680908203125

-0.3 to two places -0.3 => -0.299999999999999988897769753748434595763683319091796875

5.551115123125783E-17 to two places 0.0 => 0

Conclusion

If you have a project standard which says you should use BigDecimal or double, that is what you should follow. However, there is not a good technical reason to fear using double for money.

Why testing code for thread safety is flawed

2011-08-13T09:18:00.003+01:00

Overview

We know that ++ is not thread safe, even for volatile field, however there is a trick to proving this.

The problem with testing code for thread safety is that it can happen to work repeatedly, but still be unsafe.

An example

I wrote a lock free ring buffer which passed multi-threaded tests of one billion entries repeatedly. However, a couple of days later the test consistently failed. What was the difference? There was a couple of CPU intensive processes also running on the same box. When these processes finished, the test passed again.

The problem

If you try to prove that incremental volatile variable is not thread safe, you can get a result like this.

public static void main(String... args) throws InterruptedException {

    for (int nThreads = 1; nThreads <= 64; nThreads*=2)

        doThreadSafeTest(nThreads);

}

static class VolatileInt {

    volatile int num = 0;

}

private static void doThreadSafeTest(final int nThreads) throws InterruptedException {

    final int count = 32 * 1000;



    ExecutorService es = Executors.newFixedThreadPool(nThreads);

    final VolatileInt vi = new VolatileInt();

    for (int i = 0; i < nThreads; i++)

        es.submit(new Runnable() {

            public void run() {

                for (int j = 0; j < count; j += nThreads)

                    vi.num++;

            }

        });

    es.shutdown();

    es.awaitTermination(10, TimeUnit.SECONDS);

    System.out.printf("With %,d threads should total %,d but was %,d%n", nThreads, count, vi.num);

}

On my machine with 8 logical threads prints

With 1 threads should total 32,000 but was 32,000

With 2 threads should total 32,000 but was 32,000

With 4 threads should total 32,000 but was 32,000

With 8 threads should total 32,000 but was 32,000

With 16 threads should total 32,000 but was 32,000

With 32 threads should total 32,000 but was 32,000

With 64 threads should total 32,000 but was 32,000

There doesn't appear to be a problem. Why? This is because it takes time to start each thread, and each thread doesn't take long to complete so even though many tasks are started, each completes before the next one starts. i.e. it is effectively single threaded.

Thread safety bugs can hide

In a more complex test, you might not know what subtle thing to change which causes your code to break. In fact you can deploy your application into production and it can work for years. One day something changes like you add another application, increasing the load, a version of Java or your machine is upgraded and suddenly it fails intermittently. It is tempting to assume that the most recent change is the cause of the problem when actually the bug has always been there, it just hasn't shown itself.

Changing the test

When we run the test long enough to have multiple threads running at once, we see a different pattern. We see that the single threaded test behaves as expected, without losing any counts, however the multi-threaded test runs start dropping incremented values.

With 1 threads should total 100,000,000 but was 100,000,000

With 2 threads should total 100,000,000 but was 75,127,690

With 4 threads should total 100,000,000 but was 51,338,289

With 8 threads should total 100,000,000 but was 35,177,375

With 16 threads should total 100,000,000 but was 15,264,270

With 32 threads should total 100,000,000 but was 14,385,095

With 64 threads should total 100,000,000 but was 15,818,747

Fixing the test

If you replace a volatile int with AtomicInteger you get the following result.

With 1 threads should total 100,000,000 but was 100,000,000

With 2 threads should total 100,000,000 but was 100,000,000

With 4 threads should total 100,000,000 but was 100,000,000

With 8 threads should total 100,000,000 but was 100,000,000

With 16 threads should total 100,000,000 but was 100,000,000

With 32 threads should total 100,000,000 but was 100,000,000

With 64 threads should total 100,000,000 but was 100,000,000

Conclusion

When trying to prove a multi-threaded test fails by experimentation is it not easy, even for trivial examples. This is why understanding the thread safety guarantees Java provides is important. This way you will know code is thread safe.

Work around

What can you do if you can't read all the code to guarantee thread safety? I would suggest loading up the box until everything is busy. Create processes so every thread is busy and create disk and network activity so they are always busy. While this is happening run your test. If it passes, your application is less likely to fail under load. This is no guarantee but it is better than testing your application without load.

The Code

IncrementNotThreadSafeMain.java

Collections Library for millions of elements

2011-08-09T15:06:00.011+01:00

When to use this library

If you want to efficiently store large collections of data in memory. This library can dramatically reduce Full GC times and reduce memory consumption as well.

When you have a data type which can be represented by an interface and you want a List for this type.

List<Iinterfacetype> list = new HugeArrayBuilder<Interfacetype>() {}.create();

The type needs to be described using an interface so its represented can be changed. (Using generated byte code)

The HugeArrayBuilder builds generated classes for the InterfaceType on demand. The builder can be configured to change how the HugeArrayList is created.

A more complex example is

HugeArrayList<Mutabletypes> hugeList = new HugeArrayBuilder<Mutabletypes>() {{

        allocationSize = 1024*1024;

        classLoader = myClassLoader;

    }}.create();

How does the library differ

Uses long for sizes and indecies.
Uses column based data making the per element overhead minimal and speed up scans over a single or small set of attributes. This reduces memory usages by 2x or more.
Stores attributes in direct memory as much as possible, reducing heap usage dramatically, 10x or more.
Allocates blocks of data for consistent add() times, rather than exponentially growing an underlying store (with exponentially increasing delays on a grow of capacity)

Performance comparison

This test compares using HugeCollection vs ArrayList of JavaBeans. The class has 12 fields of various types which can be converted to primitives in different ways. By storing these primitives (or objects encoded as primitives), the time to perform GCs is almost eliminated.

With 20 GB of free memory, only 250 million JavaBeans could be created and a HugeCollection can store 500 million elements.

Classes with fields which cannot be encoded as primitives are supported in version 0.1.1 and still show an improvement in GC times.

In both cases, the amount of memory used was halved.

The project web site

HugeCollections on Google Code

The source

The best way to get the whole source, including tests is to use subversion.

svn co http://vanilla-java.googlecode.com/svn/trunk/collections/ vanilla-java-collections

cd vanilla-java-collections

mvn test

Tuning buffer sizes

2011-08-05T13:21:00.003+01:00

Overview

When the typical read/write size is small, using a buffer can make a significant improvement in performance. However when reading/writing large amounts of data, additional buffered doesn't help and can add a small amount of overhead.

Additionally, it can be tempting to assume; the larger the buffer the better. However is appears a more modest buffer size, around the size of your L1 cache could be better. e.g 8 KB to 32 KB.

The test

In the following test I compared using buffered and unbuffered reads and writes to a temporary file on a tmpfs filesystem (ram disk)

Size of read/write	Unbuffered Writes	Buffered Writes	Unbuffered Reads	Buffered Reads
1	2 MB/s	86 MB/s	3 MB/s	72 MB/s
2	4 MB/s	165 MB/s	6 MB/s	147 MB/s
4	8 MB/s	333 MB/s	11 MB/s	291 MB/s
8	17 MB/s	578 MB/s	24 MB/s	560 MB/s
16	34 MB/s	920 MB/s	49 MB/s	983 MB/s
32	67 MB/s	1,345 MB/s	99 MB/s	1,679 MB/s
64	133 MB/s	1,746 MB/s	198 MB/s	2,518 MB/s
128	254 MB/s	2,024 MB/s	391 MB/s	3,387 MB/s
256	463 MB/s	2,172 MB/s	742 MB/s	4,104 MB/s
512	798 MB/s	2,270 MB/s	1,334 MB/s	4,549 MB/s
1,024	1,270 MB/s	2,299 MB/s	2,355 MB/s	4,752 MB/s
2,048	1,789 MB/s	2,310 MB/s	3,704 MB/s	4,923 MB/s
4,096	2,287 MB/s	2,301 MB/s	5,324 MB/s	4,859 MB/s
8,192	2,589 MB/s	2,497 MB/s	6,346 MB/s	6,142 MB/s
16,384	2,534 MB/s	2,559 MB/s	5,764 MB/s	5,697 MB/s
32,768	2,591 MB/s	2,561 MB/s	5,793 MB/s	5,723 MB/s
65,536	2,613 MB/s	2,581 MB/s	5,861 MB/s	5,883 MB/s
131,072	2,580 MB/s	2,581 MB/s	5,401 MB/s	5,405 MB/s
262,144	1,918 MB/s	1,907 MB/s	3,269 MB/s	3,262 MB/s
524,288	1,749 MB/s	1,734 MB/s	2,845 MB/s	2,851 MB/s
1,048,576	1,471 MB/s	1,469 MB/s	2,501 MB/s	2,502 MB/s

The default size of a BufferedInputStream and BufferedOutputStream is 8KB. This is part of the reason why they don't help at this point and larger.

The code

BufferTest.java

Comparing Collections speeds

2011-08-04T21:39:00.001+01:00

Overview

The speed of different collections tends to depend on their usage pattern however it can be useful to have an idea of their relative performance.

The test

In this test I compare both single thread and thread safe collections of different sizes.

Adding is from lowest to highest values. Removal is from start and end, finishing with the middle value. This disadvantages ArrayList and LinkedList relatively equally.

Collection	Size	Adding	Iterating	Removing
ArrayList	100,000	30.1	14.5	67,359
ArrayList	10,000	8.3	11.2	6,323
ArrayList	1,000	6.4	9.4	585
ArrayList	100	6.8	9.5	92.9
ArrayList	10	9.7	13.2	36.6
LinkedList	100,000	46.4	41.4	139,326
LinkedList	10,000	9.3	30.3	13,413
LinkedList	1,000	8.7	27.6	1,025
LinkedList	100	7.8	19.8	110
LinkedList	10	11.2	30.3	38.7
HashSet	100,000	28.6	115	69.5
HashSet	10,000	25.7	324	58.6
HashSet	1,000	26.0	2,521	59.2
HashSet	100	30.0	24,490	64.6
HashSet	10	51.7	244,045	131
LinkedHashSet	100,000	35.9	103	69.2
LinkedHashSet	10,000	30.3	101	65.0
LinkedHashSet	1,000	29.2	100	65.8
LinkedHashSet	100	31.5	98.8	60.6
LinkedHashSet	10	45.4	110	69.8
TreeSet	100,000	159	106	187
TreeSet	10,000	99.6	77.6	111
TreeSet	1,000	78.5	57.5	93.7
TreeSet	100	54.0	47.9	83.7
TreeSet	10	30.2	51.0	49.4
newSetFromMap IdentityHashMap	100,000	74.1	216	153
newSetFromMap IdentityHashMap	10,000	65.5	370	126
newSetFromMap IdentityHashMap	1,000	60.4	1,644	115
newSetFromMap IdentityHashMap	100	21.1	14,216	48.9
newSetFromMap IdentityHashMap	10	46.7	140,162	109
newSetFromMap WeakHashMap	100,000	52.4	148	87.4
newSetFromMap WeakHashMap	10,000	33.5	217	71.2
newSetFromMap WeakHashMap	1,000	32.9	1,088	72.2
newSetFromMap WeakHashMap	100	32.1	9,717	64.3
newSetFromMap WeakHashMap	10	48.0	98,769	93.0
Thread Safe Collections
synchronized ArrayList	100,000	22.6	101	98,735
synchronized ArrayList	10,000	12.1	101	10,084
synchronized ArrayList	1,000	11.5	99.5	1,023
synchronized ArrayList	100	11.4	101	144
synchronized ArrayList	10	14.0	111	54.0
Vector	100,000	23.9	298	64,333
Vector	10,000	20.4	372	5,919
Vector	1,000	19.4	372	612
Vector	100	19.3	375	145
Vector	10	22.9	397	97.5
synchronized LinkedList	100,000	37.6	100	132,660
synchronized LinkedList	10,000	19.2	99.6	13,049
synchronized LinkedList	1,000	22.2	99.1	1,005
synchronized LinkedList	100	23.7	102	134
synchronized LinkedList	10	26.1	115	62.6
synchronized HashSet	100,000	50.1	138	95.7
synchronized HashSet	10,000	43.0	347	93.1
synchronized HashSet	1,000	42.7	2,555	95.3
synchronized HashSet	100	47.0	24,608	97.4
synchronized HashSet	10	85.7	245,343	204
synchronized LinkedHashSet	100,000	48.6	103	93.1
synchronized LinkedHashSet	10,000	45.6	101	88.1
synchronized LinkedHashSet	1,000	48.7	106	94.6
synchronized LinkedHashSet	100	48.1	101	86.8
synchronized LinkedHashSet	10	57.8	114	93.4
synchronized TreeSet	100,000	116	105	179
synchronized TreeSet	10,000	74.1	75.4	122
synchronized TreeSet	1,000	63.5	53.9	103
synchronized TreeSet	100	50.8	46.2	90.4
synchronized TreeSet	10	29.1	49.1	57.6
CopyOnWriteArrayList	100,000	35,354	65.8	165,197
CopyOnWriteArrayList	10,000	2,115	97.7	36,269
CopyOnWriteArrayList	1,000	217	75.1	1,828
CopyOnWriteArrayList	100	60.0	63.4	227
CopyOnWriteArrayList	10	48.2	71.0	103
CopyOnWriteArraySet	100,000	106,116	63.3	165,708
CopyOnWriteArraySet	10,000	28,736	91.2	29,820
CopyOnWriteArraySet	1,000	1,143	75.1	1,852
CopyOnWriteArraySet	100	134	63.4	233
CopyOnWriteArraySet	10	55.3	73.0	109
newSetFromMap ConcurrentHashMap	100,000	70.6	291	149
newSetFromMap ConcurrentHashMap	10,000	57.2	485	120
newSetFromMap ConcurrentHashMap	1,000	53.4	2,869	121
newSetFromMap ConcurrentHashMap	100	54.7	24,150	140
newSetFromMap ConcurrentHashMap	10	68.7	93,921	197
newSetFromMap ConcurrentSkipListMap	100,000	135	96.8	365
newSetFromMap ConcurrentSkipListMap	10,000	113	95.1	285
newSetFromMap ConcurrentSkipListMap	1,000	97.8	94.7	234
newSetFromMap ConcurrentSkipListMap	100	83.3	95.2	192
newSetFromMap ConcurrentSkipListMap	10	64.2	112	151

The code

AddIterateRemoveTest.java
Timings are in nano-seconds per element.

Collections Library for millions of elements

Reading/writing GC-less memory

2011-08-04T15:54:00.005+01:00

Overview

How you access data can make a difference to the speed. Whether you use manual loop unrolling or let the JIT do it for you can also make a difference to performance.

I have included C++ and Java tests doing the same thing for comparison.

Tests

In each case, different approaches to storing 16 GB of data were compared.

In the following tests I compared storing data

allocating, writing to, reading from and total GC times
byte[] (smallest primitive) and long[] (largest primitive)
arrays, direct ByteBuffer and Unsafe
JIT optimised and hand unrolled four times

store	type	size	unrolled	allocate	writing	reading	GC time
C++ char[]	native	8-bit char	no	31 μs	12.0 s	8.7 s	N/A
C++ char[]	native	8-bit char	yes	5 μs	8.8 s	6.6 s	N/A
C++ long long[]	native	64-bit int	no	11 μs	4.6 s	1.4 s	N/A
C++ long long[]	native	64-bit int	yes	12 μs	4.2 s	1.2 s	N/A
byte[]	heap	byte	no	4.9 s	20.7/7.8 s	7.4 s	51 ms
byte[]	heap	byte	yes	4.9 s	7.1 s	8.5 s	44 ms
long[]	heap	long	no	4.7 s	1.6 s	1.5 s	37 ms
long[]	heap	long	yes	4.7 s	1.5 s	1.4 s	45 ms
ByteBuffer	direct	byte	no	4.8 s	18.1/10.0 s	14.0 s	6.1 ms
ByteBuffer	direct	byte	yes	4.8 s	12.2/10.0 s	16.7 s	6.1 ms
ByteBuffer	direct	long	no	4.7 s	6.0/3.9 s	2.4 s	6.1 ms
ByteBuffer	direct	long	yes	4.6 s	4.7/2.3 s	7.9 s	6.1 ms
Unsafe	direct	byte	no	10 μs	18.2 s	13.8 s	6.0 ms
Unsafe	direct	byte	yes	10 μs	8.7 s	8.3 s	6.0 ms
Unsafe	direct	long	no	10 μs	5.2 s	1.9 s	6.0 ms
Unsafe	direct	long	yes	10 μs	4.2 s	1.3 s	6.0 ms

In each case, this is the time to perform 8-bit byte or 64-bit long operations on 16 GB of data in different structures as required. In C++ and using Unsafe, I single array/block memory was used. For Java array and ByteBuffer multiple objects were use to create the same total amount of space.

C++ test configuration

All tests were performed with gcc 4.5.2 on ubuntu 11.04, compiled with -O2

Java test configuration

All test were performed with Java 6 update 26 and Java 7 update 0, on a fast PC with 24 GB of memory. Timings are for 6/7. Where there one value they were the same.

All tests were run with the options -mx23g -XX:MaxDirectMemorySize=20g -verbosegc

Curiosity

For me the most curious result was the performance of the long[] which was very fast in Java, faster than using C++ or Unsafe directly.

The code

C++ tests - memorytest/main.cpp

Java tests - MemoryTest.java

50,000 pages views last month

2011-08-03T15:31:00.000+01:00

Thank you for your interest.

At the moment I am working a few pet projects including

A low latency, low GC, parsing, logging and writing library.
A direct memory collection library for storing massive amounts of data efficiently with minimal heap.

See some of my previous post for teasers on how these will work.

A collection with billions of entries

2011-08-03T13:17:00.005+01:00

Overview

There are a number of problems with having a large number of records in memory. One way around this is to use direct memory, but this is too low level for most developers. Is there a way to make this more friendly?

Limitations of large numbers of objects

The overhead per object is between 12 and 16 bytes for 64-bit JVMs. If the object is relatively small, this is significant and could be more than the data itself.
The GC pause time increases with the number of objects. Pause times can be around one second per GB of objects.
Collections and arrays only support two billion elements

Huge collections

One way to store more data and still follow object orientated principles is have wrappers for direct ByteBuffers. This can be tedious to write, but very efficient.

What would be ideal is to have these wrappers generated automatically.

Small JavaBean Example

This is an example of JavaBean which would have far more overhead than actual data contained.

interface MutableByte {

    public void setByte(byte b);



    public byte getByte();

}

It is also small enough that I can create billions of these on my machine. This example creates a List<Bytes> with 16 billion elements.

final long length = 16_000_000_000L;

HugeArrayList<MutableByte> hugeList = new HugeArrayBuilder<MutableByte>() {{

    allocationSize = 4 * 1024 * 1024;

    capacity = length;

}}.create();



List<MutableByte> list = hugeList;

assertEquals(0, list.size());



hugeList.setSize(length);



// add a GC to see what the GC times are like.

System.gc();



assertEquals(Integer.MAX_VALUE, list.size());

assertEquals(length, hugeList.longSize());



byte b = 0;

for (MutableByte mb : list)

    mb.setByte(b++);



b = 0;

for (MutableByte mb : list) {

    byte b2 = mb.getByte();

    byte expected = b++;

    if (b2 != expected)

        assertEquals(expected, b2);

}

From start to finish, the heap memory used is as follows. with -verbosegc

0 sec - 3100 KB used

[GC 9671K->1520K(370496K), 0.0020330 secs]

[Full GC 1520K->1407K(370496K), 0.0063500 secs]

10 sec - 3885 KB used

20 sec - 4428 KB used

30 sec - 4428 KB used

  ... deleted ...

1380 sec - 4475 KB used

1390 sec - 4476 KB used

1400 sec - 4476 KB used

1410 sec - 4476 KB used

The only GC is one triggered explicitly. Without the System.gc(); no GC logs appear.

After 20 sec, the increase in memory used is from logging how much memory was used.

Conclusion

The library is relatively slow. Each get or set takes about 40 ns which really adds up when there are so many calls to make. I plan to work on it so it is much faster. ;)

On the upside, it wouldn't be possible to create 16 billion objects with the memory I have, nor could it be put in an ArrayList, so having it a little slow is still better than not working at all.

Should server applications limit themselves to 4 GB?

Collections Library for millions of elements

Should server applications limit themselves to 4 GB?

2011-08-03T08:39:00.004+01:00

Overview

A very interesting talk by CTO of Azul, Gil Tene raises many timely issues about GC performance and server memory sizes.

A typical new server should be 100 GB

One point he brings up is; with memory so cheap a typical server should be around 100 GB (at around $7K) Installing less memory is wasting data centre space. A typical JVM only uses 2-4 GB as the GC pause hurts responsiveness at this point. However, if you are developing an application which only uses 2-4 GB you are writing an application which will soon fit on a mobile phone. So how can we write server applications which can use the whole server in Java?

Java without the GC Pauses: Keeping Up with Moore’s Law and Living in a Virtualized World

He raises questions about how best to use that memory and not surprisingly Azul have a product which will scales to that much memory efficiently.

For those who are not planing to buy such a system, you could be thinking about how you can use more memory efficiently.

My view

When you increase the Eden size of an application but just create temporary garbage, the pause times don't increase. Its the retained objects which increase the pause time.

The simplest thing to try is having a very large Eden size and see if the pause times increase or perhaps decrease. It can decrease as you give more time for medium lived objects to die and less objects leave the Eden/Survivor spaces to make it into the tenured space which require long pauses to clean up.

What can you buy today

The prices Gil quotes are actually 6 months old now.

I only quote Dell here because I find their web site easy to get a quote from.

I found a Dell T610 with 96GB cost $5.8K and T710 with 192 GB costs $12.2K on their web site.

I recently bought a PC with 24 GB for £1K. ;)

A collection with billions of entries

Collections Library for millions of elements

Strange Hello World in Java

2011-08-02T09:43:00.002+01:00

Overview

This is a strange Hello World program because it only needs to be compiled, not run. How does it work? Hint: it only works on MS-DOS/Windows. ;)

The Program

In a file called A.java or any name exception Con.java

class Con {
    String hi = "\n\n\tHello World!\n\n";
}

when compiled produces

How does this work

MS-DOS/Windows treats all files which start with CON (in any case and with any extension) as the console. So when javac writes the Con.class file, it is written to the console instead.

In the MS world; its not a bug, its a feature.

For more details

Use PRINT# to MS-DOS "CON" Device to Send ANSI Escape Codes

Comparing Java 7 Async NIO with NIO.

2011-08-01T17:41:00.002+01:00

Overview

SDP (Sockets Direct Protocol) in Java 7 promises better integration with InfiniBand. This comes with a new Socket classes AsynchronousSocketChannel and AsynchronousServerSocketChannel. Is there any advantage in using these libraries if you don't have InfiniBand?

Creating a server socket

The API for AsynchronousServerSocketChannel is slightly different to ServerSocketChannel. The most notable difference is the use of Futures instead of always blocking.

final AsynchronousServerSocketChannel ssc =
      AsynchronousServerSocketChannel.open().bind(new InetSocketAddress("localhost", 9999));
Future<AsynchronousSocketChannel> accepted = ssc.accept();
AsynchronousSocketChannel sc2 = accepted.get();

ByteBuffer bb = ByteBuffer.allocateDirect(4096);
Future<Integer> readFuture = sc2.read(bb);

Creating a client socket

Similarly the client can start a connection and later wait when the connection is really needed.

AsynchronousSocketChannel sc = AsynchronousSocketChannel.open();
Future connected = sc.connect(new InetSocketAddress("localhost", 9999));
// later ensure we are connected.
connected.get();

ByteBuffer bb = ByteBuffer.allocateDirect(4096);
// populate bb
Future<Integer> writeFuture = sc2.write(bb);

Is there any performance differences?

Without threads, the Asynchronous IO was 5-10% faster. However once threads were used, the performance dropped. This could be because this is Java 7 update 0. I look forward to testing this again in the future.

Async Socket latency was 1/50/99%tile 5.2/5.4/7.3 us
Async Socket Throughput was 186 K/s
Threaded Async Socket Latency for 1/50/99%tile 13.8/16.9/24.7 us
Threaded Async Socket Throughput was 183 K/s

The best of three runs was used.

For comparison, the same tests using regular NIO on Java 7 were

Socket latency was 1/50/99%tile 5.6/5.8/7.0 us
Socket Throughput was 170 K/s
Threaded Socket Latency for 1/50/99%tile 6.0/8.5/10.7 us
Threaded Socket Throughput was 234 K/s

The code

Its worth nothing that the code is slightly more complex to use than regular NIO. However, the features added are powerful and for the brave, it will be valuable.

Asynchronous NIO Socket - AsyncPingTest.java

Plain NIO Socket - PingTest.java

Conclusion

The API for Asynchronous sockets looks promising despite the added complexity. However the performance many not be there unless you have the right hardware, yet.

Using tmpfs to speed up "disk" access

2011-08-01T09:06:00.006+01:00

Overview

If you have an application which performs a lot disk reads/writes and a modest amount of data, you don't need to keep. e.g. a unit tests, application builds. Using tmpfs may be the answer speeding up the process.

In this article I compare using a tmpfs, an SSD, a hard drive and an NFS drive.

Comparing creating a file and deleting it

Small files (256 bytes) are created repeatedly and an average time taken. These files are deleted in a second test.

File system type	machine	file creation	file deletion
tmpfs	fast	7.2 us	3.9 us
tmpfs	older	19.9 us	8.9 us
SSD ext4	fast	22.9 us	9.1 us
7200 RPM ext4	older	42.9 us	24.1 us
NFS	-	11,238 us	5,294 us

The "fast" machine was a 3.8 GHz i7 with 1600 MHz memory.

The "older" machine was a 2.5 GHz AMD 4800 with 533 MHz memory.

The NFS drive is a QNAP TS-210 with mirrored 7,200 RPM drives over a home plug network.

The write cache for the 7,200 RPM disk is making a big difference. Without the disk cache the performance would closer to that of the NFS file system.

In each case, the tmpfs was limited to 80% of the total main memory. Using a larger tmpfs will impact performance.

The Code

The core part of the test looks like this.

byte[] bytes = new byte[256];
long start = System.nanoTime();
for (int i = 0; i < files; i++) {
    File file = new File(dir, Integer.toString(i));
    FileOutputStream fos = new FileOutputStream(file);
    fos.write(bytes);
    fos.close();
}
long time = System.nanoTime() - start;
System.out.printf("Took an average of %.1f us to write to LOCAL filesystem%n", time/1e3/files);

OpenCloseFilesTest.java

Conclusion

Using a tmpfs can be 2-3x faster than a local disk with write cache. When you have working data you don't need to keep it can speed up your process.

Synchronized vs Lock performance

2011-07-30T20:52:00.008+01:00

Overview

There are a number of articles on whether synchronized or Locks are faster. There appear to be opinions in favour of either option. In this article I attempt to show how you can achieve different views depending on how you benchmark the two approaches.

I have included AtomicInteger to see how a volatile field compares.

What are some of the differences

The synchronized keyword has naturally built in language support. This can mean the JIT can optimise synchronised blocks in ways it cannot with Locks. e.g. it can combine synchronized blocks.

The Lock has additional method such as tryLock which is not an option for a synchronized block.

The test

As the JIT can optimise synchronized in ways a Lock cannot, I wanted to have a test which might demonstrate this and one which might "fool" the JIT.

In this test, 25 million locks were performed between each of the threads. Java 6 update 26 was used.

Threads	1x synch	1x Lock	1x AtomicInteger	2x synch	2x Lock	2x AtomicInteger
1 :	0.937	0.786	0.400	1.532	1.484	0.569
2 :	2.766	4.597	0.676	5.398	6.355	1.278
4 :	3.904	1.267	0.694	6.330	2.657	1.354
8 :	3.884	0.953	1.011	5.418	2.073	2.761
16 :	3.207	0.869	1.171	4.817	1.656	2.800
32 :	3.213	0.853	1.240	4.915	1.680	2.843
64 :	3.322	0.921	1.269	5.049	1.639	2.843

These are the times to perform 25 million locks/operation in seconds. Lower numbers are better. Different system will get different results, so these should be taken as a relative performance.

Note: It appears that Lock performs best with high numbers of threads. However this may because the performance approaches the single threaded performance. It may do this by avoiding contention and letting just one thread run for long periods of time.

The Code

SynchronizedVsLockTest.java

Conclusion

In general, unless you have measured you system and you know you have a performance issue, you should do what you believe is simplest and clearest and it is likely to performance well.

These results indicate that synchronized is best for a small number of threads accessing a lock (<4) and Lock may be best for a high number of threads accessing the same locks.

Java Concurrency in practice - Favours locks for performance, otherwise suggest synchronized be used if not an issue. States Lock are much faster for Java 5.0, slightly faster for Java 6
Java Performance: synchronized() vs Lock - Favours synchronized, based on a micro-benchmark. Compares one and two threads
java.util.concurrent ReentrantLock vs synchronized() - which should you use? - Favours synchronized on technical arguments
Synchronized vs. Lock vs. fair Lock - Compares locks based on fairness rather than performance
synchronized vs custom locking: Java synchronization performance - Determines that Locks were 5x faster for Java 5.0
Java synchronized block vs ReentantLock performance - Compares synchronized vs Locks with 10 threads, concludes Locks are significantly faster (about 5x) Not clear if this test was done with Java 5.0 also
Performance of ReentrantLock and Synchronized - Compares different numbers of threads and concludes synchronized is only fastest for one thread

C++ or Java, which is faster for high frequency trading?

2011-07-30T13:40:00.003+01:00

Overview

There are conflicting views as to what is the best solution for high frequency trading. Part of the problem is that what is high frequency trading varies more than you might expect, another part is what is meant by faster.

My View

If you have a typical Java programmer and typical C++ programmer, each with a few years experience writing a typical Object Oriented Program, and you give them the same amount of time, the Java programmer is likely to have a working program earlier and will have more time to tweak the application. In this situation it is likely the Java application will be faster. IMHO.

In my experience, Java performs better at C++ at detecting code which doesn't need to be done. esp micro-benchmarks which don't do anything useful. ;) If you tune Java and C++ as far as they can go given any amount of expertise and time, the C++ program will be faster. However, given limited resources and in changing environment a dynamic language will out perform. i.e. in real world applications.

In the equities space latency you need latencies sub-10 us to be seriously high frequency. Java and even standard OOP C++ on commodity hardware is not an option. You need C or a cut down version of C++ and specialist hardware like FPGAs, GPUs.

In FX, high frequency means a latencies of sub-100 us. In this space C++ or a cut down Java (low GC) with kernel bypass network adapter is an option. In this space, using one language or another will have pluses and minuses. Personally, I think Java gives more flexibility as the exchanges are constantly changing, assuming you believe you can use IT for competitive advantage.

In many cases, when people talk about high frequency, esp Banks, they are talking sub 1 ms or single digit ms. In this space, I would say the flexibility/dynamic programming of Java, Scala or C# etc would give you time to market, maintainability and reliability advantages over C/C++ or FPGA.

The problem Java faces

The problem is not in the language as such, but a lack of control over caches, context switches and interrupts. If you copy a block of memory, something which occurs in native memory, but using a different delay between runs, that copy gets slower depending on what has happened between copies.

The problem is not GC, or Java as neither of these play much of a part. The problem is that part of the cache has been swapped out and the copy itself takes longer. This is the same for any operation which accesses memory. e.g. accessing plain objects will also be slower.

private void doTest(Pauser delay) throws InterruptedException {
    int[] times = new int[1000 * 1000];
    byte[] bytes = new byte[32* 1024];
    byte[] bytes2 = new byte[32 * 1024];
    long end = System.nanoTime() + (long) 5e9;
    int i;
    for (i = 0; i < times.length; i++) {
        long start = System.nanoTime();
        System.arraycopy(bytes, 0, bytes2, 0, bytes.length);
        long time = System.nanoTime() - start;
        times[i] = (int) time;
        delay.pause();
        if (start > end) break;
    }
    Arrays.sort(times, 0, i);
    System.out.printf(delay + ": Copy memory latency 1/50/99%%tile %.1f/%.1f/%.1f us%n",
            times[i / 100] / 1e3,
            times[i / 2] / 1e3,
            times[i - i / 100 - 1] / 1e3
    );
}

The test does the same thing many times, with different delays between performing that test. The test spends most of its time in native methods and no objects are created or discarded as during the test.

YIELD: Copy memory latency 1/50/99%tile 1.6/1.6/2.3 us
NO_WAIT: Copy memory latency 1/50/99%tile 1.6/1.6/1.6 us
BUSY_WAIT_10: Copy memory latency 1/50/99%tile 2.8/3.5/4.4 us
BUSY_WAIT_3: Copy memory latency 1/50/99%tile 2.7/3.0/4.0 us
BUSY_WAIT_1: Copy memory latency 1/50/99%tile 1.6/1.6/2.5 us
SLEEP_10: Copy memory latency 1/50/99%tile 2.2/3.4/5.1 us
SLEEP_3: Copy memory latency 1/50/99%tile 2.2/3.4/4.4 us
SLEEP_1: Copy memory latency 1/50/99%tile 1.8/3.4/4.2 us

With -XX:+UseLargePages with Java 7

YIELD: Copy memory latency 1/50/99%tile 1.6/1.6/2.7 us
NO_WAIT: Copy memory latency 1/50/99%tile 1.6/1.6/1.8 us
BUSY_WAIT_10: Copy memory latency 1/50/99%tile 2.7/3.6/6.6 us
BUSY_WAIT_3: Copy memory latency 1/50/99%tile 2.7/2.8/5.0 us
BUSY_WAIT_1: Copy memory latency 1/50/99%tile 1.7/1.8/2.6 us
SLEEP_10: Copy memory latency 1/50/99%tile 2.4/4.0/5.2 us
SLEEP_3: Copy memory latency 1/50/99%tile 2.3/3.9/4.8 us
SLEEP_1: Copy memory latency 1/50/99%tile 2.1/3.3/3.7 us

The best of three runs was used.

The typical time (the middle value) it takes to perform the memory copy varies between 1.6 and 4.6 us depending on whether there was a busy wait or sleep for 1 to 10 ms. This is a ratio of about 3x which has nothing to do with Java, but something it has no real control over. Even the best times vary by about 2x.

The code

ThreadlatencyTest.java

Conclusion

In ultra-high frequency, the core engine will be more C, assembly and custom hardware than OOP C++ or Java. In markets where the latency requirements of the engine are less tight C++ and Low GC Java become an option. As latency requirement become less tight, Java and other dynamic languages can be more productive. In this situation, Java is faster to market so you can take advantages of changes in the market/requirements.

How fast are Java Datagrams?

2011-07-29T09:31:00.001+01:00

Overview

Following my article How fast are Java sockets, this article follows the same tests except for Datagrams which use UDP rather than TCP.

The timings

The tests are the same except Datagrams don't support busy waiting in Java 6 which hurts the Threaded Ping latency

UDP Pings per second 224 K/s
UDP Pings latency was 1/50/99%tile 4.1/4.2/4.7 us
Threaded UDP Pings per second 131 K/s
Threaded UDP Pings latency was 1/50/99%tile 9.8/11.0/33.2 us

Comparison

Test	Threaded	Throughput	Typical latency
Datagram Ping	no	224 K/s	4.2 μs
Socket Ping	no	170 K/s	5.8 μs
Datagram Ping	yes	131 K/s	11.0 μs
Socket Ping	yes	235 K/s	8.5 μs

The Code

DatagramPingTest.java

How fast are Java sockets

Send XML over a Socket fast

Why are the keys of a Map in a jumbled order

2011-07-28T08:12:00.000+01:00

Overview

When you first try to printout a HashMap, the order doesn't make any sense and when you add entries, they appear to jump around. What is going on?

The order of Maps

The order keys should appear is not defined in many implementations.

Hash map uses a hash of the key to place the key/value in a pseudo random place in the underlying store (an array) How it does this is different in different implementations. For HashMap the size of the Map is always a power of 2. For Hashtable the size grows 11, 23, 47, 95.

For LinkedHashMap, the order will be the order the keys were added and for TreeMap & ConcurrentSkipList, the order is based of the Comparable.compareTo() result (asciibetical order for String)

For Hashtable and HashMap changing the initial size changes how the keys are hashed and thus their order

public static void main(String... args) {
    populate(new Hashtable());
    populate(new Hashtable(47), " (47)");
    populate(new Hashtable(95), " (95)");
    populate(new HashMap());
    populate(new HashMap(32), " (32)");
    populate(new HashMap(64), " (64)");
    populate(new LinkedHashMap());
    populate(new IdentityHashMap());
    populate(new WeakHashMap());
    populate(new ConcurrentHashMap());
    populate(new TreeMap());
    populate(new ConcurrentSkipListMap());
}

private static void populate(Map map) {
    populate(map, "");
}

private static void populate(Map map, String suffix) {
    for (String s : "one,two,three,four,five,six,seven,eight,nine,ten".split(","))
        map.put(s, s);
    System.out.println(map.getClass().getSimpleName() + suffix + " " + map.keySet());
}

prints

Hashtable [three, six, ten, seven, nine, one, five, four, two, eight]
Hashtable (47) [ten, five, seven, two, three, one, nine, six, eight, four]
Hashtable (95) [nine, five, six, one, seven, eight, ten, two, four, three]
HashMap [ten, two, seven, five, nine, one, three, four, eight, six]
HashMap (32) [ten, five, nine, one, eight, six, two, seven, three, four]
HashMap (64) [ten, nine, one, eight, six, three, four, five, two, seven]
LinkedHashMap [one, two, three, four, five, six, seven, eight, nine, ten]
IdentityHashMap [four, two, five, nine, three, six, eight, one, seven, ten]
WeakHashMap [six, eight, four, three, nine, one, seven, five, ten, two]
ConcurrentHashMap [seven, two, one, nine, four, six, eight, three, ten, five]
TreeMap [eight, five, four, nine, one, seven, six, ten, three, two]
ConcurrentSkipListMap [eight, five, four, nine, one, seven, six, ten, three, two]

Size of an entry in a Map

2011-07-27T19:22:00.003+01:00

Overview

The have been some very good articles on the size of a map. However as a map grows, it initial size become less important and the size per entry is what matters.

How are the sizes measured

In these tests an int key and long values are used. This adds a small but realistic size to each entry.

Size per entry of a medium sized Map

The following are the size per entry in bytes. The Map has 1024 entries.

Type of Map	32-bit	64-bit compressed	64-bit not compressed
TIntLongHashMap	26.9	26.9	27.0
FastMap (recycled)	32.0	39.9	47.9
IdentityHashMap	48.0	56.0	80.0
ConcurrentSkipListMap	68.3	76.1	108.3
TreeMap	64.0	80.0	112.0
HashMap	64.0	80.0	112.0
SynchronizedMap	64.0	80.0	112.0
ConcurrentHashMap	65.2	81.4	114.0
Properties	68.0	84.0	120.0
Hashtable	68.0	84.0	120.0
LinkedHashMap	72.0	88.0	128.1
WeakHashMap	80.0	88.0	136.1

The Javolution FastMap needed to be recycled. If it is not recycled, it was the largest per entry.

Conclusion

It may be worth considering The GNU Trove collections if you have primitive keys and/or values. However if you have non-trivial keys or values classes, the size of the collection is less likely to matter.

The Code

SizeOfMapsTest.java

Send XML over a Socket fast

2011-07-27T14:12:00.002+01:00

Overview

XML parsers are designed to handle any type of XML message you can send. However if you assume the XML will always follow a specific format how fast can you make it.

This follows my article on How fast are Java sockets

The format

For this article I have written a self contained test which sends a heartbeat request and which expect a heartbeat response.

<Root timestamp="{timestamp}"><HeartbeatRequest sequence="{sequence}"/></Root>

<Root timestamp="{timestamp}"><HeartbeatResponse sequence="{sequence}"/></Root>

In this test, the sequence number contains the System.nanoTime(). When the client gets back the heartbeat response it can calculate the round trip time.

Messages are parsed and a listener interface called.

static interface EventListener {

        void heartbeatRequest(long timestamp, long sequenceNumber);



        void heartbeatResponse(long timestamp, long sequenceNumber);



        void error(String message);

    }

Latency

Two messages are sent in quick succession and any data returned is processed. From this the latency of each message can be determined by comparing the System.nanoTime() with the sequence number.

Sending simple XML messages

Socket latency was 1/50/99%tile 11.3/15.6/63.9 μs

Compared with sending 1KB with no data.

Threaded Socket Latency for 1/50/99%tile 6.0/8.5/10.7 μs

The latency has increased, in particular the high percentile latency. This indicates the variation in times has also increased.

Throughput

Two messages are sent in quick succession and any data returned is processed. The throughput after more than 10 seconds is calculated.

Send simple XML messages.

Socket throughput was 264 K/s

Compared with sending 1KB with no data.

Threaded Socket Throughput was 234 K/s

The throughput is slightly higher. This could be because the message size is much smaller.

The code

It is worth noting that this example creates next to no garbage and the GC doesn't run (checked with -verbosegc) even though the test is running flat out for more than 10 seconds.

XmlServiceTest.java

How fast are Java sockets

How fast are Java Datagrams?

How fast are Java sockets

2011-07-27T09:52:00.004+01:00

Overview

How long a request/response takes and the rate requests can be performed in a Java application depends on a number of factors. The network, the network adapter, Java Socket and TCP layer, and what your application does.

Usually the last factor is your limitation. What if you wanted to test the overhead Java/TCP contributes, here is a way you can test this.

Latency and throughput

The Latency, in this test, is the Round Trip Time (sometimes written as RTT) This is the time between sending a request and receiving the response. This includes the delay on the client side, the transport and the delay on the server side.

The Throughput is a measure of how many request/responses can be performed in a given amount of time. How long each request/response takes is not measured, and has no impact unless its really large.

The Results

These results are for a fast PC doing nothing but pass data back and forth over loopback. This will be one of the limiting factors to using Java and TCP on your system. Your server running a real application on a real network will not be faster than this.

Your should test your system as the hardware used can make a big difference. (See The Code below)

Socket latency was 1/50/99%tile 5.6/5.8/7.0 us
Socket Throughput was 170 K/s
Threaded Socket Latency for 1/50/99%tile 6.0/8.5/10.7 us
Threaded Socket Throughput was 234 K/s

The first pair of results, test just the Socket. Its single threaded and as you would expect, the throughput is the inverse of the latency. i.e. 170K * 5.8e-6 = 0.986 (about 1 thread busy) In the threaded test, the latency and throughput are higher. i.e. 234K * 8.5e-6 = 1.989 (about two threads were busy) Put another way, the throughput was double the inverse of the latency.

Can throughput be increased

Throughput can be increased further by batching and using multiple connections. This will increase/worsen latency but can give a significant increase in throughput. Between 2x to 10x can be expected with one server. Additional servers have the potential to increase throughput to the limits of your budget. ;)

However, once you have a real application on a real network, you will be lucky to achieve this throughput numbers on one server even with batching and multiple connections.

Follow on Article

Send XML over a Socket fast

The Code

PingTest.java

Send XML over a Socket fast

How fast are Java Datagrams?

Java: How much memory do different arrays consume

2011-07-24T13:24:00.006+01:00

Overview

Arrays can be large and consume a significant amount of memory. It can me worth choosing the most memory efficient array/collection.

Comparing array sizes

How much space does a `new int[1024]` take compared with an `new Integer[1024]`?

int[] ints = new int[1024];
for (int i = 0; i < ints.length; i++) ints[i] = i;

compared with

Integer[] ints = new Integer[1024];
for (int i = 0; i < ints.length; i++) ints[i] = i;

Note: 1/8th of Integer values will come from the auto-box cache and not use additional memory. All possible Boolean and Byte values are cached.

array	size in bytes 32-bit JVM	size in bytes 64-bit JVM
new BitSet(1024)	168	168
new boolean[1024]	1040	1040
new Boolean[1024]	4112	4112
new ArrayList<Boolean>(1024)	4136	4136
new LinkedList<Boolean>() with 1024	24624	24624
new byte[1024]	1040	1040
new Byte[1024]	4112	4112
new ArrayList<Byte>(1024)	4136	4136
new LinkedList<Byte>() with 1024	24624	24624
new char[1024]	2064	2064
new Character[1024]	18448	18448
new short[1024]	2064	2064
new Short[1024]	18448	18448
new ArrayList<Character/Short>(1024)	18472	18472
new LinkedList<Character/Short>() with 1024	38960	38960
new int[1024]	4112	4112
new Integer[1024]	18448	18448
new float[1024]	4112	4112
new Float[1024]	20496	20496
new ArrayList<Integer/Float>(1024)	18472	18472
new LinkedList<Integer/Float>() with 1024	38960	38960
new long[1024]	8208	8208
new Long[1024]	18448	25616
new double[1024]	8208	8208
new Double[1024]	20496	28688
new ArrayList<Long/Double>(1024)	18472	25640
new LinkedList<Long/Double>() with 1024	38960	46128
new String[1024]	52464	61456
new ArrayList<String>(1024)	52488	61480
new LinkedList<String>() with 1024	72976	81968

In both cases, Java 6 update 26 was used. For the 64-bit JVM of this version, -XX:+UseCompressedOops is the default option which uses 32-bit references. If you use more than 32 GB of memory, you would need to turn this option off, using more memory for the arrays of objects.

The full code

Is available here: MemoryUsageExamplesTest

Java and Memory Leaks

2011-07-22T23:25:00.002+01:00

Overview

The term "memory leak" is used in Java in a manner which is different to how it is used in other languages. What does a "memory leak" mean in general terminology and how is it used in Java?

Wikipedia definition

A memory leak, in computer science (or leakage, in this context), occurs when a computer program consumes memory but is unable to release it back to the operating system.

The JVM reserves the heap as virtual memory on startup and doesn't gives that memory back until it exits. This virtual memory turns into main memory as it is used. This is why the virtual size and the resident size for a JVM can be very different and the resident memory can grow without the virtual memory changing.

In object-oriented programming, a memory leak happens when an object is stored in memory but cannot be accessed by the running code.

The GC can always find every object on the heap, even those which are not reachable to the application. As such there is no object which is not reachable to running code.

however, many people refer to any unwanted increase in memory usage as a memory leak, though this is not strictly accurate from a technical perspective.

In Java, the amount of memory required cannot be determined without a full GC. It is normal to see the "used" memory of a Java application sawtooth. Returning to the same amount of memory used after each GC indicates the memory required has not increased.

A memory leak can diminish the performance of the computer by reducing the amount of available memory. Eventually, in the worst case, too much of the available memory may become allocated and all or part of the system or device stops working correctly, the application fails, or the system slows down unacceptably due to thrashing.

This is how the term is used in Java. There is a reduction in available memory, conclusion: it is a memory leak.

But is it really a memory leak?

Examples of "memory leaks" in Java

Recently, two questions were asked on StackOverflow which illustrate a variety of views over what a "memory leak" means in Java.

Is Go subject to the same subtle memory-leaks that Java is?
Creating a memory leak in Java

In the first article there was a view expressed that a "memory leak" is when an application holds references to objects which are no longer needed. Another view was that the JVM itself doesn't have memory leaks.

In the second article there were many examples of how the JVM could be used to hide away memory usage or operations which would consume memory. Examples included File.deleteOnExit(), creating large static fields, discarded sockets, file handles, threads, JDBC connection which you don't need.

The File.deleteOnExit on exit must use some memory to be able to perform its task. This is not a leak in my option as it is not retaining memory which is not needed.

Having static fields and threads which you don't need will waste memory and this is bug which the JVM cannot correct for.

However, creating sockets, file handles, and JDBC connections the JVM does handle. When the finalize() method is called, these resources are cleaned up.

Diagnosing excess memory consumption

If you have a system which is getting an OutOfMemoryError, you can add -XX:+HeapDumpOnOutOfMemoryError to generate a heap dump you can analyse with a free profiler like VisualVM, jhat or a commercial profiler like YourKit.

If you want to analyse a running system, you can use jmap which can give you a break down of the biggest consuming classes or a full heap dump.

Conclusion

In Java it is meaningful to refer to objects which are retained and are not longer needed as a "memory leak".

There is nothing in the Java language which is prone to this problem and the JRE libraries do protect themselves from bugs in application code.

Your application can still have a memory leak, and you need to make sensible choices about when you still need a resource, in particular a thread and if you hold onto it too long it can mean you have a "memory leak".

Java: What is the limit to the number of threads you can create?

2011-07-18T13:54:00.003+01:00

Overview

I have seen a number of tests where a JVM has 10K threads. However, what happens if you go beyond this?

My recommendation is to consider having more servers once your total reaches 10K. You can get a decent server for $2K and a powerful one for $10K.

Creating threads gets slower

The time it takes to create a thread increases as you create more thread. For the 32-bit JVM, the stack size appears to limit the number of threads you can create. This may be due to the limited address space. In any case, the memory used by each thread's stack add up. If you have a stack of 128KB and you have 20K threads it will use 2.5 GB of virtual memory.

Bitness	Stack Size	Max threads
32-bit	64K	32,073
32-bit	128K	20,549
32-bit	256K	11,216
64-bit	64K	stack too small
64-bit	128K	32,072
64-bit	512K	32,072

Note: in the last case, the thread stacks total 16 GB of virtual memory.

Java 6 update 26 32-bit,-XX:ThreadStackSize=64

4,000 threads: Time to create 4,000 threads was 0.522 seconds 
8,000 threads: Time to create 4,000 threads was 1.281 seconds 
12,000 threads: Time to create 4,000 threads was 1.874 seconds 
16,000 threads: Time to create 4,000 threads was 2.725 seconds 
20,000 threads: Time to create 4,000 threads was 3.333 seconds 
24,000 threads: Time to create 4,000 threads was 4.151 seconds 
28,000 threads: Time to create 4,000 threads was 5.293 seconds 
32,000 threads: Time to create 4,000 threads was 6.636 seconds 
After creating 32,073 threads, java.lang.OutOfMemoryError: unable to create new native thread
 at java.lang.Thread.start0(Native Method)
 at java.lang.Thread.start(Thread.java:640)
 at com.google.code.java.core.threads.MaxThreadsMain.addThread(MaxThreadsMain.java:46)
 at com.google.code.java.core.threads.MaxThreadsMain.main(MaxThreadsMain.java:16)

Java 6 update 26 32-bit,-XX:ThreadStackSize=128

4,000 threads: Time to create 4,000 threads was 0.525 seconds 
8,000 threads: Time to create 4,000 threads was 1.239 seconds 
12,000 threads: Time to create 4,000 threads was 1.902 seconds 
16,000 threads: Time to create 4,000 threads was 2.529 seconds 
20,000 threads: Time to create 4,000 threads was 3.165 seconds 
After creating 20,549 threads, java.lang.OutOfMemoryError: unable to create new native thread
 at java.lang.Thread.start0(Native Method)
 at java.lang.Thread.start(Thread.java:640)
 at com.google.code.java.core.threads.MaxThreadsMain.addThread(MaxThreadsMain.java:46)
 at com.google.code.java.core.threads.MaxThreadsMain.main(MaxThreadsMain.java:16)

Java 6 update 26 32-bit,-XX:ThreadStackSize=128

4,000 threads: Time to create 4,000 threads was 0.526 seconds 
8,000 threads: Time to create 4,000 threads was 1.212 seconds 
After creating 11,216 threads, java.lang.OutOfMemoryError: unable to create new native thread
 at java.lang.Thread.start0(Native Method)
 at java.lang.Thread.start(Thread.java:640)
 at com.google.code.java.core.threads.MaxThreadsMain.addThread(MaxThreadsMain.java:46)
 at com.google.code.java.core.threads.MaxThreadsMain.main(MaxThreadsMain.java:16)

Java 6 update 26 64-bit,-XX:ThreadStackSize=128

4,000 threads: Time to create 4,000 threads was 0.577 seconds 
8,000 threads: Time to create 4,000 threads was 1.292 seconds 
12,000 threads: Time to create 4,000 threads was 1.995 seconds 
16,000 threads: Time to create 4,000 threads was 2.653 seconds 
20,000 threads: Time to create 4,000 threads was 3.456 seconds 
24,000 threads: Time to create 4,000 threads was 4.663 seconds 
28,000 threads: Time to create 4,000 threads was 5.818 seconds 
32,000 threads: Time to create 4,000 threads was 6.792 seconds 
After creating 32,072 threads, java.lang.OutOfMemoryError: unable to create new native thread
 at java.lang.Thread.start0(Native Method)
 at java.lang.Thread.start(Thread.java:640)
 at com.google.code.java.core.threads.MaxThreadsMain.addThread(MaxThreadsMain.java:46)
 at com.google.code.java.core.threads.MaxThreadsMain.main(MaxThreadsMain.java:16)

Java 6 update 26 64-bit,-XX:ThreadStackSize=512

4,000 threads: Time to create 4,000 threads was 0.577 seconds 
8,000 threads: Time to create 4,000 threads was 1.292 seconds 
12,000 threads: Time to create 4,000 threads was 1.995 seconds 
16,000 threads: Time to create 4,000 threads was 2.653 seconds 
20,000 threads: Time to create 4,000 threads was 3.456 seconds 
24,000 threads: Time to create 4,000 threads was 4.663 seconds 
28,000 threads: Time to create 4,000 threads was 5.818 seconds 
32,000 threads: Time to create 4,000 threads was 6.792 seconds 
After creating 32,072 threads, java.lang.OutOfMemoryError: unable to create new native thread
 at java.lang.Thread.start0(Native Method)
 at java.lang.Thread.start(Thread.java:640)
 at com.google.code.java.core.threads.MaxThreadsMain.addThread(MaxThreadsMain.java:46)
 at com.google.code.java.core.threads.MaxThreadsMain.main(MaxThreadsMain.java:16)

The Code

MaxThreadsMain.java

Java: Getting the size of an Object

2011-07-16T17:18:00.004+01:00

Overview

Java was designed with the principle that you shouldn't need to know the size of an object. There are times when you really would like to know and want to avoid the guess work.

Measuring how much memory an object uses

There are three factors which make measuring how much an object uses difficult.

The TLAB allocates blocks of memory to a thread. This means small amount of memory don't appear to reduce the free memory. If you do this repeatedly, you will see a block of free memory be used. The way around this is to turn off the TLAB. -XX:-UseTLAB
A GC can occur while you are creating your object. This will result in more free memory at the end than when you started. I ignore any negative sizes in this test ;)
Other threads in the system could use memory at the same time. I perform multiple test and take the median, which removes any outliers.

Size of objects in a 32-bit JVM

Running this SizeofTest, with on 32-bit Sun/Oracle Java 6 update 26, -XX:-UseTLAB I get

The average size of an int is 4.0 bytes
The average size of an Object is 8.0 bytes
The average size of an Integer is 16.0 bytes
The average size of a Long is 16.0 bytes
The average size of an AtomicReference is 16.0 bytes
The average size of an SimpleEntry(Map.Entry) is 16.0 bytes
The average size of a DateTime is 24.0 bytes
The average size of a Calendar is 424.0 bytes
The average size of an Exception is 400.0 bytes
The average size of a bit in a BitSet is 0.125 bytes

Looking a the size of Long confirms the size of header/Object being 8 bytes.

Size of objects with 32-bit references

Running this SizeofTest, with 32-bit references On Sun/Oracle Java 6 update 26, -XX:+UseCompressedOops -XX:-UseTLAB I get

The average size of an int is 4.0 bytes
The average size of an Object is 16.0 bytes
The average size of an Integer is 16.0 bytes
The average size of a Long is 24.0 bytes
The average size of an AtomicReference is 16.0 bytes
The average size of an SimpleEntry(Map.Entry) is 24.0 bytes
The average size of a DateTime is 24.0 bytes
The average size of a Calendar is 448.0 bytes
The average size of an Exception is 440.0 bytes
The average size of a bit in a BitSet is 0.125 bytes

Objects are 8-byte aligned on this JVM, and you could conclude from the size of an Integer that the header is 12-bytes in size.

Size of objects with 64-bit references

Running the same test with 64-bit references. i.e. -XX:-UseCompressedOops -XX:-UseTLAB

The average size of an int is 4.0 bytes
The average size of an Object is 16.0 bytes
The average size of an Integer is 24.0 bytes
The average size of a Long is 24.0 bytes
The average size of an AtomicReference is 24.0 bytes
The average size of an SimpleEntry(Map.Entry) is 32.0 bytes
The average size of a DateTime is 32.0 bytes
The average size of a Calendar is 544.0 bytes
The average size of an Exception is 648.0 bytes
The average size of a bit in a BitSet is 0.125 bytes

From looking at the size of a Long, confirms the size of the header/Object is 16 bytes in length.

The code for the SizeofUtil

The code for the SizeofUtil is here

30,000 hits last month.

2011-07-15T07:13:00.000+01:00

I keep expecting interest to wane, but it is still growing.

I have lots more ideas for articles on back to basics Java. :)

BTW; I apologise for my English. If you see any typos or bad grammar don't be afraid to tell me.

If you have any suggestions for articles you would like to see or you have seen an article you think I should review, let me know.

peter.lawrey (a) gmail.com

Incorrect Core Java Interview Answers

2011-07-14T16:01:00.011+01:00

Overview

On the Internet, Java interview questions and answers get copied from one web site to another. This can mean that an incorrect or out of date answer might never be corrected. Here are some questions and answer which are not quite correct or are now out of date. i.e. are pre Java 5.0.

How many ways can an argument be passed to a subroutine and explain them?

An argument can be passed in two ways. They are passing by value and passing by reference. Passing by value: This method copies the value of an argument into the formal parameter of the subroutine. Passing by reference: In this method, a reference to an argument (not the value of the argument) is passed to the parameter.

Java only supports Pass-By-Value. You can pass a reference by value, but you cannot pass by reference in Java. Java references can be described as Call By Sharing but this is not commonly used.

What is Garbage Collection and how to call it explicitly?

When an object is no longer referred to by any variable, java automatically reclaims memory used by that object. This is known as garbage collection. System. gc() method may be used to call it explicitly.

An object is eligible for cleanup when it no longer has a strong reference from a Root context. An object which has a weak or soft reference can be cleaned up. An object without a strong reference might not be cleaned up (i.e. there is no guarentee a GC will be run and a minor GC will not clean up tenured objects)

System.gc() is a hint that a Full GC should be run. This can be disabled using a command line option.

What are Transient and Volatile Modifiers?

Transient: The transient modifier applies to variables only and it is not stored as part of its object’s Persistent state. Transient variables are not serialized. Volatile: Volatile modifier applies to variables only and it tells the compiler that the variable modified by volatile can be changed unexpectedly by other parts of the program.

transient can only be applied to fields and cannot be applied to local variables. It can be applied to static variables but will be generally ignored. Transient fields are not serialized automatically, but can be serialized by custom serialization e.g. writeObject and readObject()

volatile can only be applied to fields and the tell the JIT rather than the compiler that every access must get a cache coherent copy of the field. (Notionally from "main" memory)

Explain the usage of the keyword transient?

This keyword indicates that the value of this member variable does not have to be serialized with the object. When the class will be de-serialized, this variable will be initialized with a default value of its data type (i.e. zero for integers).

This keyword means the field cannot be serialized automatically. It is not de-serialized automatically leaving the default value for the field. The default for Integer is null. The default for int is 0

What is method overloading and method overriding?

Method overloading: When a method in a class having the same method name with different arguments is said to be method overloading. Method overriding : When a method in a class having the same method name with same arguments is said to be method overriding.

Method overloading occurs when two methods have the same name but different signatures. The signature includes the parameter types and generic type. A single method can be called with different arguments and two overloaded methods can be called with the same arguments. i.e. its the signature not the arguments which matter.

Method overriding only occurs when a sub-class has the same signature as a method in a parent class.

It is worth clarifying that the return type is not part of the signature in Java. At the JVM level it is and covariant return types are implemented with generated method.

What is the difference between Integer and int

a) Integer is a class defined in the java. lang package, whereas int is a primitive data type defined in the Java language itself. Java does not automatically convert from one to the other. b) Integer can be used as an argument for a method that requires an object, whereas int can be used for calculations.

An Integer is a reference to an object which wraps an int The key difference since autoboxing and unboxing was added is that an Integer can be null and the == operator compares references for Integer and the actual values for an int type.

Integer i1 = 1;
Integer i2 = 1;
// true as the same autoboxed Integer is used.
System.out.println(i1 == i2); 

Integer i3 = -200;
Integer i4 = -200;
// false as different autoboxed Integer objects are used.
System.out.println(i3 == i4);

i3 == i4 is false as new Integer(int) is called by Integer.valueOf(int) which does the autoboxing.

Note: On the Sun/Oracle JVM the maximum value of integer cached defaults to 127, however it can be increased with the -XX:AutoBoxCacheMax= or -Djava.lang.Integer.IntegerCache.high= options. Thank you @Pedro Kowalski.

What are the different states of a thread ?

The different thread states are ready, running, waiting and dead.

Since Java 5.0, which should be most Java systems under development, the Thread.State class lists the threads possible states as

NEW
A thread that has not yet started is in this state.

RUNNABLE
A thread executing in the Java virtual machine is in this state.

BLOCKED
A thread that is blocked waiting for a monitor lock is in this state.

WAITING
A thread that is waiting indefinitely for another thread to perform a particular action is in this state.

TIMED_WAITING
A thread that is waiting for another thread to perform an action for up to a specified waiting time is in this state.

TERMINATED
A thread that has exited is in this state.

Which is the base class for all classes?

java.lang.Object

This is true for custom classes. For primitive types such as int.class, void.class and Object itself have no super class.

Class parent = boolean.class.getSuperclass(); // returns null

What is daemon thread?

Theards [sic] which are running on the background are called deamon threads. daemon thread is a thread which doesn't give any chance to run other threads once it enters into the run state it doesn't give any chance to run other threads.

A Daemon thread is any thread which will not prevent the JVM from shutting down. Any thread can be considered a "background" thread. Daemon threads are given the same priority as non-Daemon threads (based on their priority) When a daemon thread is running it doesn't prevent another thread from running any differently from a non-daemon thread running.

Daemon thread is a low priority thread which runs intermittently in the back ground doing the garbage collection operation for the java runtime system.

The garbage collector is an example of a daemon thread. A daemon thread can have a high priority and it can run all the time.

What are the restrictions placed on the values of each case of a switch statement?

At compile time, each case values of switch statement must evaluate to a an int value

From Java 5.0, switching on an enum is supported and from Java 7, switching on a String is supported.

What is a Java Bean?

A Java Bean is a software component that has been designed to be reusable in a variety of different environments.

IMHO: This answer is vague and could be talking about anything.

A Java Bean is a "Java Object that is serializable, has a nullary constructor, and allows access to properties using getter and setter methods."

Why would you use a synchronized block vs. synchronized method?

Synchronized blocks place locks for shorter periods than synchronized methods.

This can be true but is not guaranteed. Often synchronized blocks are used to hold a lock over multiple calls to an object with synchronized methods. IMHO the most common use for synchronized blocks is locking on another object other than this

Map<Key, Value> map = Collections.synchronizedMap(new LinkedHashMap<Key, Value>());
// perform multiple operations in a thread safe manner
synchronized(map) {
    Value value = map.get(key);
    if (value == null)
        map.put(key, value = new Value(key));
    return value;
}

Which one is faster in Java ?

for(int i = 100000; i > 0; i--) {}

for(int i = 1; i < 100001; i++) {}

Answer: Which ever is run second with be fastest. The server JVM can detect and eliminate loops which don't do anything. A method with either loop is compiled when the loop iterates about 10,000 times. (Based on -XX:CompileThreshold=10000) The first loop will take time to detect it doesn't do anything, however the second will have been compiled.

Which Java operator is right associative?

The = operator is right associative.

According to http://introcs.cs.princeton.edu/java/11precedence/ the list of right to left associative operators are. (A lot more than one)

( ) cast
new Object
? :
assignment = += -= *= /= %= &= ^= |= <<= >>= >>>=

What class of exceptions are generated by the Java run-time system?

The Java runtime system generates RuntimeException and Error exceptions.

IMHO: This an answer to a different question. This is an answer to; what are the super classes of runtime, unchecked exceptions?

The Java runtime can generate an Error, Exception or RuntimeException.

Links to this page

http://news.ycombinator.com/item?id=2789570

http://news.ycombinator.com/item?id=2793399

http://www.javacodegeeks.com/2011/07/incorrect-core-java-interview-answers.html

http://java.dzone.com/articles/incorrect-core-java-interview

http://www.dzone.com/links/15_incorrect_yet_popular_core_java_interview_answ.html?ref=ps

http://news.ycombinator.com/item?id=2789570

http://www.softwareservices.com/news/15833/incorrect-core-java-interview-answers/

http://www.dzone.com/links/rss/incorrect_core_java_interview_answers.html

Java Secret: Generated methods

2011-07-14T13:38:00.000+01:00

Overview

The Java compiler generates extra methods which appear in stack traces. These can be confusing at first. What are they and why do they exist?

The access model in the JVM

The access model in the JVM has not changed significantly since version 1.0. However, Java 5.0 added features such as inner/nested classes and convariant return types which were not in the original design. So how are they supported?

The issue with nested classes

Nested classes can access private methods and fields of an outer class. However the JVM does not support this so the compiler generates methods as a workaround.

Private Methods

In this example, the inner class calls a private method init() of the outer class.

public class PrivateMethod { // line 4
    private void init() {
        throw new UnsupportedOperationException(); // line 6
    };

    class Inner {
        Inner() {
            init();
        }
    }

     public static void main(String... args) {
        PrivateMethod pm = new PrivateMethod();
        Inner inner = pm.new Inner();
    }
}

So what does the stack trace look like when we run this?

Exception in thread "main" java.lang.UnsupportedOperationException
 at com.google.code.java.core.javac.generated.PrivateMethod.init(PrivateMethod.java:6)
 at com.google.code.java.core.javac.generated.PrivateMethod.access$000(PrivateMethod.java:4)
 at com.google.code.java.core.javac.generated.PrivateMethod$Inner.(PrivateMethod.java:11)
 at com.google.code.java.core.javac.generated.PrivateMethod.main(PrivateMethod.java:17)

In the stack trace there is a method called access$000 on line 4 which is the first line of the class. Is this a real method? What do we see in the byte code?

$ javap -c -private -classpath . com.google.code.java.core.javac.generated.PrivateMethod

static void access$000(com.google.code.java.core.javac.generated.PrivateMethod);
  Code:
   0:   aload_0
   1:   invokespecial   #1; //Method init:()V
   4:   return

$ javap -c -private -classpath . com.google.code.java.core.javac.generated.PrivateMethod\$Inner
Compiled from "PrivateMethod.java"
public class com.google.code.java.core.javac.generated.PrivateMethod$Inner extends java.lang.Object{
final com.google.code.java.core.javac.generated.PrivateMethod this$0;

com.google.code.java.core.javac.generated.PrivateMethod$Inner(com.google.code.java.core.javac.generated.PrivateMethod);
  Code:
   0:   aload_0
   1:   aload_1
   2:   putfield        #1; //Field this$0:Lcom/google/code/java/core/javac/generated/PrivateMethod;
   5:   aload_0
   6:   invokespecial   #2; //Method java/lang/Object."":()V
   9:   aload_1
   10:  invokestatic    #3; //Method com/google/code/java/core/javac/generated/PrivateMethod.
                        access$000:(Lcom/google/code/java/core/javac/generated/PrivateMeth
   13:  return

}

The compiler has added a static method which is not private so the Inner class can access the private method of the outer class indirectly.

Private Fields

Private fields are accessed via a getter and setter, but the compiler can generate methods for assignment operations such as ++ and *=

public class PrivateField {
    private int num = 0;

    public class Inner {
        public void set(int n) {
            num = n;
        }

        public int get() {
            return num;
        }

        public void increment() {
            num++;
        }

        public void multiply(int n) {
            num *= n;
        }
    }
}

Compiles with four generated methods, one for each of get, set, ++ and *=

$ javap -c -private -classpath . com.google.code.java.core.javac.generated.PrivateField
setter
static int access$002(com.google.code.java.core.javac.generated.PrivateField, int);
  Code:
   0:   aload_0
   1:   iload_1
   2:   dup_x1
   3:   putfield        #1; //Field num:I
   6:   ireturn

getter
static int access$000(com.google.code.java.core.javac.generated.PrivateField);
  Code:
   0:   aload_0
   1:   getfield        #1; //Field num:I
   4:   ireturn

increment ++
static int access$008(com.google.code.java.core.javac.generated.PrivateField);
  Code:
   0:   aload_0
   1:   dup
   2:   getfield        #1; //Field num:I
   5:   dup_x1
   6:   iconst_1
   7:   iadd
   8:   putfield        #1; //Field num:I
   11:  ireturn

multiplier *=
static int access$028(com.google.code.java.core.javac.generated.PrivateField, int);
  Code:
   0:   aload_0
   1:   dup
   2:   getfield        #1; //Field num:I
   5:   iload_1
   6:   imul
   7:   dup_x1
   8:   putfield        #1; //Field num:I
   11:  ireturn

Covariant return types

Covariant return types is a feature which was added to Java 5.0 but isn't supported in the JVM. For this reason, the compiler generates a method which overrides all the super methods and their return types.

public class CovariantReturnTypeA {
    public Object method() { return 1L; }
}

public class CovariantReturnTypeB extends CovariantReturnTypeA {
    public Number method() { return 2.0; }
}

public class CovariantReturnTypeC extends CovariantReturnTypeB {
    public Integer method() { return 3; }
}

The last method() overrides the method which returns Number and the method which returns Object. To implement this, the compile generates a method with the same signature which calls the method which returns Integer

$ javap -c -private -classpath . com.google.code.java.core.javac.generated.CovariantReturnTypeC

public java.lang.Integer method();
  Code:
   0:   iconst_3
   1:   invokestatic    #2; //Method java/lang/Integer.valueOf:(I)Ljava/lang/Integer;
   4:   areturn

public java.lang.Number method();
  Code:
   0:   aload_0
   1:   invokevirtual   #3; //Method method:()Ljava/lang/Integer;
   4:   areturn

public java.lang.Object method();
  Code:
   0:   aload_0
   1:   invokevirtual   #3; //Method method:()Ljava/lang/Integer;
   4:   areturn

There are three implementations of method() in the byte code.

Performance implications

The performance implications for Java Standard Edition are small as these methods can be inlined and effectively have no impact. In Java Mobile Edition, this might not be the case.

They can cause some confusion and if this is a problem you can make the fields/methods package-local instead and the generated methods will go away.

Java low level: Converting between integers and text (part 2)

2011-07-14T11:09:00.002+01:00

Parsing an integer from text

Parsing an integer is relatively simple depending on how many checks you make. This loop does almost no validation. The input can multiple '-' signs and the number can overflow. As soon as it reaches a character is does not accept to stops. It is left to the caller to check if this character was a valid separartor.

ByteBufferTextLongReader.read()

long num = 0;
boolean negative = false;
while (true) {
    byte b = buffer.get();
//  if (b >= '0' && b <= '9')
    if ((b - ('0' + Integer.MIN_VALUE)) <= 9 + Integer.MIN_VALUE)
        num = num * 10 + b - '0';
    else if (b == '-')
        negative = true;
    else
        break;
}
return negative ? -num : num;

Note: The expression (b >= '0' && b <= '9') has been re-written taking advantage of an underflow to turn this into one comparison.

To follow...

Converting floating point numbers to text

Java low level: Converting between integers and text (part 1)

2011-07-14T10:32:00.009+01:00

Overview

As Java has a number of way to convert an integer to a String, its not something you might have considered writing yourself.

However, there may be situations where you want to do this. One of them is when performance is critical. Java libraries tend to create more objects than are required. Usually this doesn't matter but there are times when you need the system to go faster and reading and writing numbers is a big hit for you.

Performance difference

The following is based on a tests of 128K integers in binary and text formats repeatedly to take an average time to write and read an integer.
Source to run all tests
Source for the examples Scroll down for the Unsafe examples.

On a 2.6 GHz Xeon

Unsafe text: Typically took 41.4 ns to write/read per long.
ByteBuffer direct text: Typically took 63.9 ns to write/read per long.
ByteBuffer heap text: Typically took 68.9 ns to write/read per long.
Print text: Typically took 325.7 ns to write/read per long.
DecimalFormat text: Typically took 645.5 ns to write/read per long.

Unsafe binary: Typically took 4.2 ns to write/read per long.
ByteBuffer binary: Typically took 10.3 ns to write/read per long.
DataStream binary: Typically took 72.1 ns to write/read per long.

On a 3.8 GHz i7

Unsafe text: Typically took 32.1 ns to write/read per long.
ByteBuffer direct text: Typically took 48.4 ns to write/read per long.
ByteBuffer heap text: Typically took 58.4 ns to write/read per long.
Print text: Typically took 205.6 ns to write/read per long.
DecimalFormat text: Typically took 436.8 ns to write/read per long.

Unsafe binary: Typically took 5.0 ns to write/read per long.
ByteBuffer binary: Typically took 17.4 ns to write/read per long.
DataStream binary: Typically took 50.8 ns to write/read per long.

The i7 has a faster clock speed than the Xeon, but a smaller cache. This narrows the gap between the fastest and slowest times. When comparing using a direct ByteBuffer and a heap ByteBuffer, there was little difference on the Xeon, however the direct ByteBuffer was consistently faster on the i7.

In this test, reading/writing integers as text using different approaches varies by as much as 14x. If your integer format is needs to be customised you may need to use DecimalFormat, or write your own.

Note: the faster options for writing/reading text were faster than using the binary DataInput/OutputStream. The stream arranges a long as 8 bytes in big-endian order which is more work than converting the number to text in these cases.

Writing an integer to text

For this example, all integers are treated as long type. There is a small performance advantage in having an int type instead but it is relatively small.

Integer representation

All signed integers, byte, short, int and long are represented as twos-complement Encoding/decoding this format doesn't require any bitwise operations like floating point numbers can to.

Extract the sign

Firstly extract the sign. This is simple to do,

Extracting the sign

if (num < 0) {
   writeByte('-');
   num = -num;
}

There is one edge case here which is Long.MIN_VALUE. Due to two-complement representation, this value is the negative of itself. One way to handle this value is to encode it specially. e.g. have a constant which contains what it should be encoded as. Another approach is to treat Long.MIN_VALUE as an unset value or NaN. Most spreadsheet applications treat an empty field as an unset cell. (This is my preference) Another special value is zero. Other numbers do not have a leading zero, but zero needs to have at least one digit.

Handling 0

if (num == 0) {
    writeByte('0');
    writeByte(SEPARATOR);
} else {

Writing the digits

It can be easier to decode a number from the end. This is the approach I have taken here.

Writing each digit in reverse

// find the number of digits
int digits = ParserUtils.digits(num);
// starting from the end, write each digit
for (int i = digits - 1; i >= 0; i--) {
    // write the lowest digit.
    buffer.put(buffer.position() + i, (byte) (num % 10 + '0'));
    // remove that digit.
    num /= 10;
}
// move the position to after the digits.
buffer.position(buffer.position() + digits);
writeByte(SEPARATOR);

Part 2

Decoding an integer from text

Java: All about 64-bit programming

2011-07-12T11:22:00.005+01:00

Overview

I found this article series very interesting All about 64-bit programming in one place which collects "a lot of links on the topic of 64-bit C/C++ software development."

However some of these issues are relevant to Java and can make a difference.

The size_t in C++ is 64-bit

Java uses the int type for sizes and this doesn't change in a 64-bit JVM. This gives backward compatibility but limits arrays, collections and ByteBuffer's to this size. Generally 2 billion is enough, but as files sizes and memory sizes get larger, the number of situations where it is not will grow over time.

As of mid 2011, for £1K you can buy a PC with 24 GB of memory and for £21K you can buy a server with 512 GB of memory.

This is already a problem for memory mapping a file larger than 2 GB. This can only be done by mapping in a 2 GB window of memory (2^31-1 bytes at a time). This is rather ugly and removes one of memory mapping's key features; transparency.

BTW: I have tried using the underlying library directly using reflection which supports `long` lengths and I could get this working for reading files larger than 2 GB, but not writing.

x64 has more registers than x86

This is be a small advantage. If you are performing a lot of operations using long I have seen about 10% performance improvement.

64-bit JVM can access more memory

This is essential if you need more than 1.2-3.5 GB of memory (depending on the OS). The downside is 64-bit references can increase memory usage and slow performance.

One way to use a 64-bit JVM efficiently is to use the -XX:+UseCompressedOops which uses 32-bit references in a way which can still access 32 GB of memory. It can do this because every object in the Sun/Oracle JVM is allocated on a 8-byte boundary (i.e. the lower 3 bits of the address are 000) By shifting the bits of the 32-bit reference, it can access 4GB * 8 or 32 GB in total. It has been suggested that this should be the default for Java 7.

Link: What 64-bit systems are.

Support for 32-bit programs

Programs written and compiled for a 32-bit JVM will work without re-compilation. However any native libraries used will not. A 64-bit JVM can only load 64-bit native libraries.

Switching between int and long

The int and long types work the same on a 32-bit and 64-bit JVM however if you switch code between int and long you can get some issues.

Long literals may need an ell

With all int literals you can just use the number

int i = 123456789;
long j = 123456789;

However for large numbers an L is required.

long i = 111111111111111L; // a long literal.
long j = 111111111111111l; // using `l` is discouraged as it looks like a 1.

If you have a calculated values you may need to use L

long i = 1 << 40; // i = 256!
long i = 1L << 40; // i = 2^40

The shift operator only takes the lower 5 bits of the shift for 32-bit numbers, and 6 bits for 64-bit values. So the first line is like

long i = 1 << (40 % 32);

Shifting puzzle

A puzzle for you. ;) What does this do for a 32-bit and 64-bit for x?

sign = x >> -1;

64-bit references and Object size

When using 64-bit references, the size of a reference doubles. In the Sun/Oracle JVM the header includes a reference. From the Source for Map.Entry

class MapEntry implements Map.Entry, Cloneable {
       K key;
       V value;

In a 32-bit JVM, the header takes 8 bytes, with each reference, this takes 16 byte total.In a 64-bit JVM with 32-bit references, the header takes 8 + 4 bytes and each reference takes 4 bytes. 8-bytes aligned means it uses (12+4+4 bytes + 4 padding) total: 24 bytes.With 64-bit references, the header uses 16-bytes and each references uses 8 bytes. (16 + 8 + 8) total: 32 bytes.For more details read Java: Getting the size of an Object

Conclusion

Migrating from 32-bit to a 64-bit in Java is relatively easy compared with C/C++ however there are some issues you may need to consider when migrating.

Links to this page

http://java.dzone.com/articles/java-all-about-64-bit

http://www.codeproject.com/News/15990/Java-All-about-64-bit-programming.aspx

Human Readable vs Machine Readable Formats

2011-07-11T10:52:00.004+01:00

Overview

Most file/serialization formats can be broadly broking into two formats, Human Readable Text and Machine Readble Binary. The Human Readable formats have the advantage of being easily understood by a person reading them. Machine readable formats are easier/faster for a machine to encode/decode.

There are formats which attempt to be a little of both. XML, JSon, CSV are examples of these. However these do not achieve close to the performance a binary format can achieve.

Myth: Machine Readable Binary is always more compact than a Human Readable

Binary can be more compact, however the obscurity of its format makes it difficult to ensure every byte counts. i.e. its usually hard enough getting something work. Making it compact as well is an added complication. However with Human Readable formats, determing how the format can be made more compact is more easily understood.

As text:  38 bytes long, [-1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
As binary: 290 bytes long, 
....sr..java.util.ArrayListx.....a....I..sizexp....w.....sr..java.lang.Long;
.....#....J..valuexr..java.lang.Number...........xp........sq.~..........sq.~
..........sq.~..........sq.~..........sq.~..........sq.~..........sq.~
..........sq.~..........sq.~..........sq.~..........sq.~..........x

Even though the first format is more compact, you can immedately see you could drop the [ ] and spaces after the ", " to make it more compact. With the binary formats, it is hard to know where to start.

ComparingHumanReadableToBinaryMain.java

List longs = new ArrayList();
for(long i=-1;i<=10;i++)
    longs.add(i);
String asText = longs.toString();
byte[] bytes1 = asText.getBytes();
System.out.println("As text:  "+ bytes1.length+" bytes long, "+asText);

ByteArrayOutputStream baos = new ByteArrayOutputStream();
ObjectOutputStream oos = new ObjectOutputStream(baos);
oos.writeObject(longs);
oos.close();
byte[] bytes2 = baos.toByteArray();
System.out.println("As binary: "+bytes2.length+" bytes long, "
    +new String(bytes2, 0).replaceAll("[^\\p{Graph}]", "."));

Myth: Machine Readable Binary is always faster than a Human Readable

Its assumed the cost of parsing data in a human readable format always makes it slower, however machine sreadbale formats have to deal with an issue human readbale formats takes for granted, that is byte endianness. For human readable formats the order of digits is fairly obvious, however for machine formats the byte endianess of the data might not match that the natrual byte order of the CPU, leading to a source of overhead (as it has to swap the bytes around)One example of this is using big-endian (e.g. TCP/Network byte order) on a little endian machine e.g. Windows/Linux Intel/AMD. A common class which has this issue is DataInputStream and DataOutputStream which re-arranges the byte order (even if the native byte order matches)For this reason, a fast human readable parse can be as fast or faster.In an earlier article I showed how a Human Readable format could be used to read/write integers 30% faster than using DataInput/DataOuput. Writing human readable data faster than binary.

Myth: Using a Human Readable Format makes it easy to read

Just using a human readable format doesn't mean it will be easier to read than a machine readable format. Reusing existing tools as much as possible makes human readable format preferrable. However, machine readable formats can come with tools which decode the data and make maintain it easier. If you have data which can only be managed with the use of specialist tools, being human readable is not much advantage.Images are a good example of where a machine readable format is the best option. It is hard to image editing or viewing an image without the need for a specialist tool. A practical human readable format would undoubtably lower the quality of the image. ;)

________/.- ,’_______`-. \
_________\ /`__________\’/
_________ /___’a___a`___\
_________|____,’(_)`.____ |
_________\___( ._|_. )___ /
__________\___ .__,’___ /
__________.-`._______,’-.__
________,’__,’___`-’___`.__`.
_______/____/____V_____\___\_
_____,’____/_____o______\___`.__
___,’_____|______o_______|_____`.
__|_____,’|______o_______|`._____|
___`.__,’_.-\_____o______/-._`.__,’
__________/_`.___o____,’__\_
__.””-._,’_____`._:_,’_____`.,-””._
_/_,-._`_______)___(________’_,-.__\
(_(___`._____,’_____`.______,’___)_)
_\_\____\__,’________`.____/.___/_/

On the other hand human readable formats can be almost as obscure. This is a piece of code written in a language I am not worthy of mentioning. ;) Its is descibed as "used to list all of the prime numbers between 1 and R"

(!R)@&{&/x!/:2_!x}'!R

Conclusion

If you are designing a file format, start with a human readable one as its much easier to understand. If this is not compact enough, consider compressing it. If it is not fast enough concider making it a binary format, but make sure it really is faster to use such a format. If you are going to use a binary format make sure you have tools in place to supprot viewing (possibly editing) the data (which you would get for free with a text format)

20000 hits last month.

2011-07-08T21:05:00.000+01:00

Thank you for all who read my articles. It encourages me to do more. :)

Low GC in Java: Using primitives

2011-07-08T19:36:00.008+01:00

Overview

In a recent article I examined how using primitives and collections which support primitives natively instead of Wrappers and standard collections can reduce memory usage and improve performance.

Different way to have a Map of int/Integer

There are a number of ways you can use int/Integer and a number of collections you store them in. Depending on which approach you use can have a big difference on the performance and the amount of garbage produced.

Test	Performance Range	Memory used
Use Integer wrappers and HashMap	71 - 134 (ns)	53 MB/sec
Use int primitives and HashMap	45 - 76 (ns)	36 MB/sec
Use int primitives and FastMap	58 - 93 (ns)	28 MB/sec
Use int primitives and TIntIntHashMap	18 - 28 (ns)	nonimal
Use int primitives and simple hash map	6 - 9 (ns)	nonimal

The performance range was the typical (50%tile) and one of the higher (98%tile) timings. The garbage was the result of 900,000 loops per second.

These tests were run on my new system.

The Code

Loop tested

int runs = 300 * 300;
for (int i = 0; i < runs; i++) {
    int x = i % 300;
    int y = i / 300;
    int times = x * y;
    Integer count = counters.get(times);
    if (count == null)
        counters.put(times, 1);
    else
        counters.put(times, count + 1);
}

Link to all the code is here

Directory of performance examples

World's first commercial quantum computer

2011-07-08T14:45:00.000+01:00

There is news of the World's first commercial quantum computer sold to Lockheed Martin You get a 128 qubit computer for $10 million. Since this computer works on different paradigms, its likely it will need a new programming language to describe the problem.

New toy for home

2011-07-07T11:17:00.002+01:00

I have set up a new PC for home. Its got

An Intel i7 running at 3.8 GHz
24 GB of 1600 MHz memory.
120 GB SSD drive
Two 20" screens.
Ubuntu 11.04 64-bit.

It cost me just over £1K incl tax.

I will be using this as a based system to benchmark in future articles.

With lots of memory and a flash disk it does pretty much everything immediately. ;)

If you want look at a good range of overclocked processors up to 4.8 GHz try Scan's Overclocked Bundles

Vanilla #Java

"Java Sucks" revisited

Overview

Review of short comings

Java doesn't have free().

lexically scoped local functions

No macro system

Explicitly Inlined functions

I find lack of function pointers a huge pain

The fact that static methods aren't really class methods is pretty dumb

It's far from obvious how one hints that a method should be inlined, or otherwise go real fast

Two identical byte[] arrays aren't equal and don't hash the same

Hashtable/HashMap does allow you to provide a hashing function

iterate the characters in a String without implicitly involving half a dozen method calls per character

overhead added by Unicode support in those cases where I'm sure that there are no non-ASCII characters.

Interfaces seem a huge, cheesy copout for avoiding multiple inheritance; they really seem like they were grafted on as an afterthought.

There's something kind of screwy going on with type promotion

You can't write a function which expects and Object and give it a short

it's a total pain that one can't iterate over the contents of an array without knowing intimate details about its contents

The only way to handle overflow is to use BigInteger (and rewrite your code)

I miss typedef

I think the available idioms for simulating enum and :keywords are fairly lame

there's no efficient way to implement `assert'

By having `new' be the only possible interface to allocation, ... there are a whole class of ancient, well-known optimizations that one just cannot perform.

The finalization system is lame.

Relatedly, there are no ``weak pointers.''

You can't close over anything but final variables in an inner class!

The access model with respect to the mutability (or read-only-ness) of objects blows

The language also should impose the contract that literal constants are immutable.

The locking model is broken.

There is no way to signal without throwing

Doing foo.x should be defined to be equivalent to foo.x(),

The notion of methods "belonging" to classes is lame.

Libraries

It comes with hash tables, but not qsort

String has length+24 bytes of overhead over byte[]

String.substring can be a source of "memory leak"

The file manipulation primitives are inadequate

here is no robust way to ask ``am I running on Windows'' or ``am I running on Unix.'

There is no way to access link() on Unix, which is the only reliable way to implement file locking.

There is no way to do ftruncate(), except by copying and renaming the whole file.

Is "%10s %03d" really too much to ask?

A RandomAccessFile cannot be used as a FileInputStream or FileOutputStream

markSupported is stupid

What in the world is the difference between System and Runtime?

What in the world is application-level crap like checkPrintJobAccess() doing in the base language class library

Demonstrating when volatile is required

Overview

An example

The code

The solution

Why does this fail

Another Shifty Challenge

Overview

Over shifting

A puzzle

See if you can work it out without running the code.

Shifting Challenge

Overview

Getting the sign

Is a power of two

Unsigned Challenge

Overview

The challenge

Java Thread Affinity support for ExecutorService

Overview

Example

Related topics

Java Thread Affinity support for hyper threading.

Overview

A solution to get the best of both worlds

Example

How does this look in code

Related topics

Surprising results of autoboxing

Overview

== and equals may or may not match

The performance improvements

Auto-boxed objects don't get garbage collected

Don't use auto-boxed object for as locks