flint-devel

[flint-devel] Timing code

[Richard Howell-P. <ric...@gm...>]

I was wondering how best to do the time comparisons with magma for the
factorisation algorithm. Is there an interface in flint for calling magma
functions, or shall I get some timings in magma, then do some timings in
flint and compare them like that?

-- 
Richard

[flint-devel] Timing code

[Richard Howell-P. <ric...@gm...>]

ok, I will look into that. Before I read your reply I wrote this code which
just does timings in Flint, then I was going to do some magma timings and do
the graph in Excel. I guess proper timings are important officially for the
project but if this way is quicker then I'd do it instead so I can get
something on my poster. Is this a reasonable way to time the factorisation
function? It seems to work for me but I'm not sure I trust the std C time
library very much.

here goes:

#include <time.h>
#include <sys/times.h>
#include <unistd.h>
/**
 * Main timing function for zmod_poly_factorise
 */
#define MIN_LENGTH 250
#define MAX_LENGTH 270        //Maximum length of polynomial to be timed
#define NUMBER 3        //Number of random poly's we test to get average
time
void timing()
{
    //Variables
    clock_t start, end;
    double total_time;
    double timings[MAX_LENGTH - MIN_LENGTH];    //store the average time of
poly length [i]
    zmod_poly_t input;
    zmod_poly_factor_t factors;

printf("Computing Timings \n");
    for(unsigned long k = MIN_LENGTH; k < MAX_LENGTH; ++k)
    {
        total_time = 0;
        for(unsigned long i = 0; i < NUMBER; ++i)
        {
            //Set up a polynomial
            zmod_poly_init(input, PRIME);
            randpoly(input, k, PRIME);
            zmod_poly_make_monic(input, input);
            //set up factors
            zmod_poly_factor_init(factors);

            //Begin
            printf(".");
            start = clock();
            //do stuff
            zmod_poly_factorise(factors, input);
            //End
            end = clock();
            printf("/");
            fflush(stdout);
            //Calc timing
            total_time = ((double) (end - start)) / CLOCKS_PER_SEC;

            //clear memory
            zmod_poly_clear(input);
            zmod_poly_factor_clear(factors);
        }
        total_time = ((double) total_time ) / NUMBER;
        timings[k - MIN_LENGTH] = total_time;
    }

    //output the data
    printf("\n\t \t Average Timings: \n");
    printf("Length \t Average Time \n");
    for(unsigned long k=0; k < MAX_LENGTH - MIN_LENGTH; ++k)
        printf("%lu \t %f \n", k + MIN_LENGTH, timings[k]);
}



-- 
Richard

Re: [flint-devel] Timing code

[Bill H. <goo...@go...>]

Well, apart from the fact that you'll get a much nicer graph the other
way, and the fact that you are being a little unfair to yourself by
not subtracting the time it takes to generate the random polynomials,
this looks like it should work.

It's up to you how you'd like to present your data. You definitely
want to use more than 3 iterations, otherwise the timings will be very
inconsistent. Also, you want to use a number of different *sized*
primes and length polynomials. I suspect you'll find Magma is way
faster for very small primes.

I have in the past profiled by hand on occasion, as it is "quicker".

The time function is alright I find down to times of about 10ms. Of
course you can increase the amount of time by putting everything in a
loop and timing the whole loop. You will of course get microsecond
timing if you use the FLINT code. Magma uses millisecond timing, but
the example profile code is set up to do all the loops for you and
figure out the individual times.

Fortunately factorisation takes a long time on average, so it
shouldn't be that hard to time.

Bill.

