Ilya Zakharevich on Fri, 13 Dec 2002 21:55:57 -0800


[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]

Re: [PATCH oldish CVS] primelimit above 1<<31


On Fri, Dec 13, 2002 at 09:16:19PM -0500, Igor Schein wrote:
> On Thu, Dec 12, 2002 at 03:20:20PM -0800, Ilya Zakharevich wrote:
> > Actually, the bug in initprimes0() has a one-line fix, but this patch
> > also fixes other places where the limit was signed, and adds some minimal docs.
> > 
> > Some minimal cache optimizations are also performed.  Now sieving up
> > to 4e9 takes less than 2min on Athlon/850 or Ultra Sparc/333.
> 
> !!!
> 
> Remember I kept saying that MPQS and primetable are 2 things that
> exhibit performance inconsistenly between iterations on Linux?  Well,
> whatever Ilya did fixed that for primetable.  Now I get consistent
> timing for the following:
> 
> while 1
> time gp -q -f -p `echo 2^32-2^12|bc` < /dev/null
> end

I use

 gp -p 4000m </dev/null

> Now if the same cache optimizations could be applied to MPQS, I'd be
> a very happy camper :)  And, we could legitimately talk about a
> comparison between MPQS and PPSIQS.

I spent *a lot* of time trying to provide some cache strategy which
may be reused in other procedures.  I ran out of time...  [It did not
help that I misplaced timings for Sparc...  - but with the new API in
place it is much easier to test things:

  install(set_internal,lLDG)
  set_internal(2,100)	\\ disable dependence on limit

  { time_primes_arena(ar,limit) =
      set_internal(1,floor(ar*1024));
      default(primelimit, 100 000);
      gettime;
      default(primelimit, limit);
      if(ar >= 1, ar=floor(ar));
      print("arena "ar"K => "gettime"ms");
  }
  { time_primes(lim) =
      print("test primelimit = "lim);
      X = 16;
      while(X < 4000,
	time_primes_arena(X,lim);
	time_primes_arena(X*1.5,lim);
	X *= 2;
      );
  }

  \\time_primes(10 000 000);
  \\time_primes(30 000 000);
  \\time_primes(100 000 000);
  \\time_primes(300 000 000);
  \\time_primes(1 000 000 000);
  time_primes(2 000 000 000);
  \\time_primes(4 000 000 000);


]

Ilya