Changeset 32555 in project


Ignore:
Timestamp:
07/06/15 23:05:35 (5 years ago)
Author:
sjamaan
Message:

numbers: Improve stability of Burnikel-Ziegler performance.

This changes Burnikel-Ziegler division's threshold check to look at
the *difference* between the two arguments instead of the size of the
smallest one. This idea is taken from MCA, algorithm 1.9.

This seems to make a big difference on the "pidigits" benchmark from
the Great Language Shootout game, which somehow triggers such
pathological behaviour of the B/Z division routine that using plain
gradebook division would be up to three times faster on that
benchmark. Other benchmarks are mostly unaffected by this issue.

Many thanks to "balkenbrij" on Reddit for finding this issue!

Location:
release/4/numbers/trunk
Files:
3 edited

Legend:

Unmodified
Added
Removed
  • release/4/numbers/trunk/numbers-c.c

    r32548 r32555  
    31293129  case 1:
    31303130  default:
    3131     size = C_bignum_size(y);
    3132     if (size > C_BURNIKEL_ZIEGLER_THRESHOLD &&
    3133         /* This avoids endless recursion for odd Ns just above threshold */
    3134         !(size & 1 && size < (C_BURNIKEL_ZIEGLER_THRESHOLD << 1))) {
     3131    size = C_bignum_size(x) - C_bignum_size(y);
     3132    if (size > C_BURNIKEL_ZIEGLER_DIFF_THRESHOLD) {
    31353133      try_extended_number("numbers#@bignum-2-divrem-burnikel-ziegler", 5,
    31363134                          k, x, y, return_q, return_r);
  • release/4/numbers/trunk/numbers-c.h

    r32303 r32555  
    3636 * division.  It creates even more garbage than Karatsuba :(
    3737 */
    38 #define C_BURNIKEL_ZIEGLER_THRESHOLD 300
     38#define C_BURNIKEL_ZIEGLER_DIFF_THRESHOLD 300
    3939/* This threshold is in terms of the expected string length.  It
    4040 * depends on division speed: if you change the above, change this too.
  • release/4/numbers/trunk/numbers.scm

    r32544 r32555  
    538538  (define-inline (digit-bits n)
    539539    (fx* (foreign-value "C_BIGNUM_DIGIT_LENGTH" int) n))
    540   (define DIV-LIMIT (foreign-value "C_BURNIKEL_ZIEGLER_THRESHOLD" int))
     540  (define DIV-LIMIT (foreign-value "C_BURNIKEL_ZIEGLER_DIFF_THRESHOLD" int))
    541541
    542542  ;; Here and in 2n/1n we pass both b and [b1, b2] to avoid splitting
     
    560560
    561561  (define (burnikel-ziegler-2n/1n a b b1 b2 n)
    562     (if (or (fxodd? n) (fx< n DIV-LIMIT))
     562    (if (or (fxodd? n) (fixnum? a) (fixnum? b)
     563            ;; Paper says we should check for N being less than
     564            ;; DIV-LIMIT, but in practice that causes performance
     565            ;; stability issues.  Instead, we look at the actual
     566            ;; difference between the numbers (idea taken from MCA,
     567            ;; Algorithm 1.9).
     568            (fx< (fx- (bignum-digit-count a) (bignum-digit-count b))
     569                 DIV-LIMIT))
    563570        ((##core#primitive "C_u_integer_divrem") a b)
    564571        (let* ((n/2 (fxshr n 1))
Note: See TracChangeset for help on using the changeset viewer.