Idea: Try to implement asm.js

[pvdz]

The idea of asm.js is to use certain operations to force values to be of a certain type. The overhead this causes is eliminated by the browser which will know about these tricks and at the same time they work as type annotations which allow the browser to be more effective when optimizing. An example is let foo = getCount(); foo = foo|0; return foo;. The browser will eliminate the |0 line and assume the returned value is an integer.

I'm not entirely sure how precise these additions have to be and how complete. You tell the browser you use asm.js with the "use asm" header and it will kick you into this mode.

There's various articles on the web on asmjs, like here.

For finitedomain it could mean some improvements though I'm not certain how much. Additionally it would either mean we would need to translate the code to asmjs with a tool first. We don't want asmjs in our regular code base. I'm not sure how much effort is needed for that. But we should check it because if the effort is low, or can for the most part be done through jsdocs then we should totally do it. It'd basically be "free".

[pvdz]

I've given this a go. Moved every domain function that only concerned itself with numbers to asmjs. Effectively I moved:

  asmdomain_addRange,
  asmdomain_containsValue,
  asmdomain_createRange,
  asmdomain_createValue,
  asmdomain_createRangeZeroToMax,
  asmdomain_getValue,
  asmdomain_intersection,
  asmdomain_isSolved,
  asmdomain_isUndetermined,
  asmdomain_isValue,
  asmdomain_max,
  asmdomain_min,
  asmdomain_removeGte,
  asmdomain_removeLte,
  asmdomain_removeValue,
  asmdomain_sharesNoElements,
  asmdomain_size,

The results ... give us no significant improvements.

Maybe that's because Chrome (so v8) doesn't actively support asm.js. But since it's just good at what it does it picks up on the asm.js stuff anyways, and was already fast. The actual algorithm changes weren't that significant.

This may be a different story for array domains. But that also entails managing memory and that's not that trivial for arrays with an upper limit of 100000000 elements. That would mean requesting (4*100000000/(1024*1024))=381mb to be totally safe. And where do you put the limit. Some further investigation is in order because it's not very likely to hit the worse case (that's when you literally remove every even number from the SUB,SUP domain). We can get some more realistic numbers with profiling real world cases.

Still, you need to figure out what to do when you do hit that limit. You can't really request more memory in asmjs (you can in wasm, apparently, but that's a different story) so maybe return an error code and fall back to slow(er) paths?

[pvdz]

Note that, even on chrome, the bigger win with moving more domain manipulation stuff to asmjs would come from doing memory management ourselves, on ArrayBuffers. That probably still applies, though we could do that without asmjs (but hey).

[pvdz]

Tried this for a bit. No significant improvement. A next step could be that this is completely rewritten to fit in the asmjs paradigm but that's food for thought for another day.