0
\$\begingroup\$

Could the performance of this function be optimized (without making the code much longer)?

The function zips two arrays into another.

function zip(p,q) {
  if( p.length > 1 || q.length > 2) {
    return ([[p[0],q[0]]]).concat(zip(p.slice(1),q.slice(1)));
  } else {
    return ([[p[0],q[0]]]);
  }
}
  • How exactly does the slice work? Is it immutable, like getting the tail in Haskell?

  • What values are inside the value returned by .concat()? Are these copy-constructed values from references, or are these references and are copied when a new array is constructed with the call to .concat()?

\$\endgroup\$
  • \$\begingroup\$ Yes, it works as expected, since the order doesn't matter for me, but of course the arrays in the if clause should be swapped if the order would matter. I swap them. \$\endgroup\$ – ntj Dec 17 '17 at 12:18
  • 1
    \$\begingroup\$ How exactly does the slice work?: well, if this is your code, then you are not supposed to ask this \$\endgroup\$ – Billal Begueradj Dec 17 '17 at 12:22
  • 1
    \$\begingroup\$ I know what slice does, the question is how it's implemented. Does slice(x) return a reference to the rest of the array, or does it copy the value of the rest of the array? \$\endgroup\$ – ntj Dec 17 '17 at 12:30
2
\$\begingroup\$

Recursive memory hog!!

I have to say that this is not at all a practical way to zip two arrays.

Recursive functions are huge memory hogs in JS if done badly

In Javascript calling a function adds a minimum of about 1 - 1.5K to the call stack, and you create copies each array of each call, ouch..

Test

I ran your function giving it two 8Mb array (1,000,000 numbers each) and it crashed Chrome. Something I would expect to do using a function like zip.

Crashed at 0.01% complete

Canary 65 devtools has a live performance monitor, so I ran that and I watched memory climb in less than a second to 1GB befor the browser interrupted and paused the code. The heap is full and the function was only 97 iterations in (approx 0.01% complete).

Why the memory usage?

Your use of Array.slice is the reason. Slice creates a shallow copy of each array. So if you have an array of size 100 and slice at 1 you now have two arrays for a total of 199 items.

Lets follow the recursion with 2 3 itemed arrays

function zip(p,q) {
  if( p.length > 1 || q.length > 2) {
    return ([[p[0],q[0]]]).concat(zip(p.slice(1),q.slice(1)));
  } else {
    return ([[p[0],q[0]]]);
  }
}

Make the call

zip([1,2,3],[4,5,6]);

zip(p.slice(1),q.slice(1));       // create 2 copies 2 bytes each
>> zip(p.slice(1),q.slice(1))     // create 2 copies 1 bytes each
>> >>  return ([[p[0],q[0]]]);    

At this point there are arrays [3,6], [3], [6], [2,3], [5,6], [1,2,3], [4,5,6]

return ([[p[0],q[0]]]).concat( << <<

This is when you hit peek memory use, just before the above return you add another array [1,4,3,6] so you have stored in memory 18 references

return ([[p[0],q[0]]]).concat( <<
End.

Result is an array with 6 references.

Calculating memory use

You memory usage assuming same sized arrays is

len = array.length; // both arrays are the same size

totalReferences = (len / 2) * (len + 1) * 2 + 6

So for 2 array of size 100

(100 / 2) * (100 + 1) * 2 + 6 === 10,106

And for larger

1,000   === 1,001,006
10,000  === 100,010,006
100,000 === 10,000,100,006

How to improve.

Can Tail Call Optimisation (TCO) help?

TCO basically lets you call a function without adding a new context to the call stack. This makes calling a function almost as fast as running inline code. This would be the single best thing to have happened to the language for decades (and its only decades old), if it happened :(.

Javascript ES6 spec has (the very anticipated and needed) TCO but it remains the only unimplemented ES6 feature on Chrome, Firefox, and Edge. Reason?? I believe too many pages are kept running due to call stack overflow error, TCO prevents this and thus a bad recursion function blocks the page rather than throws an error.

Don't hold your breath waiting for TCO, for now its not going to help.

The only solution

In reality without TCO you can not safely do this via recursion. The call stack size is much smaller than the max array size. If you do recursion you would have to limit the array sizes, but even then you can not know how deep you are already in the call stack when you start, so there is no safe way to do this (Yes all recursive functions in javascript are fatally flawed, until TCO)

Quick simple and low memory use.

function zip(a, b) {
    const min = Math.min(a.length, b.length);
    var i, j, c;
    c = [];
    i = j = 0;
    while (j < min) {  
        c[i ++] = a[j];
        c[i ++] = b[j ++];
    }
    if (a.length < b.length) { [a, b] = [b, a] }
    while (j < a.length) { c[i ++] = a[j ++] }
    return c;
}
\$\endgroup\$
1
\$\begingroup\$

Performance

Could the performance of this function be optimized? (Without making the code much longer.)

If you want to stick with a functional implementation, one possible improvement I see is avoiding slices. Slicing is likely to create new arrays, which is inefficient. You could instead use a helper function that takes a 3rd parameter to track the start position of the first two parameters. The recursive calls would pass on the first two parameters without slicing, and increment the value of the 3rd parameter.

Another possible improvement is to avoid the concatenation, which is another inefficient operation. You could add the helper function another parameter, a pre-allocated array of the correct target size to populate with the value pairs, according to the tracked position.

If you don't mind breaking with the functional style, it will be good to replace recursion with iteration, because as of today JavaScript implementations don't normally have tail call optimization.

Usability

The current implementation creates value pairs in reverse of their original order. This is different from the typical behavior of the zip function in other languages, so I find that confusing. Also, when one of the parameters is longer, the current implementation uses undefined in place of the missing values. This is different from the behavior in Python, for example, where excess elements are dropped.

Bug?

Due to the condition p.length > 1 || q.length > 2, these calls will produce arrays of different lengths:

zip('a', '123');
zip('123', 'a');

I would expect to get arrays of equal length in these calls.

\$\endgroup\$
  • \$\begingroup\$ length > 2 is a bug, where the num supposed to be 1, anyway thanks for the advice. \$\endgroup\$ – ntj Dec 17 '17 at 17:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.