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?

A slight performance gain could be to use pre-decremet/pre-increment instead of post-decrement/post-increment. — Gumbo
– Gumbo, Commented Sep 19, 2009 at 17:41
Gumbo, you're right. It's a little faster. If you write your comment as an answer and there's no best solution i'll give it to you — Peter
– Peter, Commented Sep 19, 2009 at 18:01
I know this is very late but was curious. Why not just var dst = src.concat() ? I think this is probably the fastest way to clone an array. This isn't deep copy though. For deep copy looping is the only way to go. — Shripad Krishna
– Shripad Krishna, Commented Nov 27, 2011 at 23:19

Cem Kalyoncu · Accepted Answer · 2009-09-19 17:03:26Z

4

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++];
}

answered Sep 19, 2009 at 17:03

Cem Kalyoncu

14.6k4 gold badges45 silver badges63 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Peter Over a year ago

It is (tested in chrome, FF3.5 and Opera) Have a look at: codebase.es/test/copytest.htm

Carson Myers · Accepted Answer · 2009-09-19 18:07:37Z

2

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
    ...

edited Sep 19, 2009 at 18:07

answered Sep 19, 2009 at 17:51

Carson Myers

38.7k42 gold badges131 silver badges183 bronze badges

Comments

juanjis · Accepted Answer · 2010-10-14 21:26:48Z

1

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);
}

edited Oct 14, 2010 at 21:26

answered Oct 14, 2010 at 20:06

juanjis

112 bronze badges

Comments

idrosid · Accepted Answer · 2009-09-19 17:06:48Z

0

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

answered Sep 19, 2009 at 17:06

idrosid

8,0295 gold badges48 silver badges41 bronze badges

4 Comments

Cem Kalyoncu Over a year ago

He asks to replace contents of another array, not to form a new one.

Gumbo Over a year ago

@cemkalyoncu: Then do slice and splice.

Matthew Crumley Over a year ago

"Slice and splice" sounds like a TV direct-response product. "Tired of writing clumsy for loops? Try new Slice and Splice! It slices, it splices, it takes the pain out of array processing. Order now for only $19.95!"

Peter Over a year ago

slice + splice is much slower. Look at copy 3: codebase.es/test/copytest.htm

Alex Martelli · Accepted Answer · 2009-09-19 17:22:39Z

0

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;-).

answered Sep 19, 2009 at 17:22

Alex Martelli

887k175 gold badges1.3k silver badges1.4k bronze badges

3 Comments

Peter Over a year ago

this is around 10 times slower

Cem Kalyoncu Over a year ago

Some internal functions which most probably written in C++ works slower than interpreting bunch of lines, strange. BTW I tested same code in C resulting 6-14ms of copy time (1000 x 0x4000 elements)

Peter Over a year ago

modern browsers compile javascript into machine code. For example Chrome's V8 and FF's TraceMonkey.

Gumbo · Accepted Answer · 2009-09-19 17:28:46Z

0

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

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

edited Sep 19, 2009 at 17:28

answered Sep 19, 2009 at 17:23

Gumbo

657k112 gold badges792 silver badges852 bronze badges

2 Comments

Peter Over a year ago

Sorry. Your solution is around 50 times slower.

Derrick Over a year ago

Not if you want it to perform well.

Christoph · Accepted Answer · 2009-09-19 19:02:29Z

0

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).

answered Sep 19, 2009 at 19:02

Christoph

171k36 gold badges186 silver badges241 bronze badges

2 Comments

Peter Over a year ago

But the start indexes are hardcoded into the "compiled" function. For each copy call you would need to "compile" it again.

Peter Over a year ago

but they could be function parameters without performance loss.

Collectives™ on Stack Overflow

Javascript - Fastest way of copying an array portion into another

7 Answers 7

1 Comment

Comments

Comments

4 Comments

3 Comments

2 Comments

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

7 Answers 7

1 Comment

Comments

Comments

4 Comments

3 Comments

2 Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related