Shared toom evaluation functions
tg at gmplib.org
Thu Nov 19 15:56:06 CET 2009
nisse at lysator.liu.se (Niels Möller) writes:
Torbjorn Granlund <tg at gmplib.org> writes:
> I think we might want to make our lives in toom more difficult:
> We should add, to gmp-mparam.h, cycle counts for available mpn functions
> as first degree polynomials. Measurements for that can easily be added
> to tuneup.c.
I was about to suggest something similar, but a little simpler, with
only a cycles/limb value for each of the O(n) functions. Do you think
the constant overhead is important here?
Perhaps not here, but it will be useful elsewhere. It is not hard to
measure one paramater when we measure the other.
If we in toom thin the cnstat term is irrelevent, then of course we can
just compare the x^1 term. Much simpler indeed.
The first conditional (add_n_sub_n, which I guess should always be
used when available natively) appears in toom32_mul. It's more
relevant for the variuos interpolation functions, i.e., from
toom33/toom42 and up, where there are several possible strategies for
division and multiplication by constants.
My gut feeling is that the constant term shouldn't be so significant
for the choices for toom interpolation.
Perhaps not. But when working with operands that are known to be small
(say in toom22) three calls might be slower than two calls, even if the
three calls are asymptotically faster.
We might have such a situation with the new toom22 code compared to the
old kara code; we have one more add_n call but n/2 less adding. This is
surely not always a good idea, on all machines. The constant term is
needed to determine that.
More information about the gmp-devel