Thursday, June 11, 2009

ConcurrentMultimap please

This blog seems to be a good place to tackle hard problems. It helps that you can modify and delete posts in case you're wrong. That's certainly preferable to making an ass of yourself on a mailing list.

I just signed Google Collections issue 135 and additionally shared one of my use-cases: session management.

Solving the problem of ConcurrentMultimap.remove(K,V) is a cat and mouse game of "where are the holes" in cascading visible CAS changes. If any code deserves to be formally proven, concurrency problems like this do. (tho I'm not equal to the challenge tonight)

UPDATE: I've found 2 additional data races since making this post. Will update when I've sussed out the conditions under which they can occur.

Because all of the mutating operations guarantee visibility the path to reach a genuine data race is quite twisted. At one point I thought CopyOnWriteArrayList's visibility saved me, but then reconsidered.

In add and remove methods I have indicated points where visibility to other threads is critical. Here's the code:


private final ConcurrentMap<GUID, Collection<SessionHandle>> sessions = ...; // mapmaker make me a map!

...

public boolean addSession(SessionHandle handle) {
Collection<SessionHandle> sessionsForGUID = sessions.get(handle.guid()); // A
if(sessionsForGUID != null) {
sessionsForGUID.add(handle); // B
return true;
}

// put if absent double check to avoid extra list creation
sessionsForGUID = new CopyOnWriteArrayList<SessionHandle>();
sessionsForGUID.add(handle);
Collection<SessionHandle> old = sessions.putIfAbsent(handle.guid(), sessionsForGUID); // C
if(old != null) old.add(handle); // D
return true;
}

public boolean removeSession(SessionHandle handle) {
// 0
Collection<SessionHandle> sessionsForGUID = sessions.get(handle.guid());
if(sessionsForGUID == null) return false;

// O(n) remove is the least of my worries
// 1
if( ! sessionsForGUID.remove(handle)) return false;

// 2
if( ! sessionsForGUID.isEmpty()) return true;

// double-check remove
// 3
if( ! sessions.remove(handle.guid(),sessionsForGUID)) return true; // already removed! (yikes)

// 4
if(sessionsForGUID.isEmpty()) return true;

// another entry was added!
// 5
Collection<SessionHandle> old = sessions.putIfAbsent(handle.guid(), sessionsForGUID);

if(old == null) return true;

// 6
old.addAll(sessionsForGUID);
return true;
}



What follows is the exchange of four adds and two removes which cause both methods to reach their very last return statement.

Given 3 threads: T1, T2, T3.
T1 calls add and reaches statement A and the list is not present so T1 does not reach statement B.
T2 calls add and reaches statement A, skips B as did T1 and reaches statement C then returns. The map is now populated with list alpha.
T2 calls add again and reaches statement A and B then returns.
T1 reaches statement C but sees list alpha present.
List alpha now has two members and the map's total size is 2 tho T1's element is still in-flight.
T2 calls remove and reaches statement 0.
T3 calls remove and reaches statements 0 thru 3 and removes list alpha from the map.
T2 reaches statements 1 thru 3 and returns since it sees list alpha was removed from the map.
T1 reaches statement D and adds its in-flight element to list alpha which T3 successfully removed with a CAS. T1 returns not knowing its element is on the orphaned list alpha.
T3 reaches statement 4 and sees that list alpha which it just removed is no longer empty!
T2 calls add again just to be difficult and completes the operation at statement C creating list beta on what appeared to be an empty map.
T3 reaches statement 5 and replaces list alpha on the map, but then sees list beta prevented the CAS put.
T3 reaches statement 6 and adds all elements in list alpha in list beta and finally returns.

In a table the seemingly improbable narrative looks as follows:
T1 T2 T3 size
0
A 0
A 0
C 1
ret 1
A 1
B 2
ret 2
C 2
0 2
0 2
1 1
2 1
3 1
1 0
2 0
3 0
ret 0
D 0 T1's add is on a removed list
ret 0
4 0
A 0
C 1
ret 1
5 1
6 2
ret


If you cling to the idea that this sequence of events is impossible, please check out the JavaOne 2009 session by Cliff Click and Brian Goetz - "This Is Not Your Father's Von Neumann Machine; How Modern Architecture Impacts Your Java™ Apps". The session content should be available a few weeks from now.

A ConcurrentMultimap could share its region locking with its constituent lists and prevent the catastrophic rollback you see here. Until then I will use the GCollections synchronized Multimap wrapper. The hit in performance is a small price to pay for confidence in the implementation.

Sunday, April 12, 2009

Multiple return/tuples and closures in Java

Learning from Functional Programming

I spent some time crafting a file scanner and developing byte-level file scanning. Since I've spent some time learning Erlang I had an eye on how to duplicate the same algorithms in a functional language.

Java's lack of transparent multiple-return values inevitably leads to some implementation patterns that result in sub-optimal (object hungry) or thread-hostile code. The JVM has been optimized to handle these, but key language features may produce a more expressive language and will certainly allow novices a more direct and intuitive path to better performing implementations of common algorithms.

At the very least all Java developers can be helped a great deal by programming in functional / side-effect free code. The trade-off for multithread safe code is the rapid creation/collection of small objects.

The Scanning Algorithm

The basic algorithm is present here intertwined with some code that marks the offsets of message boundaries in an array.

    // LISTING 1 - primordeal Scanner algorithm

int length = _prototypes.remaining();

int[] offsets = new int[length / 15 + 1];

int offsetIndex = 0;
int i = 0;
loop: while (true)
{
if (i >= length)
{ // EOF case
offsets = ensureCapacity(offsets, offsetIndex + 1);
offsets[offsetIndex++] = i;
break loop;
}
switch (_prototypes.get(i))
{
case 10: // unix newline \10
offsets = ensureCapacity(offsets, offsetIndex + 1);
offsets[offsetIndex++] = i;
break;
case 13: // dos or apple newline \13 \10
offsets = ensureCapacity(offsets, offsetIndex + 1);
offsets[offsetIndex++] = i;
if (_prototypes.get(i + 1) == 10)
i++; // skip 10
break;
case 0: // pad case
offsets = ensureCapacity(offsets, offsetIndex + 1);
offsets[offsetIndex++] = i;
break loop;
}
i++;
}
int[] copy = new int[offsetIndex];
System.arraycopy(offsets, 0, copy, 0, Math.min(offsets.length,
offsetIndex));
_prototypeOffsets = copy;


This served its purpose for reading a single chunk of text and splitting it. Different inputs and outputs or continuing past a single buffer dictate the need for a different operation to take place at each of the cases.

Object-Oriented Abstraction

Here I extracted the scanning algorithm from that code, producing an abstract and concrete implementation. If I were going to scan for a different message boundary or introduce additional end-of-file conditions they could be included in an alternate scanner implementation.
  // LISTING 2 - Scanner as an object
abstract class ByteScanner {
public enum ScanResult {
UNDERFLOW,
BOUNDARY_MATCH,
END_MATCH;
}

protected int position = 0;

public void position(int pos) {
position = pos;
}

public int position() {
return position;
}

public abstract ScanResult scan(ByteBuffer buff, int start, int limit);
}

class NewlineScanner extends ByteScanner {
public ScanResult scan(final ByteBuffer buff, final int start, final int limit) {
position = start;

while(true) {
if (position >= limit) { // read data
return ScanResult.UNDERFLOW;
}

switch (buff.get(position)) {
case 10: // unix newline \10
if (position - start <= 1)
continue; // dos newline detect
return ScanResult.BOUNDARY_MATCH;
case 13: // dos or apple newline \13 (\10)
return ScanResult.BOUNDARY_MATCH;
case 0: // pad case
return ScanResult.END_MATCH; // eof
}
position++;
}
}
}


While the first listing is capable of processing separate files with only additional overhead of its required input & output variables, the second listing also requires a new instance of the scanner because it contains the position state.

Toward Side-Effect Free Code

Many many Java libraries hold some state or object caches in their instances including the chief Java anti-patterns: java.util.Calendar and java.util.Date. Java's Date class is so badly broken that it simply should be avoided in a multithreaded application (try joda-time or JSR 310's time API). XML input and output factories and other encoding libraries may seem stateless, but enough of them hold a state (or the use-case to avoid side-effect is unclear) that it is usually safer to make use of ThreadLocal to work around any hidden state.

