Opened 12 years ago

Last modified 11 years ago

#354 new enhancement

Need faster bignums

Reported by: gz Owned by: rme
Priority: minor Milestone:
Component: Runtime (threads, GC) Version:
Keywords: Cc:

Change History (3)

comment:1 Changed 12 years ago by gb

There seems to be some low-hanging fruit there.

On a fairly fast x86-64 Linux box, (DOTIMES (I 10) (FACT 10000)) took about 8.5 seconds; a lot of that was spent in the FLETed function MULTIPLY-BIGNUM-AND-1-DIGIT-FIXNUM (defined in MULTIPLY-BIGNUM-AND-FIXNUM). Profiling suggested that a lot of the time in the inner function was spent in the inline expansion of BIGNUM-REF and BIGNUM-SET (especially the latter), and the paranoid (LOGAND ...) in BIGNUM-SET seemed to cause some type- and bounds-checking that shouldn't have happened with SPEED=3 SAFETY=0.

I'm sure that there are ways of speeding things up that require more effort, but changing BIGNUM-REF and BIGNUM-SET to macros (and removing the LOGAND paranoia) caused the time to drop to a bit under 4 seconds. That may just be the difference between "really bad" and "still pretty bad" and getting things to the next level may be a lot harder, but there may be a few other things that're simple, obvious, and effective.

comment:2 Changed 12 years ago by rme

Since the 64-bit bignum code is mostly lisp, and a bit less crufty than that 32-bit code, it might be fun and not too hard to implement Karatsuba-style multiplication for long bignums. The ppc32 port does that, but I didn't implement the necessary code for x8632. I was getting pretty tired of hacking x86 lap...

If we were really ambitious, we could increase the bignum digit size to 64 bits on 64-bit platforms.

comment:3 Changed 11 years ago by rme

  • Owner changed from gb to rme

On 64-bit platforms, r12839, r12847, and r12850 try to speed up bignum * bignum and bignum * fixnum operations by operating on 64 bits at a time.

Note: See TracTickets for help on using tickets.