Double Trouble

I'm writing a maths library in my spare time for fun. I've only got around to matrices but already I am seeing interesting behaviour.

Primarily, my library needs to be fast so I use primitives. My first matrix implementation uses doubles and I'm testing performance by calculating cross products.

I'm using the Caliper microbenchmarking framework to performance test my code with methods that look a little like:

    public int timeMutable2DDoubleMatrixCross(int reps) {

        Mutable2DDoubleMatrix accumulator = null;
        for (int i = 0 ; i < reps ; i++) {
            accumulator = mutable2DDoubleMatrix.cross(mutable2DDoubleMatrix);
        }
        return accumulator == null ? 0 : accumulator.getWidth();
    }

On my machine*, I get a result of  1.299ms (standard deviation of 0.011ms) to run an iteration of my code.

But you know when I wrote other implementations for other primitive types, there was an awful lot of copy, paste and make a minor change going on. Bearing in mind the usual autoboxing caveats I've mentioned before, what if I just changed the interface to use Double but the implementation and the call site were using primitive doubles? Maybe then I could make the code more generic with no loss of performance.

No joy - we still get the overhead of autoboxing. Average call time is now 4.041ms (standard deviation of 0.040ms). The JVM is not going to be fooled.

Ah, well. I was half expecting that and it's still better than using BigDecimal (that was taking 68.354ms per call.)

But what was really interesting is that double was faster than long (typically 1.403ms per call, 0.013ms std dev). That blew out of the water my plan to use inflated longs and then right rotate them to give approximate answers, echoing Kronecker's assertion that "God made natural numbers; all else is the work of man".


This might be because floating point calculations are passed to the Floating Point Unit. "In most computers, floating point arithmetic is usually much slower than integer arithmetic, though on the Intel Pentium it is usually faster because the integer unit was not given the same care as the floating point unit." [1]

As ever, your mileage may vary (YMMV).

* A 1.8 GHz Intel Core i7 running Mac OS X 10.7.5 and using java version 1.6.0_41.

[1] http://mindprod.com/jgloss/floatingpoint.html

