23 April 2014

What to do when you get "Comparison method violates its general contract!"

Java 7 switched to a new sort algorithm - called ComparableTimSort. The old algorithm would silently ignore when you violate the Comparator/Comparable contract. The new one throws an exception "Comparison method violates its general contract!"

The contract is in the interface Comparable. The most common is to break the transitive contract. That is: If A < B and B < C, than A should be less than C. Stackoverflow.com has several posts on the issue.

I have made a small program that detects what elements that causes this issue. It only works for small lists but has helped me to debug compareTo()/compare() methods.

package se.lesc.blog;

import java.util.Comparator;

public class TransitivityTester {

    public static void transitivityTester(Object list[]) {
        transitivityTester(list, null);
    }
    
    /** Check that a lists compareTo() method is correct with respect to transitivity */    
    public static void transitivityTester(Object list[], Comparator<Object> comparator) {

        //Cache all possible comparison (for speed)
        byte[][] compareTable = new byte[list.length][];
        for (int x = 0; x < list.length; x++) {
            byte[] column = new byte[list.length];
            compareTable[x] = column;
            for (int y = 0; y < list.length; y++) {
                int result;
                if (comparator != null) {
                    result = comparator.compare(list[x], list[y]);    
                } else {
                    @SuppressWarnings("unchecked")
                    Comparable<Object> comparableX = (Comparable<Object>)list[x];
                    result = comparableX.compareTo(list[y]);
                }
                
                byte normalizedResult = normalize(result);
                column[y] = normalizedResult; 
            }
        }
        
        //Expensive O(n^3) iteration
        for (int a = 0; a < list.length; a++) {
            for (int b = 0; b < list.length; b++) {
                for (int c = 0; c < list.length; c++) {

                    if (compareTable[a][b] < 0 && compareTable[b][c] < 0) {
                        if (! (compareTable[a][c] < 0)) {
                            transitiveError("A < B && B < C but not A < C", a, b, c);
                        }
                    } else if (compareTable[a][b] > 0 && compareTable[b][c] > 0) {
                        if (! (compareTable[a][c] > 0)) {
                            transitiveError("A > B && B > C but not A > C", a, b, c);
                        }
                    } else if (compareTable[a][b] == 0 && compareTable[b][c] == 0) {
                        if (! (compareTable[a][c] == 0)) {
                            transitiveError("A == B && B == C but not A == C", a, b, c);
                        }
                    }
                }
            }
        }
    }
    
    private static void transitiveError(String transitiveRule, int a, int b, int c) {
        String errorMessage =
                        transitiveRule +
                        " (A = " + a + ", B= " + b + ", C = " + c + ") " + 
                        "Comparison method violates its general contract!";
        throw new IllegalArgumentException(errorMessage);
    }

    private static byte normalize(int result) {
        byte normalizedResult;
        if (result > 0) {
            normalizedResult = 1;
        } else if (result < 0) {
            normalizedResult = -1;
        } else {
            normalizedResult = 0;
        }
        return normalizedResult;
    }
}

Here is some test code for the above class:
package se.lesc.blog;

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

import org.junit.Before;
import org.junit.Test;

public class TransitivityTesterTest {

    private List<Integer> list;

    @Before
    public void setUp() {
        list = new ArrayList<Integer>();
        list.add(1);
        list.add(2);
        list.add(3);
    }

    @Test
    public void testNormalIntegerListShouldWork() {
        TransitivityTester.transitivityTester(list.toArray(new Integer[0]));        
    }
    
    @Test
    public void testCrazyOneIsAlwaysMoreComparator() {
        TransitivityTester.transitivityTester(list.toArray(new Integer[0]), new CrazyOneIsAlwaysMoreComparator());        
    }
    
    @Test
    public void testCrazyAllIsOneComparator() {
        TransitivityTester.transitivityTester(list.toArray(new Integer[0]), new CrazyAllIsOneComparator());        
    }
    
