Skip to content

Use Long arithmetics in ju.Random, instead of Doubles. #5195

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom
Open
wants to merge 2 commits into
base: main
Choose a base branch
from
Open

Use Long arithmetics in ju.Random, instead of Doubles. #5195

wants to merge 2 commits into from

Conversation

sjrd
Copy link
Member

@sjrd sjrd commented Jun 8, 2025

We've come full circle. Back in 5e27def, we had optimized ju.Random by using Doubles instead of Longs. This commit optimizes it further by ... using Longs instead of Doubles.

It is still more complicated than using the spec as is. We compute things in a slightly different way, that allows some internal constant-folding to happen. This way, there are as many underlying int multiplications as there were double multiplications before (namely 4).

Here is the breakdown of how many operations in which category we have before and after.

Category Count before Count after
double multiplications 4 0
int multiplications 0 4
double additions 2 0
int additions 2 6
double-to-int wrap (x | 0) 3 0
logical 7 12
total 18 22

That's 4 more primitive operations, but we removed 9 operations involving Doubles to replace them by Int operations only.

I did not do any benchmarks of this. I'm not currently on a machine that is suited to benchmarking. I can do some benchmarks in a week, if that is desirable.

Produced code before:

$c_ju_Random.prototype.setSeed__J__V = (function(seed_in) {
  var lo = ((-554899859) ^ seed_in.RTLong__f_lo);
  var hi = (5 ^ seed_in.RTLong__f_hi);
  var hi$1 = (65535 & hi);
  var lo$1 = (((lo >>> 24) | 0) | (hi$1 << 8));
  this.ju_Random__f_java$util$Random$$seedHi = lo$1;
  this.ju_Random__f_java$util$Random$$seedLo = (16777215 & lo);
  this.ju_Random__f_haveNextNextGaussian = false;
});
$c_ju_Random.prototype.next__I__I = (function(bits) {
  var oldSeedHi = this.ju_Random__f_java$util$Random$$seedHi;
  var oldSeedLo = this.ju_Random__f_java$util$Random$$seedLo;
  var loProd = ((1.5525485E7 * oldSeedLo) + 11.0);
  var hiProd = ((1502.0 * oldSeedLo) + (1.5525485E7 * oldSeedHi));
  var x = (loProd / 1.6777216E7);
  var newSeedHi = (16777215 & (($uI((x | 0)) + (16777215 & $uI((hiProd | 0)))) | 0));
  var newSeedLo = (16777215 & $uI((loProd | 0)));
  this.ju_Random__f_java$util$Random$$seedHi = newSeedHi;
  this.ju_Random__f_java$util$Random$$seedLo = newSeedLo;
  var result32 = ((newSeedHi << 8) | (newSeedLo >> 16));
  return ((result32 >>> ((32 - bits) | 0)) | 0);
});

Produced code after:

$c_ju_Random.prototype.setSeed__J__V = (function(seed_in) {
  var lo = ((-554899859) ^ seed_in.RTLong__f_lo);
  var hi = (5 ^ seed_in.RTLong__f_hi);
  var hi$1 = (65535 & hi);
  this.ju_Random__f_java$util$Random$$seedHi = hi$1;
  this.ju_Random__f_java$util$Random$$seedLo = lo;
  this.ju_Random__f_haveNextNextGaussian = false;
});
$c_ju_Random.prototype.next__I__I = (function(bits) {
  var value = this.ju_Random__f_java$util$Random$$seedHi;
  var x = this.ju_Random__f_java$util$Random$$seedLo;
  var b0 = (65535 & x);
  var b1 = ((x >>> 16) | 0);
  var a1b0 = Math.imul(58989, b0);
  var lo = (a1b0 << 16);
  var hi$1 = ((((((Math.imul((-429064192), value) + Math.imul(384748, x)) | 0) + Math.imul(58989, b1)) | 0) + ((a1b0 >>> 16) | 0)) | 0);
  var lo$1 = ((720896 + lo) | 0);
  var hi$2 = ((hi$1 + (((lo & (~lo$1)) >>> 31) | 0)) | 0);
  var lo$2 = ((hi$2 >>> 16) | 0);
  this.ju_Random__f_java$util$Random$$seedHi = lo$2;
  var lo$3 = (((lo$1 >>> 16) | 0) | (hi$2 << 16));
  this.ju_Random__f_java$util$Random$$seedLo = lo$3;
  return ((hi$2 >>> ((32 - bits) | 0)) | 0);
});

Diff of setSeed (next is a complete rewrite, so no useful diff there):

@@ -316573,23 +316573,25 @@
   var lo = ((-554899859) ^ seed_in.RTLong__f_lo);
   var hi = (5 ^ seed_in.RTLong__f_hi);
   var hi$1 = (65535 & hi);
-  var lo$1 = (((lo >>> 24) | 0) | (hi$1 << 8));
-  this.ju_Random__f_java$util$Random$$seedHi = lo$1;
-  this.ju_Random__f_java$util$Random$$seedLo = (16777215 & lo);
+  this.ju_Random__f_java$util$Random$$seedHi = hi$1;
+  this.ju_Random__f_java$util$Random$$seedLo = lo;
   this.ju_Random__f_haveNextNextGaussian = false;
 });

sjrd added 2 commits June 8, 2025 13:10
@sjrd
Use Long arithmetics in ju.Random, instead of Doubles.
22bb602 
We've come full circle. Back in 5e27def,
we had optimized `ju.Random` by using `Double`s instead of `Long`s.
This commit optimizes it further by ... using `Long`s instead of
`Double`s.

It is still more complicated than using the spec as is. We compute
things in a slightly different way, that allows some internal
constant-folding to happen. This way, there are as many underlying
int multiplications as there were double multiplications before
(namely 4).

Here is the breakdown of how many operations in which category we
have before and after.

| Category                     | Count before | Count after |
|------------------------------|--------------|-------------|
| double multiplications       | 4            | 0           |
| int multiplications          | 0            | 4           |
| double additions             | 2            | 0           |
| int additions                | 2            | 6           |
| double-to-int wrap (`x | 0`) | 3            | 0           |
| logical                      | 7            | 12          |
| total                        | 18           | 22          |

That's 4 more primitive operations, but we removed 9 operations
involving `Double`s to replace them by `Int` operations only.
@sjrd
Use Math.random() instead of js.Math.random() to seed ju.Random.
21d007e 
That removes the only occurrence of JS "things" in `ju.Random`.

It is strictly equivalent, since `Math.random()` calls
`js.Math.random()`.
@sjrd sjrd requested a review from gzm0 June 8, 2025 11:32
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Reviewers

@gzm0 gzm0 Awaiting requested review from gzm0

At least 1 approving review is required to merge this pull request.

Assignees
No one assigned
Labels
None yet
Projects
None yet
Milestone
No milestone
Development

Successfully merging this pull request may close these issues.
1 participant
@sjrd