Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

fixes #309: call stack exceeded in Control.Bind.Bind instance for Array #311

Open
wants to merge 2 commits into
base: master
Choose a base branch
from

Conversation

michaelficarra
Copy link
Contributor

@michaelficarra michaelficarra commented Jan 25, 2024

Description of the change

Fixes #309 by batching the arguments passed to Array.prototype.push by Function.prototype.apply. I chose 10,000 for the batch size because it's definitely in the safe range for major implementations while still being large enough to not have much effect on performance.

I couldn't find where the tests for Control.Bind live so I didn't add a test.


Checklist:

  • Added the change to the changelog's "Unreleased" section with a reference to this PR (e.g. "- Made a change (#0000)")
  • Linked any existing issues or proposals that this pull request should close
  • Updated or added relevant documentation
  • Added a test for the contribution (if applicable)

@JordanMartinez
Copy link
Contributor

There's likely not any tests for Control.Bind.

However, what is the underlying issue here and how does this fix the underlying issue?

@michaelficarra
Copy link
Contributor Author

The underlying issue is that JS implementations have a limit to the number of arguments that can be passed to a function (even through Function.prototype.apply). The limit is implementation-specific, but generally ≥ 65,535. The repro in #309 was causing the second argument to Function.prototype.apply (the argument list for Array.prototype.push) to exceed this limit. The solution is to just call Array.prototype.push multiple times, batching the work.

@JordanMartinez
Copy link
Contributor

The limit is implementation-specific, but generally ≥ 65,535.

Where is that documented?

@JordanMartinez
Copy link
Contributor

Found this on MDN docs:

The consequences of calling a function with too many arguments (that is, more than tens of thousands of arguments) is unspecified and varies across engines. (The JavaScriptCore engine has a hard-coded argument limit of 65536.) Most engines throw an exception; but there's no normative specification preventing other behaviors, such as arbitrarily limiting the number of arguments actually passed to the applied function. To illustrate this latter case: if such an engine had a limit of four arguments (actual limits are of course significantly higher), it would be as if the arguments 5, 6, 2, 3 had been passed to apply in the examples above, rather than the full array.

@michaelficarra
Copy link
Contributor Author

Like all OOM errors, it is a violation of the JS spec. The JS spec requires infinite memory for compliance, which obviously no implementation can provide. The best I can do is this article on MDN which recommends a strategy like the one I've used here.

@JordanMartinez
Copy link
Contributor

Since this is already a bug, I think fixing the underlying issue with a limit of 65535 is desirable because that's a known hard limit. If someone has proof that this number is still too large for a given JS engine, we could decrease the number for the other JS engine. But I think a limit of 10k is too small given that it loops potentially 6 times unnecessarily.

@michaelficarra
Copy link
Contributor Author

michaelficarra commented Jan 25, 2024

Personally, I would prefer to stay well below the known upper bound. Implementations may reduce this limit in the future, and lesser-known implementations (such as those for embedded systems) may already have a lower limit today. I don't think the overhead of 6 loop iterations matters much for such heavy workloads. We could prove it out with benchmarking if we really wanted to know.

edit: The example from mdn uses 32768, half of JSC's limit. This seems like an okay compromise.

@JordanMartinez
Copy link
Contributor

I still stand by what I said. When we find a new limit, we can decrease it. But until I have hard evidence of that, there's nothing to say that my arbitrary choice is better/worse than your arbitrary choice.

@acple
Copy link

acple commented Jan 26, 2024

Current change is sliceing array twice per loop but it is not necessary I think.
How about this:

var v = f(arr[i]);
for (var j = 0; j < v.length;)
  Array.prototype.push.apply(result, v.slice(j, j += CHUNK));

But this always slice at least once if even not necessary, should we consider it?

@acple
Copy link

acple commented Jan 26, 2024

I agree that 65535 as a hard limit.
Because the JSC's hard limit is also an arbitrary value as a limitation.

Stack size is finite, and 0xFFFF seems as good an arbitrary limit as any other would be. :-)

So it should work fine for now.

@JordanMartinez
Copy link
Contributor

Current change is sliceing array twice per loop but it is not necessary I think. How about this:

var v = f(arr[i]);
for (var j = 0; j < v.length;)
  Array.prototype.push.apply(result, v.slice(j, j += CHUNK));

But this always slice at least once if even not necessary, should we consider it?

This does seem like a better implementation. Thanks for the suggestion.

@JordanMartinez
Copy link
Contributor

But this always slice at least once if even not necessary, should we consider it?

This implementation only slices if needed at the cost of an if block. I'm not sure which is faster and we'd need to benchmark this to know.

var APPLY_CHUNK_SIZE = 10e3;
var push = Function.prototype.apply.bind(Array.prototype.push);

export const arrayBind = function (arr) {
  return function (f) {
    var result = [];
    for (var i = 0, l = arr.length; i < l; i++) {
      var subArr = f(arr[i]);
      if (subArr.length <= APPLY_CHUNK_SIZE) {
        push(result, subArr);
      } else {
        for (var j = 0; j < v.length;) {
          Array.prototype.push.apply(result, v.slice(j, j += APPLY_CHUNK_SIZE));
        }
      }
    }
    return result;
  };
};

Testing would need to check for off-by-one errors here.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

Successfully merging this pull request may close these issues.

arrayBind causes Maximum call stack size exceeded
3 participants