    public static class CrazyOneIsAlwaysMoreComparator implements Comparator<Object> {
        @Override
        public int compare(Object o1, Object o2) {
            Integer i1 = (Integer) o1;
            Integer i2 = (Integer) o2;
            if (i1.intValue() == 1) {
                return 1; 
            } else {
                return i1.compareTo(i2);
            }
        }
    }
    
    public static class CrazyAllIsOneComparator implements Comparator<Object> {
        @Override
        public int compare(Object o1, Object o2) {
            Integer i1 = (Integer) o1;
            Integer i2 = (Integer) o2;
            if (i1.intValue() == 1 || i2.intValue() == 1) {
                return 0; 
            } else {
                return i1.compareTo(i2);
            }
        }
    }
}

15 January 2014

More Btrace debugging

In the post http://blog.lesc.se/2009/06/btrace-debugging-tool-with-bugs.html I wrote about how it is possible to debug a running Java application. Here is some more magic.

Let say you have this simple program:

import javax.swing.JFrame;

public class SimpleApp {
  public static void main(String args[]) {
    JFrame frame = new JFrame("Simple application");
    frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
    frame.setSize(200, 100);
    frame.setVisible(true);
  }
}


And this Btrace script:
import com.sun.btrace.annotations.*;
import static com.sun.btrace.BTraceUtils.*;
import java.awt.EventQueue;
import java.awt.AWTEvent;
import java.awt.event.MouseEvent;
import java.lang.reflect.Field;

@BTrace
public class SimpleAppMouseTracer {
  @OnMethod(
     clazz="java.awt.EventQueue",
     method="dispatchEvent"
  )
  public static void onevent(@Self EventQueue queue, AWTEvent event) {
    if (event instanceof MouseEvent) {
      MouseEvent mouseEvent = (MouseEvent) event;
      Field idField = field("java.awt.AWTEvent", "id");
      Field xField = field("java.awt.event.MouseEvent", "x");
      Field yField = field("java.awt.event.MouseEvent", "y");
      if (getInt(idField, mouseEvent) == MouseEvent.MOUSE_CLICKED) {
        println(
          strcat("x = ", strcat(str(getInt(xField, mouseEvent)),
          strcat(", y = ", str(getInt(yField, mouseEvent))))));
      }
    }
  }
}