2008/8/18 Richard Howell-Peak <ric...@gm...>:
> ok, I will look into that. Before I read your reply I wrote this code which
> just does timings in Flint, then I was going to do some magma timings and do
> the graph in Excel. I guess proper timings are important officially for the
> project but if this way is quicker then I'd do it instead so I can get
> something on my poster. Is this a reasonable way to time the factorisation
> function? It seems to work for me but I'm not sure I trust the std C time
> library very much.
>
> here goes:
>
> #include <time.h>
> #include <sys/times.h>
> #include <unistd.h>
> /**
>  * Main timing function for zmod_poly_factorise
>  */
> #define MIN_LENGTH 250
> #define MAX_LENGTH 270        //Maximum length of polynomial to be timed
> #define NUMBER 3        //Number of random poly's we test to get average
> time
> void timing()
> {
>     //Variables
>     clock_t start, end;
>     double total_time;
>     double timings[MAX_LENGTH - MIN_LENGTH];    //store the average time of
> poly length [i]
>     zmod_poly_t input;
>     zmod_poly_factor_t factors;
>
> printf("Computing Timings \n");
>     for(unsigned long k = MIN_LENGTH; k < MAX_LENGTH; ++k)
>     {
>         total_time = 0;
>         for(unsigned long i = 0; i < NUMBER; ++i)
>         {
>             //Set up a polynomial
>             zmod_poly_init(input, PRIME);
>             randpoly(input, k, PRIME);
>             zmod_poly_make_monic(input, input);
>             //set up factors
>             zmod_poly_factor_init(factors);
>
>             //Begin
>             printf(".");
>             start = clock();
>             //do stuff
>             zmod_poly_factorise(factors, input);
>             //End
>             end = clock();
>             printf("/");
>             fflush(stdout);
>             //Calc timing
>             total_time = ((double) (end - start)) / CLOCKS_PER_SEC;
>
>             //clear memory
>             zmod_poly_clear(input);
>             zmod_poly_factor_clear(factors);
>         }
>         total_time = ((double) total_time ) / NUMBER;
>         timings[k - MIN_LENGTH] = total_time;
>     }
>
>     //output the data
>     printf("\n\t \t Average Timings: \n");
>     printf("Length \t Average Time \n");
>     for(unsigned long k=0; k < MAX_LENGTH - MIN_LENGTH; ++k)
>         printf("%lu \t %f \n", k + MIN_LENGTH, timings[k]);
> }
>
>
>
> --
> Richard
>
> -------------------------------------------------------------------------
> This SF.Net email is sponsored by the Moblin Your Move Developer's challenge
> Build the coolest Linux based applications with Moblin SDK & win great
> prizes
> Grand prize is a trip for two to an Open Source event anywhere in the world
> http://moblin-contest.org/redirect.php?banner_id=100&url=/
> _______________________________________________
> flint-devel mailing list
> fli...@li...
> https://lists.sourceforge.net/lists/listinfo/flint-devel
>
>

[flint-devel] Timing code

[Richard Howell-P. <ric...@gm...>]

Well I'm pretty sure I don't time how long it takes to generate the
polynomial anyway since I start timing just before and after I call
Factorisation. I had the iterations low just so it would run at a reasonable
speed on my laptop, I was thinking maybe 10 or so would be sufficient.

I was wondering what data ranges would be good. I was thinking of doing a
few primes, a small one, a medium one and a large and comparing the output,
then maybe later in the week I'll do one that runs through a whole load of
primes and makes a 2x2 array for each one which I can make into a nice
picture. At the moment I've only been going up to polynomials of length 250
and it looks quite promising - sometimes flint is way ahead, sometimes magma
has the edge and sometimes they're pretty close so we'll see what happens.

-- 
Richard

Re: [flint-devel] Timing code

[William H. <ha...@ya...>]

The timings certainly sound encouraging!

I should mention that sometimes you can be misled
about a timing due to optimisations the compiler is
making. It might decide that it can rearrange things
in a different order, and then you end up timing
something you didn't intend to.

I've certainly had this happen. Usually when you are
making a call to a function in another file or module
this is not a problem, but it is definitely worth
checking by timing everything then timing just the bit
you are not interested in, and taking the difference,
to make sure the result is what you expect.

Regarding primes, Magma has special code for primes p
such that p-1 can be represented in 1, 2, 4, (possibly
also 8 and 16), 22/23, 30 or 64 bits I believe.
Strangely I've not been able to find variances at 53
bits which I found odd, since this is the size of a
double. 

I would try a small prime, e.g. p = 5, one at 22 bits,
one at 30 and one at about 62 or 63 bits. I suspect
you'll be way ahead for large primes. 

Bill.

--- Richard Howell-Peak <ric...@gm...> wrote:

