Javascript - Fastest way of copying an array portion into another

Question

I need to copy FAST a portion of an array into another, replacing it's old values.

• No range checkings needed.
• Number of items to copy: 16384
• The array only contains integers

benchmark code: http://codebase.es/test/copytest.htm

This is my approach:

  var i = 0x4000>>5; // loops count
  var j = 0x4000;    // write start index
  var k = 0x8000;    // read start index
  while (i--) {      // loop unrolling
    dst[j++]=src[k++]; dst[j++]=src[k++];
    dst[j++]=src[k++]; dst[j++]=src[k++];    
    dst[j++]=src[k++]; dst[j++]=src[k++];
    dst[j++]=src[k++]; dst[j++]=src[k++];
    //8
    dst[j++]=src[k++]; dst[j++]=src[k++];
    dst[j++]=src[k++]; dst[j++]=src[k++];    
    dst[j++]=src[k++]; dst[j++]=src[k++];
    dst[j++]=src[k++]; dst[j++]=src[k++];
    //16
    dst[j++]=src[k++]; dst[j++]=src[k++];
    dst[j++]=src[k++]; dst[j++]=src[k++];    
    dst[j++]=src[k++]; dst[j++]=src[k++];
    dst[j++]=src[k++]; dst[j++]=src[k++];
    //24
    dst[j++]=src[k++]; dst[j++]=src[k++];
    dst[j++]=src[k++]; dst[j++]=src[k++];    
    dst[j++]=src[k++]; dst[j++]=src[k++];
    dst[j++]=src[k++]; dst[j++]=src[k++];
    //32
  }

can this be done faster?

Answer 1

Im not sure your method is faster than this:

var i = 0x4000;     // loops count
var j = 0x4000;    // write start index
var k = 0x8000;    // read start index
while (i--) {      // loop unrolling
  dst[j++]=src[k++];
}

Answer 2

I would consider the slice method:

var dst = src.slice(start,end)

The performance depends on the implementation of javascript engine, but presumably all the browsers have implemented as efficient as possible on their platform.

See more here

Answer 3

An alternative worth benchmarking may be building a brand new dst array with just a few powerful primitives rather than performing the loop, i.e.:

dst = dst.slice(0, writestart).concat(
    src.slice(readstart, readstart+count),
    dst.slice(writestart+count));

How the performance of this approach compares to looping will no doubt vary with the array lengths and counts involved, as well as with the underlying Javascript engine -- guessing would not be very productive, which is why I suggest benchmarking instead;-).

Answer 4

Try a combination with the build-in method slice and splice:

Array.prototype.splice.apply(dst, [j, i].concat(src.slice(k, k+i)));

Answer 5

You could keep unrolling the loop for even slighter increases in performance, but it seems like this is just about as fast as you're going to get it. As Gumbo stated in a comment, try using pre-increment instead of post-increment:

var i = 0x4000>>5 + 1; // loops count
var j = 0x4000 - 1;    // write start index
var k = 0x8000 - 1;    // read start index
while (--i) {      // loop unrolling
    dst[++j]=src[++k]; dst[++j]=src[++k];
    dst[++j]=src[++k]; dst[++j]=src[++k];    
    dst[++j]=src[++k]; dst[++j]=src[++k];
    dst[++j]=src[++k]; dst[++j]=src[++k];
    //8
    ...

Answer 6

You can create a completely unrolled version, eg via

function compileCopy(count, di, si) {
    var sb = new Array(count);
    di += count, si += count;
    while(count--) sb[count] = --di + ']=src[' + --si;
    return new Function('dst[' + sb.join('];dst[') + '];');
}

var copy = compileCopy(0x4000, 0x4000, 0x8000);

In Opera, it will be slightly faster than the looping version. In FF... not (there might even be some bug somewhere).

Answer 7

Sorry, one year later, but.. this is fastest in FF:

function copy4() {
  var i = 0x4000; // loops count
  var j = 0x4000; // write start index
  var k = 0x8000; // read start index

  var args = src.slice(k, k+i);
  args.unshift(i);
  args.unshift(j);
  Array.prototype.splice.apply(dst,args);
}