RFR 4641897: Faster string conversion of large integers

[Dmitry Nadezhin]

Thank you, Aleksey!

Alan said: "I'm willing to review any rewrites that people might suggest".

Here is a concretization of Aleksey's patch for Alan's review.

*** Alan's BigInteger.java
--- BigInteger.java patched according to Aleksey's advice
***************
*** 1038,1048 ****
      /**
       * The cache of powers of each radix.  This allows us to not have to
       * recalculate powers of radix^(2^n) more than once.  This speeds
       * Schoenhage recursive base conversion significantly.
       */
!     private static ArrayList<BigInteger>[] powerCache;

      /** The cache of logarithms of radices for base conversion. */
      private static final double[] logCache;

      /** The natural log of 2.  This is used in computing cache indices. */
--- 1038,1048 ----
      /**
       * The cache of powers of each radix.  This allows us to not have to
       * recalculate powers of radix^(2^n) more than once.  This speeds
       * Schoenhage recursive base conversion significantly.
       */
!     private static volatile BigInteger[][] powerCache;

      /** The cache of logarithms of radices for base conversion. */
      private static final double[] logCache;

      /** The natural log of 2.  This is used in computing cache indices. */
***************
*** 1059,1076 ****
          /*
           * Initialize the cache of radix^(2^x) values used for base
conversion
           * with just the very first value.  Additional values will be
created
           * on demand.
           */
!         powerCache = (ArrayList<BigInteger>[])
!             new ArrayList[Character.MAX_RADIX+1];
          logCache = new double[Character.MAX_RADIX+1];

          for (int i=Character.MIN_RADIX; i<=Character.MAX_RADIX; i++)
          {
!             powerCache[i] = new ArrayList<BigInteger>(1);
!             powerCache[i].add(BigInteger.valueOf(i));
              logCache[i] = Math.log(i);
          }
      }

      /**
--- 1059,1074 ----
          /*
           * Initialize the cache of radix^(2^x) values used for base
conversion
           * with just the very first value.  Additional values will be
created
           * on demand.
           */
!         powerCache = new BigInteger[Character.MAX_RADIX+1][];
          logCache = new double[Character.MAX_RADIX+1];

          for (int i=Character.MIN_RADIX; i<=Character.MAX_RADIX; i++)
          {
!             powerCache[i] = new BigInteger[] { BigInteger.valueOf(i) };
              logCache[i] = Math.log(i);
          }
      }

      /**
***************
*** 3450,3473 ****
       * If this value doesn't already exist in the cache, it is added.
       * <p/>
       * This could be changed to a more complicated caching method using
       * <code>Future</code>.
       */
!     private static synchronized BigInteger getRadixConversionCache(int
radix,
!                                                                    int
exponent) {
          BigInteger retVal = null;
!         ArrayList<BigInteger> cacheLine = powerCache[radix];
!         int oldSize = cacheLine.size();
          if (exponent >= oldSize) {
!             cacheLine.ensureCapacity(exponent+1);
              for (int i=oldSize; i<=exponent; i++) {
!                 retVal = cacheLine.get(i-1).square();
!                 cacheLine.add(i, retVal);
              }
!         }
!         else
!             retVal = cacheLine.get(exponent);

          return retVal;
      }

      /* zero[i] is a string of i consecutive zeros. */
--- 3448,3471 ----
       * If this value doesn't already exist in the cache, it is added.
       * <p/>
       * This could be changed to a more complicated caching method using
       * <code>Future</code>.
       */
!     private static BigInteger getRadixConversionCache(int radix, int
exponent) {
          BigInteger retVal = null;
!         BigInteger[][] pc = powerCache;
!         BigInteger[] cacheLine = pc[radix];
!         int oldSize = cacheLine.length;
          if (exponent >= oldSize) {
!             cacheLine = Arrays.copyOf(cacheLine, exponent + 1);
              for (int i=oldSize; i<=exponent; i++) {
!                 retVal = cacheLine[i-1].square();
!                 cacheLine[i] = retVal;
              }
!             powerCache = pc; // publish by writing volatile variable
!         } else
!             retVal = cacheLine[exponent];

          return retVal;
      }

      /* zero[i] is a string of i consecutive zeros. */


On Sat, Jun 22, 2013 at 2:54 PM, Aleksey Shipilev <
aleksey.shipilev at oracle.com> wrote:

> On 06/22/2013 02:50 PM, Aleksey Shipilev wrote:
> > On 06/22/2013 08:06 AM, Dmitry Nadezhin wrote:
> >> Alexey,
> >>
> >> Each possible radix has its cacheLine in the cache.
> >>
> >> Cache contents looks like
> >> BigInteger[][] powerCache = new BigInteger[37] {
> >> /*0*/ null,
> >> /*1*/ null,
> >> /*2*/ new BigInteger[] { 2, 4, 16, 256, 32768, ... },
> >> /*3*/ new BigInteger[] { 3, 9, 81, ... },
> >> /*4*/ new BigInteger[] { 4, 16, 256, ... }
> >> /*5*/ new BigInteger[] { 5, 25, 625, ... },
> >> /*6*/ new BigInteger[] { 6 },
> >> /*7*/ new BigInteger[] { 7 },
> >> . . .
> >> /*36*/ new BigInteger[] { 36 }
> >> };
> >>
> >> Is there an idiom for a list/array of volatile references ?
> >
> > AtomicReferenceArray is your friend there. Although I'm not sure why you
> > need the list of volatile references in this case. Placing volatile to
> > the root reference resolves the race.
> >
> >> I am not sure that such naive code works:
> >> volatile BigInteger[][] powerCache = ..,
> >
> > Why wouldn't it work?
> >
> >  volatile T[][] cache;
> >
> >  T[] get(int index) {
> >     T[][] lc = cache;
> >     if (index >= lc.length) { // need resizing
> >        lc = generateNew(index << 1);
> >        cache = lc;
> >     }
> >     return lc[index];
> >  }
> >
> > If you need to populate the 2nd level, then you have to have the final
> > volatile write to the $cache. The corresponding $cache volatile read
> > makes the update on 2nd level visible.
> >
> >  T get(int index1, index2) {
> >     T[][] lc = cache;
> >     if (index1 >= lc.length) { // needs resizing
> >        lc = generateNewT2(index1 << 1);
> >        cache = lc;
> >     }
> >     T[] lt = lc[index2];
> >     if (index2 >= lt.length) { // needs resizing
> >        lt = generateNewT1(index2 << 1);
> >        lc[index2] = lt;
> >        cache = lc; // publish
> >     }
> >     return lt[index2];
> >  }
>
> Of course, there is a series of typos. Should instead be:
>
>   T get(int index1, index2) {
>      T[][] lc = cache;
>      if (index1 >= lc.length) { // needs resizing
>         lc = <generate_new_T[][]_of_size>((index1 << 1) + 1);
>         cache = lc;
>      }
>      T[] lt = lc[index2];
>      if (index2 >= lt.length) { // needs resizing
>         lt = <generate_new_T[]_of_size>((index2 << 1) + 1);
>         lc[index1] = lt;
>         cache = lc; // publish
>      }
>      return lt[index2];
>   }
>
> -Aleksey.
>