15

I have to find the maximum and minimum value of very huge arrays. For this I'm using

Math.max.apply(Math, my_array);
Math.min.apply(Math, my_array);

It works good on Firefox and IE, but on Chrome I always get Maximum call stack size exceeded errors... my current array has 221954 elements, and that's not my biggest.

Does someone know how to solve this error on Chrome? How can I optimize the search of max and min value?

For those people who can't believe, try this in the console of Chrome:

var xxx = []
for(var i=0; i<300000; i++){
    xxx.push(Math.random());
}
Math.max.apply(Math, xxx);

---> RangeError: Maximum call stack size exceeded

PanChan
  • 372
  • 1
  • 6
  • 18
  • You might want to take a look at this question: http://stackoverflow.com/questions/1669190/javascript-min-max-array-values – Qantas 94 Heavy Aug 19 '13 at 08:20
  • I saw this. From there I copied my two lines. But there is nothing about my problem... – PanChan Aug 19 '13 at 08:54
  • Try scrolling down: http://stackoverflow.com/a/13440842/2074608 – Qantas 94 Heavy Aug 19 '13 at 08:56
  • This answer works good in FF but crashing in chrome... When using this I get a lot of jQuery errors! btw: they mentioned that you only have to use this when having ~10⁷ elements, but I have the problem much more earlier :/ – PanChan Aug 19 '13 at 09:17
  • On Chrome this works for me: `for (var a = [], i = 0; i < 999999; ++i) a[i] = Math.random() + 1; a.min();` Anyway the issue is to do with Function.prototype.apply - try this: `for(var a = [],i=0; i<130000; i++)xxx.push(Math.random());(function(){}).apply(null, a);` – Qantas 94 Heavy Aug 19 '13 at 09:21

4 Answers4

22

This problem has nothing to do specifically with Math.max and Math.min.

Function.prototype.apply can only receive array of limited length as its second argument.

Locally, I tested it in Chrome using:

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

Locally, limit(l) crashed exactly with l = 124980. In canary, that was another number, but also ~125k.

This is an example explanation of why that happens: https://code.google.com/p/v8/issues/detail?id=2896 (it is also reprodusible in other JS engines, for example MDN has a mention of the issue: https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Function/apply#Using_apply_and_built-in_functions (Starting with "But beware..."), pointing to this issue in WebKit bugzilla: https://bugs.webkit.org/show_bug.cgi?id=80797). As far as I understand why RangeError is thrown in V8:

V8 implements Function.prototype.apply in assembly. Before calling the function, it should place all function call parameters, e.g. thisArg, and all of the members of 2nd arg array, one by one, onto stack, before calling the javascript function. But the stack has limited capacity, and if you hit the limit, you will get RangeError.

This is what I've found in V8 source (IA-32 assembly, builtins-ia32.cc):

