Nails or no nails?

[Torbjorn Granlund]

  The GMP code can be difficult to understand, but I think that configure 
  defaults nails to false, and that digit words are always full of data, 
  with no holes. It looks like there's an option to set 1 or 2 nail bits, 
  but the manual says that this is experimental. The 'dumb' code always 
  uses lots of nail bits.

One can ask configure for any number of nail bits (less than the limbs
bits).  But there are some shortcomings in various places in GMP that
will cause errors for large nail sizes.  This is one reason why nails
is marked as experimental.  Another reason is that some parts of the
library, most notably FFT multiplication, does not work at all with
nails and is therefore disabled.

I don't think anything will get better for a nail of more than 4 bits.
On Alpha ev6 and ev7 a 4-bit nail will improve many operations, but
other operations will slow down.

In GMP, a lot of time has been spent on improving the non-nails code,
while very little time has been spent on the nails code.  Infact, for
most machines, enabling a nail will make almost everying fall back to
C code.

I'd expect 32-bit Pentium4 code could be sped up by close to 2x with
well-written nails code.  If the Alpha nails effort were finished, it
would also give close to a 2x speedup.  Opteron would also benefit
from nails; one could accumulate 1 product close to every 2nd cycle
using nails but only one product about every 3rd cycle without nails.

  If I'm adding code, then it's more difficult to use nails, but at least 
  it's then compatible with ltm.

  So, I guess what I'm asking is, how much use do you think nails actually 
  are? Is there a significant potential speed-up benefit?

Yes, for some machines there is a huge potential.  In particular, it
allows one to sum up a column of partial products, without having to
worry about carry.  The number of carry propagations for a schoolbook
multiply goes from O(n^2) to O(n).

  Are you intending to make more use of nails in the future?

Perhaps, but there is a lot of fish to catch.  :-)

Remember that GMP is run as a hobby project, which tend to make me
prioritize what I think is fun for the moment.

-- 
Torbjörn