Additional reading:
 - interesting read on the history of floating points (http://www.intel.com/standards/floatingpoint.pdf).
 - stats for the i7 processor (http://elrond.informatik.tu-freiberg.de/papers/WorldComp2012/PDP2833.pdf)

Going Atomic with Locks

You might have read about non-blocking algorithms, how the synchronized keyword is so 2012 and how things are much faster if you use atomics. Then, you might have written your own atomic-based locks and discovered that things are no better.

I certainly have. But thanks to this fine book I've learned not only to make them faster but why they're faster.

Test-and-set Locks

Let's take a typical Java lock:


    private ReentrantLock lock = new ReentrantLock();

    @Override
    public void unlock() {
        lock.unlock();
    }

    @Override
    public void lock() {
        lock.lock();
    }

and let's have 100 threads trying to attain the lock to increment an int 50000 time. Naively, I thought this would be efficient:

    private final AtomicBoolean state = new AtomicBoolean(false);
    
    public void lock() {
        while (state.getAndSet(true)) { }
    }


    public void unlock() {
        state.set(false);
    }

It was an order of magnitude slower. The questions are: why is it much slower and how do we improve it?

Herlihy and Shavit [1] call this a TASLock (a test-and-set lock). They describe why it's so slow:

"For simplicity, we consider a typical multiprocessor architecture in which processors communicate by a shared broadcast medium called a bus (like a tiny Ethernet). Both the processors and the memory controller can broadcast on the bus, but only one processor (or memory) can broadcast on the bus at the a time. All processors (and memory) can listen. Today, bus-based architecture are common because they are easy to build, although they scale poorly to large numbers of processors.


"Each processor has a cache, a small high-speed memory where the processor keeps data likely to be of interest. A memory access typically requires orders of magnitude more machine cycles than a cache access... When a processor reads from an address in memory, it first checks whether that address and its contents are present in the cache. If so, then the processor has a cache hit, and can load the value immediately. If not, the the processor has a cache miss, and must find the data either in the memory or in another processor's cache. The processor then broadcasts the address on the bus. The other processors snoop on the bus. If one processor has that address in its cache, then it responds by broadcasting the address and value. If no processor has that address, then the memory responds with the value at theat address.

"Each getAndSet() call is broadcast on the bus. Because all threads must use the bus to communicate with memory, these getAndSet() calls delay all threads, even those not waiting for the lock. Even worse, the getAndSet() call forces other processors to discard their own cached copies of the lock, so every spinning thread encounters a cache miss almost every time, and must use the bus to fetch the new, but unchanged value. Adding insult to injury, when the thread holding the lock tries to release it, it may be delayed because the bus in monopolized by the spinners." [1]

Using the Linux perf command shows the number of bus cycles and cache-misses:


[henryp@corsair Performance]$ perf stat -e cycles,bus-cycles,cache-misses,L1-dcache-load-misses,L1-dcache-store-misses,LLC-load-misses,LLC-store-misses  java -cp bin/ com.henryp.test.concurrent.spin.LockMain

 Performance counter stats for 'java -cp bin/ com.henryp.test.concurrent.spin.LockMain':

   564,815,071,755 cycles                    #    0.000 GHz                     [57.17%]
    16,620,454,218 bus-cycles                                                   [57.18%]
           832,399 cache-misses                                                 [57.19%]
       421,992,129 L1-dcache-misses                                             [57.17%]
        14,457,236 L1-dcache-misses                                             [57.14%]
           247,642 LLC-misses                                                   [57.11%]
           529,972 LLC-misses                                                   [57.14%]

      10.681204987 seconds time elapsed



where LLC is the Last Level Cache (L3 on my machine). Misses to this cache mean a call to RAM.

We'll compare these figures to the other strategies.

Test-and-test-and-set Locks

Herlihy and Shavit propose an improvement that looks something like this:


    private final AtomicBoolean state = new AtomicBoolean(false);
    
    @Override
    public void lock() {
        while (true) {
            while (state.get()) { };
            if (!state.getAndSet(true))
                return;
        }
    }    

    @Override
    public void unlock() {
        state.set(false);
    }

It is somewhat better but not by much (about 25%). The authors call this a TTASLock (test-and-test-and-set lock)

"The first time thread B reads the lock it takes a cache miss, forcing B to block while the value is loaded into B's cache. As long as A holds the lock, B repeatedly rereads the value, but hits in the cache every time. B thus produces no bus traffic, and does not slow down other threads' memory accesses. Moreover, a thread that releases a lock is not delayed by threads spinning on that lock.

"The situation deteriorates, however, when the lock is released. The lock holder releases the lock by writing false to the lock variable, which immediately invalidates the spinners' cached copies. Each one takes a cache miss, rereads the new value, and they all (more-or-less simultaneously) call getAndSet() to acquire the lock. The first to succeed invalidates the others, who must then reread the value, causing a storm of bus traffic. Eventually, the threads settled down once again to local spinning.

"The notion of local spinning, where threads repeatedly reread cached values instead of repeatedly using the bus, is an important principle critical to the design of efficient spin locks." [1]

With this strategy, perf gives figures like:


   412,122,456,391 cycles                    #    0.000 GHz                     [57.19%]
    12,132,558,770 bus-cycles                                                   [57.15%]
           783,803 cache-misses                                                 [57.15%]
       128,832,596 L1-dcache-misses                                             [57.14%]
        11,947,461 L1-dcache-misses                                             [57.16%]
           256,900 LLC-misses                                                   [57.18%]
           560,395 LLC-misses                                                   [57.17%]

       7.813546393 seconds time elapsed

So, although the LLC figures are comparable, there is less bus activity and fewer L1 misses as Herlihy and Shavit suggested.

Back off!

The solution is to implement a back off strategy (since vying for a highly contended lock may be a waste of time). The code the authors suggest looks a lot like the TTASLock, something like this:


    private final AtomicBoolean state = new AtomicBoolean(false);
    
    @Override
    public void lock() {
        while (true) {
            while (state.get()) { backOff(); };
            if (!state.getAndSet(true))
                return;
        }
    }

    @Override
    public void unlock() {
        state.set(false);
    }

    

    private final Random random = new Random();

    public void backOff() throws InterruptedException {
        int delay = random.nextInt(limit);
        limit = Math.min(maxDelay, 2 * (limit == 0 ? 1 : limit));
        Thread.sleep(delay);
    }

This actually makes it faster than Java's built in locks. The results look something like this:

JavaReentrantLock took 459 ms

TTASLockWithBackOff took 321 ms

TTASLock took 8932 ms

TASLock took 12600 ms

Repeatedly running the tests indicate that TTASLock with a backoff is the fastest by a margin of about 25%.

Perf gives figures for this strategy like:

       900,772,793 cycles                    #    0.000 GHz                     [62.65%]

        56,529,667 bus-cycles                                                   [64.05%]

           468,664 cache-misses                                                 [62.47%]

         9,728,368 L1-dcache-misses                                             [60.17%]

         6,039,764 L1-dcache-misses                                             [57.58%]

           173,197 LLC-misses                                                   [57.86%]

           573,249 LLC-misses                                                   [60.75%]

       0.465015535 seconds time elapsed

Now the differences are orders of magnitude. 

Quick Addendum

I initially tried to use Valgrind to analyse what was going on but saw very little difference between the figures (about 4% fewer cache-misses between the best and worst locks). But reading the documentation explains why:

"Valgrind serialises execution so that only one (kernel) thread is running at a time. This approach avoids the horrible implementation problems of implementing a truly multithreaded version of Valgrind, but it does mean that threaded apps never use more than one CPU simultaneously, even if you have a multiprocessor or multicore machine." [2]


[1] The Art of Multiprocessor Programming.

[2] http://valgrind.org/docs/manual/manual-core.html

Dumpster Diving in the JVM

If you're monitoring your application, you might notice the maximum amount of heap memory changing with time. How can this be? Surely the maximum is, well, the maximum and not a moving target?

The JavaDocs for the MemoryUsage defines the maximums as:

"the maximum amount of memory (in bytes) that can be used for memory management. Its value may be undefined. The maximum amount of memory may change over time if defined. The amount of used and committed memory will always be less than or equal to max if max is defined. A memory allocation may fail if it attempts to increase the used memory such that used > committed even if used <= max would still be true (for example, when the system is low on virtual memory)."

In Linux, it's easy to reserve more memory than you can use. For instance:

#include <sys/mman.h>

.

.

size_t sillyAmountOfMemory = 1024 * 1024 * 1024 * 1024; // over 1 terabyte!

printf("About to map %lld bytes\n", sillyAmountOfMemory);

addr = mmap(NULL, sillyAmountOfMemory, PROT_READ | PROT_WRITE,

                MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);

.

.

Meanwhile, in a shell:

[phenry@localhost MyMemoryTestsC]$ ps aux | head -1 ; ps aux | grep MyMemoryTest

USER       PID %CPU %MEM    VSZ   RSS TTY      STAT START   TIME COMMAND

phenry   11905  0.0  0.0 1050452  236 pts/0    S    13:43   0:00 /home/phenry/workspaceGanymedeC/MyMemoryTestsC/Debug/MyMemoryTests

Notice the VSZ value - that's the virtual size of our application:

[phenry@localhost MyMemoryTestsC]$ man ps | grep -A2 VSZ
.
.

       vsz         VSZ       virtual memory size of the process in KiB (1024-byte units). Device mappings are currently excluded; this is subject to change.

This is much more physical memory than I have on this machine:


[phenry@localhost MyMemoryTestsC]$ cat /proc/meminfo | head -1
MemTotal:        1026144 kB

Back to our Java process. Depending on the Garbage Collector being used, the maximum heap size may change to optimize performance. Oracle says:

"The statistics such as average pause time kept by the collector are updated at the end of each collection. The tests to determine if the goals have been met are then made and any needed adjustments to the size of a generation is made. The exception is that explicit garbage collections (e.g., calls to System.gc()) are ignored in terms of keeping statistics and making adjustments to the sizes of generations...

"If the maximum pause time goal is not being met, the size of only one generation is shrunk at a time. If the pause times of both generations are above the goal, the size of the generation with the larger pause time is shrunk first.

"If the throughput goal is not being met, the sizes of both generations are increased."

On a beefier machine, I can see the Parallel Scavenging collector being used. Oracle says of this type of collector:

"The parallel scavenge collector is similar to the parallel copying collector, and collects young generation garbage. The collector is targeted towards large young generation heaps and to scale with more CPUs. It works very well with large young generation heap sizes that are in gigabytes, like 12GB to 80GB or more, and scales very well with increase in CPUs, 8 CPUs or more. It is designed to maximize throughput in enterprise environments where plenty of memory and processing power is available.

"The parallel scavenge collector is again stop-the-world, and is designed to keep the pause down. The degree of parallelism can again be controlled. In addition, the collector has an adaptive tuning policy that can be turned on to optimize the collection. It balances the heap layout by resizing, Eden, Survivor spaces and old generation sizes to minimize the time spent in the collection. Since the heap layout is different for this collector, with large young generations, and smaller older generations, a new feature called "promotion undo" prevents old generation out-of-memory exceptions by allowing the parallel collector to finish the young generation collection."

(As an aside, there have been enhancements in JDK 7:

"The Parallel Scavenger garbage collector has been extended to take advantage of machines with NUMA (Non Uniform Memory Access) architecture. Most modern computers are based on NUMA architecture, in which it takes a different amount of time to access different parts of memory. Typically, every processor in the system has a local memory that provides low access latency and high bandwidth, and remote memory that is considerably slower to access.

"In the Java HotSpot Virtual Machine, the NUMA-aware allocator has been implemented to take advantage of such systems and provide automatic memory placement optimizations for Java applications. The allocator controls the eden space of the young generation of the heap, where most of the new objects are created. The allocator divides the space into regions each of which is placed in the memory of a specific node. The allocator relies on a hypothesis that a thread that allocates the object will be the most likely to use the object. To ensure the fastest access to the new object, the allocator places it in the region local to the allocating thread. The regions can be dynamically resized to reflect the allocation rate of the application threads running on different nodes. That makes it possible to increase performance even of single-threaded applications. In addition, "from" and "to" survivor spaces of the young generation, the old generation, and the permanent generation have page interleaving turned on for them. This ensures that all threads have equal access latencies to these spaces on average." [1])

Now, we connect to our Java process from another Java process and examine the first's MBeans with something like this:


        HashMap map = new HashMap();
        JMXConnector c = JMXConnectorFactory.newJMXConnector(createConnectionURL(host, port), map);
        c.connect();
        Object o = c.getMBeanServerConnection().getAttribute(new ObjectName("java.lang:type=Memory"), "HeapMemoryUsage");
        CompositeData cd = (CompositeData) o;

        Object max = cd.get("max");

.

.

.

This is after we have changed the C++ code in hotspot/src/share/vm/services/management.cpp thus:

// Returns a java/lang/management/MemoryUsage object representing

// the memory usage for the heap or non-heap memory.

JVM_ENTRY(jobject, jmm_GetMemoryUsage(JNIEnv* env, jboolean heap))

.

.

.

        printf("PH: MemoryPool %s has %llu bytes\n", pool->name(), u.max_size());

.

.

        printf("PH: so the total is %llu bytes\n", total_max);

We see output from the JVM that looks like:

PH: MemoryPool PS Survivor Space has 65536 bytes

PH: PSGenerationPool::get_memory_usage: size 1431699456: 

PH: MemoryPool PS Old Gen has 14316601344 bytes

PH: so the total is 21473656832 bytes

when we hit it with the above MBean code. The JVM being monitored has the command line switch -Xmx20g.

Now, when this monitored process starts consuming large amounts of memory, our Java code that is monitoring it prints out:

Tue Apr 09 22:59:42 BST 2013: committed = 18403360768 (17550 mb, 17972032kb), max = 19088801792 (18204 mb, 18641408kb)

Tue Apr 09 22:59:43 BST 2013: committed = 20726546432 (19766 mb, 20240768kb), max = 20726546432 (19766 mb, 20240768kb)

(notice how the maximum changes) and the output from the JVM being monitored indicates a change:

PH: PSYoungGen::resize_spaces

.

.

.

PH: MemoryPool PS Survivor Space has 1179648 bytes

PH: PSGenerationPool::get_memory_usage: size 1431699456: 

PH: MemoryPool PS Old Gen has 14316601344 bytes

PH: so the total is 21473722368 bytes

So the maximum is only the maximum until the next one :-)

[1] Java HotSpot™ Virtual Machine Performance Enhancements

The Case of the Missing Memory

If you start Java with -Xmx512m, you'd expect the max heap size to be 512 megs, right? So, when you connect via JConsole (or JMX) why is the heap size smaller? My JConsole shows a committed and maximum size of the "Heap Memory Usage" as about 491MiB.

I've been fiddling with the OpenJDK source and been putting log statements into it to see how the GC is behaving. So, for instance, I changed:

hotspot/src/share/vm/gc_implementation/parallelScavenge/parallelScavengeHeap.cpp

added:

#include <stdio.h>

and liberally sprinkled the code with statements like:


  printf("PH: ParallelScavengeHeap::initialize: size %d: \n", _reserved.byte_size());

And sure enough, when I run my application, I see the JVM spit out:

PH: ParallelScavengeHeap::initialize: size 536870912: 

So, it's using the collector that is the "default on certain machine types" [1] with the full 512MiB allocated to it. This collector is "targeted towards large young generation heaps and to scale with more CPUs. It works very well with large young generation heap sizes that are in gigabytes, like 12GB to 80GB or more, and scales very well with increase in CPUs, 8 CPUs or more" [2] (I have 16 CPUs and 64GBs, although obviously have not set my heap that high).

Now, when I connect to the JVM and look at the memory usage, I see statements like:

PH: EdenMutableSpacePool::get_memory_usage: size 134217728: 

PH: SurvivorMutableSpacePool::get_memory_usage: size 22347776: 

PH: PSGenerationPool::get_memory_usage: size 357957632: 

since I have changed these C++ classes that can all be found in

hotspot/src/share/vm/services/psMemoryPool.cpp

(Note that these three classes are all the subtypes of CollectedMemoryPool for the PS collector.)

This memory usage totals the 491MiB usage we saw in JConsole but is still exactly 22 347 776 bytes short of the 512MiB we defined at start up time.

The "missing" memory is of course because there are two survivor spaces [3] but since only one has live objects at any point, we only count its size.

[1] Dr Richard Warburton's blog.
[2] Oracle's Improving Java Application Performance and Scalability by Reducing Garbage Collection Times and Sizing Memory Using JDK 1.4.1.
[3] Oracle's Virtual Machine Garbage Collection Tuning.

Multidimensional arrays and Java

There are no true multidimensional arrays in Java. This is Java 101. But why?

I always knew that Java's closest representation was arrays of arrays. This differs from true multidimensional arrays as the length of the second array is not bound. That is, an  M x N multidimensional array can be represented in Java but also, it might be jagged (that is, N is not the same for all M).


        int[][] array2D = new int[2][];

        array2D[0] = new int[] {1,2,3};
        array2D[1] = new int[] {1,2,3,4,5};

        // prints: [[1, 2, 3], [1, 2, 3, 4, 5]]
        System.out.println(Arrays.deepToString(array2D));

        assertEquals(3, array2D[0].length);
        assertEquals(5, array2D[1].length);

In a true multidimensional arrays, each row would have the same length.

This shouldn't be too surprising. But a silly bug this week also highlighted another aspect of why 2 (or more) dimensioned arrays are not true multidimensional arrays.


        int[][] original = new int[10][10];
        assertEquals(0, original[5][5]);
        int[][] copied = original.clone();

        // change element in the '1st dimension'
        copied[4] = new int[] {1, 2, 3, 4, 5};
        assertEquals(2, copied[4][1]);
        assertEquals(0, original[4][1]); // change not seen in the original

        // change element in the '2nd dimension'
        copied[5][5] = 100;
        assertEquals(100, copied[5][5]);
        assertEquals(0, original[5][5]); // fails. change *is* seen in the original

Cloning an array produces a deep copy of the first array but not the elements in it (the other "dimensions"). These other "dimensions" of the array are treated like any other object and are not deep copied. In this way, our "multidimensional" array is just like a 1-D array of any other type of object.

Sorted!

Surprises in SortedSet

There is more information in a collection than its elements. There is also its structure.

For instance, if the elements of a collection were steps in a recipe, the order of these steps is significant. Change the order and your meal may taste bad.

So, if I used a SortedSet to hold the steps in my recipe, I might reasonably assume that this is not the same recipe as one with the same steps but in a different order.

However, in Java this is not true.


        SortedSet sortedSet = new TreeSet();
        addElementsInAnyOrder(sortedSet);
        
        assertOrder(sortedSet); // passes
        
        Set noSortGuarantee = new HashSet();
        addElementsInAnyOrder(noSortGuarantee);
        
        assertEquals(sortedSet, noSortGuarantee);
        
        assertOrder(noSortGuarantee); // fails

TreeSet.equals doesn't take order into account. Indeed, the equals method is in the superclass - the same superclass as HashSet, which has no notion of order.

Consistent With Equals

The JavaDocs say:

"The natural ordering for a class C is said to be consistent with equals if and only if e1.compareTo(e2) == 0 has the same boolean value as e1.equals(e2) for every e1 and e2 of class C.... Virtually all Java core classes that implement Comparable have natural orderings that are consistent with equals. One exception is java.math.BigDecimal, whose natural ordering equates BigDecimal objects with equal values and different precisions (such as 4.0 and 4.00)."

BigDecimal is not consistent with equals. To check whether two BigDecimals are equal as most people would understand it, we must compare them thus:


        BigDecimal _4_00 = new BigDecimal("4.00");
        BigDecimal _4 = new BigDecimal("4");
        
        assertFalse(_4_00.equals(_4));        // wrong
        assertEquals(0, _4_00.compareTo(_4)); // right

Identity

Comparisons are useful in identity elements. An identity element "is a special type of element of a set with respect to a binary operation on that set. It leaves other elements unchanged when combined with them."

For instance, for the + operator, the identity is 0 (since x + 0 = x).

For the * operator, the identity element is 1 (since x * 1 = x).

Where it gets interesting is that for the maximum operator, the identity element is negative infinity. That is, any argument to the partially applied function max(NEGATIVE_INFINITY, ... is itself.

For floating point numbers, x > NEGATIVE_INFINITY for all x.

The converse is true for the minimum function.

When x does not equal x

When is x != x ? How can this be?

Take this:


> insert into bar (id, avalue) values (22, null);
Query returned successfully: 1 rows affected, 18 ms execution time.
> select * from bar where avalue = null;
>


Hmm, but select * shows me that the row is there. OK, what about:


> select * from bar where not avalue = null;
>


I saw a bug only this week where somebody thought that just because a comparison with null didn't return anything that noting the predicate would mean the the row will show up in the result set. This is not the case. You would have to use is null in SQL.

Comparisons with null in SQL do not compute. This is part of the SQL standard called F571 and all databases I cared to check implement it. You can't even join tables on null values. For instance:


> insert into foo (id, avalue) values (33, null);
> select * from foo f, bar b where f.avalue = b.avalue;
>


SQL and Java are different in the way that they treat nulls. SQL uses Three Value Logic where null means undefined (or unknown or whatever semantics the developer wants to associate it with).

But you might be surprised to know that Java too has a notion of x != x.

Of course,

assertTrue(null == null);

is true. However, with floating points, this:

assertTrue(aDouble == aDouble);

may not always be true. This is nothing to do with rounding errors. If aDouble = Double.NaN then this assertion will fail (where NaN is not a number). The same is true for Float.NaN as defined in the IEEE spec.

Interestingly, infinities can be compared.

assertTrue((10d/0) == Double.POSITIVE_INFINITY);
assertTrue(Double.POSITIVE_INFINITY == Double.POSITIVE_INFINITY);

passes their assertions. And although (10d/0) may return an infinity, (0d/0d) returns NaN. This is consistent with the rules of arithmetic as mathematicians rather than software engineers understand it.

Finally, note that autoboxing may change your results, thus:


    public void testNans() {
        checkDoublePrimitivesEqual(Double.POSITIVE_INFINITY, Double.POSITIVE_INFINITY);
        checkDoubleObjectsNotEqual(Double.POSITIVE_INFINITY, Double.POSITIVE_INFINITY);
    }

    private void checkDoubleObjectsNotEqual(Double d1, Double d2) {
        assertFalse(d1 == d2);
    }

    private static void checkDoublePrimitivesEqual(double d1, double d2) {
        assertTrue(d1 == d2);
    }


[1] Wikipedia.