`Int32` math

[claudiameadows]

GitHub - tc39/proposal-bigint-math: Draft specification for supporting BigInts in JavaScript’s Math methods. proposes a number of integer math methods on BigInt. That gave me the idea of extending that to 32-bit integers.

Here's my idea:

• Int32(x): Coerce an integer to a 32-bit signed integer. Equivalent to x | 0 and ~~x, but way clearer.
• All the methods in GitHub - tc39/proposal-bigint-math: Draft specification for supporting BigInts in JavaScript’s Math methods.
• Int32.clz = Math.clz32
• Int32.mul = Math.imul

32-bit integers can uniquely be optimized for here.

• abs is just 2-3 integer instructions on most platforms. It's very well-known, with algorithms going back decades.
  • Notably, AArch64 can do CMP a, #0; CSNEG r, a, a, GE, and ARM 32-bit can merge the usual mask shift into the other two operations with EOR r, a, a, ASR #31; SUB r, r, a, ASR #31. They only need two instructions, not the usual 3-operation asr; xor; sub/asr; add; sub sequence that others need.
• sqrt for integers has its own dedicated Wikipedia page. Hacker's Delight includes a cbrt implementation, and hypot also has some stuff online.
• pow is obvious: exponentiation by squaring. But the loop is a lot tighter with 32-bit integers than it is with bigints.
• max and min are trivial with conditional selects, but there's ways to do it branch-free even without it for platforms like RISC-V (where Zicond is both too new and not adequate). This way could also be done with bigints, but it's way more efficient to just compare once and branch with heap-allocated bigints.

It'd also provide a stepping stone for better native support for bit-oriented ops like ctz and bitReverse that also commonly have some level of native support.

CC @jschoi since you said you have thoughts of your own about this.

[jschoi]

Thank you for your post. Here’s that feedback I mentioned having.

• Need for real-world use cases:

  • As you know, achieving Stage 1 for any proposal requires that the proposal has a compelling problem statement, rather than focusing on specific solutions or API designs first.
  • It’s best to focus on specific real-world use cases to define the problem space.
  • This is essential to show why a feature is worth exploring to Committee delegates.
  • This particularly applies to the engine implementors who would have to maintain the feature in perpetuity.
  • In general, showing that a feature is merely possible or efficient (e.g., the Hacker’s Delight page or the Stack Overflow answer) is insufficient to showing why it is worth adding. Real-world use cases are needed.
  • Showing that a feature is merely possible or efficient is also a mismatch with Stage 1’s “problem statement” model. Defining a real-world problem statement using use cases is essential to Stage 1.
  • In particular, multiple engine implementors generally find mere ‘“completeness” to be a very weak argument’ for including anything; they have expressed a preference for using “established usecases” instead.
  • Furthermore, if the problem statement does not involve new developer capabilities, then the problem statement must demonstrate that its problem / use cases are common among developers.

• More bitwise operations:

  • I agree that CTZ (count trailing zeroes) and bit reverse may also be useful, although presenting specific real-world use cases are still essential.
  • There has been interest from at least some delegates in more bitwise operations like bit length and byte-array conversions. (Jakob Kummerrow is from Chromium.)
  • I am personally interested in standardizing population count / popcount, which has plenty of use cases.

• Integer roots, real-world use cases:

  • It’s clear that there has been demand for integer square roots (“isqrt”), given their presence in many languages’ standard libraries.
  • But I’m still searching for specific real-world use cases for integer square roots. The examples would ideally be in popular applications/libraries. I’ve been having difficulty.
  • I did find a single JavaScript library that uses integer square roots of BigInts to determine if a number’s prime factors are “too close” .
  • I’ve had even less success with finding use cases for integer cube roots or integer hypotenuses.
  • This is relevant to the BigInt Math proposal because, if I don’t present specific use cases for BigInt.sqrt or BigInt.cbrt (or BigInt.hypot, if I add hypot back to the proposal), then Committee pushback to implementing them becomes more likely—even if they can be efficiently implemented.
  • As mentioned above, some delegates find “completeness” to be a weak argument for standard implementation.

• Integer roots, naming:

  • You have made me realize that BigInt.sqrt may be better named as BigInt.isqrt, because there is a clear precedent with other languages to call integer square root isqrt.
  • This would be consistent with any future Math.isqrt function that performs integer square roots.
  • The same would apply to integer cbrt and hypot: maybe they should be BigInt.icbrt and BigInt.ihypot instead.
  • This would, of course, go against your preference that integer-specific math functions live in a separate namespace object. And that leads to…

• Separate namespace for 32-bit integer functions:

  • As far as I can tell, the problems that this idea would address are:
    1. abs, sqrt, pow, max, and min ought to be more efficient on Numbers that are 32-bit integers.
    2. Developer experience of bitwise operations (like the existing Math.clz32 or a future CTZ function) is currently poor because they are in the Math namespace.
    3. Developer experience of coercing to 32-bit integers (x | 0 and ~~x) is currently poor because those operations’ meaning is not commonly known.
  • These three points are the best problem statements for Stage 1 I could come up with. (Remember that we need to explore a problem first, before jumping to solutions.)
  • Notably, there are no increased developer capabilities in this problem statement; all functionality is already possible in user code.
  • I unfortunately think that much of the Committee would find both of these problem statements insufficiently compelling.
  • Regarding Problem Statement 1, optimizability:
    • I am not an expert in the big three engines, but I’m pretty sure that determining whether +, -, *, /, abs, sqrt, pow/**, max and min are acting on 32-bit integers is a relatively easy task for all three engines’ JITs to determine and monomorphize.
    • I suspect that the JITs are already optimizing these operations, once monomorphized, into very small instruction sequences. The biggest actual benefit would be in the one-time warmup of hot loops.
    • I also suspect that, if someone presented Problem Statement 1 in plenary, the engine vendors would respond, “The performance of these operations on 32-bit integers is not a problem in web apps today.”
    • I don’t know this for sure.
  • Regarding Problem Statement 2, developer experience of bitwise operations:
    • It is questionable whether it is a big deal that Math containing clz32, imul, and any future special bitwise operations like bit length.
    • Developers who need to use those functions can use them in Math as “easily” as they would in Int32.
    • I suspect that, if someone presented Problem Statement 2 in plenary, many delegates would ask why this is actually a problem for clz32, imul, bit length, etc.
    • (Some delegates may also be specifically against solutions to Problem Statement 2 like an Int32 namespace, because they arguably obscure from developers the fact that JavaScript “32-bit integers” are just JavaScript Numbers with no fraction part.)
  • Regarding Problem Statement 3, developer experience of 32-bit integer coercion:
    • The case for this problem is clearer.
    • x | 0 and ~~x are indeed obscure and take some time for developers to understand.
    • There is a somewhat good chance for this problem statement to get to Stage 1.
    • However, clear real-world use cases and evidence that they are common would have to be made.
    • Rather than a Int32 global function, the plenary would probably only accept a solution that uses existing language idioms, like Number.prototype.toInt32, Number.toInt32, or (less likely) Math.toInt32. But this would be a Stage 2 concern.

I always appreciate your ideas. And I’m glad that you made me realize that BigInt.sqrt should maybe be BigInt.isqrt; I made an issue about that.

[blob]

I find this proposal quite interesting however I wonder how far we are willing to go for Javascript performance when solutions like WebAssembly exist. Bringing javascript from 10x slower-than-native to 1.5x slower-than-native is quite a huge feat but bridging that to 1.1x slower-than-native is just webassembly with a lot of extra steps