Small optimisations

[eira-fransham]

These are only small improvements (cargo benchcmp tells me that small sieves get a boost of ~30%, medium a boost of ~15%, but huge sieves are more-or-less unaffected), but we use this in a hot part of code and so any small speed boost is a win. You're encouraged to benchmark on your own machine to verify the numbers I'm seeing. I do see a noticeable slowdown for sieve_large and iterate_small, I will rerun the benchmarks a few times each and see if those (and the improvements, of course) are consistent and then update this PR.

EDIT: So from running the benches 3 times before this PR and 3 times after, then running cargo benchcmp on the cross product of these results, it looks like none of the slowdowns are consistent and the presieve, sieve, factor and iterate speedups are consistent. Score. Please do confirm this on your machine, however. I haven't tried the cross-product of each of these commits individually.

[autohuonw]

Thanks for the pull request, and welcome! You should hear from @huonw (or someone else) soon.

[eira-fransham]

The CI has failed because of num-traits, can someone (@huonw, I guess) rerun it?

[cuviper]

num doesn't support 1.0.0 any more -- see rust-num/num#257. I'm actually surprised that such cargo didn't fail up front, because it still does locally for me.

There's also a failure here on nightly for the unstable step_by changes.

@huonw, AFAICS you haven't touched primal in quite some time. If you can't work on this any more, would you like a co-maintainer? Or should some interested parties fork a new crate?

[eira-fransham]

So it's rebased, waiting on CI now

[cuviper]

You'll need to bump the CI minimum to rust 1.9.

I want to run the benchmark comparison myself, but it will be about a week before I'm back to my dev machine.

[eira-fransham]

"You" meaning me? Or @huonw?

By the way: here's my results for the benchmarks (this is the multiple of iter/ns after this PR compared to before).

➤ cargo benchcmp pre.bench post.bench | tail -n +2 | awk '{ if (last == $1) tot = (tot " " $7); else { sub(/^ */, "", tot); print last "\t" tot; tot = $7 } last = $1 }' | column -t
sieve::benches::factor_composite               1.00  1.01  1.00
sieve::benches::factor_large_prime             1.01  1.08  1.00
sieve::benches::factor_medium_prime            1.00  1.08  1.01
sieve::benches::factor_over_prime              1.00  1.07  1.00
sieve::benches::factor_small_prime             1.02  1.04  1.02
sieve::benches::iterate_huge                   1.00  0.99  0.99
sieve::benches::iterate_large                  0.99  1.00  1.00
sieve::benches::iterate_small                  1.01  1.02  1.01
sieve::benches::prime_pi_huge                  1.00  1.00  1.00
sieve::benches::prime_pi_large                 1.00  1.01  1.00
sieve::benches::prime_pi_medium                1.00  1.00  0.97
sieve::benches::prime_pi_small                 1.00  1.00  0.91
sieve::benches::sieve_huge                     1.00  1.00  1.00
sieve::benches::sieve_large                    1.13  1.13  1.14
sieve::benches::sieve_medium                   1.07  1.06  1.06
sieve::benches::sieve_small                    1.13  1.10  1.09
streaming::benches::sieve_huge                 1.00  1.00  1.01
streaming::benches::sieve_large                1.14  1.14  1.14
streaming::benches::sieve_larger               1.08  1.09  1.07
streaming::benches::sieve_medium               1.07  1.05  1.08
streaming::benches::sieve_small                1.08  1.04  1.08
streaming::presieve::benches::presieve_huge    1.27  1.26  1.26
streaming::presieve::benches::presieve_large   1.34  1.34  1.34
streaming::presieve::benches::presieve_larger  1.34  1.34  1.34
streaming::presieve::benches::presieve_medium  1.11  1.11  1.11
streaming::presieve::benches::presieve_small   1.03  1.03  0.97
streaming::primes::benches::iterate_huge       1.00  1.00  1.00
streaming::primes::benches::iterate_large      1.12  1.12  1.12

[cuviper]

Sorry, I meant you @Vurich should bump .travis.yml in this PR. (@huonw is currently unable to contribute to primal at all.)

Benchmarks look good to me, so let's just update that and get this merged!

[eira-fransham]

@cuviper So I've updated the .travis.yml, everything should be in order.

[cuviper]

Thanks! These are now published as primal-bit v0.2.4 and primal-sieve v0.2.7.