All the Maths

[mikeal]

From a few conversations with @mikolalysenko I learned that languages like R and libraries like scipy which are known for amazing math are just binding to the same old Fortran libraries (and in a few cases C). That said, I don't think a binding layer will work for JavaScript, especially if we want to use them in the browser, but I do think we could use emscripten to transpile them in to JS, hopefully asm.js.

I got as far as writing most of a script to pull down calgo, which is laid out incredibly horribly, extract them all and generate package.json files which we could eventually checkin to git.

My attempts at getting emscripten to work ended at getting dragonegg to find the right llvm :(

Anyway, my instinct is that the best strategy is to:

• Pull down all these ancient libraries in to a repo and check them in to git (they aren't in any source control as is).
• Write scripts which can automate creating a package.json and individual npm package for each algorithm.
• Write benchmarks to get the VM engineers competing for performance, hopefully ending in superior performance to the original Fortran libraries.

Thoughts?

I know that @groundwater is interested in this as I imagine @substack and @maxogden are as well. Additionally, I saw @rwaldron throw out some links on twitter which I think were related to crazy math in JS.

[mikeal]

Oh, forgot to link to the other two big algorithm collections: lapack and arpack.

[bnoordhuis]

I'm unclear about the goal. Is it to provide BLAS and/or LAPACK/LINPACK bindings for people to use in their applications? Encourage the V8 people to work on numerical performance? Both?

There's a strawman for native SIMD support and I believe Intel is committed to bringing that to V8.

(Spidermonkey nightly already implements the strawman but I don't think it has made its way into a release yet. Or if it did, it's probably behind a flag.)

There's also River Trail (strawman), another Intel effort that aims to bring parallel numerical computing to JS.

Mozilla calls it PJS and I believe they have declared an intent to implement it but I don't know what the status is. This meta-bug is the tracking bug, if you're interested.

[mikeal]

@bnoordhuis I think all the enhancements that Mozilla and Intel have been working on will be great and I'm looking forward to them but R and scipy don't have them and are seeing adoption in one area that JS isn't at the moment. The only they have but we don't is access to these ancient libraries. If we were able to transpile them we might see some of that adoption, if they are slow the VM engineers will likely make them faster or work a little faster getting these other features in and improving emscripten or these libraries directly to use them.

[mikolalysenko]

The obstacles to getting high performance numerical code working in JS are relatively clear:

1. Lack of SIMD data types, which prevents using high performance CPU features
2. Lack of value types or pass-by-value semantics, which severely restricts optimizations based on cache and memory bandwidth considerations
3. Limited multithreading and shared memory support, which restricts the effective memory bandwidth available in JS
4. No viable pathway for either porting or linking to legacy code bases

The first three of these issues are really language design problems, and not things that we are going to solve at the node level. It is up to the ES committee to get these real performance impacting issues fixed, and the best we can do is put pressure on them to make it a priority over syntactic twiddling.

Still even if the ES committee never sorts these problems out, I would like to point out that at least in regards to the first 3 points JS is certainly no worse than Python, which suffers from exactly the same draw backs. And yet, people use Python extensively for numerical computing, even though an equally strong case could be made that the semantics of the language do not make it suitable for the task.

Accepting the first 3 items as a given, we are left with what I believe is the real problem here:

The main blocking issue to getting numerical computing working in JavaScript is interoperability with C and Fortran code bases.

Interoperability is really a broader problem that affects many applications (for example crypto could benefit a lot here as well), but it is felt in numerical computing especially acutely due to the size, sophistication and fundamental importance of legacy numerical code.

In my dream of how things could work, I would love to see a more modular/npm-centric solution to this problem. Something where we could just npm install lapack and then require it and call things like DGESVD directly -- without having to install or set up a bunch of external native code, using apt or whatever. The resulting bundles ought to work both in node.js and in the browser, and while we are at it on native environments there could be a fallback to the original Fortran where possible.

[trevnorris]

I think ruling out making native bindings to existing libraries sells Node short of possibilities. Especially in terms of performance. TBH I don't care about making this browser compatible, because even with all the proposed optimizations (which will take a while to come out) it'll still be much slower than using native methods.

V8 has dome some great work to make calling into C++ from JS really cheap. Here's an example that just sums an array of uint32_t.

// run.js
var runMe = require('./build/Release/addon').runMe;
var smalloc = require('smalloc');
var stypes = smalloc.Types;
var ITER = 1e5;
var SIZE = 1024;
var b = smalloc.alloc(SIZE, {}, stypes.Uint32);

for (var i = 0; i < SIZE; i++)
  b[i] = i;

function simpleSum(arr, len) {
  var ret = 0;
  for (var i = 0; i < len; i++)
    ret += arr[i];
  return ret;
}

var t = process.hrtime();
for (var i = 0; i < ITER; i++) {
  //runMe(b);
  //simpleSum(b, SIZE);
}
t = process.hrtime(t);
console.log(((t[0] * 1e9 + t[1]) / ITER).toFixed(1) + ' ns/op');

#include <v8.h>
#include <node.h>

using v8::FunctionCallbackInfo;
using v8::Handle;
using v8::Local;
using v8::Object;
using v8::Value;

void RunMe(const FunctionCallbackInfo<Value>& args) {
  Local<Object> obj = args[0].As<Object>();
  uint32_t* arr =
      static_cast<uint32_t*>(obj->GetIndexedPropertiesExternalArrayData());
  size_t len = obj->GetIndexedPropertiesExternalArrayDataLength();
  uint32_t ret = 0;

  for (size_t i = 0; i < len; i++)
    ret += arr[i];

  args.GetReturnValue().Set(ret);
}

void init(Handle<Object> exports) {
  NODE_SET_METHOD(exports, "runMe", RunMe);
}

NODE_MODULE(addon, init)

So, simpleSum() runs in 851 ns while runMe() runs in 90 ns.

Now, the math libraries themselves should be able to be done without much build pain and, TBH, if computationally complex operations are being done on my server I'll care way more about taking a minute to build a library and save the CPU cycles.

[AndreasMadsen]

As a data scientist in learning (who use Python for that), with a huge love for JavaScript, I can name three reasons why I doubt I will ever get to use JavaScript for actual numerical computing.

• It is not possible to create a Uint8Array or Buffer with more than 1024^3 elements. If you think that is a huge number, just imagine that you have 1024 picture with a 1024 x 1024 resolutions. It is really not that many pictures and not that high a resolution.
• Even if that is solved, there is still the 64bit integer problem. After 4 * 1024^3 elements, accessing items beyond that index becomes unreliable. I have seen some suggestions on how to implement 64bit integers, but they all seams too obscure to use for simple indexing.
• There is no operator overloading, for people to be interested in numerical computing there has to be someone to use it. Those are typically people with a more mathematical background and expect A * B to involve a matrix multiplication. You can implement it with objects and function, but it quickly becomes quite ugly to look at. mul(mul(inv(mul(t(X), X)), t(X)), y) (not numerically stable solution to OLS). As you see the distance between the arguments and the operator quickly becomes to long as opposed to np.inv(X.T * X) * X.T * y. I have seen some suggest methods, but that is not extendable and the I think the mathematical syntax is lost, making operation ordering difficult to keep track of. X.T.mul(X).inv().mul(X.T).mul(y).

[trevnorris]

@AndreasMadsen

It is not possible to create a Uint8Array or Buffer with more than 1024^3 elements.

After 4 * 1024^3 elements, accessing items beyond that index becomes unreliable.

For technical clarity, it's actually 1024^3 - 1 bytes. That aside, it is easily possible to attach more than that to an object but not have it accessible by array index. Slightly more complicated, it is possible to access up to 2^52 bytes by numeric index but at a performance hit.

There is no operator overloading

True, and this could be a challenge. Technically someone could create their own parser and instead of operating in native JS operations they instead pass in a string. Ugly, yes, but it could get the job done.

One reason why I implemented the smalloc module for v0.12 was for scientific computing. It's easy to integrate into a little C++ and call existing C/C++ math libraries.

[Qard]

I like the idea of extending the Buffer concept to implement a BigNum type, which could be further extended to implement things like Vector and Matrix types. If I recall correctly, it might even be possible to override operators at the C++ level to have the prettier syntax for working with those more complex types.

[trevnorris]

@Qard

it might even be possible to override operators at the C++ level

Do you mean JS operators?

[Qard]

Yeah, I thought I remembered seeing functions to define operator behaviour
at C++ level. I could be wrong. I've never tried it myself.

[trevnorris]

@Qard Not that I remember. @bnoordhuis You know of some such black magic?

[bnoordhuis]

I don't think there's any such magic. About the only thing you can do in C++ that you can't do from JS is make objects callable as functions (like how RegExp used to be.)

[Qard]

Indeed. You appear to be right. After some quick grepping of the source, I'm finding no such convenience. I must've been remembering some other VM. :(

[domenic]

It is not possible to create a Uint8Array or Buffer with more than 1024^3 elements. If you think that is a huge number, just imagine that you have 1024 picture with a 1024 x 1024 resolutions. It is really not that many pictures and not that high a resolution.

In ES6 it is possible to create a typed array with up to 2^53 - 1 elements. If this is not implemented in V8 (or perhaps, not implemented in the version of V8 that ships with Node) than it is worth filing a bug to make sure it gets fixed.

Even if that is solved, there is still the 64bit integer problem. After 4 * 1024^3 elements, accessing items beyond that index becomes unreliable.

You should be able to access up to 2^53 - 1. Not quite 2^64 - 1, but certainly a lot more than 4 * 1024^3.

There is no operator overloading, for people to be interested in numerical computing there has to be someone to use it.

This is where things get tougher, and require tricky ESfuture-track work. The current thought on all things in this design space is found in https://github.com/nikomatsakis/typed-objects-explainer/; operator overloading is the least-developed of these proposals, unfortunately. But the good news, at least, is that everyone on TC39 agrees this must be done. It's just a matter of finding the right people and time to design an operator overloading extension to the JavaScript language, and making sure it integrates with all the related topics like value types and typed objects and user-defined literals.

[domenic]

Lack of SIMD data types, which prevents using high performance CPU features

This is an accepted ESfuture-track proposal with good detail already, shipping in SpiderMonkey and with a patch open for V8 by Intel.

Lack of value types or pass-by-value semantics, which severely restricts optimizations based on cache and memory bandwidth considerations

(See above about value types)

Limited multithreading and shared memory support, which restricts the effective memory bandwidth available in JS

This gets tricky. We'd really like to avoid shared-memory multithreading and that whole concurrency model, with data races etc. But there is definitely room for improving the existing web worker and transferable infrastructure into something with more room for performance. I don't remember if this is exactly right, but I think at one point I was convinced you could allow a typed array (or similar) to be shared among multiple workers as long as only one of them had write access.

No viable pathway for either porting or linking to legacy code bases

Emscripten seems perfect for this?