void Builtins::Generate_FunctionApply(MacroAssembler* masm) {
  static const int kArgumentsOffset = 2 * kPointerSize;
  static const int kReceiverOffset = 3 * kPointerSize;
  static const int kFunctionOffset = 4 * kPointerSize;
  {
    FrameScope frame_scope(masm, StackFrame::INTERNAL);

    __ push(Operand(ebp, kFunctionOffset));  // push this
    __ push(Operand(ebp, kArgumentsOffset));  // push arguments
    __ InvokeBuiltin(Builtins::APPLY_PREPARE, CALL_FUNCTION);

    // Check the stack for overflow. We are not trying to catch
    // interruptions (e.g. debug break and preemption) here, so the "real stack
    // limit" is checked.
    Label okay;
    ExternalReference real_stack_limit =
        ExternalReference::address_of_real_stack_limit(masm->isolate());
    __ mov(edi, Operand::StaticVariable(real_stack_limit));
    // Make ecx the space we have left. The stack might already be overflowed
    // here which will cause ecx to become negative.
    // !! ADDED COMMENT: IA-32 stack grows downwards, if address to its current top is 0 then it cannot be placed any more elements into. esp is the pointer to stack top.
    __ mov(ecx, esp);
    // !! ADDED COMMENT: edi holds the "real_stack_limit", which holds the  minimum address that stack should not grow beyond. If we subtract edi from ecx (=esp, or, in other words, "how much space is left on the stack"), we may get a negative value, and the comment above says that
    __ sub(ecx, edi);
    // Make edx the space we need for the array when it is unrolled onto the
    // stack.
    // !! ADDED COMMENT: eax holds the number of arguments for this apply call, where every member of the 2nd argument array counts as separate argument
    __ mov(edx, eax);
    // !! ADDED COMMENT: kPointerSizeLog2 - kSmiTagSize is the base-2-logarithm of how much space would 1 argument take. By shl we in fact get 2^(kPointerSizeLog2 - kSmiTagSize) * arguments_count, i.e. how much space do actual arguments occupy
    __ shl(edx, kPointerSizeLog2 - kSmiTagSize);
    // Check if the arguments will overflow the stack.
    // !! ADDED COMMENT: we compare ecx which is how much data we can put onto stack with edx which now means how much data we need to put onto stack
    __ cmp(ecx, edx);
    __ j(greater, &okay);  // Signed comparison.

    // Out of stack space.
    __ push(Operand(ebp, 4 * kPointerSize));  // push this
    __ push(eax);
    __ InvokeBuiltin(Builtins::APPLY_OVERFLOW, CALL_FUNCTION);

Please check !! ADDED COMMENT for explanations of how I understand it.

And this is APPLY_OVERFLOW function, written in JS (again, V8 source, runtime.js):

function APPLY_OVERFLOW(length) {
  throw %MakeRangeError('stack_overflow', []);
}

EDIT: In your case, I would go like:

var max = -Infinity; 
for(var i = 0; i < arr.length; i++ ) if (arr[i] > max) max = arr[i];
t.O
  • 517
  • 5
  • 11
  • 1
    In my case, the limit of the following function is 251100 (on fresh start): `function max(arr) { return Math.max.apply(null, arr); }` – Richard Cotrina Feb 03 '15 at 03:21
1

You're reaching function parameter size limit. And it is OK. Function should accept only a few parameters as else is a code smell.

If you have a bunch of items? - Use Array. You are using .apply() which passes arguments like: fun(1,2,3,4,5,6....) and reaches the limit. This is bad practice.

The problem is - Math.max() is wired to work only like this, so your best bet would be iterative search function. But that's another topic, as performance and algorithm may vary for example if you first sort the array.

lukas.pukenis
  • 13,057
  • 12
  • 47
  • 81
  • 4
    This is some elitist bullocks. Using variable quantity arguments is one of the wonders of JavaScript flexibility. No need not to do it! It's very convenient in many cases. You should give a reason for it being bad! – Lodewijk Dec 12 '13 at 22:39
  • 2
    I love it and use it. Except I am all about edge cases in the answer:) – lukas.pukenis Dec 13 '13 at 05:19
0

To me the error shouldn't come from the call into Math.min / max it looks like the result of using recursion which I cannot beleive Chrome would use to implement those functions.

Are they embeded in recursive code?

You can roll your own min / max code trivially to avoid the problem in Chrome.

Tom
  • 43,583
  • 4
  • 41
  • 61
  • When debugging in Chrome, it always stops at the line with 'Math.max.apply', I also couldn't believe it, but it's the truth... And I don't have any recursion in this code. These two lines are in an init-function wich is only called once. – PanChan Aug 19 '13 at 08:51
0
var a=[]; 
for(var i=0;i<1125011;i++){ 
    a[i] = i;
}
function maxIterate(arr){
    var max = arr[0];
    for(var i = 1;i< arr.length; i++){
        (max < arr[i]) && (max = arr[i])
    }
    return max;
}
console.log(maxIterate(a));

Math.max may use recursive method to get max value, just rewrite an iterating function to get max instead.This will avoid RangeError.

Fly_pig
  • 155
  • 8