Thursday, January 24, 2013

Java 7, ulimit, and non-heap memory


A couple of co-workers of mine found the following problem:

Error occurred during initialization of VM
  Could not reserve enough space for object heap
  Could not create the Java virtual machine.

It happened in a batch-job environment where we use ulimit (for all programs, Java or not), in addition to Java's heap specification with -Xms and -Xmx. And it only started happening on a test switch from Java 6 to Java 7.

Now, Java requires memory for more than just heap --- native C malloc in JNI, mmap, and so on. But it also (moreso in Java 7, which is the point of this post) needs some non-heap memory to keep track of the heap itself.

A way to measure this is the following script called trymem:

#!/bin/bash
if [ $# -ne 3 ]; then
    echo "Usage: $0 {javadir} {heap MB} {extra MB}"
    exit 1
fi
javadir=$1
heap_mb=$2
xtra_mb=$3

totl_mb=$[heap_mb+xtra_mb]
totl_kb=$[totl_mb*1024]

ulimit -v $totl_kb

$javadir/bin/java -cp . -Xmx${heap_mb}m -Xms${heap_mb}m MyProgram
status=$?
echo ${heap_mb}+${xtra_mb}:${status}
exit $status

where MyProgram.java is simply

public class MyProgram {
    public static void main(String[] args) {
    }
}

along with a second script called searchmem:

#!/bin/bash

if [ $# -ne 1 ]; then
    echo "Usage: $0 {Java dir}"
    exit 1
fi
javadir=$1

heap_mb=10000
while [ $heap_mb -le 60000 ]; do
    echo -n "$heap_mb "
    xtra_mb=100
    while true; do
        ./trymem $javadir $heap_mb $xtra_mb 1> /dev/null 2> /dev/null
        status=$?
        echo -n .
        if [ $status -eq 0 ]; then
            echo $xtra_mb
            break
        elif [ $xtra_mb -gt $heap_mb ]; then
            echo "> $heap_mb"
            break
        fi
        xtra_mb=$[xtra_mb+100]
    done
    heap_mb=$[heap_mb+5000]
done

The idea is to set ulimit to the heap size, then keep increasing it until the test program can run without error. The difference between Java 6 and Java 7 is significant:

$ ./searchmem /usr/local/jdk/x86_64/jdk1.6.0_35

10000 ....400
15000 ....400
20000 ....400
25000 ....400
30000 .....500
35000 .....500
40000 .....500
45000 .....500
50000 .....500
55000 ......600
60000 ......600

$ ./searchmem /usr/local/jdk/x86_64/jdk1.7.0_9

10000 ........800
15000 ..........1000
20000 .............1300
25000 ..............1400
30000 ................1600
35000 ...................1900
40000 .....................2100
45000 .......................2300
50000 .........................2500
55000 ............................2800
60000 .............................2900
We couldn't find a pronouncement from Oracle regarding minimum ulimit as a function of heap size. But a plot of the above numbers suggests a linear relationship, and a regression (with more densely sampled data in searchmem, stepping heap_mb by 1000 rather than 5000) shows slope 1/24 and intercept 400MB. That is, given a Java heap size in MB, divide it by 24 and add 400 to it to find Java 7's heap-management overhead.

P.S. Thanks to David Craft for syntax highlighting in Blogspot:
http://www.craftyfella.com/2010/01/syntax-highlighting-with-blogger-engine.html

Thursday, January 17, 2013

Threw an exception from a method that throws no exceptions -- wait, what?


Here's a fun little false positive I ran into recently.

Application (ClassBeingTested) believes Library (ClassBeingMocked) throws an exception, but Library really does not.  Yet Application's unit-test case passes! This takes an interplay of JUnit, Jmock, and their use of reflection.

Library:
public interface ClassBeingMocked {
    public void neverThrowsAnException();
}

public class ClassBeingMockedImpl implements ClassBeingMocked {
    public void neverThrowsAnException() {
        System.out.println("ClassBeingMocked: in the method which does not throw an exception");
    }
}

Application:

public class ClassBeingTested {

    private final ClassBeingMocked _them;

    public ClassBeingTested(ClassBeingMocked them) {
        _them = them;
    }

    public void neverThrowsAnExceptionEither() {
        try {
            _them.neverThrowsAnException();
        }
        catch (Exception e) {
            System.out.println("ClassBeingTested#neverThrowsAnExceptionEither: " +
                "caught \"" + e.toString() + "\"");
        }
    }

}

Test code:

public class MyTest {
    private Mockery _mockery;
    private ClassBeingMocked _mockedInstance;
    private ClassBeingTested _testedInstance;

    @Before

    public void setup() {
        _mockery = new Mockery();
        _mockedInstance = _mockery.mock(ClassBeingMocked.class);
        _testedInstance = new ClassBeingTested(_mockedInstance);
    }

    @Test

    public void testMethod() {

        _mockery.checking(new Expectations() {{
            one(_mockedInstance).neverThrowsAnException();
            will(throwException(new Exception("we expect an exception on timeout")));
            }});
        _testedInstance.neverThrowsAnExceptionEither();
       _mockery.assertIsSatisfied();
    }    

}

What prints is:
JUnit version 4.10
..ClassBeingTested#neverThrowsAnExceptionEither: caught "java.lang.IllegalStateException: tried to throw a java.lang.Exception from a method that throws no exceptions"

Time: 0.021

OK (4 tests)

One handy item is the print to stdout in the application's exception handler; without that, the misunderstanding proceeds silently.  Yet this will disappear in logging contexts.

One solution is a narrower catch:  If the application instead does

try { _them.neverThrowsAnException(); } catch (MoreSpecificExceptionType e) { ... }
then this is caught at compile time:
"exception MoreSpecificExceptionType is never thrown in body of corresponding try statement"
This must be used carefully in a catch-all-exceptions server-thread context.

dircolors and dead symlinks


Thanks to a careful coworker, I realized that colored ls wasn't working as usual after an OS upgrade.  Namely, I was getting

$ ls -l
total 4
drwxrwsr-x 2 jkerl jkerl 4096 Sep 20 13:47 actual-dir
lrwxrwxrwx 1 jkerl jkerl   14 Sep 20 13:47 invalid-link -> no-such-target
lrwxrwxrwx 1 jkerl jkerl   10 Sep 20 13:47 valid-link -> actual-dir

rather than the expected

$ ls -l
total 4
drwxrwsr-x 2 jkerl jkerl 4096 Sep 20 13:47 actual-dir
lrwxrwxrwx 1 jkerl jkerl   14 Sep 20 13:47 invalid-link -> no-such-target
lrwxrwxrwx 1 jkerl jkerl   10 Sep 20 13:47 valid-link -> actual-dir

It turns out that I need an explicit eval $(dircolors)in my bash startup.

Monday, January 7, 2013

Cyclic random-number generation using finite fields

I ran across a very nice post the other day, by Jeff Preshing, about generating non-repeating sequences of pseudo-random numbers. All PRNGs have periods (a fact about functions mapping from finite sets to themselves and the Pigeonhole Principle) but there's a difference between state size and output size. E.g. Mersenne twister has a very long period, but with 624-bit state. You can get repeats on the 32-bit outputs -- as Jeff found. It might be nice to get all 2^32 32-bit integers, permuted, without repeats.

Jeff's approach is to use properties of the finite field F_p, for large p near 2^32 -- in particular, 4296967291 is just 5 shy of 2^32 and he worked around that neatly. But there are also finite fields of order p^n for all p and n -- in particular, p=2 and n=32.

The neat thing is that all p^n-1 non-zero elements of a finite field always form a cyclic group -- there is one non-zero number g (many, really) such that all others are powers of it. For example, mod p=11, g=2 is a generator: its successive powers are 2, 4, 8, 16=5, 32=10, 64=9, 128=7, 256=3, 512=6, 1024=1. You can convince yourself that other generators mod 11 are 6, 7, and 8.

For n>1 the arithemetic is a little (although not too much) more involved. You just have to find an irreducible polynomial r of degree n with coefficients mod p -- this plays the role of the prime -- as well as a generator g. The details are here (including Berlekamp's algorithm) but for example one can use r = 0x17bc0cb37 -- a 33-bit number so all the residues have 32 bits -- and g = 0xb139e84d. (I got these particular values using RUFFL, generating random 32-degree polynomials until I found one which is irreducible, and likewise found a g with full period 2^32-1.) Note that if you need period 2^32 rather than 2^32-1 you can special-case that: e.g. if the PNRG gives a maps to f(a) then just use an if-statement to splice in a maps to 0 maps to f(a); maybe pick a = 0xdeadbeef, or anything else.

Jeff used TestU01 to run some statistical tests on his cyclic generator. This is a C library so I used iff2 to try it out.

The generator is simply


int      degr  = 32;
unsigned r     = 0x7bc0cb37;
unsigned g     = 0xb139e84d; // 2 ** 65539
unsigned state = 2;

unsigned f232() {
    state = iff2mul(state, g, r, degr);
    return state;
}

and you can seed it by setting state to anything non-zero.


Using this I found:

* (+) The mathematical theory gives you full period very cleanly.
* (+) You can seed by simply setting the state variable.
* (+) State is only 32 bits (96 if you count r and g).
* (-) To generate a different permutation entirely, you need not just any 32-bit number g but rather one which is a generator.  This makes the parameterization a bit less user-friendly.
* (-) I didn't get as good results with TestU01's SmallCrush suite as Jeff got with his permuteQPR -- tests 1 and 8 have p-value of eps.  More experimenting with r's and g's might give better results.