Cache the intermediate result of a div (or rem) operation on bigint and reuse if

runtime/lib/bigint.dart

 // Copyright (c) 2014, the Dart project authors.  Please see the AUTHORS file
 // for details. All rights reserved. Use of this source code is governed by a
 // BSD-style license that can be found in the LICENSE file.
 
 // Copyright 2009 The Go Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style
 // license that can be found in the LICENSE file.
 
 /*
  * Copyright (c) 2003-2005  Tom Wu
@@ skipping 47 matching lines @@
   static const int _MIN_INT64 = (-1) << 63;
   static const int _MAX_INT64 = 0x7fffffffffffffff;
 
   // Bigint constant values.
   // Note: Not declared as final in order to satisfy optimizer, which expects
   // constants to be in canonical form (Smi).
   static _Bigint _MINUS_ONE = new _Bigint._fromInt(-1);
   static _Bigint _ZERO = new _Bigint._fromInt(0);
   static _Bigint _ONE = new _Bigint._fromInt(1);
 
+  // Result cache for last _divRem call.
+  static Uint32List _lastDividend_digits;
+  static int _lastDividend_used;
+  static Uint32List _lastDivisor_digits;
+  static int _lastDivisor_used;
+  static Uint32List _lastQuoRem_digits;
+  static int _lastQuoRem_used;
+  static int _lastRem_used;
+  static int _lastRem_nsh;
+
   // Internal data structure.
   bool get _neg native "Bigint_getNeg";
   int get _used native "Bigint_getUsed";
   Uint32List get _digits native "Bigint_getDigits";
 
   // Factory returning an instance initialized with the given field values.
   // The 'digits' array is first clamped and 'used' is reduced accordingly.
   // A leading zero digit may be initialized to guarantee that digit pairs can
   // be processed as 64-bit values on 64-bit platforms.
   factory _Bigint(bool neg, int used, Uint32List digits)
@@ skipping 107 matching lines @@
     return new _Bigint(_neg, r_used, r_digits);
   }
 
   // r_digits[0..r_used-1] = x_digits[0..x_used-1] << n*_DIGIT_BITS.
   // Return r_used.
   static int _dlShiftDigits(Uint32List x_digits, int x_used, int n,
                             Uint32List r_digits) {
     if (x_used == 0) {
       return 0;
     }
-    if (n == 0 && r_digits == x_digits) {
+    if (n == 0 && identical(r_digits, x_digits)) {
       return x_used;
     }
     final r_used = x_used + n;
     assert(r_digits.length >= r_used + (r_used & 1));
     var i = x_used;
     while (--i >= 0) {
       r_digits[i + n] = x_digits[i];
     }
     i = n;
     while (--i >= 0) {
@@ skipping 731 matching lines @@
         args[_QD] = _DIGIT_MASK;
       } else {
         args[_QD] = qd;
       }
     }
     return 1;
   }
 
   // Return trunc(this / a), a != 0.
   _Bigint _div(_Bigint a) {
-    return _divRem(a, true);
+    assert(a._used > 0);
+    if (_used < a._used) {
+      return _ZERO;
+    }
+    // Check if result is cached (identical on Bigint is too expensive).
+    if (this._used != _lastDividend_used ||
+        a._used != _lastDivisor_used ||
+        !identical(this._digits, _lastDividend_digits) ||
+        !identical(a._digits, _lastDivisor_digits)) {
+      _divRem(a);
+    }
+    // Return quotient, i.e.
+    // _lastQuoRem_digits[_lastRem_used.._lastQuoRem_used-1] with proper sign.
+    var lastQuo_used = _lastQuoRem_used - _lastRem_used;
+    var quo_digits = _cloneDigits(_lastQuoRem_digits,
+                                  _lastRem_used,
+                                  _lastQuoRem_used,
+                                  lastQuo_used);
+    var quo = new _Bigint(false, lastQuo_used, quo_digits);
+    if (_neg != a._neg && quo._used > 0) {

[srdjan, 2015/04/02 21:06:41]

Use parentheses.

[regis, 2015/04/06 19:51:18]

Done.

+      quo = quo._negate();
+    }
+    return quo;
   }
 
   // Return this - a * trunc(this / a), a != 0.
   _Bigint _rem(_Bigint a) {
-    return _divRem(a, false);
+    assert(a._used > 0);
+    if (_used < a._used) {
+      return this;
+    }
+    // Check if result is cached (identical on Bigint is too expensive).
+    if (this._used != _lastDividend_used ||
+        a._used != _lastDivisor_used ||
+        !identical(this._digits, _lastDividend_digits) ||
+        !identical(a._digits, _lastDivisor_digits)) {

[srdjan, 2015/04/02 21:06:41]

Factor out the test.

[regis, 2015/04/06 19:51:18]

I moved the test to _divRem.

+      _divRem(a);
+    }
+    // Return remainder, i.e.
+    // denormalized _lastQuoRem_digits[0.._lastRem_used-1] with proper sign.
+    var rem_digits = _cloneDigits(_lastQuoRem_digits,
+                                  0,
+                                  _lastRem_used,
+                                  _lastRem_used);
+    var rem = new _Bigint(false, _lastRem_used, rem_digits);
+    if (_lastRem_nsh > 0) {
+      rem = rem._rShift(_lastRem_nsh);  // Denormalize remainder.
+    }
+    if (_neg && rem._used > 0) {

[srdjan, 2015/04/02 21:06:42]

Use parentheses please

[regis, 2015/04/06 19:51:18]

Done.

+      rem = rem._negate();
+    }
+    return rem;
   }
 
-  // Return trunc(this / a), a != 0, if div == true.
-  // Return this - a * trunc(this / a), a != 0, if div == false.
-  _Bigint _divRem(_Bigint a, bool div) {
-    assert(a._used > 0);
-    if (_used < a._used) {
-      return div ? _ZERO : this;
-    }
+  // Cache concatenated positive quotient and normalized positive remainder.
+  void _divRem(_Bigint a) {
     var nsh = _DIGIT_BITS - _nbits(a._digits[a._used - 1]);
     // For 64-bit processing, make sure y has an even number of digits.
     if (a._used.isOdd) {
       nsh += _DIGIT_BITS;
     }
     // Concatenated positive quotient and normalized positive remainder.
     var r_digits;
     var r_used;
     // Normalized positive divisor.
     var y_digits;
@@ skipping 70 matching lines @@
             if (yt_qd[_QD] == 0) {
               --yt_qd[_QD_HI];
             }
             --yt_qd[_QD];
             assert(r_digits[i] <= yt_qd[_QD_HI]);
           }
         }
       }
       i -= d0;
     }
-    if (div) {
-      // Return quotient, i.e. r_digits[y_used..r_used-1] with proper sign.
-      r_digits = _cloneDigits(r_digits, y_used, r_used, r_used - y_used);
-      var r = new _Bigint(false, r_used - y_used, r_digits);
-      if (_neg != a._neg && r._used > 0) {
-        r = r._negate();
-      }
-      return r;
-    }
-    // Return remainder, i.e. denormalized r_digits[0..y_used-1] with
-    // proper sign.
-    r_digits = _cloneDigits(r_digits, 0, y_used, y_used);
-    var r = new _Bigint(false, y_used, r_digits);
-    if (nsh > 0) {
-      r = r._rShift(nsh);  // Denormalize remainder.
-    }
-    if (_neg && r._used > 0) {
-      r = r._negate();
-    }
-    return r;
+    // Cache result.
+    _lastDividend_digits = _digits;
+    _lastDividend_used = _used;
+    _lastDivisor_digits = a._digits;
+    _lastDivisor_used = a._used;
+    _lastQuoRem_digits = r_digits;
+    _lastQuoRem_used = r_used;
+    _lastRem_used = y_used;
+    _lastRem_nsh = nsh;
   }
 
   // Customized version of _rem() minimizing allocations for use in reduction.
   // Input:
   //   x_digits[0..x_used-1]: positive dividend.
   //   y_digits[0..y_used-1]: normalized positive divisor.
   //   ny_digits[0..y_used-1]: negated y_digits.
   //   nsh: normalization shift amount.
   //   yt_qd: top y digit(s) and place holder for estimated quotient digit(s).
   //   t_digits: temp array of 2*y_used digits.
@@ skipping 680 matching lines @@
 
   int _mul(Uint32List x_digits, int x_used,
            Uint32List y_digits, int y_used,
            Uint32List r_digits) {
     var r_used = _Bigint._mulDigits(x_digits, x_used,
                                     y_digits, y_used,
                                     r_digits);
     return _reduce(r_digits, r_used);
   }
 }