FULL PRODUCT VERSION :
java version "1.7.0_45"
Java(TM) SE Runtime Environment (build 1.7.0_45-b18)
Java HotSpot(TM) 64-Bit Server VM (build 24.45-b08, mixed mode)


FULL OS VERSION :
Linux sexus.law.di.unimi.it 3.9.10-100.fc17.x86_64 #1 SMP Sun Jul 14 01:31:27 UTC 2013 x86_64 x86_64 x86_64 GNU/Linux


A DESCRIPTION OF THE PROBLEM :
During heavily concurrent computations of betweenness centrality we started getting these exceptions:

Exception in thread "main" java.lang.NullPointerException
        at it.unimi.dsi.fastutil.ints.IntArrayList$1.hasNext(IntArrayList.java:362)
        at it.unimi.dsi.webgraph.LazyIntIterators$EagerToLazyIntIterator.nextInt(LazyIntIterators.java:220)
        at it.unimi.dsi.law.rank.BetweennessCentralityMultipleVisits$IterationThread.call(BetweennessCentralityMultipleVisits.java:186)
        at it.unimi.dsi.law.rank.BetweennessCentralityMultipleVisits$IterationThread.call(BetweennessCentralityMultipleVisits.java:135)
        at java.util.concurrent.FutureTask.run(FutureTask.java:262)
        at java.util.concurrent.Executors$RunnableAdapter.call(Executors.java:471)
        at java.util.concurrent.FutureTask.run(FutureTask.java:262)
        at java.util.concurrent.ThreadPoolExecutor.runWorker(ThreadPoolExecutor.java:1145)
        at java.util.concurrent.ThreadPoolExecutor$Worker.run(ThreadPoolExecutor.java:615)
        at java.lang.Thread.run(Thread.java:744)

The exception happens in fastutil's code (http://fastutil.di.unimi.it/):

 public IntListIterator listIterator( final int index ) {
  ensureIndex( index );
  return new AbstractIntListIterator () {
    int pos = index, last = -1;
    public boolean hasNext() { return pos < size; } <-----
    public boolean hasPrevious() { return pos > 0; }
    public int nextInt() { if ( ! hasNext() ) throw new NoSuchElementException(); return a[ last = pos++ ]; }
    public int previousInt() { if ( ! hasPrevious() ) throw new NoSuchElementException(); return a[ last = --pos ]; }
    public int nextIndex() { return pos; }
    public int previousIndex() { return pos - 1; }
    public void add( int k ) {
     if ( last == -1 ) throw new IllegalStateException();
     IntArrayList.this.add( pos++, k );
     last = -1;
    }
    public void set( int k ) {
     if ( last == -1 ) throw new IllegalStateException();
     IntArrayList.this.set( last, k );
    }
    public void remove() {
     if ( last == -1 ) throw new IllegalStateException();
     IntArrayList.this.removeInt( last );
     /* If the last operation was a next(), we are removing an element *before* us, and we must decrease pos correspondingly. */
     if ( last < pos ) pos--;
     last = -1;
    }
   };
 }

As you can see, the problem lies in the fetch of the size variable, which is a variable of the outer class. The reference this$0 contains a null and an exception is thrown.

Replacing the anonymous class with an inner class entirely solved the problem. There is no semantic difference, so the problem must lie in some race condition for the initalization of the this$0 reference under heavy concurrency.

We can provide source code to reproduce the bug. It takes a while, and the bug occurs at different times, but with 80 parallel visiting thread it always occurs. We were never able to complete a computation.

THE PROBLEM WAS REPRODUCIBLE WITH -Xint FLAG: Did not try

THE PROBLEM WAS REPRODUCIBLE WITH -server FLAG: Yes

