12
Mar
09

Fastest Way to Copy An Array: Concat() or Slice(0)

What is the fastest way to copy an array? Concat or Slice? There is only one way to find out. FIGHT!

OK, so we can dismiss any kind of for-loop – far too slow, so that leaves us with:
1) array.concat() – i.e. concatenate an array onto nothing and deliver that as a new array.
2) array.slice(0) – i.e. return a new array consisting of all of the elements of the old array – from 0 till the end (up to a max of 16777215)

I’ve set up an array with a cool 1million entries (ok, it is not big, and it is not clever so it certainly isn’t cool). I need to copy this. The following code executes each method once on every iteration. It keeps a running total and records the average time each takes. I’ve limited the code to 100 iterations.

package
{
import flash.display.Sprite;
import flash.events.Event;
import flash.events.MouseEvent;
import flash.text.TextField;
import flash.utils.*;
public class TestConcat extends Sprite
{
private var iteration_count:int=0
private var concat_total:int=0
private var slice_total:int=0
private var clone_total:int=0
private var tf:TextField = new TextField()
private var test_array:Array = [];

public function TestConcat():void
{
tf.x = tf.y = 100; tf.width = 600;
addChild(tf)

//Set up array to copy
for(var i:int = 0; i < 1000000; i++) test_array.push(i);
//Mouse click to rerun test
stage.addEventListener(MouseEvent.CLICK, go);
//First run
go()
}

private function go(e:Event = null):void
{
iteration_count=concat_total=slice_total=clone_total=0
addEventListener(Event.ENTER_FRAME, iterate)
}

//Loop through tests
private function iterate(e:Event=null):void
{
concat_total +=testConcat()
slice_total += testSlice()
clone_total += testByteArrayClone()
iteration_count++
tf.text = "Av. Concat time=" + (concat_total / iteration_count)
+ "ms Av. Slice time=" + (slice_total / iteration_count)
+ "ms Av. BA Clone time=" + (clone_total / iteration_count) + "ms";
if(iteration_count<99) removeEventListener(Event.ENTER_FRAME,iterate)
}

//test array slice
private function testSlice():int
{
var time_slice_start:Number = getTimer();
var slice_copy:Array = test_array.slice(0);
return getTimer()-time_slice_start
}

//test array concat
private function testConcat():int
{
var time_concat_start:Number = getTimer();
var concat_copy:Array = test_array.concat();
return getTimer()-time_concat_start
}

//test BA Clone method
private function testByteArrayClone():int
{
var time_concat_start:Number = getTimer();
var concat_copy:Array = clone(test_array);
return getTimer()-time_concat_start
}

//Clone method for Deep Objects(via Bruno)
private function clone(source:Object):*
{
var myBA:ByteArray = new ByteArray();
myBA.writeObject(source);
myBA.position = 0;
return(myBA.readObject());
}
}
}

On my laptop I’m clocking the concat at 14ms and the slice at over 29ms.

So a conclusive result. concat is twice the speed (with large arrays – the difference diminishes considerably with smaller arrays)

Give the code a few run throughs and see what you get. Let me know if your results are markedly different.

UPDATED:
I have updated the code and added a swf to try out here and the source code here

Fastest way to copy an array

Test the array copy for yourself


I’ve also added in a test for the Byte Array Clone method suggested by Bruno (see his comments below). This method seems a great one for copying ‘deep’ arrays – arrays of complex objects (arrays, objects or other types). In this context and test (copying shallow arrays) the instantiation, writing and reading adds too much overhead. I’ll need to test this in a useful context: with deep arrays.

Demo: Array Copy test
Source: Source.as

About these ads

