Bignums considered harmful

[blerner]

fun in-to-cm(i): in-to-cm(i * 2.54) end
in-to-cm(1)

hangs the browser (Aw Snap! in Chrome), and the stop button doesn't work.

If you change it to

fun in-to-cm(i): in-to-cm(i * 5) end
in-to-cm(1)

The problem is less pronounced, but there is noticeable and worrying lag in the stop button.

If you change it to

fun in-to-cm(i): in-to-cm(i * 1) end
in-to-cm(1)

then the problem completely goes away.

There have also been programs like this one:

include image
r = reactor:
  init: {0; 200},
  on-tick: lam({x;y}): { x + 1; y * 0.999999 } end,
  to-draw: lam({x;y}): put-image(circle(20, "solid", "yellow"), x, y, rectangle(500, 200, "solid", "light-blue")) end
end

That eventually slow down and/or run out of memory during simulation.

This bad symptoms happen because the number library is spending a ton of time allocating new bignums, calculating their exact value, and reducing rationals to simplest form. Short of stopifying the bignum library itself, there's little to be done about this.

Basically, we are accumulating evidence that extremely large numbers do show up in users' programs, so we can't just sweep it under the rug and say “those huge numbers won't ever be a problem because we don't use them.” They do show up and they do cause weird behavior and crash folks' tabs.

[jpolitz]

Radical proposal: Pick a cutoff after which exact rationals turn into roughnums, determined by (for rationals) the size of the numerator and denominator, and (for bignums) after a certain large threshold.

Concrete proposal: this happens if the calculation needs more than 100 digits of exactness in either the numerator or denominator, including the case where the denominator is 1. This can be a parameter provided to the runtime at startup, and can be set to infinity. For CPO, we pick 100.

[blerner]

From http://www.joseprio.com/blog/2013/04/27/biginteger-libraries-for-js/ (which, admittedly, is old): some bigint libraries that might be faster (by some constant factor, I'd guess, not an algorithmic change) than our current library:

https://silentmatt.com/biginteger/
https://github.com/Evgenus/BigInt/blob/master/src/BigInt.js

[blerner]

This has now bitten one of the simulations being developed in Physics today: air resistance, which is proportional to velocity squared, implies that fractions roughly double in length (#digits of numerator and denominator) each step...which broke the sim and crashed the page. Converting to roughnums completely "fixed" the problem.

[olopierpa]

Il giorno 9 agosto 2017, alle ore 19:41, Ben Lerner <notifications@github.com> ha scritto:

This has now bitten one of the simulations being developed in Physics today: air resistance, which is proportional to velocity squared, implies that fractions roughly double in length (#digits of numerator and denominator) each step...which broke the sim and crashed the page. Converting to roughnums completely "fixed" the problem.

If one represents measurements of physical quantities with exact numbers, they're going to be disappointed very quickly. The sooner they learn not to do this the better, no?

…

— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub, or mute the thread.

[rachitnigam]

I'm curious about something: bignums seems to be a critical feature in pyret and yet seem to cause major bottlenecks like these.

Would it be feasible to implement bignums as a WASM module that do these computations quicker and call into this module from the pyret runtime? Would you expect it do have a significant performance impact for programs that do lots of numeric computation?

[blerner]

I think that's a non-sequitur: the problem seems to be in the allocation of absurdly many digits of precision, not the computations themselves (which look like they are already written in a hideously-low-level bit-twiddling subset of JS). Ironically, I think perceived performance would improve (in the responsiveness of the Stop button) if we made the bignums less efficient, so that proportionally more time was spent on interruptable computation than on uninterruptable mallocing...

[jpolitz]

+1 to Ben's comment relative to this issue. This issue would be a problem if the numbers library were 10x or 100x faster.

That said, it's not a bad idea to make the numbers faster.

I think there's a twofold practical approach for actually making numbers faster in the cases where speed counts:

• Unbox as much as we can
• Use roughnums when performance matters

Then, when we find programs that are still demanding performance out of numbers, we should do a better/more low-level implementation.

[sorawee]

Can we simply make a warning box at the REPL when a Rational allocates space beyond a threshold?

[schanzer]

Picking this up again, as a teacher in BS:A got bitten by the same thing yesterday. The more we talk about our sexy technology stack (and we're likely to talk about it more once Stopify gets picked up by CodeHS), the more embarrassing it is that a simple arithmetic program can hang our editor.

I'm all for Joe's suggestion of defaulting to roughnums at some threshhold. Stopifying everything is likely to lead to a performance hit (which I think outweighs the gains in perceived responsiveness), and I'm assuming we can't Stopify only numbers bigger than N (true?).

Given that 99.99% of teachers never see this perf problem, we're talking about only a few outliers. And for those outliers, "why is this a roughnum?" is a much better confusion for them to have than "why did my browser hang?"

[blerner]

I don't see how Stopify would be related to this...it provides the stop button, not the jsnums library.

Failing over from exact rationals to roughnums seems like a winning compromise, but I'd love to be told when that failover is reached in my program. Which means, for the first time, that we have a fairly compelling use-case for a runtime non-fatal warning from pyret, rather than runtime fatal errors. What should that look like?

[schanzer]

(I was thinking we could stopify the JS-nums library itself, possibly allowing the stop button to work for cases like this)

I would want that notification as well. As far as the user interface goes, we already have an existing mechanism we could expand and leverage: the fading status bar at the bottom of the screen. Users already see it when they try to save a program, so the learning curve is pretty flat. It’s unobtrusive, and is just noticeable enough to draw attention for a moment.

For me, what’s missing is the ability to bring the panel back if I want to see a history of all such notifications. Perhaps a small button at the bottom right of the screen could be reserved for bringing this panel up? Or other features (such as different runtime options - like whether or not to fall back to roughnums!) could be accessible from the same area if we add buttons later on.

[schanzer]

FWIW - by next year all the major browsers (including mobile) will support BigInts natively. This might be a legitimate reason to overhaul the jsnums library, since there's much better performance to be had and it will likely at least mitigate this issue.

[blerner]

Unclear -- they're ints and not decimals, so we would still have a lot of trouble implementing all the numeric operations.

[schanzer]

Adding notes from Ben's Slack discussion, so I don't forget a year from now and poke again:

Until browsers implement Math.some-function and fractions using BigInts, we'll still need to use our own Math implementation. So dropping in native BigInt support would - at best - give us a constant factor improvement over our own implementation. But this wouldn't actually fix the problem in the issue.

[jswrenn]

Unclear -- they're ints and not decimals, so we would still have a lot of trouble implementing all the numeric operations.

Anybody looking to tackle this might find guidance here: https://github.com/substack/bigint-rational

[shriram]

#1535 is another example to test on.