STEPS TO FOLLOW TO REPRODUCE THE PROBLEM :
- Download and install WebGraph (http://webgraph.di.unimi.it/)
- Download a data set such as http://law.di.unimi.it/webdata/hollywood-2011/
- Compile the source code below and use it as follows on a server with at least 64 cores:

java -server -Xmx200G it.unimi.dsi.law.rank.BetweennessCentralityMultipleVisits -e hollywood-2011 hollywood-2011-bet

EXPECTED VERSUS ACTUAL BEHAVIOR :
The computation should terminate. Instead, an "impossible" exception is thrown.
REPRODUCIBILITY :
This bug can be reproduced always.

---------- BEGIN SOURCE ----------

/*
 * Copyright (C) 2012 Sebastiano Vigna
 *
 * This program is free software; you can redistribute it and/or modify it
 * under the terms of the GNU General Public License as published by the Free
 * Software Foundation; either version 3 of the License, or (at your option)
 * any later version.
 *
 * This program is distributed in the hope that it will be useful, but
 * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
 * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
 * for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, see <http://www.gnu.org/licenses/>.
 *
 */

import it.unimi.dsi.fastutil.ints.IntArrayList;
import it.unimi.dsi.fastutil.ints.IntArrays;
import it.unimi.dsi.fastutil.io.BinIO;
import it.unimi.dsi.fastutil.longs.LongArrays;
import it.unimi.dsi.logging.ProgressLogger;
import it.unimi.dsi.webgraph.ArrayListMutableGraph;
import it.unimi.dsi.webgraph.ImmutableGraph;
import it.unimi.dsi.webgraph.LazyIntIterator;

import java.io.IOException;
import java.util.concurrent.Callable;
import java.util.concurrent.ExecutionException;
import java.util.concurrent.ExecutorCompletionService;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.atomic.AtomicInteger;

import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

import com.martiansoftware.jsap.FlaggedOption;
import com.martiansoftware.jsap.JSAP;
import com.martiansoftware.jsap.JSAPException;
import com.martiansoftware.jsap.JSAPResult;
import com.martiansoftware.jsap.Parameter;
import com.martiansoftware.jsap.SimpleJSAP;
import com.martiansoftware.jsap.Switch;
import com.martiansoftware.jsap.UnflaggedOption;

/** Computes the betweenness centrality using an implementation of Brandes's algorithm
 * (Ulrik Brandes, &ldquo;A Faster Algorithm for Betweenness Centrality&rdquo;, <i>Journal of Mathematical Sociology</i> 25(2):163&minus;177, 2001)
 * that uses multiple parallel breadth-first visits.
 *
 * <p>To use this class you first create an instance, and then invoke {@link #compute()}.
 * After that, you can peek at the field {@link #betweenness} to discover the betweenness of each node.
 *
 * <p>For every three distinct nodes <var>s</var>, <var>t</var> and <var>v</var>, let <var>&sigma;</var>_{<var>s</var><var>t</var>} be
 * the number of shortest paths from <var>s</var> to <var>t</var>, and <var>&sigma;</var>_{<var>s</var><var>t</var>}(<var>v</var>) the
 * number of such paths on which <var>v</var> lies. The betweenness centrality of node <var>v</var> is defined to be the sum of
 * <var>&delta;</var>_{<var>s</var><var>t</var>}(<var>v</var>)=<var>&sigma;</var>_{<var>s</var><var>t</var>}(<var>v</var>) / <var>&sigma;</var>_{<var>s</var><var>t</var>} over all
 * pairs of distinct nodes <var>s</var>, <var>t</var> different from <var>v</var> (the summand is assumed to be zero whenever the denominator
 * is zero).
 *
 * <p>Brandes's approach consists in performing a breadth-first visit from every node, recording the
 * distance of the node from the current source. After each visit, nodes are considered in decreasing order of
 * distance, and for each of them we consider the arcs (<var>v</var>,<var>w</var>) such that the distance of <var>w</var>
 * is exactly one plus the distance of <var>v</var>: in this case we say that <var>v</var> is a parent of <var>w</var>.
 * Such parents are used to compute the values of <var>&delta;</var> (exactly as in the original algorithm, but without
 * any need to keep an explicit set of parents).
 *
 * <h2>Performance issues</h2>
 *
 * <p>This class performs a different visit in each thread. The memory requirements are thus significantly higher than
 * those of {@link BetweennessCentrality}, but this class has essentially no contention and can provide better performance
 * for relatively small graphs and a large number of threads, provided that enough memory is available.
 */

public class BetweennessCentralityMultipleVisits {
private final static Logger LOGGER = LoggerFactory.getLogger( BetweennessCentralityMultipleVisits.class );

/** An exception telling that the path count exceeded 64-bit integer arithmetic. */
public static final class PathCountOverflowException extends RuntimeException {
private static final long serialVersionUID = 1L;
}

/** The graph under examination. */
private final ImmutableGraph graph;
/** The array of betweenness value. */
public final double[] betweenness;
/** The global progress logger. */
private final ProgressLogger pl;
/** The number of threads. */
private final int numberOfThreads;
/** The next node to be visited. */
protected final AtomicInteger nextNode;
/** Whether to stop abruptly the visiting process. */
protected volatile boolean stop;

/** Creates a new class for keeping track of the state of multiple parallel breadth-first visits.
 *
 * @param graph a graph.
 * @param requestedThreads the requested number of threads (0 for {@link Runtime#availableProcessors()}).
 * @param pl a progress logger, or <code>null</code>.
 */
public BetweennessCentralityMultipleVisits( final ImmutableGraph graph, final int requestedThreads, final ProgressLogger pl ) {
this.pl = pl;
this.graph = graph;
this.betweenness = new double[ graph.numNodes() ];
this.nextNode = new AtomicInteger();
numberOfThreads = requestedThreads != 0 ? requestedThreads : Runtime.getRuntime().availableProcessors();
}

/** Creates a new class for keeping track of the state of multiple parallel breadth-first visits, using as many threads as
 * the number of available processors.
 *
 * @param graph a graph.
 * @param pl a progress logger, or <code>null</code>.
 */
public BetweennessCentralityMultipleVisits( final ImmutableGraph graph, final ProgressLogger pl ) {
this( graph, 0, pl );
}

/** Creates a new class for keeping track of the state of multiple parallel breadth-first visits.
 *
 * @param graph a graph.
 * @param requestedThreads the requested number of threads (0 for {@link Runtime#availableProcessors()}).
 */
public BetweennessCentralityMultipleVisits( final ImmutableGraph graph, final int requestedThreads ) {
this( graph, 1, null );
}

/** Creates a new class for keeping track of the state of multiple parallel breadth-first visits, using as many threads as
 * the number of available processors.
 *
 * @param graph a graph.
 */
public BetweennessCentralityMultipleVisits( final ImmutableGraph graph ) {
this( graph, 0 );
}

private final class IterationThread implements Callable<Void> {
/** The queue of visited nodes. */
private final IntArrayList queue;
/** At the end of a visit, the cutpoints of {@link #queue}. The <var>d</var>-th cutpoint is the first node in the queue at distance <var>d</var>. The
 * last cutpoint is the queue size. */
private final IntArrayList cutPoints;
/** The array containing the distance of each node from the current source (or -1 if the node has not yet been reached by the visit). */
private final int[] distance;
 /** The array containing the values of &sigma; incremented for each parent/child pair during each visit, as explained in Brandes's algorithm. */
private final int[] sigma;
/** The array of dependencies (computed at the end of each visit). */
private final double[] delta;

private IterationThread() {
this.distance = new int[ graph.numNodes() ];
this.sigma = new int[ graph.numNodes() ];
this.delta = new double[ graph.numNodes() ];
this.queue = new IntArrayList( graph.numNodes() );
this.cutPoints = new IntArrayList();
}

public Void call() {
// We cache frequently used fields.
final int[] distance = this.distance;
final double[] delta = this.delta;
final int[] sigma = this.sigma;
final IntArrayList queue = this.queue;
final ImmutableGraph graph = BetweennessCentralityMultipleVisits.this.graph.copy();

for(;;) {
final int curr = nextNode.getAndIncrement();
if ( BetweennessCentralityMultipleVisits.this.stop || curr >= graph.numNodes() ) return null;
queue.clear();
queue.add( curr );
cutPoints.clear();
cutPoints.add( 0 );
IntArrays.fill( distance, -1 );
IntArrays.fill( sigma, 0 );
distance[ curr ] = 0;
sigma[ curr ] = 1;

int d;
for( d = 0; queue.size() != cutPoints.getInt( cutPoints.size() - 1 ); d++ ) {
cutPoints.add( queue.size() );
final int start = cutPoints.getInt( d );
final int end = cutPoints.getInt( d + 1 );

for( int pos = start; pos < end; pos++ ) {
final int node = queue.getInt( pos );
final int currSigma = sigma[ node ];
final LazyIntIterator successors = graph.successors( node );
for( int s; ( s = successors.nextInt() ) != -1; ) {
if ( distance[ s ] == -1 ) {
distance[ s ] = d + 1;
delta[ s ] = 0;
queue.add( s );
sigma[ s ] += currSigma;
}
else if ( distance[ s ] == d + 1 ) {
sigma[ s ] += currSigma;
}
}
}
}

while( --d > 0 ) {
final int start = cutPoints.getInt( d );
final int end = cutPoints.getInt( d + 1 );

for( int pos = start; pos < end; pos++ ) {
final int node = queue.getInt( pos );
double sigmaNode = sigma[ node ];
final LazyIntIterator succ = graph.successors( node );
for( int s; ( s = succ.nextInt() ) != -1; )
if ( distance[ s ] == d + 1 ) delta[ node ] += ( 1 + delta[ s ] ) * sigmaNode / sigma[ s ];
}

synchronized ( BetweennessCentralityMultipleVisits.this ) {
for( int pos = start; pos < end; pos++ ) {
final int node = queue.getInt( pos );
betweenness[ node ] += delta[ node ];
}
}
}

if ( BetweennessCentralityMultipleVisits.this.pl != null )
synchronized ( BetweennessCentralityMultipleVisits.this.pl ) {
BetweennessCentralityMultipleVisits.this.pl.update();
}
}
}
}


/** Performs a full computation. */
public void compute() throws InterruptedException {
final IterationThread[] thread = new IterationThread[ numberOfThreads ];
for( int i = 0; i < thread.length; i++ ) thread[ i ] = new IterationThread();

if ( pl != null ) {
pl.start( "Starting visits..." );
pl.expectedUpdates = graph.numNodes();
pl.itemsName = "nodes";
}

final ExecutorService executorService = Executors.newFixedThreadPool( Runtime.getRuntime().availableProcessors() );
final ExecutorCompletionService<Void> executorCompletionService = new ExecutorCompletionService<Void>( executorService );

for( int i = thread.length; i-- != 0; ) executorCompletionService.submit( thread[ i ] );

try {
for( int i = thread.length; i-- != 0; ) executorCompletionService.take().get();
}
catch( ExecutionException e ) {
stop = true;
Throwable cause = e.getCause();
throw cause instanceof RuntimeException ? (RuntimeException)cause : new RuntimeException( cause.getMessage(), cause );
}
finally {
executorService.shutdown();
}

if ( pl != null ) pl.done();
}


public static void main( final String[] arg ) throws IOException, InterruptedException, JSAPException {

SimpleJSAP jsap = new SimpleJSAP( BetweennessCentralityMultipleVisits.class.getName(), "Computes the betweenness centrality a graph using an implementation of Brandes's algorithm that uses multiple parallel breadth-first visits.",
new Parameter[] {
new Switch( "expand", 'e', "expand", "Expand the graph to increase speed (no compression)." ),
new Switch( "mapped", 'm', "mapped", "Use loadMapped() to load the graph." ),
new FlaggedOption( "threads", JSAP.INTSIZE_PARSER, "0", JSAP.NOT_REQUIRED, 'T', "threads", "The number of threads to be used. If 0, the number will be estimated automatically." ),
new UnflaggedOption( "graphBasename", JSAP.STRING_PARSER, JSAP.NO_DEFAULT, JSAP.REQUIRED, JSAP.NOT_GREEDY, "The basename of the graph." ),
new UnflaggedOption( "rankFilename", JSAP.STRING_PARSER, JSAP.NO_DEFAULT, JSAP.REQUIRED, JSAP.NOT_GREEDY, "The filename where the resulting rank (doubles in binary form) are stored." )
}
);

JSAPResult jsapResult = jsap.parse( arg );
if ( jsap.messagePrinted() ) System.exit( 1 );

final boolean mapped = jsapResult.getBoolean( "mapped", false );
final String graphBasename = jsapResult.getString( "graphBasename" );
final String rankFilename = jsapResult.getString( "rankFilename" );
final int threads = jsapResult.getInt( "threads" );
final ProgressLogger progressLogger = new ProgressLogger( LOGGER, "nodes" );

ImmutableGraph graph = mapped? ImmutableGraph.loadMapped( graphBasename, progressLogger ) : ImmutableGraph.load( graphBasename, progressLogger );
if ( jsapResult.userSpecified( "expand" ) ) graph = new ArrayListMutableGraph( graph ).immutableView();

BetweennessCentralityMultipleVisits betweennessCentralityMultipleVisits = new BetweennessCentralityMultipleVisits( graph, threads, progressLogger );
betweennessCentralityMultipleVisits.compute();

BinIO.storeDoubles( betweennessCentralityMultipleVisits.betweenness, rankFilename );
}
}

---------- END SOURCE ----------

CUSTOMER SUBMITTED WORKAROUND :
Turning the anonymous class in fastutil's code into an inner class seems to have solved the problem, but we're waiting (it takes one week to complete the computation).