11 Responses to “Fastest Way to Copy An Array: Concat() or Slice(0)”


  1. 1 sinclairc5
    May 19, 2009 at 12:01 am

    i ran this test using a code testing class returning concat speeds between 12-13ms and consistant slice times of 24ms. Performed on a Q6600.

  2. October 2, 2009 at 1:52 pm

    Since you are using trace() I assume that you are testing this in the debug player. That is not a good idea since there are big speed differences between the debug player and the release player as well as the debug version and the release version of a SWF. You should add a textfield to your test and log the results on screen and then test it with the release version in the release player.

  3. February 7, 2010 at 9:11 pm

    Would this really be considered a copy, if the array is just referencing the old array? Changes made on the new array will be reflected on the old array.

    START OF TEST CODE

    // Setting up the Original Array called old_array

    var old_array:Array = [];

    old_array[0][0] = “0×0″;
    old_array[0][1] = “0×1″;

    old_array[1][0] = “1×0″;
    old_array[1][1] = “1×1″;

    old_array[2][0] = “2×0″;
    old_array[2][1] = “2×1″;

    // ‘Copying’ old_array array into the newly created new_array

    var new_array:Array = old_array.concat();

    trace(“Old Array:”);
    trace(old_array.concat());

    trace(“New Array:”);
    trace(new_array.concat());

    trace(” “)
    trace(“Removing a Node from New Array”);
    trace(” “)

    // Removing an element from new_array

    new_array[2].splice(1,1);

    trace(“Old Array:”);
    trace(old_array.concat());

    trace(“New Array:”);
    trace(new_array.concat());

    END OF TEST CODE

    You maybe able to discern from the Output data that the new_array does not independently exist, but instead is coupled with old_array. Any changes made to new_array will be reflected on old_array.

    • 4 swingpants
      February 7, 2010 at 10:38 pm

      This is a good point. But in your example you have built a multi-dimensional array – or an array of arrays.

      Simple data types don’t need ‘cloning’, whereas complex ones do. An array is a complex data type so when the concat is executed the pointers to the 2nd dimension of array are copied not the actual data.

      This issue is common to both the methods that I tested, even a simple for-loop would need to dig into each 2nd dimension array and loop that as well.

      So concat & splice(0) are valid copy methods for a simple array – for multidimensional you will need a loop and concat combination.

  4. 5 nook
    June 27, 2010 at 2:45 pm

    It would be interesting to see how a manual copy would do in comparison. (Ie a function that iterates the array and put elements in new array.)

  5. 7 Bruno
    October 31, 2010 at 6:34 pm

    See it:

    http://help.adobe.com/en_US/ActionScript/3.0_ProgrammingAS3/WS5b3ccc516d4fbf351e63e3d118a9b90204-7ee7.html

    Cloning arrays

    The Array class has no built-in method for making copies of arrays. You can create a shallow copy of an array by calling either the concat() or slice() methods with no arguments. In a shallow copy, if the original array has elements that are objects, only the references to the objects are copied rather than the objects themselves. The copy points to the same objects as the original does. Any changes made to the objects are reflected in both arrays.

    In a deep copy , any objects found in the original array are also copied so that the new array does not point to the same objects as does the original array. Deep copying requires more than one line of code, which usually calls for the creation of a function. Such a function could be created as a global utility function or as a method of an Array subclass.

    The following example defines a function named clone() that does deep copying. The algorithm is borrowed from a common Java programming technique. The function creates a deep copy by serializing the array into an instance of the ByteArray class, and then reading the array back into a new array. This function accepts an object so that it can be used with both indexed arrays and associative arrays, as shown in the following code:

    import flash.utils.ByteArray;

    function clone(source:Object):*
    {
    var myBA:ByteArray = new ByteArray();
    myBA.writeObject(source);
    myBA.position = 0;
    return(myBA.readObject());
    }

  6. 8 Washington Wizards
    November 10, 2010 at 8:07 pm

    good post, added you to my RSS reader. Greetings from DC :)

  7. 9 Angry1
    April 7, 2011 at 12:49 pm

    I’d kick the Actionscript developers’ ass really hard for omitting such a critical function.
    It took me two days to find out that it was that lame $#@@%&^%^ shallow copy the cause of my troubles. In an almost 100% OOP environment, = assignment and swallow alternatives like concat() are practically useless. We work with objects moron developers! Where is your highly important built-in deep copy function?

    Fortnunately there are exceptions: Developers able to *think* about the obvious who also offer for free their valuable thoughts and work. Far better than Addobe’s payed ones! I’m grateful to you Bruno!

    Fire flash developers ASAP!

  8. 10 John
    September 20, 2011 at 10:19 am

    You have a XSS problem on your site.

    Install noscript plugin for firefox and see the error report.


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


Categories

Reasons to be Creative 2012

FITC Amsterdam 2012

Flash on the Beach 2011

Flash on the Beach 2010

Flash on the Beach 2009

Swingpants at FOTB2009

Twitter Updates

Error: Twitter did not respond. Please wait a few minutes and refresh this page.


Follow

Get every new post delivered to your Inbox.

%d bloggers like this: