max() crashes on long arrays

[sgcrews]

Most appropriate sub-area of p5.js?

• Accessibility
• Color
• Core/Environment/Rendering
• Data
• DOM
• Events
• Image
• IO
• Math
• Typography
• Utilities
• WebGL
• Build Process
• Unit Testing
• Internalization
• Friendly Errors
• Other (specify if possible)

p5.js version

1.5.0

Web browser and version

Operating System

Windows 10 22H2

Steps to reproduce this

Steps:

1. Create a simple 1D array of floats of length > ~ 126,000
2. Pass the array as argument to max()
3. "Maximum call stack size exceeded" error is reported

Snippet:

// Paste your code here :)
  const m = new Array(126000);
  let myMax = max(m);

[welcome]

Welcome! 👋 Thanks for opening your first issue here! And to ensure the community is able to respond to your issue, please make sure to fill out the inputs in the issue forms. Thank you!

[aditya-shrivastavv]

This problem has nothing to do specifically with Math.max.
Function.prototype.apply can only receive an array of limited length as its second argument.

p5.prototype.max = function(...args) {
  if (args[0] instanceof Array) {
    return Math.max.apply(null, args[0]);
  } else {
    return Math.max.apply(null, args);
  }
};

On local testing, it in Chrome using:

function limit(l) {
  var x = []; x.length = l;
  (function (){}).apply(null, x);
}

Locally, limit(l) crashed exactly with l = 124980.
means the array of size 126000 @sgcrews want to pass is already exceeding the limit.

I don't think there is a direct solution to it, other than implementing our own max

mdn on apply

[sgcrews]

Is the limitation because max takes a recursive approach and the number of recursions is limited?
I am working around it in my own script by breaking the array into chunks that are small enough to use max() on, but this is somewhat tedious.

[limzykenneth]

The limitation is because Math.max() (or rather any function in JS) can only accept a limited number of arguments when being called. p5.js max() while able to accept an array, it is passing that array to Math.max() as individual arguments. One way to get around this limit is to use the following

const arr = [1, 2, 3];
const max = arr.reduce((a, b) => Math.max(a, b), -Infinity);

as recommended by MDN. However, this will likely be slower (maybe even significantly slower) than if you have a smaller list of numbers.

[davepagurek]

We could maybe fall back to that method if the user passes in an array over some threshold length. Wouldn't be able to do anything about it if they use multiple parameters, but it'd be something.

[limzykenneth]

@davepagurek There is the underscore/lodash method of looping through the whole array and not using Math.max which will be faster than reduce/Math.max but I'm not sure how that will benchmark against just Math.max for smaller list of numbers.

[aditya-shrivastavv]

This stack overflow thread is completely relevant to the issue.

[pmarsh-scottlogic]

I'm looking to make a contribution, so I've gone and read through those forums and tried to understand the problem.

Approaches

From what I've seen, the obvious ways to find the max of a list of numbers are as follows:

Apply

return Math.max.apply(null, arr);

Iterate

let max = -Infinity;
for (let i = 0; i < arr.size; i++) {
max = arr[i] > max ? arr[i] : max;
}
return max;

Spread

return Math.max(...arr)

Reduce

return arr.reduce((a, b) => Math.max(a, b), -Infinity);

We are currently using apply which is problematic because it fills up the stack. Apparently in V8, each element is added to the stack individually before any operations on elements are carried out. Spread seems to have the same issue.

Benchmarking

I ran each method through jsbench.me to see which was fastest for different array sizes. Here's the benchmark project https://jsbench.me/anlgxgqdm2/2

small array, size 10

The Iterate method wins by a mile on small arrays.

big array, size 100,000

Iterate method wins again.

**really big array, size 1,000,000

Iterate method gets the hat-trick! Reduce runs, but slowly and the other two methods hit the same stack error.

I'm running these on Chrome, Version 112.0.5615.138 (Official Build) (64-bit).

for Chrome:

