Uploaded image for project: 'Commons RNG'
  1. Commons RNG
  2. RNG-87

MultiplyWithCarry256

    XMLWordPrintableJSON

Details

    • Improvement
    • Status: Closed
    • Minor
    • Resolution: Implemented
    • 1.3
    • 1.3
    • core

    Description

      The MultiplyWithCarry256 currently uses a length 256 array for internal state. This is cycled through continuously. The current implementation refills the state every 256 calls to next:

      public int next() {
          if (index == Q_SIZE) { // Whole state used up.
              // Refill.
              for (int i = 0; i < Q_SIZE; i++) {
                  final long t = A * (state[i] & 0xffffffffL) + carry;
                  carry = (int) (t >> 32);
                  state[i] = (int) t;
              }
      
              // Reset current index.
              index = 0;
          }
      
          return state[index++];
      }
      

      This can be changed to continuously update the state for only a single index on each call to next:

      public int next() {
          // Produce an index in the range 0-255
          final int i = index++ & 0xFF;
          final long t = A * (state[i] & 0xffffffffL) + carry;
          carry = (int) (t >> 32);
          return state[i] = (int) t;
      }
      

      This avoids an if statement check and marginally improves performance. It has the advantage of not advancing the state further ahead than necessary.

      MWC_256B is the new version. JMH results from the GenerationPerformance benchmark.

      openjdk version "1.8.0_191"
      OpenJDK Runtime Environment (build 1.8.0_191-8u191-b12-2ubuntu0.16.04.1-b12)
      OpenJDK 64-Bit Server VM (build 25.191-b12, mixed mode)
      
      numValues randomSourceName Method Score Error Median
      1 SPLIT_MIX_64 nextInt 0.00478 4.45e-05 0.00477
      1 MWC_256 nextInt 0.00521 1.69e-05 0.00521
      1 MWC_256B nextInt 0.00519 0.000321 0.00512
      100 SPLIT_MIX_64 nextInt 0.421 0.0131 0.418
      100 MWC_256 nextInt 0.452 0.000968 0.452
      100 MWC_256B nextInt 0.443 0.00183 0.442
      10000 SPLIT_MIX_64 nextInt 41.7 0.0725 41.7
      10000 MWC_256 nextInt 44.5 2.25 43.9
      10000 MWC_256B nextInt 42.6 0.037 42.6
      1000000 SPLIT_MIX_64 nextInt 3.77e+03 21.2 3.77e+03
      1000000 MWC_256 nextInt 4.16e+03 12.8 4.16e+03
      1000000 MWC_256B nextInt 3.98e+03 120 3.96e+03
      java version "11.0.2" 2019-01-15 LTS
      Java(TM) SE Runtime Environment 18.9 (build 11.0.2+9-LTS)
      Java HotSpot(TM) 64-Bit Server VM 18.9 (build 11.0.2+9-LTS, mixed mode)
      
      numValues randomSourceName Method Score Error Median
      1 SPLIT_MIX_64 nextInt 0.00469 4.98e-06 0.00469
      1 MWC_256 nextInt 0.00553 2.09e-05 0.00553
      1 MWC_256B nextInt 0.00493 4.32e-05 0.00492
      100 SPLIT_MIX_64 nextInt 0.435 0.000624 0.435
      100 MWC_256 nextInt 0.467 0.00284 0.466
      100 MWC_256B nextInt 0.455 0.00105 0.455
      10000 SPLIT_MIX_64 nextInt 43 4.94 41.9
      10000 MWC_256 nextInt 45.8 0.132 45.8
      10000 MWC_256B nextInt 43 0.033 43
      1000000 SPLIT_MIX_64 nextInt 3.7e+03 7.88 3.7e+03
      1000000 MWC_256 nextInt 4.17e+03 45.3 4.15e+03
      1000000 MWC_256B nextInt 4.12e+03 4.76 4.12e+03

      Attachments

        1. big.jpg
          20 kB
          Alex Herbert
        2. MWC_256_2.jpg
          21 kB
          Alex Herbert
        3. MWC_256_3.jpg
          26 kB
          Alex Herbert
        4. MWC_256_3.png
          80 kB
          Alex Herbert
        5. MWC_256.jpg
          22 kB
          Alex Herbert
        6. Shuffle.jpg
          25 kB
          Alex Herbert
        7. small.jpg
          17 kB
          Alex Herbert

        Issue Links

          Activity

            People

              aherbert Alex Herbert
              aherbert Alex Herbert
              Votes:
              0 Vote for this issue
              Watchers:
              1 Start watching this issue

              Dates

                Created:
                Updated:
                Resolved:

                Time Tracking

                  Estimated:
                  Original Estimate - Not Specified
                  Not Specified
                  Remaining:
                  Remaining Estimate - 0h
                  0h
                  Logged:
                  Time Spent - 50m
                  50m