// LISTING 3 - Scanner as an object with faked multi-return
abstract class ByteScanner2 {
public enum ResultType {
UNDERFLOW,
BOUNDARY_MATCH,
END_MATCH;
}

public static class ScanResult {

public int position;
public ResultType type;
}

public ScanResult result(int position, ResultType type) {
ScanResult sr = new ScanResult();
sr.position = position;
sr.type = type;
return sr;
}

public abstract ScanResult scan(ByteBuffer buff, int start, int limit);
}

class NewlineScanner2 extends ByteScanner2 {
public ScanResult scan(final ByteBuffer buff, final int start, final int limit) {
int position = start;

while(true) {
if (position >= limit) { // read data
return result(position,ResultType.UNDERFLOW);
}

switch (buff.get(position)) {
case 10: // unix newline \10
if (position - start <= 1)
continue; // dos newline detect
return result(position,ResultType.BOUNDARY_MATCH);
case 13: // dos or apple newline \13 (\10)
return result(position,ResultType.BOUNDARY_MATCH);
case 0: // pad case
return result(position,ResultType.END_MATCH); // eof
}
position++;
}
}
}


Listing 3 presents a side-effect free scanner implementation. There is a fair amount of boilerplate code needed to encapsulate the multiple parts of the state. This is the pattern on which I continue to base my state-free parsers.

