Compare SWAR scanning rows of (x,y) coordinates

swar.subword.SWAR_v_Arrays_Perf_NoComments.java

package swar.subword;

import java.util.Random;

public class SWAR_v_Arrays_Perf_NoComments 
{
	private static final int ROW_COUNT = 1000000; 
	
	private static final int SCAN_ITERATIONS = 100;
	
	public static void main (String[] args)
	{
		int[] xs = new int [ ROW_COUNT ];
		int[] ys = new int [ ROW_COUNT ];
		
				
		int[][] xy = new int[ 2 ][ ROW_COUNT ]; 
		
		long[] xyCompound = new long[ ROW_COUNT ];		
		Random r = new Random();
		for ( int i = 0; i < ROW_COUNT; i++ )
		{
			int x = r.nextInt();
			int y = r.nextInt();
			xs[ i ] = x;
		    ys[ i ] = y;
			
			xy[ 0 ][ i ] = x;
			xy[ 1 ][ i ] = y;
			                                         //we need this & MASK to avoid Java sign extension   
			xyCompound[ i ] = ( x + 0L << 32 ) | ( y & (-1L >>> 32 ) );
		}
		
		System.gc();
		
		timeParallelIntArrays(xs, ys, SCAN_ITERATIONS );
		
		time2DIntArray( xy, SCAN_ITERATIONS );
		
		timeCompoundShift( xyCompound, SCAN_ITERATIONS );
		
		timeCompoundSWARMask ( xyCompound, SCAN_ITERATIONS ); 
	}
	
	private static void timeCompoundSWARMask ( long[] xyCompound, int iterations )
	{
		
		long start = System.currentTimeMillis();		   
		int found = compoundSWARMaskBothOdd( xyCompound, iterations );
		long end = System.currentTimeMillis();
		
		System.out.println ("Compound SWAR Bit Mask  "+(end-start)+"ms for ("+iterations+"x) scanned "+xyCompound.length+" found "+found);		
	}
	
	private static void timeCompoundShift ( long[] xyCompound, int iterations )
	{
		long start = System.currentTimeMillis();		   
		int found = compoundShiftBothOdd( xyCompound, iterations );
		long end = System.currentTimeMillis();
		
		System.out.println ("Compound Shift >>       "+(end-start)+"ms for ("+iterations+"x) scanned "+xyCompound.length+" found "+found);
	}
	
	private static void timeParallelIntArrays(int[] xs, int[]ys, int iterations )
	{
		
		long start = System.currentTimeMillis();		   
		int found = parallelIntArraysBothOdd(xs, ys, iterations );
		long end = System.currentTimeMillis();
		
		System.out.println ("xs=int[]; ys=int[]      "+( end - start)+"ms for ("+iterations+"x) scanned "+xs.length+" found "+found );
	}
	
	private static void time2DIntArray( int[][] xy, int iterations )
	{
		int found = 0;
		
		long start = System.currentTimeMillis();		   
		found = intArray2DBothOdd(xy, iterations );
		long end = System.currentTimeMillis();
		
		System.out.println ("2d array int[2][count]  "+(end-start)+"ms for ("+iterations+"x) scanned "+xy[0].length+" found "+found);		
	}
	
	private static final long BOTH_ODD_SWAR_MASK = ( 1L << 32 ) + 1;
	
	private static int compoundSWARMaskBothOdd(long[] xyCompound, int iterations )
	{
		int found = 0;
		for (int it = 0; it < iterations; it++ ) 
		{
			for (int i = 0; i < xyCompound.length; i++ )
			{
				if ( ( xyCompound[ i ] & BOTH_ODD_SWAR_MASK ) == BOTH_ODD_SWAR_MASK )
				{
					found++;
				}
			}				
		}
		return found;
	}
	
