Maximum call stack on non recursive function

Question

Hello I'm running on a problem with this function that results in a maximum call stack exceeded error. This function is not recursive, so I don't really understand why it is exceeding the call stack.

I copied this function from some blog (maybe stackoveflow), It converts a Word Array to a Byte Array to use in pako.js.

It's used to inflate a zlib compressed string.

When the string is small It doesn't exceed the call stack, but with longer strings it exceeds it.

I've tried rewriting it with setTimeout, but it becomes very slow. Do any of you have any suggestions?

Thanks.

const wordToByteArray = function (word, length) {
    let ba = [];
    let i;
    let xFF = 0xFF;

    if (length > 0)
        ba.push(word >>> 24);
    if (length > 1)
        ba.push((word >>> 16) & xFF);
    if (length > 2)
        ba.push((word >>> 8) & xFF);
    if (length > 3)
        ba.push(word & xFF);

    return ba;
};

const wordArrayToByteArray = function(wordArray, length) {
    if (wordArray.hasOwnProperty("sigBytes") && wordArray.hasOwnProperty("words")) {
        length = wordArray.sigBytes;
        wordArray = wordArray.words;
    }

    let result = [];
    let bytes;
    let i = 0;

    while (length > 0) {
        bytes = wordToByteArray(wordArray[i], Math.min(4, length));
        length -= bytes.length;
        result.push(bytes);
        i++;
    }

    return [].concat.apply([], result);
};

Solution Thanks for the answers bellow, this was the solution.

    ...
    while (length > 0) {
        bytes = wordToByteArray(wordArray[i], Math.min(4, length));
        length -= bytes.length;
        bytes.forEach(function (byte) {
            result.push(byte);
        });
        i++;
    }

    return result;
};

Out of curiosity, why you perform this step `[].concat.apply([], result);` ? — Alex, Aug 12 '19 at 19:37
@Aleksey i was about to ask exactly the same question. Why not just `[].concat(result)`? — Guerric P, Aug 12 '19 at 19:38
There's not point cloning the array as far as I can understand — Guerric P, Aug 12 '19 at 19:40
I was beginning to question the necessity of `return [].concat.apply([], result);` I think its because wordToByteArray returns an array, so the actual result before concat should be `[[x], [y], ...]` and the result after concat will be `[x, y, ..]` , but it is possible to push directly to result, thus avoiding the concat and apply. — chemisax, Aug 12 '19 at 19:46

score 3 · Accepted Answer · answered Aug 12 '19 at 19:37

[].concat.apply([], result); is likely your problem; that's effectively saying "please call [].concat(result[0], result[1], result[2], ..., result[result.length - 1]). For a large input, you likely have a proportionately large result. Per MDN's warnings on apply:

But beware: in using apply this way, you run the risk of exceeding the JavaScript engine's argument length limit. The consequences of applying a function with too many arguments (think more than tens of thousands of arguments) vary across engines (JavaScriptCore has hard-coded argument limit of 65536), because the limit (indeed even the nature of any excessively-large-stack behavior) is unspecified. Some engines will throw an exception. More perniciously, others will arbitrarily limit 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.

If your result array is truly huge, trying to pass tens of thousands (or more) arguments to Array.concat could blow your stack. The MDN docs suggest that in scenarios like yours you could use a hybrid strategy to avoid blowing the stack, applying to chunks of arguments at a time instead of all the arguments, no matter how big.

Luckily, someone has already provided a guide on how to do this safely; just use that and explicitly loop to extend with each sub-array in result.

It's interesting that it raises a stackoverflow error as if arguments would really be allocated on a stack ... — Jonas Wilms, Aug 12 '19 at 19:56

score 0 · Answer 2 · answered Aug 12 '19 at 19:35

0

Your result array is very large. Problem here is in apply method where you provide result as arguments. Arguments of a function are pushed onto stack and it causes stack overflow.

answered Aug 12 '19 at 19:35

Alex

1,724
13
25

Maximum call stack on non recursive function

2 Answers2