Comparing List And Array Speeds

In my previous post on Optimizing A Query Dump for my cfExcelProxy project, Hem suggested I use arrays instead of lists in some of my operations. After making some modifications to my code, I noticed that I indeed managed to shave a couple of seconds to my total processing time. This got me thinking: Are arrays always better than lists? If not, then when are they better suited? Armed with only my courage and an old, beaten laptop I decided it was time I put these two types against each other to determine, once and for all, which was the best of the best!

Creating test variables

The first thing I needed was some nice, random test variables. I wanted to see how both types fared depending on their size, so I started by defining a list of lengths.

Using this list, I then looped over it to create my test arrays and lists.

You can see by the above snippet of code that I am creating distinct variables for each test and giving them dynamic names. I am also using the cftimer tag to display the timer information in the debug window. In both cases I populate the current element with a random float with the rand() function.

Running the above code to generate the variables, here is what we get in the timer section:

[0ms] 100 Elements - Array Initialization
[10ms] 1000 Elements - Array Initialization
[81ms] 10000 Elements - Array Initialization
[741ms] 50000 Elements - Array Initialization

[0ms] 100 Elements - List Initialization
[210ms] 1000 Elements - List Initialization
[20172ms] 10000 Elements - List Initialization
[615341ms] 50000 Elements - List Initialization

Looking at these numbers, I can't help but feel sorry for my poor little ColdFusion server. Initialization an array seems rather trivial, taking less than a second for even 50k elements. However, generating a list seems to grow exponentially harder as we add elements. I'm especially impressed by the jump from 1000 to 10000 elements. Although it's only 10 times as many elements, the time needed to generate the larger list is 100 times more!

Creating test variables conclusion: From these (non-scientific) test results, we realize that generating an array seems much faster than generating a list, especially so as the number of elements grows.

Retrieving elements from our variables

Another test I wanted to try was seeing how fast we can extract data from arrays or lists. To do this, I simply loop 100 times and extract a random element from the variable. Here's how I went about doing this:

Nothing too complicated here. For the arrays, we simply access an element at a random position, using the randRange() function. For the list, we need to use the listGetAt() function to do the same thing. We then store the result in a dummy container variable, to simulate an actual operation.

[0ms] 100 Elements - Retrieve 100 Elements From Array
[0ms] 1000 Elements - Retrieve 100 Elements From Array
[10ms] 10000 Elements - Retrieve 100 Elements From Array
[0ms] 50000 Elements - Retrieve 100 Elements From Array

[0ms] 100 Elements - Retrieve 100 Elements From List
[20ms] 1000 Elements - Retrieve 100 Elements From List
[451ms] 10000 Elements - Retrieve 100 Elements From List
[2243ms] 50000 Elements - Retrieve 100 Elements From List

We can see that accessing an element in an array seems to be completely trivial, taking practically no time at all regardless of the amount of elements in the variables. Doing the same thing for the list, however, takes more time as the length grows.

Retrieving elements from our variables conclusion: Although the access time is rather short (a little over 2 seconds for 100 elements isn't too bad), it still takes longer using listGetAt() than accessing an array's index directly.

Finding elements in our variables

Both tests so far seemed to indicate that arrays were generally the fastest option for dealing with multiple-element variables. However, I still had my doubts. What if I want to find a particular value within my variable? Lists have the listFind() (and listFindNoCase()) function, while arrays have nothing. The only way to find something within an array is to loop over it and compare the current element with the searched value.

Nothing too complicated here. We simply look for a random element within all of our test variables. Chances are the value won't be found, but that's against the point. All we want to do is see how long it takes to search through our variables. Here are the results of the previous tests:

[20ms] 100 Elements - Find 100 Elements From Array
[581ms] 1000 Elements - Find 100 Elements From Array
[2714ms] 10000 Elements - Find 100 Elements From Array
[13580ms] 50000 Elements - Find 100 Elements From Array

[10ms] 100 Elements - Find 100 Elements From List
[40ms] 1000 Elements - Find 100 Elements From List
[330ms] 10000 Elements - Find 100 Elements From List
[1733ms] 50000 Elements - Find 100 Elements From List

This is where the tests get interesting. We need to loop over our array to find our value. If we're lucky, we might find it rather fast and break from the loop. However, chances are that that won't be the case. Lists, however, don't seem to have this issue. Coldfusion must use some sort of hidden voodoo magic (regular expressions?) to quickly search through our list and find (or not) our searched value.

Finding elements in our variables conclusion: This last test complicates things a bit. Arrays aren't the best solution for every situation. We would need to find a compromise between both variable types to account for every situation possible.

Converting between variable types (list <> array)

Luckily for us, Coldfusion provides us with easy-to-use functions to convert from lists to arrays, and vice-versa. What I wanted to know, however, is whether there was any significant impact for these conversions. So, here we go again:

This test is rather simple, so let's jump right into the results.

[0ms] 100 Elements - Convert Array to List
[10ms] 1000 Elements - Convert Array to List
[40ms] 10000 Elements - Convert Array to List
[251ms] 50000 Elements - Convert Array to List

[0ms] 100 Elements - Convert List to Array
[0ms] 1000 Elements - Convert List to Array
[0ms] 10000 Elements - Convert List to Array
[100ms] 50000 Elements - Convert List to Array

251ms for converting a 50k element array into a list, and 100ms for converting a 50k element list into an array...

Converting between variable types conclusion: There doesn't seem to be any significant impact on converting the variables between types. Considering a variable containing 50000 elements, and the time possibly saved from converting, 250ms seems like a very little price to pay.

In conclusion

Generally speaking, using arrays seems to be the fastest option. Whether it's for actually generating it, or accessing an element from it's position, they are the winner by far. However, if you need to find an element in your array, it would be much faster to convert it using arrayToList() and then using listFind() on the result.

I just want to stress again that none of these tests can be considered scientific. I ran these on my development laptop and only a couple of times. However, the results seemed to align every time. If you have different results I encourage you to post a comment so we can compare and find out what the cause could be.

Thanks for reading, and stay tuned for an announcement later this week.