A fast BigInt.js in an evening, compiling C++ to JavaScript

Carlo Piovesan

Follow

Sep 9, 2019 · 5 min read

A few days ago I stumbled upon an article: https://v8.dev/features/bigint on the V8 blog. I had been busy at work with trying to figure out ways to optimize i32 and i64 operations for our C/C++ to JavaScript compiler Cheerp; this seemed like a fun side project to experiment on.

The goal:

Implement a pure JavaScript library, callable by some code like:

var one = BigInt("1");
var A = BigInt("1");
var B = BigInt("1");for (var i=1; i<=1000; i++) 
{
        A = BigInt.multiply(A, B);
        B = BigInt.add(B, one);
}console.log("factorial(1000) is " + A);

The plan:

• finding a C/C++ library for arbitrary precision integer arithmetic.
• adapt/implement a (basic) interface (eg. a constructor that accepts a JavaScript String, multiply(a,b), add(a,b), a.toString() are required from the above example).
• adapt the code and feed it to the Cheerp compiler.
• test it and benchmark it.
• go to bed.

Choosing a C/C++ BigInt library

I googled a few keywords, ended up on Boost.Multiprecision. In particular, they support 3 integer types backends: cpp_int, gmp_int and tom_int.

From Boost’s classification: gmp_int (based on GMP) is the fastest, cpp_int (Boost’s creation) the more versatile (?) while tom_int have no licence restrictions.

I wrestled a bit with Boost and GMP build systems (I had to make them work with the Cheerp compiler) before turning to LibTomMath and managing at the first attempt. It’s a pure C library with a mainly educational purpose. No dependencies required, very liberal license, seemed the perfect choice for my purpose.

[[ps: while publishing the article I realized that there is a sister library that promise to be even faster: TomsFastMath. I will give it a try at some point]]

API

Wrapping the memory management and C-style functions calls in a C++ class was needed and consulting the library manual it turned out straightforward (and required no understanding of how a BigInt library internally works).

This is, for example, a function to sum 2 BigInts:

static BigInt* BigInt::add(const BigInt& a, const BigInt& b)
{
       BigInt* res = new BigInt();
       //mp_add            is the libtommath backend function
       //wrapper           takes care of checking the error
                           code returned by mp_add
       wrapper( mp_add(&a.number, &b.number, &res->number) );//Every resource will be garbage collected by JavaScript's GC
       return res;
}

Then I played a bit with calculating some factorials, fixed the inevitable errors, and I had a working C++ class.

Compile it with Cheerp

Cheerp aims to be just a regular C/C++ compiler. You call it like:

/opt/cheerp/bin/clang++ source_file.cpp -o output.js -target cheerp

In the basic settings, it takes in a cpp file in and it outputs a JavaScript file (wasm / wasm+js / asmjs being other possible output).

cd build_libtommath &&
/opt/cheerp/bin/clang *.c -c -O3 -target cheerp &&
cd .. &&
/opt/cheerp/bin/clang++ wrapper.cpp -c -Ilibtommath -O3 -target cheerp &&
/opt/cheerp/bin/clang++ build_libtommath/*.bc wrapper.bc -o wrapper.js -O3 -target cheerp -cheerp-pretty-code

Here I had to build the library files into .bc files (LLVM internal representation) then my wrapper.cpp into a .bc file, then all .bc files together into a JavaScript file.

It builds, perfect.

Cheerp provides a C++11 attribute [[cheerp::jsexport]], to preserve class names and interfaces into JavaScript, so it was just needed to tag the class with it and now it could be called as a library.

Now I went back to implementing the API, added a few more static methods that were missing in the wrapper class: subtraction, division, remainder, a constructor accepting native JavaScript String, and a toString() member function:

#include <client/types.h>     //Cheerp provided header
                              //that forward declares String methodsclient::String* BigInt::toString(int radix) const
{
        int dim = 0;
        wrapper( mp_radix_size(&number, radix, &dim) );
        std::string std_string;
        std_string.resize(dim-1);
        wrapper( mp_toradix(&number, &std_string[0], radix) );
        return new client::String( std_string.c_str() );
}

Here is the toString implementation. client::String is just the JavaScript string type. A String constructor from a C char* is also provided in the header file.

Recompiling everything (by now I had a script in place), a couple of more bug fixing, and …with more

It works!

Test & benchmark

I ran some tests, it seemed to work well enough, it was late… I will need to get back to checking things for real at some other point.

I found some great resources on BigInt around, and one had a very easy to hack benchmarking page, that allowed to add your very own implementation of BigInt to be pit against the others directly on the client-side.

You could try it for yourself: BigInt’s benchmark.

Ideally, try it on different browsers/devices. On Chrome the results are not very encouraging (= is the last among the considered libraries), while on Firefox and Safari the Cheerp backed BigInt implementation is clearly the fastest in the first 2 families of benchmarks.

Why it matters the difference between Chrome and the others? Chrome has a good BigInt native implementation (native != relying on pure JavaScript), and some libraries default to it if available. [[I will need to do a deeper dive into the difference and do some more testing on other devices, I may be back with a second article]]

There are lots of benchmarks, I would advise to concentrate on addition/subtraction one, that are the only ones in which this library is competitive (and luckily, they are at the top of the page).

The results is a 5771 line of generated JavaScript code, comprising Karatsuba’s and Toom-Cook’s algorithm for fast multiplications, usable freely for any (not) so serious scope.

To have a look of what generated JavaScript look like: BigInt.js.

What does all this mean?

So, by being very restrictive I could claim to be “creator of the best addition and subtraction BigInt library that exists outside Chrome”.

A part nonsensical titles (that I will brag nonetheless), the idea that in a few hours, requiring no domain knowledge I was able to create a pure JavaScript library that performs a complex task at close to peak performance seems great to me.

I don’t see anything coming in the way of you repeating the same outlined process for [fill in with whatever library you may need]. The problem is not in finding great C/C++ libraries, nor in adapting the few lines of code required.

Learning to work with the Cheerp compiler may take a few tries, we are trying to render less steep the process, and there are lots of resources to get you started.