> Well I'm pretty sure I don't time how long it takes
> to generate the
> polynomial anyway since I start timing just before
> and after I call
> Factorisation. I had the iterations low just so it
> would run at a reasonable
> speed on my laptop, I was thinking maybe 10 or so
> would be sufficient.
> 
> I was wondering what data ranges would be good. I
> was thinking of doing a
> few primes, a small one, a medium one and a large
> and comparing the output,
> then maybe later in the week I'll do one that runs
> through a whole load of
> primes and makes a 2x2 array for each one which I
> can make into a nice
> picture. At the moment I've only been going up to
> polynomials of length 250
> and it looks quite promising - sometimes flint is
> way ahead, sometimes magma
> has the edge and sometimes they're pretty close so
> we'll see what happens.
> 
> -- 
> Richard
> >
-------------------------------------------------------------------------
> This SF.Net email is sponsored by the Moblin Your
> Move Developer's challenge
> Build the coolest Linux based applications with
> Moblin SDK & win great prizes
> Grand prize is a trip for two to an Open Source
> event anywhere in the world
>
http://moblin-contest.org/redirect.php?banner_id=100&url=/>
_______________________________________________
> flint-devel mailing list
> fli...@li...
>
https://lists.sourceforge.net/lists/listinfo/flint-devel
> 



      

Re: [flint-devel] Timing code

[Bill H. <goo...@go...>]

Hi Richard,

You could just obtain some timings in both and compare.

If you wanted to do a more comprehensive timing then in the
magma-profiles directory of the source tree are some example profiles
and a template which you can modify. Basically you'll see in the
examples that in one part of the code the entire thing is timed, e.g.
suppose we are timing multiplication of polynomials, we'd time the
entire thing, including multiplying the polynomials, random generation
of the polynomials and setting them up. In the second part, we time
just generating the random polynomials and setting them up. The latter
time is subtracted from the former, leaving the time it took to
multiply the polynomials. This is done for a range of different values
and output to a file.

For example to run the polynomial multiplication example, you have to type:

magma -b poly-mult.m > magma.prof &

To time FLINT is slightly trickier, but not much. You have to add a
file called zmod_poly-profile.c, which you can get by modifying
fmpz_poly-profile.c say. That file contains numerous examples and you
should throw all of them away except one, which you can use as a
template for ideas.

Replace the randpoly function with one that generates random
zmod_poly's with a modulus with a given number of bits and of a given
length.

You can probably throw away the run_triangle function. I'd replace it
with a run_rectangle function which just runs from bits = 2 .. 63 and
length from 1 .. 250 (there isn't much point going beyond 250 since we
don't have asymptotically fast GCD yet).

Keep for example one specific example, e.g. the functions:
sample_fmpz_poly_mul_KS, profDriverString_fmpz_poly_mul_KS,
profDriverDefaultParams_fmpz_poly_mul_KS, profDriver_fmpz_poly_mul_KS.
Obviously you'll have to modify each, including all the names and text
strings and constants so it does what you want and times you
zmod_poly_factor function (which is the equivalent of what Magma
does).

You'll have to add some stuff to the makefile so it builds
zmod_poly-profile.o and zmod_poly-profile. Finally to run the profile
do:

./zmod_poly-profile -t 1 > flint.prof &

You can of course see the last few lines of the profile files being
generated using tail flint.prof or tail magma.prof.

Once they are done, it is actually possible to create a colour graph
in an automated way to compare the two. I'll describe how to do that
once you are up to that stage.

Most importantly, please retain all profiling code. It is very
important when publicly comparing FLINT and Magma that people can see
the precise profiling code used. This is very important for fairness
and so others can check it.

Bill.





2008/8/18 Richard Howell-Peak <ric...@gm...>:
> I was wondering how best to do the time comparisons with magma for the
> factorisation algorithm. Is there an interface in flint for calling magma
> functions, or shall I get some timings in magma, then do some timings in
> flint and compare them like that?
>
> --
> Richard
>
> -------------------------------------------------------------------------
> This SF.Net email is sponsored by the Moblin Your Move Developer's challenge
> Build the coolest Linux based applications with Moblin SDK & win great
> prizes
> Grand prize is a trip for two to an Open Source event anywhere in the world
> http://moblin-contest.org/redirect.php?banner_id=100&url=/
> _______________________________________________
> flint-devel mailing list
> fli...@li...
> https://lists.sourceforge.net/lists/listinfo/flint-devel
>
>