Dumb python questions
phr-n2001 at nightsong.com
Sun Aug 19 21:12:35 CEST 2001
"Alex Martelli" <aleaxit at yahoo.com> writes:
> Unfortunately, gmpy just relies on GMP, which in turn only has the
> carefully tuned machine-language inner loops on a few selected
> architectures -- elsewhere they're replaced by carefully-coded C
> which, indeed, cannot be quite as fast. I noticed because at first
> I only had a C-only version of GMP for Windows/VC++6; when I
> moved to a GMP version including the port of the assembly part,
> performance soared [and another boost came from switching to
> an Athlon chip from a pure-Intel one -- so I sort of suspect that
> there should probably be different machine-language inner loops
> for top performance on Athlon vs Pentium3, given different
> caching, branch-prediction, etc, etc]. Unfortunately I did no
> careful measurements (mea culpa!) so thanks for giving them...
The main bottleneck in C is integer multiplication. Most computers
have an integer multiply instruction that multiplies two words and
gives a doubleword result (32*32->64 bits), so in asm you just use it.
There's not a good way to code that portably in C, so you end up using
four 16*16->32 multiplications instead of one 32*32->64
multiplication. That slows you down by a factor of 4 right away.
The other differences coming from e.g. differences in cpu architecture
between x86 variants are minor by comparison. One exception: the
original Pentium had a much faster FMUL (floating point mul) instruction
than IMUL, and it paid off to totally reorganize the bignum calculation
to do the intermediate calculations in floating point.
(an MS Word file, unfortunately) has a bunch of description of how
to do fast bignum arithmetic. See also http://indigo.ie/~mscott
for some benchmarks.
> > in portable C. Python's arithmetic is around 100x faster than
> > perl's Math::BigInt.
> Interesting -- I guess (and hope, because competition is what
> keeps everybody on their toes:-) that some devoted Perlist is
> already busy recoding their big-int module for performance?-)
I think there are GMP and other native C extensions for fast
arithmetic in Perl. Math::BigInt is written in pure Perl,
representing long ints as strings. That's why it's so slow.
More information about the Python-list