size	reduce	spread	apply	iterate
10	150M ops/s	19M ops/s	125M ops/s	2.1B ops/s
100,000	478 ops/s	515 ops/s	433 ops/s	633M ops/s
1,000,000	72 ops/s	stack error	stack error	1.1B ops/s

For Firefox:

size	reduce	spread	apply	iterate
10	17M ops/s	85M ops/s	170M ops/s	176M ops/s
100,000	2.2K ops/s	2.8K ops/s	2.9K ops/s	173M ops/s
1,000,000	211 ops/s	stack error	stack error	172M ops/s

For Edge:

size	reduce	spread	apply	iterate
10	142M ops/s	12M ops/s	114M ops/s	1.2B ops/s
100,000	827 ops/s	991 ops/s	553 ops/s	1.2B ops/s
1,000,000	77 ops/s	stack error	stack error	1.3B ops/s

This page explains the benchmarking results. I don't quite understand how the iterate keeps such a consistent speed as the array size scales... I'm willing to trust that it is, indeed, the fastest method regardless of array size.

[davepagurek]

Thanks for making such detailed benchmarks! This seems like a pretty convincing reason to go with our own max() implementation using a loop under the hood.

[pmarsh-scottlogic]

@davepagurek
I propose that we change the methods as follows:

p5.prototype.max = function (...args) {
  const findMax = (arr) => {
    let max = -Infinity;
    for (let x of arr) {
      max = x > max ? x : max;
    }
    return max;
  };

  if (args[0] instanceof Array) {
    return findMax(args[0]);
  } else {
    return findMax(args);
  }
};

p5.prototype.min = function (...args) {
  const findMin = (arr) => {
    let min = Infinity;
    for (let x of arr) {
      min = x < min ? x : min;
    }
    return min;
  };

  if (args[0] instanceof Array) {
    return findMin(args[0]);
  } else {
    return findMin(args);
  }
};

With approval, I'd like to open a PR to make this change :) Let me know!

[davepagurek]

This looks good to me! @limzykenneth does this seem ok?

[limzykenneth]

I believe the consistency and high performance of the iterate benchmark is due to the js engine's JIT which will typically cache loop results when run repeatedly, the actual performance difference might not be that significant. I don't remember if browser nowadays allow JIT to be disabled but that may give a more real world performance indication.

reduce I've expected it to be the slowest because it needs to call a callback function repeatedly.

Spread and apply are essentially the same thing and I think when the code is transpiled through babel they will likely end up having the same or similar implementation. There is also a possibility to combine for loop with spread/apply by processing the array in batches of say around 120000 which is the case I'm not sure about whether it will outperform just one simple loop through everything.

[pmarsh-scottlogic]

Okay I've refactored the test to try to eliminate any clever caching that could go on in the background, simply by generating a fresh array for each iteration of the test. On inspection it seems to give much more useful results! I acknowledge that the array generation is now included in the benchmarking time, but if we assume that each array generation takes the same time, then we can still identify a ranking across our max methods. Let me know if you see any flaws with this benchmarking approach :)

Here's what it looks like now:
https://jsbench.me/anlgxgqdm2

And here's the results over several browsers (speeds are in ops/sec):

Chrome:

array size	reduce	spread	apply	iterate
10	13M	7.6M	10M	12M
10^5	120	229	362	447
10^7	4.6	stack error	stack error	6

Firefox:

array size	reduce	spread	apply	iterate
10	9M	21M	22M	24M
10^5	962	1.2K	1.2K	2.4K
10^7	5.5	RangeError	RangeError	7.5

Edge:

array size	reduce	spread	apply	iterate
10	5.8M	3.9M	5.3M	5M
10^5	231	256	258	391
10^7	2.7	RangeError	RangeError	3.8

So overall, my judgement is that iterate is still the best method. It is fastest, or at least not significantly slower, than the other methods across every array size. Plus, in my view, a simpler implementation without splitting the array into chunks is more readable.