Reducing Boilerplate and Encouraging Functional Programming in Novices

I'm still studying the Java closures and tuples proposals, but here is an approximation of the implementation with those features included. The motivation is not only to make listing 3 look better, but to make it more expressive and elegant thereby encouraging implementations which
are free of side-effects without the need for analysis. This means that novices can regularly produce correct (multithread safe or side-effect free) code the first time they compile it.

Here let "Function<int,ResultType>" represent a closure with a 2 parameter return statement. This isn't in the current closures spec and the tuples spec doesn't address the closure syntax issue.

// LISTING 4 - Scanner as a closure with true multi-return
public enum ResultType {
UNDERFLOW,
BOUNDARY_MATCH,
END_MATCH;
}

Function<int,ResultType> scan = { ByteBuffer buff, int start, int limit =>
int position = start;

while(true) {
if (position >= limit) { // read data
return position,ResultType.UNDERFLOW;
}

switch (buff.get(position)) {
case 10: // unix newline \10
if (position - start <= 1)
continue; // dos newline detect
return position,ResultType.BOUNDARY_MATCH;
case 13: // dos or apple newline \13 (\10)
return position,ResultType.BOUNDARY_MATCH;
case 0: // pad case
return position,ResultType.END_MATCH; // eof
}
position++;
}
}
}

Monday, January 26, 2009

Introduction to the Java Diaspora

How many years does Java and the Sun VM have left? Will the JCP continue to maintain the standards?

The Java diaspora is not a positive thing. This is not about the ubiquity of Java technology in our modern technological marketplace, but instead this is about Java being displaced from the server and the standards of Java technology escaping from Sun.

Three days ago Sun let go 1300 employees... after Logitech, Microsoft, IBM, Creative, and many more other blue-chip computer companies than I remember have laid off thousands of their own. The register claims this will hit OpenJDK, Java desktop, and OpenSolaris. I wonder what Java desktop losses mean for JavaFX. Between Silverlight and Adobe AIR JavaFX can't afford many setbacks.

There was some less notable but significant news that Redhat's server offering has begun to eclipse Sun's. Redhat has recently played a very significant role in employing developers who are dedicated to developing the art and science of Java server technology. It seems that just as Glassfish promised to offer better performance, and Sailfin was going to lead server technology back into layer 5 via SIP; that customers would return to the percieved stability of a Tomcat J2EE implementation.

I feel a strong pull away from Java as a career path. It has been a good introduction, but the common wisdom is that in these times developers NEED to branch out into other technologies. Indeed, Java itself has seen developers do this for years and they take their products, services, and systems with them.

The evolution of session-based services and server connections has tremendous potential. The primary feature for me would be the ability to suspend a session no matter what the application (telephony, video conf, gaming, multimedia streaing) and resume the application connection without renegotiating the layer 7 logic. This already means flexible VoIP connections (iPhone jumping from 3G to WiFi), network gaming in the car, shotgunned WWAN connections for increased reliability and throughput, and wwan closed-circuit TV and security cameras on trains & cars over commodity networks. Sun's strength lies in tapping into these new technologies but they need their J2EE customer's loyalty or they won't have the fuel to climb these initial development grades.

I hope to make my peace with the direction server technology is going between the hopefully numerous thoughts on concurrent library API design and exploring the future of programming with work-stealing algorithms and frameworks like Intel's thread building blocks and the various Java 7 analogues.