Carlo Piovesan
Sep 9 · 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 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!

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

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.

leaningtech

Leaning Technologies' Blog - everything Cheerp, CheerpJ, compile-to-JavaScript and compile-to-WebAssembly

Carlo Piovesan

Written by

at Leaning Technologies

leaningtech

Leaning Technologies' Blog - everything Cheerp, CheerpJ, compile-to-JavaScript and compile-to-WebAssembly

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade