Changeset 31313 in project


Ignore:
Timestamp:
08/30/14 21:48:27 (5 years ago)
Author:
sjamaan
Message:

numbers: Major performance boost reading numbers: try to accumulate an intermediate fixnum digit and factor instead of processing a string-digit at a time.

File:
1 edited

Legend:

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

    r31312 r31313  
    22512251         fixy = C_block_item(self, 3),
    22522252         *digits = C_bignum_digits(new_big),
    2253          *last_digit = digits + C_bignum_size(old_bigx);
     2253         *end_digit = digits + C_bignum_size(old_bigx);
    22542254
    22552255  C_memcpy(digits, C_bignum_digits(old_bigx),
     
    22612261
    22622262  /* Scale up, and sanitise the result. TODO: make normalization one op? */
    2263   *last_digit = bignum_digits_destructive_scale_up_with_carry(
    2264                   digits, last_digit, C_unfix(fixy), 0);
     2263  *end_digit = bignum_digits_destructive_scale_up_with_carry(digits, end_digit,
     2264                                                            C_unfix(fixy), 0);
    22652265  C_bignum_destructive_trim(new_big);
    22662266  C_kontinue(k, C_bignum_normalize(new_big));
     
    24112411}
    24122412
    2413 /* Hashes are mapped to 0 */
    2414 #define HEXDIGIT_CHAR_TO_INT(x)                                         \
    2415   (((x) == '#') ? 0 :                                                   \
    2416    (((x) >= (int)'a') ? ((x) - (int)'a' + 10) : ((x) - (int)'0')))
    2417 
    24182413void C_ccall
    24192414C_digits_to_integer(C_word c, C_word self, C_word k, C_word str,
    24202415                    C_word start, C_word end, C_word radix, C_word negp)
    24212416{
    2422   char *buf;
    2423   C_word n_digits;
    2424   C_word digit;
    24252417  C_word kab[C_SIZEOF_CLOSURE(6)], *ka = kab, k2, size;
    24262418  size_t nbits;
    24272419
    2428   buf = C_c_string(str) + C_unfix(start);
    2429   n_digits = C_unfix(end)-C_unfix(start);
    2430 
    2431   /* TODO: Make a loop that processes as much as possible to fill a
    2432    * fixnum, or at least a halfdigit!
    2433    */
    24342420  assert((C_unfix(radix) > 1) && C_fitsinbignumhalfdigitp(C_unfix(radix)));
    2435   if (n_digits == 0) {
     2421 
     2422  if (start == end) {
    24362423    C_kontinue(k, C_SCHEME_FALSE);
    2437   } else if (n_digits == 1) {
    2438     digit = HEXDIGIT_CHAR_TO_INT(C_tolower((int)*buf));
    2439     if (digit >= C_unfix(radix) || digit < 0)
    2440       C_kontinue(k, C_SCHEME_FALSE);
    2441     else
    2442       C_kontinue(k, C_truep(negp) ? C_fix(-digit) : C_fix(digit));
    2443   }
    2444 
    2445   k2 = C_closure(&ka, 6, (C_word)digits_to_integer_2, k, str, start, end, radix);
    2446 
    2447   nbits = n_digits * ilen(C_unfix(radix));
    2448   size = C_fix(C_BIGNUM_BITS_TO_DIGITS(nbits));
    2449   C_allocate_bignum(3, (C_word)NULL, k2, size, negp, C_SCHEME_TRUE);
     2424  } else {
     2425    k2 = C_closure(&ka, 6, (C_word)digits_to_integer_2, k, str, start, end, radix);
     2426 
     2427    nbits = (C_unfix(end) - C_unfix(start)) * ilen(C_unfix(radix));
     2428    size = C_fix(C_BIGNUM_BITS_TO_DIGITS(nbits));
     2429    C_allocate_bignum(3, (C_word)NULL, k2, size, negp, C_SCHEME_TRUE);
     2430  }
    24502431}
    24512432
     
    24582439         end = C_unfix(C_block_item(self, 4)),
    24592440         radix = C_unfix(C_block_item(self, 5)),
    2460          *digits = C_bignum_digits(result),
    2461          *last_digit = digits, /* Initially, all zeroes */
    2462          carry, digit;
    2463 
    2464   char *str_scan = C_c_string(str) + start;
    2465   char *str_end = C_c_string(str) + end;
    2466 
     2441         first_digit = C_unfix(C_block_item(self, 6)),
     2442         *digits = C_bignum_digits(result),
     2443         *last_digit = digits, /* Initially, bignum is all zeroes */
     2444         big_digit = 0, factor = radix,
     2445         next_big_digit, next_factor,
     2446         carry, str_digit;
     2447  char *str_scan = C_c_string(str) + start,
     2448       *str_end = C_c_string(str) + end;
     2449
     2450  /* Hash characters in numbers are mapped to 0 */
     2451  #define HEXDIGIT_CHAR_TO_INT(x)                                       \
     2452    (((x) == '#') ? 0 :                                                 \
     2453     (((x) >= (int)'a') ? ((x) - (int)'a' + 10) : ((x) - (int)'0')))
     2454
     2455  /* This tries to save up as much as possible in the local C_word
     2456   * big_digit, and only when it exceeds what we would be able to
     2457   * multiply easily, we scale up the bignum and add what we saved up.
     2458   */
    24672459  while (str_scan < str_end) {
    2468     digit = HEXDIGIT_CHAR_TO_INT(C_tolower((int)*str_scan));
    2469     str_scan++; /* Can't do it inline: See HEXDIGIT_CHAR_TO_INT's expansion */
    2470 
    2471     if (digit >= radix || digit < 0) {
     2460    str_digit = HEXDIGIT_CHAR_TO_INT(C_tolower((int)*str_scan));
     2461    str_scan++;
     2462
     2463    next_big_digit = big_digit * radix;
     2464    next_big_digit += str_digit;
     2465    next_factor = factor * radix;
     2466
     2467    if (str_digit >= radix || str_digit < 0) {
    24722468      C_kontinue(k, C_SCHEME_FALSE);
     2469    } else if (C_fitsinbignumhalfdigitp(next_big_digit) &&
     2470               C_fitsinbignumhalfdigitp(next_factor)) {
     2471      factor = next_factor;
     2472      big_digit = next_big_digit;
    24732473    } else {
    24742474      carry = bignum_digits_destructive_scale_up_with_carry(
    2475                 digits, last_digit, radix, digit);
    2476       if (carry) (*last_digit++) = carry;
    2477     }
    2478   }
     2475              digits, last_digit, factor, big_digit);
     2476
     2477      if (carry) (*last_digit++) = carry; /* Move end */
     2478
     2479      big_digit = str_digit;
     2480      factor = radix;
     2481    }
     2482  }
     2483
     2484  /* Final step.  We always must do this, because the loop never
     2485   * processes the "current" character into the bignum (lookahead 1).
     2486   */
     2487  carry = bignum_digits_destructive_scale_up_with_carry(
     2488          digits, last_digit, factor, big_digit);
     2489  if (carry) (*last_digit++) = carry; /* Move end */
     2490
    24792491  C_bignum_destructive_trim(result);
    24802492  C_kontinue(k, C_bignum_normalize(result));
Note: See TracChangeset for help on using the changeset viewer.