Confusing performance results for prime

[Greg Brunet]

"Bengt Richter" <bokr at oz.net> wrote in message
news:bmqfp9$1fu$0 at 216.39.172.122...
> On Fri, 17 Oct 2003 15:33:24 -0500, "Greg Brunet"
<gregbrunet at NOSPAMsempersoft.com> wrote:
>
> Without looking at the implementation code, I could only guess, but
you
> are using range instead of xrange (but maybe range is now optimized
not to build
> and actual list in iterator context?). Also, limit as a float or long
being passed to
> range must cause a little hiccup. Perhaps an iter optimization is
being interfered with?
> If range is not optimized, then you must be taking a hit from building
throwaway
> lists with range instead of using xrange, so your inner loop in
Primes2 would have
> a bunch of overhead. Also, you don't need floating point or long for
quite some time,
> and x*x > y will be faster than  x > math.sqrt(y) and avoid the float
altogether
> and long to boot, unless you are generating primes larger than maxint.
>
> If you want to conserve space for an all-int primes list, you can use
> primes = array.array('l',[2]) instead of primes = [2] to start. Just
doing that
> apparently gives about the same speed, but I imagine pre-allocating
array space
> could make it faster, though you'd have to change the append and
iteration logic.
> Hard to say without testing.
>

Bengt:

I can understand that changing from range to xrange might help things
slightly, and there are other areas as for improvement as well.  It's
the 2 areas that I mentioned that resulted in some unexpected results
for me that I still didn't understand.  I've taken your improvements on
running & comparing multiple tests (neat stuff BTW) and found the
following:

    - Changing from range to xrange doesn't make an appreciable
difference (it flip-flops back & forth over multiple runs).  I believe I
had noticed this before, I've now got that actually built into the test
now.

    - Getting rid of the Sqrt requires you to perform the (x*x>y) type
test into the loop (whereas performing the sqrt operation allows you to
move that calculation outside of the loop and do a simpler
(factor>limit) test inside the loop).  Even though I realized that this
means I need to import math (at least the sqrt function), I figured that
this still be better (which I think is Georgy's point).  As I increase
the upperlimit, the sqrt version gets better & better compared to the
x*x version (as one would expect - trading off a more 'expensive'
operation in order to move it outside of the loop).  I did tests at
100k, 200k, & 300k, and by 300k, the sqrt test was about 20% faster than
the x*x test.

I've noted some other things that I've tried and put an updated test
program in a response to my original message. Thanks for your help -
it's helped me understand where the improvements were coming from and
that's what my main goal was all about.

-- 
Greg