Last active
October 16, 2015 13:37
-
-
Save edefazio/e25e555789ccac82a44f to your computer and use it in GitHub Desktop.
Compare SWAR scanning rows of (x,y) coordinates
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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; | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
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 ];} )
Ideal candidates for this kind of SWAR optimization are those which: