Skip to content

Instantly share code, notes, and snippets.

@littleli
Forked from twolfe18/SoABenchmark.java
Created January 18, 2021 21:16
Show Gist options
  • Save littleli/fde68d3c8aa4e6d2caea6f11eaa74468 to your computer and use it in GitHub Desktop.
Save littleli/fde68d3c8aa4e6d2caea6f11eaa74468 to your computer and use it in GitHub Desktop.
Does SoA (structure of arrays) beat AoS (array of structures) for Java?
package sandbox;
import java.util.Arrays;
import java.util.Random;
public class SoABenchmark {
public static Random rand = new Random(9001);
public static int NUM_LABELS = 10;
public static Struct[] aos;
public static SoA soa;
public static boolean useFloats = false;
public static class Struct {
public int label;
public float x, y, z;
public Struct(int label, float x, float y, float z) {
this.label = label;
this.x = x;
this.y = y;
this.z = z;
}
public float dist(Struct other) {
float dx = x - other.x;
float dy = y - other.y;
float dz = z - other.z;
return dx * dx + dy * dy + dz * dz;
}
}
public static class SoA {
public int[] label;
public float[] x, y, z;
public SoA(int n) {
this.label = new int[n];
this.x = new float[n];
this.y = new float[n];
this.z = new float[n];
}
public float dist(int i, int j) {
float dx = x[i] - x[j];
float dy = y[i] - y[j];
float dz = z[i] - z[j];
return dx * dx + dy * dy + dz * dz;
}
public void randInit() {
int n = x.length;
for (int i = 0; i < n; i++)
label[i] = rand.nextInt(NUM_LABELS);
for (int i = 0; i < n; i++)
x[i] = rand.nextFloat();
for (int i = 0; i < n; i++)
y[i] = rand.nextFloat();
for (int i = 0; i < n; i++)
z[i] = rand.nextFloat();
}
public int size() {
return x.length;
}
}
public static int doSoA(int point, float dist) {
int c = 0;
int n = soa.size();
if (useFloats) {
for (int i = 0; i < n; i++) {
float d = soa.dist(point, i);
if (d < dist)
c++;
}
} else {
int l = soa.label[point];
for (int i = 0; i < n; i++) {
if (soa.label[i] == l)
c++;
}
}
return c;
}
public static int doAoS(int point, float dist) {
int c = 0;
int n = aos.length;
Struct p = aos[point];
if (useFloats) {
for (int i = 0; i < n; i++) {
float d = p.dist(aos[i]);
if (d < dist)
c++;
}
} else {
for (int i = 0; i < n; i++) {
if (aos[i].label == p.label)
c++;
}
}
return c;
}
public static void run(boolean print) {
for (boolean uf : Arrays.asList(false, true)) {
if (print)
System.out.println("useFloat: " + uf);
useFloats = uf;
for (int pow : Arrays.asList(6, 8, 10, 12, 14, 16, 18, 20, 22, 24)) {
int n = (1 << pow) + rand.nextInt(50);
soa = new SoA(n);
soa.randInit();
aos = new Struct[n];
for (int i = 0; i < n; i++)
aos[i] = new Struct(soa.label[i], soa.x[i], soa.y[i], soa.z[i]);
double totalAoS = 0, totalSoA = 0;
float dist = 0.1f;
long start, end;
for (int i = 0; i < (45 - pow); i++) {
int p = rand.nextInt(n);
start = System.nanoTime();
int c1 = doSoA(p, dist);
end = System.nanoTime();
long tSoA = end - start;
start = end;
int c2 = doAoS(p, dist);
end = System.nanoTime();
long tAoS = end - start;
assert c1 == c2;
totalSoA += tSoA;
totalAoS += tAoS;
}
if (print)
System.out.println("\tn=" + n + " soa speedup: " + (totalAoS / totalSoA));
}
}
}
public static void main(String[] args) {
System.out.println("warming up...");
run(false);
System.out.println("benchmark:");
run(true);
}
}
/* RESULTS on my Haswell i5 4200u with Oracle JDK 1.8 with -ea -server
warming up...
benchmark:
useFloat: false
n=84 soa speedup: 0.7857142857142857
n=294 soa speedup: 0.7045343536307391
n=1068 soa speedup: 1.3187064335504515
n=4121 soa speedup: 1.3069403837225353
n=16399 soa speedup: 1.3799289244742257
n=65575 soa speedup: 1.5302832432742262
n=262155 soa speedup: 1.8461104049633872
n=1048602 soa speedup: 2.033181902172616
n=4194306 soa speedup: 2.2324801985420235
n=16777243 soa speedup: 1.9858645371278731
useFloat: true
n=79 soa speedup: 1.1241627300289079
n=287 soa speedup: 1.0611872146118722
n=1038 soa speedup: 1.042999951168128
n=4134 soa speedup: 1.0774327859727248
n=16432 soa speedup: 1.1076862266067093
n=65561 soa speedup: 1.2036203658557458
n=262152 soa speedup: 1.258294343601893
n=1048606 soa speedup: 1.2271607490530783
n=4194350 soa speedup: 1.350694780253692
n=16777247 soa speedup: 1.3679167386226132
*/
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment