Changeset 31312 in project


Ignore:
Timestamp:
08/30/14 18:11:42 (5 years ago)
Author:
sjamaan
Message:

numbers: Major performance improvement in reading bignums by making the destructive scaling operation accept and return a carry value; this allows us to avoid iterating again to add the value after scaling up, making it just a pointer dereference.

File:
1 edited

Legend:

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

    r31311 r31312  
    20512051static void bignum_negate_2(C_word c, C_word self, C_word new_big);
    20522052static void allocate_bignum_2(C_word c, C_word self, C_word bigvec);
    2053 static void bignum_digits_destructive_scale_up(C_word big, C_word fix_factor);
     2053static C_word bignum_digits_destructive_scale_up_with_carry(C_word *start, C_word *end, C_word fix_factor, C_word carry);
    20542054static void bignum_times_halfdigit_fixnum(C_word k, C_word bigx, C_word fixy, C_word negp);
    20552055static void bignum_times_halfdigit_fixnum_2(C_word c, C_word self, C_word new_big);
     
    22132213}
    22142214
    2215 static void
    2216 bignum_digits_destructive_scale_up(C_word big, C_word factor)
    2217 {
    2218   C_word digit, product_hi, product_lo, carry = 0;
    2219   C_word *scan = C_bignum_digits(big);
    2220   C_word *last_digit = scan + C_bignum_size(big);
    2221 
    2222   while (scan < last_digit) {
     2215static C_word
     2216bignum_digits_destructive_scale_up_with_carry(C_word *start, C_word *end, C_word factor, C_word carry)
     2217{
     2218  C_word digit, product_hi, product_lo, *scan = start;
     2219
     2220  assert(C_fitsinbignumhalfdigitp(carry));
     2221
     2222  while (scan < end) {
    22232223    digit = (*scan);
    22242224    product_lo = factor * C_BIGNUM_DIGIT_LO_HALF(digit) + carry;
     
    22292229    carry = C_BIGNUM_DIGIT_HI_HALF(product_hi);
    22302230  }
    2231   assert(carry == 0);
    2232 }
    2233 
    2234 static void
    2235 bignum_digits_destructive_add(C_word big, C_word value)
    2236 {
    2237   C_word *scan = C_bignum_digits(big);
    2238   C_word digit = (*scan) + value;
    2239 
    2240   while(!C_fitsinbignumdigitp(digit)) {
    2241     (*scan++) = digit & C_BIGNUM_DIGIT_MASK;
    2242     digit = ((*scan) + 1);
    2243   }
    2244   (*scan) = digit;
     2231  return carry;
    22452232}
    22462233
     
    22622249  C_word k = C_block_item(self, 1),
    22632250         old_bigx = C_block_item(self, 2),
    2264          fixy = C_block_item(self, 3);
    2265 
    2266   C_memcpy(C_bignum_digits(new_big), C_bignum_digits(old_bigx),
     2251         fixy = C_block_item(self, 3),
     2252         *digits = C_bignum_digits(new_big),
     2253         *last_digit = digits + C_bignum_size(old_bigx);
     2254
     2255  C_memcpy(digits, C_bignum_digits(old_bigx),
    22672256           /* TODO: This is currently in bytes.  If we change the
    22682257            * representation that needs to change!
     
    22712260           C_header_size(C_internal_bignum(old_bigx))-C_wordstobytes(1));
    22722261
    2273   /* Most significant digit is not initialised; set it to 0. */
    2274   C_bignum_digits(new_big)[C_bignum_size(old_bigx)] = 0;
    2275 
    22762262  /* Scale up, and sanitise the result. TODO: make normalization one op? */
    2277   bignum_digits_destructive_scale_up(new_big, C_unfix(fixy));
     2263  *last_digit = bignum_digits_destructive_scale_up_with_carry(
     2264                  digits, last_digit, C_unfix(fixy), 0);
    22782265  C_bignum_destructive_trim(new_big);
    22792266  C_kontinue(k, C_bignum_normalize(new_big));
     
    24712458         end = C_unfix(C_block_item(self, 4)),
    24722459         radix = C_unfix(C_block_item(self, 5)),
    2473          digit;
     2460         *digits = C_bignum_digits(result),
     2461         *last_digit = digits, /* Initially, all zeroes */
     2462         carry, digit;
    24742463
    24752464  char *str_scan = C_c_string(str) + start;
     
    24832472      C_kontinue(k, C_SCHEME_FALSE);
    24842473    } else {
    2485       bignum_digits_destructive_scale_up(result, radix);
    2486       bignum_digits_destructive_add(result, digit);
     2474      carry = bignum_digits_destructive_scale_up_with_carry(
     2475                digits, last_digit, radix, digit);
     2476      if (carry) (*last_digit++) = carry;
    24872477    }
    24882478  }
Note: See TracChangeset for help on using the changeset viewer.