Speed Tests: Objects vs. Arrays vs. Dictionaries
I’ve been taking buses around Europe for a couple weeks now, and sometimes those trips get extremely long. Yesterday I took a bus from Venice to Seefeld (Austria), a trip that would have taken about five hours if not for the hurricane-like downpour they were having in Italy. Seriously, it was ridiculous- all traffic was on the side of the highway, and all the motorcyclists were huddled under the overpasses. But on the bright side, it did give me a lot of time to try out some things that I normally wouldn’t take the time to do, such as this experiment.
I make a lot of decisions daily based on things I think I know, but really have just always assumed. And so, on this bus ride, I decided to get to the bottom of a few of them. The first experiment I tried was with the read and write speeds of Objects, Arrays, and Dictionaries. In the past, I have always used Arrays when I need all the nifty sorting and organization methods, Dictionaries when I need fast access, object keys, or weak references, and Objects pretty much never (because they’re messy and slow). So yesterday I decided to see if my assumptions were actually valid, or if I had been doing things wrong this whole time.
So I set up a quick class to test. I created a Dictionary, an Object, and an Array, and then I put 100,000 integers in each one for the write test, and read them back out for the read test. This is what I got (all times are average and in milliseconds).
| Object | Array | Dictionary | |
|---|---|---|---|
| Read (integer key) | 86819 | 573 | |
| Write (integer key) | 24 | 17 | 22 |
| Read (string key) | 586 | N/A | 573 |
| Write (string key) | 329 | N/A | 333 |
Obviously there are many more benchmarks that I could have run, but I also had a pretty good book on that bus. I think I’ve done enough experimentation to prove that, once again, my assumptions are invalid.
July 8th, 2008 at 6:07 am
What are dictionaries?
July 10th, 2008 at 6:43 am
The Dictionary class is a really simple class in AS3 that allows you to store objects just like an object or an array. The difference is that you can use anything you want as a ‘key.’
In Arrays you have to use integers, in Objects you have to use Strings, and in Dictionaries you can use numbers, strings, or even other objects.
Here’s some more info: Adobe LiveDocs
July 12th, 2008 at 8:17 pm
It’s interesting to see actual times for these tests. I’ll tell you, though, although objects look butt-slow, their real power is in using them in data structures. An array may be a great all-purpose tool, but when you need a heap, tree, or some sort of sorted structure, an array will probably be much slower.
One reason is that for a structure made of objects, each object can have pointers (references) to the next object in the structure. So, every time you add another object, it takes the same amount of time. In many arrays (I know in C and C++, but I’m not sure in AS3), the computer begins with an array of a definite length, and if you add another element past that (with a push function), it automatically makes a new array twice the length of the old, and copies the old one into the new one (this is not the case if YOU specify the length. But for a dynamic data structure, this is normally not the case). This can cause some major speed issues if your computer is unknowingly copying a 50,000 length array into a 100,000 length array.
So be careful when choosing your data structure. You should pick arrays only when they best suit the function at hand. Many times, however, a dynamic data structure made from objects (sometimes arrays) will suit your needs better.
August 6th, 2008 at 1:31 am
So, how does xml fit into this speed comparison? I know xml has been a standard option in Flash in the past, but with it’s support in AS3, does it have a running in the speed trials of data structuring?
August 6th, 2008 at 8:05 am
That’s a good question. I’ll have to add that to the trials.
August 6th, 2008 at 2:54 pm
I mean to say “I know xml hasn’t been a standard option in Flash in the past”
April 8th, 2009 at 10:10 am
Hi we’re currently in the process of developing a game which uses a graph to store a set of planets and arcs to their neighbours.
The arcs are currently stored as a list in the new Flex SDK 3.3 Vector. data structure.
Since each planet has a unique name and lookups are done based on these names we were wondering if the dictionary class would faster or our current implementation of Vectors.
The code is nowhere near testable so I was hoping to gather some info to move along with the Implemetation.
Here’s a link but the results you’ve provided and the ones in the link seem to conflict.
http://www.zombieflambe.com/actionscript-3/as3-dictionary-class-array-object-benchmark/
May 18th, 2009 at 11:46 am
These results sparked my own interest into the performance of these data structures. Obviously, cs4 is out now and perhaps is the cause for boosted performance while reviewing my results. I found that Dictionary objects are now faster in all situations versus Arrays (I did not test Objects). Arrays suffer hugely in random deletion (which should be the case anyhow), where as the Dictionary responded on average of 0ms (sometimes 1ms). For iterative, linear reading of both data structures, the Dictionary won out by ~300ms for 1,000,000 elements. I would be more then happy to post the code used for each trial, feel free to send me an email.
October 17th, 2009 at 7:12 am
[…] Some further readings: http://www.gskinner.com/blog/archives/…/as3_dictionary.html http://www.zombieflambe.com/actionscript-3/as3-dictionary-class-array-object-benchmark/ http://pixelwelders.com/blog/best-practices/2008/speed-tests-objects-vs-arrays-vs-dictionaries/ […]