Sanctuary: Maximum call stack size exceeded when creating Just of a large array

[edahlseng]

When creating a Just of a large array, I get a RangeError: Maximum call stack size exceeded. This appears to be due to type checking within the Just constructor, and the error is pinned to sanctuary-type-classes/index.js:788. Still looking into the issue, will post more details here as I find them.

[edahlseng]

This error can be recreated with the following:

const {Just} = require('sanctuary');
const test = Just(new Array(999999));

[davidchambers]

Thanks for providing a minimal test case, @edahlseng. Much appreciated. :)

Hopefully we can find a stack-safe algorithm to handle cases such as this one.

[edahlseng]

Totally, let me know if there's any other way I can help! The codebase is too new for me to be able to work out quite where this is coming from, but if you want help and can point me to the right spot, I'm happy to take a stab at addressing the issue!

[davidchambers]

This snippet reproduces the problem using sanctuary-def only:

const $ = require ('sanctuary-def');

$.create ({checkTypes: true, env: $.env}) ('f') ({}) ([$.Array ($.Any)]) (() => 'x'.repeat(999999).split('')) ();
// ! RangeError: Maximum call stack size exceeded

The stack trace is quite short. Essentially, we determine that the value is a member of Array ??? and then need to confirm that every element of the array is a member of Any.

Z.chain(expType.types.$1.extractor, values)

In the expression above, expType.types.$1.extractor is the identity function and values is a singleton array containing our array of 999,999 elements.

This snippet reproduces the problem using sanctuary-type-classes only:

const Z = require ('sanctuary-type-classes');

Z.chain (x => x, ['x'.repeat(999999).split('')]);
// ! RangeError: Maximum call stack size exceeded

Changing Array$prototype$chain to use a for loop rather than Array#forEach prevents the stack from being consumed. For 99,999,999 elements node crashes with _Allocation failed - JavaScript heap out of memory_. Is this preventable? Regardless, switching to a for loop seems sensible. Would you like to submit a pull request, @edahlseng?

[masaeedu]

Depends on what your actual use case is, but at 100 million elements you might want to consider using a generator instead of an array. It is possible to implement valid instances of all the same classes as Array for generators (and in fact for anything that satisfies the iterable protocol).

The benefit is that this is lazy, so Iter.range(99999999), Iter.map etc. return instantly, and actually consuming the result requires constant space in memory proportional to the size of a single element.

[edahlseng]

@davidchambers thanks for being patient with my delayed response. I can get a pull request together this week!

[davidchambers]

:clap:

[edahlseng]

@davidchambers, PR added to sanctuary-type-classes.

Can you help me understand why this is happening when creating a Just? It appears to be type checking; what is that for?

[davidchambers]

Can you help me understand why this is happening when creating a Just? It appears to be type checking; what is that for?

The type of S.Just is a -> Maybe a. We determine the argument's types so we can assert that the return value is of a valid type. Given S.Just (''), for example, we determine that the types of '' are { String, RegexFlags }. We then see whether the union of the return types and { Maybe String, Maybe RegexFlags } is empty—indicating a type error—or non-empty.

[edahlseng]

Is there any way that this could be done statically instead of at runtime? I'm (selfishly) thinking of my current use case... there's a large amount of data that we're processing, and we're trying to improve performance across the board. We already use Flow, and so it feels natural in our case to turn of runtime type checking in favor of static checks both for performance reasons and for improved feedback during development.

[masaeedu]

@edahlseng You can control whether the runtime type checking is enabled by using the checkTypes option. If you do const S = create({ checkTypes: false, env }), no type checking will happen. See https://sanctuary.js.org/#create

[edahlseng]

@masaeedu thanks for pointing that out! I feel quite ignorant for missing that... I'll play around with that!

[edahlseng]

Beautiful – when type checking is removed, the test case I listed above no longer fails. Of course we'll still want type checking to handle these cases, but it's good to know that this option exists!

[davidchambers]

Function#apply is the root cause of the problem:

(() => {}).apply(null, new Array(1e6));
// ! RangeError: Maximum call stack size exceeded

As @edahlseng discovered in sanctuary-js/sanctuary-type-classes#102, pushing results one at a time prevents Array$prototype$chain from consuming stack proportional to the length of f(x).

[davidchambers]

S.Just (new Array (999999)) works in v0.15.0. :)