import java.util.Arrays;
public class DivisibilityBenchmark {
static abstract class DivPredicate {
private final String name;
public DivPredicate(String name) {
this.name = name;
}
public abstract boolean isMultiple(int n);
}
private static final long MAAARTINUS_TABLE = 0x9249249249240000L;
// = 0b1001001001001001001001001001001001001001001001000000000000000000L;
private static final DivPredicate[] SOLUTIONS = new DivPredicate[] {
new DivPredicate("canonical") {
public boolean isMultiple(int n) {
return n % 3 == 0;
}
},
new DivPredicate("200_success") {
public boolean isMultiple(int n) {
return n % 3 == 0;
}
},
new DivPredicate("JavaDeveloper") {
public boolean isMultiple(int n) {
if(n < 0) n = -n;
int evenCtr = 0;
int oddCtr = 0;
while (n != 0) {
if ((n & 1) == 1) {
oddCtr++;
}
n = n>>1;
if ((n & 1) == 1) {
evenCtr++;
}
n = n>>1;
}
return evenCtr == oddCtr;
}
},
new DivPredicate("Simon André Forsberg") {
public boolean isMultiple(int n) {
int sum = 0;
int abs = Math.abs(n);
if (abs < 10) {
return abs == 3 || abs == 6 || abs == 9 || abs == 0;
}
while (n != 0) {
sum += n % 10;
n = n / 10;
}
return isMultiple(sum);
}
},
new DivPredicate("supercat Rev 2") {
public boolean isMultiple(int n) {
int q = (n >> 20) + ((n >> 10) & 0x3ff) + (n & 0x3ff);
return q == ((q * 0x5556) >> 16) * 3;
}
},
new DivPredicate("supercat Rev 4") {
public boolean isMultiple(int n) {
if (n < 0) n = -n;
int q = (int)((n * 0x55555556L) >> 32);
n = n - q - q - q;
return n == 0;
}
},
new DivPredicate("maartinus Rev 4") {
public boolean isMultiple(int x) {
int diff = Integer.bitCount(x & 0x2AAAAAAA) + Integer.bitCount(x);
return (MAAARTINUS_TABLE << diff) < 0;
}
},
new DivPredicate("200_success (bis)") {
public boolean isMultiple(int n) {
return n % 3 == 0;
}
}
};
public static boolean[] run(DivPredicate pred, int lower, int upper) {
boolean[] results = new boolean[upper - lower];
for (int i = lower; i < upper; i++) {
results[i - lower] = pred.isMultiple(i);
}
return results;
}
public static int perf(DivPredicate pred, int lower, int upper) {
int count = 0;
for (int i = lower; i < upper; i++) {
if (pred.isMultiple(i)) { // Count results to ensure that the
count++; // work is not optimized away
}
}
return count;
}
public static void main(String[] args) {
// Warm-up and correctness tests
boolean[] expected = null;
for (DivPredicate pred : SOLUTIONS) {
boolean[] actual = run(pred, -5000, 5000);
if (expected == null) {
expected = actual;
} else if (!Arrays.equals(expected, actual)) {
System.out.println("Mismatch " + pred.name);
}
}
// Performance measurement
final int LOWER = -0x00FFFFFF, UPPER = 0x00FFFFFF;
for (DivPredicate pred : SOLUTIONS) {
long start = System.currentTimeMillis();
perf(pred, LOWER, UPPER);
long finish = System.currentTimeMillis();
System.out.printf("Time %s: %d ms\n", pred.name, finish - start);
}
for (int i = SOLUTIONS.length - 1; i >= 0; i--) {
DivPredicate pred = SOLUTIONS[i];
long start = System.currentTimeMillis();
perf(pred, LOWER, UPPER);
long finish = System.currentTimeMillis();
System.out.printf("Time %s: %d ms\n", pred.name, finish - start);
}
}
}
- Mismatch JavaDeveloper
- Time 200_successcanonical: 6362 ms (← Grossly unfair advantage!)
- Time JavaDeveloper200_success: 102079 ms (Still unreliable!)
- Time Simon André ForsbergJavaDeveloper: 1157995 ms
- Time supercat Rev 2Simon André Forsberg: 1401146 ms
- Time supercat Rev 42: 136151 ms
- Time maaartinussupercat Rev 4: 139146 ms
- Time maartinus Rev 4: 142 ms
- Time 200_success (bis): 146 ms (← Probably a fair comparison)
- Time 200_success (bis): 146 ms
- Time maartinus Rev 4: 140 ms
- Time supercat Rev 4: 146 ms
- Time supercat Rev 2: 153 ms
- Time Simon André Forsberg: 1168 ms
- Time JavaDeveloper: 1029 ms
- Time 200_success: 143 ms
- Time canonical: 144 ms
Discussion
As @maaartinus points out, the first three solutions in this benchmark receive an unfair advantage due to monomorphic inline caching or other JIT optimizations. To illustrate how the benchmark was flawed, I've included the same solution three times (as "canonical", "200_success", and "200_success (bis)"), then executed the tests in reverse order for good measure. I'll take this as a lesson to use a proper benchmarking tool such as Caliper.
Based on the revised measurements, I would draw the conclusion that solutions by @200_success, @supercat, and @maaartinus are nearly identical in performance.