A review of List.Allocate v List Expansion

A while ago I read Ossie Moore's blog post Rock, Paper, Scissors... List Expansion Beats Allocate comparing the performance of two methods of adding content to a List. In the Blog post the comparison is between 10,000 items for the Allocate approach and 100,000 for the Expansion approach, and comes up with some significant differences in performance for these two approaches :

Allocate Example:
10000 Items
1545 Ticks
6.47249190938511 Items/Tick
 
Expand Example:
100000 Items
1498 Ticks
66.7556742323097 Items/Tick

I wondered if the performance of these two approaches was at a range of sizes for the List. I used the same OScript code that is present in the Blog post, but passing in a series of different size values to see what the performance profile looked like. As an additional comparison I also added a pass where the number of items added using both approaches was the same. In OScript, a Tick is a millisecond. The following table shows the results of the testing :

    100 200 300 400 500 600 700 800 900 1000 2000 3000 4000 5000 6000 7000 8000 9000 10000
Allocate Example Ticks 1 2 2 4 5 7 7 11 13 12 41 93 165 246 351 470 567 725 883
Items/Tick 100 100 150 100 100 85.714 100 72.727 69.231 83.333 48.780 32.258 24.242 20.325 17.094 14.894 14.109 12.414 11.325
Expansion Example Ticks 1 1 2 2 3 3 4 6 5 6 14 16 24 29 34 39 45 55 56
Items/Tick 100 200 150 200 166.667 200 175 133.333 180 166.667 142.254 187.5 166.667 172.413 176.470 179.487 177.778 163.636 178.571
Expansion Example (x10) Ticks 5 11 17 22 137 34 105 54 55 232 134 346 416 468 402 419 478 581 697
Items/Tick 200 181.818 176.471 181.818 36.496 176.471 66.667 148.148 163.636 43.103 149.254 86.705 96.154 106.838 149.253 167.0644 167.364 154.905 143.472

While I only performed one pass of the code, and there are a few outliers as well, so this result can not be considered as valid as a proper review, the trend shown above are in line with, and thus support, those identified in the Blog post. The divergance becomes clearer if you plot the results in a graphical format :

As you can see, when the List contains less than 1000 items, the performance difference is relatively minor, but as the size increases the difference between the two approaches increases quickly. While the numbers may look large, its important to remember that a Tick is a millisecond, so thats not a huge amount of time, but in some systems every second, or millisecond, is important.

Website Designed by Adservio Consulting Valid HTML 4.01 Strict    Valid CSS!    Level A conformance icon, W3C-WAI Web Content Accessibility Guidelines 1.0