Loop i++ vs i+=2

Question

I've been trying to make an efficient algorithm for finding prime numbers and as part of my attempts I have been using the following code. I have a thought for speeding up the loop by changing the incitement to i+=2 but this actually making this change seems to add 2 seconds to the run time of my program. Can anyone explain why this happens, as it seems that the loop would have to do half as work work to complete?

for(int i = answers.get(answers.size()-1)+2;i<n;i++) {
        int bit = i%64;
        int currentInt = i/64;

        int isPrime = (primes[currentInt] >> bit) & 1;
        if(isPrime == 1) {answers.add(i);}
    }

Full code below:

import java.util.ArrayList;
import java.util.List;
import java.util.stream.IntStream;

public class Primes15 {
  static Long start;

  public static IntStream stream() {
    int numbers = 15350808;
    int n = 982451712;
    List<Integer> answers = new ArrayList<>();
    long[] inverseShifts = new long[64];
    long temp = 1;

    for(int i = 0; i < inverseShifts.length; i++) {
      inverseShifts[i] = temp ^ -1;
      temp = temp << 1;
    }

    long[] primes = new long[numbers+1];
    primes[0] = -6148914691370734930L;
    for(int i = 1;i<primes.length; i++) {
      primes[i] = -6148914691370734934L;
    }

    System.out.println("Setup taken " + (System.currentTimeMillis() - start) + "  millis");
    start = System.currentTimeMillis();

    for(int p =3; p*p <=n; p+=2) {
      int bit = p%64;
      int currentInt = p/64;
      long isPrime = (primes[currentInt] >> bit) & 1;
      if(isPrime == 1) {
        answers.add(p);
        int cPrimeSquared = p*p;
        int change = (p==2)? p : p+p;
        for(int i = cPrimeSquared; i <= n; i += change) {
          int innerBit = i % 64;
          int innerInt = i /64;
          isPrime = (primes[innerInt] >> innerBit) & 1;
          if(isPrime == 1) {
            primes[innerInt] = primes[innerInt] & inverseShifts[innerBit];
          }
        }
      }
      System.out.println("finder took " + (System.currentTimeMillis() - start) + "  ms");
      start = System.currentTimeMillis();
      for(int i = answers.get(answers.size()-1)+2; i<n; i++) {
        int bit = i%64;
        int currentInt = i/64;
        long isPrime = (primes[currentInt] >> bit) & 1;
        if(isPrime == 1) {answers.add(i);}
      }
      System.out.println("search took " + (System.currentTimeMillis() - start) + "  ms");
      start = System.currentTimeMillis();

      return answers.stream().mapToInt(i->i);
    }

  public static void main(String[] args) {
    start = System.currentTimeMillis();
    stream();
    Long finish = System.currentTimeMillis();
    System.out.println("Time taken " + (finish - start) + "  millis");
  }
}

Answer 1

I did some testing with JMH - since the whole code was missing and still hard to read, I used a simplified, naive version (not usable to find primes, but with similar calculations IMHO):

@State(Scope.Benchmark)
@BenchmarkMode(Mode.AverageTime)
@OutputTimeUnit(TimeUnit.NANOSECONDS)
public class Increments {

    private long[] primes;

    @Setup
    public void setup() {
        primes = new long[] {3, 5, 7, 11, 13, 17, 19, 23};
    }

    @Benchmark
    @Fork(1)
    public List<Integer> inc() {
        List<Integer> answers = new ArrayList<>();
        for (int i = 3; i < 100; i++) {
            int bit = i % 32;
            int cur = i / 32;
            long test = (primes[cur] >> bit) & 1;
            if (test == 1) {
                answers.add(i);
            }
        }
        return answers;
    }

    @Benchmark
    @Fork(1)
    public List<Integer> addOne() {
        List<Integer> answers = new ArrayList<>();
        for (int i = 3; i < 100; i+=1) {
            int bit = i % 32;
            int cur = i / 32;
            long test = (primes[cur] >> bit) & 1;
            if (test == 1) {
                answers.add(i);
            }
        }
        return answers;
    }

    @Benchmark
    @Fork(1)
    public List<Integer> addTwo() {
        List<Integer> answers = new ArrayList<>();
        for (int i = 3; i < 100; i+=2) {
            int bit = i % 32;
            int cur = i / 32;
            long test = (primes[cur] >> bit) & 1;
            if (test == 1) {
                answers.add(i);
            }
        }
        return answers;
    }
}

Results (5 warmup iterations, 5 measurement iterations):

Benchmark          Mode  Cnt    Score    Error  Units
Increments.addOne  avgt    5  304,670 ± 73,226  ns/op
Increments.addTwo  avgt    5  131,429 ± 13,616  ns/op
Increments.inc     avgt    5  249,329 ± 14,866  ns/op

that is, sorted by nanoseconds per operation:

i+=2  131ns
i++   249ns
i+=1  304ns

kind of expected: increment by 2 is 2 times faster; a bit of surprise, i += 1 is a bit slower than i++ - I would have assumed that the compiler creates the same opcode for both

_{first contact with JMH, not sure if I did it 100% correctly, but had to test it [:-)}