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

Carlo Piovesan
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

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

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

/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 methods
client::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!

Image for post
Image for post
No more floating-point precision issues, like 170!= 7.257415615307994e+306
171! = Infinity

Test & benchmark

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.

Image for post
Image for post
Image for post
Image for post

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?

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.

leaningtech

Leaning Technologies' Blog - everything Cheerp, CheerpJ…

Medium is an open platform where 170 million readers come to find insightful and dynamic thinking. Here, expert and undiscovered voices alike dive into the heart of any topic and bring new ideas to the surface. Learn more

Follow the writers, publications, and topics that matter to you, and you’ll see them on your homepage and in your inbox. Explore

If you have a story to tell, knowledge to share, or a perspective to offer — welcome home. It’s easy and free to post your thinking on any topic. Write on Medium

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store