I have installed the Btrace into Java VisualVM (I downloaded and installed all the visualvm plugins from https://kenai.com/projects/btrace/downloads).

 


Each time I click with the mouse inside the Window I get a printout with the mouse coordinates.

The Btrace code is Java, but with many restrictions. That is why the String creation code gets a bit large; because build in Btrace functions must be used. The same goes for accessing variables inside the MouseEvent object.

08 August 2013

A Java program that triggers the java.lang.OutOfMemoryError: GC overhead limit exceeded

I wanted to test how the -XX:+HeapDumpOnOutOfMemoryError JVM option worked when a JVM goes out of memory, but because of GC overheadlimit. This is my try:

import java.util.ArrayList;
import java.util.Random;
import java.util.Timer;
import java.util.TimerTask;


public class OutOfMemoryProvoker {
    
    private static final int MEMORY_BLOCK_MAX_SIZE = 1000000;
    private static final int REMOVE_BLOCK_FACTOR = 20000;

    public static void main(String[] args) throws Exception {
        final ArrayList<byte[]> list = new ArrayList<byte[]>();
        
        Random random = new Random(0);
        
        Timer timer = new Timer("reportTimer");
        timer.schedule(new TimerTask() {
            @Override
            public void run() {
                report(list);
            }
        }, 5000, 5000);
        
        while (true) {
            int memSize = random.nextInt(MEMORY_BLOCK_MAX_SIZE) + 1;
            
            byte[] memBlock = new byte[memSize];
            list.add(memBlock);
            
            
            int removeBlockIndex = random.nextInt(REMOVE_BLOCK_FACTOR);
            if (list.size() > removeBlockIndex) {
                list.remove(removeBlockIndex);
            }
        }
    }

    private static void report(ArrayList<byte[]> list) {
        System.out.println(list.size());
    }
}

This works very nice. You have to modify the MEMORY_BLOCK_MAX_SIZE and REMOVE_BLOCK_FACTOR to match your memory settings. I used a 8 GB heap for my numbers.

Nice things to note:
  1. Java GC really dislikes different sizes of memory block. This is why I randomize the memory block sizes to provoke as much GC work as possible
  2. The REMOVE_BLOCK_FACTOR controls the chance that a memory block is dereferenced and eligible for GC. It simply removes an item from the list (if the list is big enough). This has the nice characteristic the the chance that a block is removed is higher the more the list is filled.

29 January 2013

Office/Word 2003 in Windows 8

So the Windows 8 Upgrade Assistant tells me that I cannot use Office 2003:
Well I upgraded my Windows 7 to Windows 8 (that is I did NOT perform a clean install). And how does for example Word 2003 work:
Well it turns out that it works just fine! I haven't tried every feature, but everything I have tried appears to work. That includes Excel 2003 and Visio 2003.

17 January 2013

The Eclipse foreach template

There are many "hidden" features in Eclipse that are really good. Today I discovered the foreach template.

It works like this: place your cursor just above a array or Iterable (List) declaration. Press Ctrl + Space and press Enter. Eclipse will now create a for loop that you can use. It will use the Iterable variable that is closest.

Before:

After:

27 June 2012

The ++ operator is not thread safe

Findbugs is great tools for analyzing java code. It can find potential bugs. One of the warnings is the VO: An increment to a volatile field isn't atomic (VO_VOLATILE_INCREMENT). It means that the ++ operator is not an atomic operation and thus not thread safe. To demonstrate this looks at this code:

public class PlusPlusOperatorThreadSaftey {
    @Test
    public void testThreadSaftey() throws InterruptedException {
        class IntegerHolder {
            private volatile int value = 0;
            private void increase() {
                value++;
            }
            private int getValue() {
                return value;
            }
        }
        
        final IntegerHolder integerHolder = new IntegerHolder();
        final int numberOfIncreasePerThread = 50;
        final int numberOfThreads = 100;
        
        ExecutorService threadPool = Executors.newFixedThreadPool(numberOfThreads);
        for (int i = 0; i < numberOfThreads; i++) {
            threadPool.submit(new Runnable() {
                public void run() {
                    for (int i = 0; i < numberOfIncreasePerThread; i++) {
                        integerHolder.increase();
                    }
                }
            });
        }
        
        threadPool.shutdown();
        threadPool.awaitTermination(10, TimeUnit.SECONDS);
        
        assertEquals(integerHolder.getValue(), numberOfIncreasePerThread *
            numberOfThreads);
    }
}
When running this code on my dual core CPU sometimes the test case passes, and sometimes I get:
java.lang.AssertionError: expected:<4998> but was:<5000>. Thus, the ++ operator is not atomic and updates can be lost.

To fix this you could add a synchronized block, but a better approach is to use an AtomicInteger like this:
class IntegerHolder {
        private AtomicInteger value = new AtomicInteger(0);
        private void increase() {
            value.incrementAndGet();
        }
        private int getValue() {
            return value.get();
        }
    }

11 June 2012

Create named "screen"s to continue work later

The Unix command screen is a great command that lets you manage your login sessions. If you for some reasons shares an account with several people or have many different contexts it is useful to crate a named screen session:

lennart@pingvinen:~$ screen -S myScreen

To list all the screens use:
lennart@pingvinen:~$ screen -list
There are screens on:
        14825.myScreen  (2012-06-11 08.15.28)   (Attached)
        14692.pts-0.pingvinen   (2012-06-11 08.13.25)   (Detached)
2 Sockets in /var/run/screen/S-lennart.
Note that  one of the screens are named (the myScreen) and one is unnamed and gets a default name.

To attach to a named screen:
lennart@pingvinen:~$ screen -r myScreen