Skip to content

coordinates() iterators do not parallelize nicely #22

@krevelen

Description

@krevelen

Due to reuse of the same long[] object in the v0.3.0 implementations of e.g. NonZeroIterator#coordinates the following code yields unexpected results in Java 8, fixing all fork/join calls to the last coordinate emitted by the iterator:

final Matrix m = Matrix.Factory.rand( 3, 2 );
StreamSupport.stream( m.allCoordinates().spliterator(), false )
		.forEach( x -> System.out.println( "seq: (" + x[0] + "," + x[1]
				+ ") = " + m.getAsObject( x ) ) );
StreamSupport.stream( m.allCoordinates().spliterator(), true )
		.forEach( x -> System.out.println( "par: (" + x[0] + "," + x[1]
				+ ") = " + m.getAsObject( x ) ) );
// sequential results in e.g.:
seq: (0,0) = 0.1158861882656429
seq: (0,1) = 0.3210776654748966
seq: (1,0) = 0.9851934019369726
seq: (1,1) = 0.30908801636590943
seq: (2,0) = 0.5756701897595798
seq: (2,1) = 0.9616795338007531
// parallel results: only last coordinate is actually emitted
par: (2,1) = 0.9616795338007531
par: (2,1) = 0.9616795338007531
par: (2,1) = 0.9616795338007531
par: (2,1) = 0.9616795338007531
par: (2,1) = 0.9616795338007531
par: (2,1) = 0.9616795338007531

Work-around, as applied in my MatrixUtil:

public static Iterable<long[]> coordinates( Matrix source, boolean all )
{
	return () -> new Iterator<long[]>()
	{
		final long[] n = source.getSize(), x = Arrays.copyOf( n, n.length );
		Matrix row = null;

		@Override
		public long[] next()
		{
			return Arrays.copyOf( x, x.length ); // must copy to parallelize
		}

		@Override
		public boolean hasNext()
		{
			while( x[0] != -1 )
			{
				while( row == null && --x[0] != -1 )
				{
					row = source.selectRows( Ret.LINK, x[0] );
					x[1] = n[1];
				}
				if( row == null ) return false;
				while( --x[1] != -1 )
					if( all || row.containsCoordinates( 0, x[1] ) )
						return true; // lacks index[], may add log(n)*k ops

				row = null;
			}
			return false;
		}
	};
}

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type
    No fields configured for issues without a type.

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions