Collection of branchless algorithms from Hacker's Delight. #5202

sjrd · 2025-06-21T15:13:44Z

As well as some related improvements.

While we're there, we also normalize the shape of overflow checks in Math.xExact methods.

gzm0

Only a couple of minor suggestions. Mostly on comments.

gzm0 · 2025-06-21T18:21:54Z

linker-private-library/src/main/scala/org/scalajs/linker/runtime/RuntimeLong.scala

@@ -765,6 +765,10 @@ object RuntimeLong {

  @inline
  def clz(a: RuntimeLong): Int = {
+    /* Warning to the next adventurer to come here: the best branchless
+     * algorithm I found was worse than the naive implementation here.


Add how it was worse? Performance wise? Or number of operations?

Performance-wise. I added that to the comment.

gzm0 · 2025-06-21T18:22:58Z

linker-private-library/src/main/scala/org/scalajs/linker/runtime/RuntimeLong.scala

@@ -765,6 +765,10 @@ object RuntimeLong {

  @inline
  def clz(a: RuntimeLong): Int = {
+    /* Warning to the next adventurer to come here: the best branchless
+     * algorithm I found was worse than the naive implementation here.
+     * The algorithm was `val hiz = nlz(hi); hiz + ((hiz << 26 >> 31) & nlz(lo))`.


Suggested change

* The algorithm was `val hiz = nlz(hi); hiz + ((hiz << 26 >> 31) & nlz(lo))`.

* The algorithm was `val hiz = clz(hi); hiz + ((hiz << 26 >> 31) & clz(lo))`.

Seems we always abbreviate that way? Only the JDK calls it numberOfLeadingZeros.

gzm0 · 2025-07-27T18:25:40Z

javalib/src/main/scala/java/lang/Integer.scala

-  @inline def signum(i: scala.Int): scala.Int =
-    if (i == 0) 0 else if (i < 0) -1 else 1
+  @inline def signum(i: scala.Int): scala.Int = {
+    // Hacker's Delight, Section 2-7


Suggested change

// Hacker's Delight, Section 2-7

// Hacker's Delight, Section 2-8

? (I'm looking at second edition: https://doc.lagout.org/security/Hackers%20Delight.pdf)

gzm0 · 2025-07-27T18:32:52Z

javalib/src/main/scala/java/lang/Long.scala

-    if (hi < 0) -1
-    else if (hi == 0 && i.toInt == 0) 0
-    else 1
+    /* Hacker's Delight, Section 2-7


Suggested change

/* Hacker's Delight, Section 2-7

/* Hacker's Delight, Section 2-8

gzm0 · 2025-07-27T18:40:44Z

javalib/src/main/scala/java/lang/Math.scala

-    else throw new ArithmeticException("Long overflow")
+    if (((a ^ b) & (res ^ a)) < 0L)
+      longOverflow()
+    res


I do not understand how the overflow checks for addition / subtraction up to here in the file relate to Hacker's Delight. But I understand that they essentially do the same as before, just with bitwise operations. (so no additional comments required IMO, but maybe remove the hacker's delight comments?).

I elaborated the comments to point more specifically to the formulas we use. But you're right, it's basically applying De Morgan to the negation of our previous formulas.

gzm0 · 2025-07-27T18:47:49Z

javalib/src/main/scala/java/lang/Math.scala

+  @inline
+  def toIntExact(a: scala.Long): scala.Int = {
+    val res = a.toInt
+    if (res.toLong != a)


Add a comment why this is better than checking against min / max value?

I realize the previous code had branches, but it seems they could easily be avoided (or do we not have a non short circuiting boolean and?).

I added a comment. The long comparisons require 2 int comparisons each. With the new code, we only need 1 int comparison.

gzm0 · 2025-07-27T18:51:43Z

...suite/shared/src/test/require-jdk11/org/scalajs/testsuite/javalib/lang/MathTestOnJDK11.scala

 class MathTestOnJDK11 {

  @noinline
  private def hideFromOptimizer(x: Int): Int = x

+  @Test def multiplyExactLongInt(): Unit = {
+    for (n <- Seq(Long.MinValue, -1L, 0L, 1L, Long.MaxValue)) {
+      val nInt =


Instead of this, duplicate the loop and have the lhs / rhs cases separate?

As well as some related improvements. While we're there, we also normalize the shape of overflow checks in `Math.xExact` methods.

sjrd

Rebased to address a benign conflict. Otherwise I only changed comments (and the test) to address the review.

sjrd · 2025-07-28T10:01:27Z

linker-private-library/src/main/scala/org/scalajs/linker/runtime/RuntimeLong.scala

@@ -765,6 +765,10 @@ object RuntimeLong {

  @inline
  def clz(a: RuntimeLong): Int = {
+    /* Warning to the next adventurer to come here: the best branchless
+     * algorithm I found was worse than the naive implementation here.


Performance-wise. I added that to the comment.

sjrd · 2025-07-28T10:02:09Z

javalib/src/main/scala/java/lang/Math.scala

+  @inline
+  def toIntExact(a: scala.Long): scala.Int = {
+    val res = a.toInt
+    if (res.toLong != a)


I added a comment. The long comparisons require 2 int comparisons each. With the new code, we only need 1 int comparison.

sjrd · 2025-07-28T10:06:45Z

javalib/src/main/scala/java/lang/Math.scala

-    else throw new ArithmeticException("Long overflow")
+    if (((a ^ b) & (res ^ a)) < 0L)
+      longOverflow()
+    res


I elaborated the comments to point more specifically to the formulas we use. But you're right, it's basically applying De Morgan to the negation of our previous formulas.

sjrd requested a review from gzm0 June 21, 2025 15:13

sjrd force-pushed the hackers-delight-branchless-magic branch from dfd5b59 to 2f23075 Compare June 24, 2025 11:33

sjrd force-pushed the hackers-delight-branchless-magic branch from 2f23075 to 0d0b69f Compare July 9, 2025 13:34

gzm0 approved these changes Jul 27, 2025

View reviewed changes

Collection of branchless algorithms from Hacker's Delight.

b11b0ec

As well as some related improvements. While we're there, we also normalize the shape of overflow checks in `Math.xExact` methods.

sjrd force-pushed the hackers-delight-branchless-magic branch from 0d0b69f to b11b0ec Compare July 28, 2025 10:07

sjrd commented Jul 28, 2025

View reviewed changes

sjrd enabled auto-merge July 28, 2025 10:22

sjrd merged commit 07ae33a into scala-js:main Jul 28, 2025
3 checks passed

	* The algorithm was `val hiz = nlz(hi); hiz + ((hiz << 26 >> 31) & nlz(lo))`.
	* The algorithm was `val hiz = clz(hi); hiz + ((hiz << 26 >> 31) & clz(lo))`.

	// Hacker's Delight, Section 2-7
	// Hacker's Delight, Section 2-8

	/* Hacker's Delight, Section 2-7
	/* Hacker's Delight, Section 2-8

Collection of branchless algorithms from Hacker's Delight. #5202

Collection of branchless algorithms from Hacker's Delight. #5202

Uh oh!

Conversation

sjrd commented Jun 21, 2025

Uh oh!

gzm0 left a comment

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

sjrd left a comment

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!