	private static int compoundShiftBothOdd (long[] xyCompound, int iterations )
	{
		int found = 0;
		for (int it = 0; it < iterations; it++ ) 
		{
			for (int i = 0; i < xyCompound.length; i++ )
			{
				if ( ( xyCompound[ i ] & 1 ) == 1 &&
					 ( ( xyCompound[ i ] >> 32 ) & 1) == 1 )
				{
					found++;
				}
			}				
		}
		return found;
	}
	
	
	private static int parallelIntArraysBothOdd ( int[] xs, int[]ys, int iterations )
	{
		int found =0;
		for (int it=0; it<iterations; it++) 
		{
			for (int i=0; i<xs.length; i++)
			{
				if ( ( xs[i] & 1) == 1 &&
					 ( ys[i] & 1) == 1 )
				{
					found++;
				}
			}				
		}
		return found;
	}
	
	private static int intArray2DBothOdd(int[][] xy, int iterations )
	{
		int found =0;
		for (int it=0; it<iterations; it++) 
		{
			for (int i=0; i<xy[0].length; i++)
			{
				if ( ( xy[0][i] & 1) == 1 &&
					 ( xy[1][i] & 1) == 1 )
				{
					found++;
				}
			}				
		}
		return found;
	}	
}

Simple performance test over (count) "rows" of (x,y) int coordinates
to illustrate how SWAR compares to other data structures for scanning / query performance.
Including:
(2) parallel int arrays ({@code int[] xs = int[count]; int[] ys = int[count]; })
(1) 2-dimensional int arrays ( {@code int[][] xy = new int[2][count]; })
(1) compound @code long[]} ( {@code long[] xyCompound = long[ count ];} )

• each (x & y) in xyCompound are tested individually through bit shifting (>>)
• BOTH (x & y) elements are tested simultaneously with a SWAR BitMask

/TR>

Data & Strategy	Time	iterations	Dataset size
Compound SWAR Bit Mask	12545ms	100x	170000000
Compound Shift >>	78202ms	100x	170000000
xs=int[]; ys=int[]	90263ms	100x	170000000
2d array int[2][count]	86633ms	100x	170000000

Data & Strategy	Time	iterations	Dataset size
Compound SWAR Bit Mask	95ms	1x	100000000
Compound Shift >>	546ms	1x	100000000
xs=int[]; ys=int[]	678ms	1x	100000000
2d array int[2][count]	528ms	1x	100000000

Data & Strategy	Time	iterations	Dataset size
Compound SWAR Bit Mask	631ms	10000x	100000
Compound Shift >>	4382ms	10000x	100000
xs=int[]; ys=int[]	4907ms	10000x	100000
2d array int[2][count]	5115ms	10000x	100000

Data & Strategy	Time	iterations	Dataset size
Compound SWAR Bit Mask	6632ms	1000000x	10000
Compound Shift >>	26367ms	1000000x	10000
xs=int[]; ys=int[]	28106ms	1000000x	10000
2d array int[2][count]	28723ms	1000000x	10000

Data & Strategy	Time	iterations	Dataset size
Compound SWAR Bit Mask	634ms	100000x	10000
Compound Shift >>	2653ms	100000x	10000
xs=int[]; ys=int[]	2855ms	100000x	10000
2d array int[2][count]	3965ms	100000x	10000

Data & Strategy	Time	iterations	Dataset size
Compound SWAR Bit Mask	773ms	1000000x	1000
Compound Shift >>	657ms	1000000x	1000
xs=int[]; ys=int[]	782ms	1000000x	1000
2d array int[2][count]	973ms	1000000x	1000

*NOTE: when dealing with BIGGER datasets (10,000 or more elements) the effect of SWAR is more pronounced. Everything is a tradeoff, you have to weight the (potential) speedup based on the number of rows in the dataset being scanned...(and the complexity of the program).

HOWEVER: please keep in mind this is a "contrived" example intended to show
what SWAR is (it is not ideal for ALL cases).

Ideal candidates for this kind of SWAR optimization are those which:

• LARGE datasets
• are of the scanning "exact pattern matching" variety
• can model "rows" within vectorized words.(*)