How to optimize the sieving stage of QS?

[Ilya Gazman]

My latest version of QS is moving in fifth of the speed of light as it only 5 times slower than Tills version now, lol.

40% of my sieving code is spent on the below loop. Do you have an idea how to improve it?

// that loop takes 40% of the performance
for (Wheel wheel : wheels) { 
    wheel.update(logs);
}

// Wheel update method
public void update(byte[] logs) {
    for (; currentPosition < logs.length; currentPosition += prime) { // currentPosition is int
        logs[currentPosition] += log;
    }

    this.currentPosition -= logs.length;
}

[R. Gerbicz]

Originally Posted by Ilya Gazman

fifth of the speed of light as it only 5 times slower than Tills version now, lol.

And then msieve is faster than light?
Save out logs.length to a parameter. Don't know Java, but similar code in c++ is also slower when I'm using .size() in a loop.

[bsquared]

Originally Posted by Ilya Gazman

My latest version of QS is moving in fifth of the speed of light as it only 5 times slower than Tills version now, lol.

40% of my sieving code is spent on the below loop. Do you have an idea how to improve it?

// that loop takes 40% of the performance
for (Wheel wheel : wheels) { 
    wheel.update(logs);
}

// Wheel update method
public void update(byte[] logs) {
    for (; currentPosition < logs.length; currentPosition += prime) { // currentPosition is int
        logs[currentPosition] += log;
    }

    this.currentPosition -= logs.length;
}

For small-ish primes you could unroll it. log changes slowly and will be the same for 4 adjacent primes. I don't know how to to re-work this code exactly given that currentPosition, prime, log, etc., are apparently maintained by a class (?). But something like:

cp1 = currentPosition[i]
cp2 = currentPosition[i+1]
cp3 = currentPosition[i+2]
cp4 = currentPosition[i+3]

p1 = primes[i]
p2 = primes[i+1]
p3 = primes[i+2]
p4 = primes[i+3]

maxCP = MAX(cp1, cp2, cp3, cp4)
maxP = MAX(p1, p2, p3, p4)

for (; maxCP < logs.length; ) {
logs[cp1] += log;
logs[cp2] += log;
logs[cp3] += log;
logs[cp4] += log;
cp1 += p1;
cp2 += p2;
cp3 += p3;
cp4 += p4;
maxCP += maxP;
}

// now finish the last part of each range with individual loops


// finally update all positions for the next block
currentPosition[i] = cp1 - logs.length
currentPosition[i+1] = cp2 - logs.length
currentPosition[i+2] = cp3 - logs.length
currentPosition[i+3] = cp4 - logs.length

[bsquared]

Also, usually people initialize the sieve byte values to a cutoff:

for (i=0; i < sieve_length; i++) {
sieve[i] = cutoff;
}

Then sieve just like normal, but subtract instead of add.

Now, you can easily find locations that are ready for trial division by ANDing with a hi-bit mask.

if (sieve[i] & 0x80) {
trial_divide(i)
}

But most locations won't need trial division, so you can check and eliminate many at once by overloading the sieve to an 8-byte unsigned long long type:

if (((uint64_t)sieve[i] & 0x8080808080808080ULL) == 0) {
continue;'
}

Makes scanning for sieve reports much faster.

[Ilya Gazman]

I don't know how to to re-work this code exactly given that currentPosition, prime, log, etc., are apparently maintained by a class (?)

Yeah it is maintained by the Wheel class, each prime has two Wheel instances that track the current position in the logs array.

My sieving bound M is represented by an array of the size S where Sk = M for a small value of k(I use it as a square of M), I found it more memory efficient.
Then my sieving loop looks like this:

for (i=0;i<k;i++){
   for (Wheel wheel : wheels) { 
       wheel.update(logs);
   }
}

I got a planned optimization where I pick S as a multiplicate of the first few primes, then I only need to sieve them once for each M cycle and I reset the logs to their values as it don't change between the k-1 cycles of S.
----------------------------------------------------

For small-ish primes you could unroll it. log changes slowly and will be the same for 4 adjacent primes.

I perhaps don't understand it, but how having a common log value for several primes helps with performance?

if (((uint64_t)sieve[i] & 0x8080808080808080ULL) == 0) {
continue;'
}

Love it! Will try that :)

[Ilya Gazman]

Originally Posted by R. Gerbicz

And then msieve is faster than light?
Save out logs.length to a parameter. Don't know Java, but similar code in c++ is also slower when I'm using .size() in a loop.

Nice! This actually helped a bit. I rewrote the update function to only use local variables.

    public void update(byte[] logs) {
        int length = logs.length;
        int currentPosition = this.currentPosition;
        byte log = this.log;
        int prime = this.prime;
        while (currentPosition < length) {
            logs[currentPosition] += log;
            currentPosition += prime;
        }

        this.currentPosition = currentPosition - length;
    }

[bsquared]

Originally Posted by Ilya Gazman

I perhaps don't understand it, but how having a common log value for several primes helps with performance?

Saves registers. The goal of unrolling is to minimize loop overhead (comparing against loop condition, jumps). But unrolling increases the code size. A sweet spot occurs if all variables in the loop can be stored in registers (there are 14 available in x86-64). We need 4 for primes, 4 for positions, one each for the sieve address, log value, and loop counter. If we needed 4 different log values then the compiler will probably utilize stack, which is slower.

All this might be moot, as the bottleneck of the loop is probably memory access and not loop overhead. Unrolling 4x might actually help with memory access since some percentage of the time the writes might hit the same cache line (this is a good thing). Anyway, it might not be a big win but it might help.