Comparison between SIMD SWAR-based query and Object[] based query in Java

swar.subword.SWAR_v_ObjectArr_Perf.java

package swar.subword;

import java.util.Random;
public class SWAR_v_ObjectArr_Perf 
{
	public static class XY 
	{
		public final int x;
		public final int y;
		
		public XY( int x, int y )
		{
			this.x = x;
			this.y = y;
		}
		
		public boolean bothOdd()
		{
			return ( x & 1 ) == 1 &&
				   ( y & 1 ) == 1;
		}
	}
	
	private static final int ROW_COUNT = 1000000; 

	private static final int SCAN_ITERATIONS = 100;
		
	public static void main (String[] args)
	{
		long[] xyCompound = new long[ ROW_COUNT ];
		
		XY[] xyInstances = new XY[ ROW_COUNT ];
		
		Random r = new Random();
		for ( int i = 0; i < ROW_COUNT; i++ )
		{
			int x = r.nextInt();
			int y = r.nextInt();			
				                                 //we need this & MASK to avoid Java sign extension   
			xyCompound[ i ] = ( x + 0L << 32 ) | ( y &  ( -1L >>> 32 ) );
			xyInstances[ i ] = new XY( x, y );
		}
			
		/** lets try a GC BEFORE running the timings*/
		System.gc();
		
		timeObjectArrayScan( xyInstances, SCAN_ITERATIONS );	
		
		timeSWARMask ( xyCompound, SCAN_ITERATIONS );
	}
	
	public static void timeObjectArrayScan ( XY[] xyInstances, int iterations )
	{		
		int found = 0;
		
		long start = System.currentTimeMillis();		   
		found = objectArrayScanBothOdd(xyInstances, iterations );
		long end = System.currentTimeMillis();
		
		System.out.println ("Object [ ]             "+(end-start)+"ms for ("+iterations+"x) scanned "+xyInstances.length+" found "+found);
	}
	
	public static int objectArrayScanBothOdd ( XY[] xyInstances, int iterations ) 
	{
		int found = 0;
		for (int it = 0; it < iterations; it++ )
		{			
			for ( int i = 0; i < xyInstances.length; i++ )
			{
				if ( xyInstances[i].bothOdd() )
				{
					found++;
				}
			}
		}
		return found;		
	}
	
	private static void timeSWARMask ( long[] xyCompound, int iterations )
	{		
		long start = System.currentTimeMillis();		   
		int found = compoundMaskBothOdd( xyCompound, iterations );
		long end = System.currentTimeMillis();
		
		System.out.println ("Compound SWAR Bit Mask "+(end-start)+"ms for ("+iterations+"x) scanned "+xyCompound.length+" found "+found);		
	}
	
	
	public static final long BOTH_ODD_MASK = ( 1L << 32 ) + 1;
	
	public static int compoundMaskBothOdd(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_MASK ) == BOTH_ODD_MASK )
				{
					found++;
				}
			}				
		}
		return found;
	}
}

Compares performance of full row query scan (to check if x,y are BOTH x and y are ODD)

• on an XY[] Object instance array
• on long[] xyCompound using SWAR-based evaluation

Data & Strategy	Time	iterations	Dataset size
Compound SWAR Bit Mask	1497ms	10x	170000000
Object[]	FAIL OOM	10x	170000000

Data & Strategy	Time	iterations	Dataset size
Compound SWAR Bit Mask	4478ms	100x	60000000
Object [ ]	44306ms	100x	60000000

Data & Strategy	Time	iterations	Dataset size
Compound SWAR Bit Mask	390ms	10x	50000000
Object [ ]	4285ms	10x	50000000

Data & Strategy	Time	iterations	Dataset size
Compound SWAR Bit Mask	1306ms	100x	10000000
Object [ ]	10173ms	100x	10000000