Yan Cui
I help clients go faster for less using serverless technologies.
I have heard a few people argue that when it comes to performance critical code you should prefer arrays over other collections (such as F#’s lists) as it benefits from sequential reads (which is faster than seeks) and offers better memory locality.
To test that theory somewhat, I wanted to see if there is any difference in how fast you can iterate through an array versus a list in F#, and how much faster you can map over an array compared to a list:
The result is a little surprising, whilst I wasn’t expecting there to be a massive difference in the iterating through the two types of collections, I didn’t think mapping over a list would be quite as slow in comparison. I knew that constructing a list is much heavier than constructing an array, but I didn’t think it’d take 22x as long in this case.
What was even more surprising was how much slower the Seq.iter and Seq.map functions are compared to the Array and List module equivalents! This is, according to John Palmer:
Once you call in to
Seqyou lose the type information – moving to the next element in the list requires a call toIEnumerator.MoveNext. Compare to forArrayyou just increment an index and forListyou can just dereference a pointer. Essentially, you are getting an extra function call for each element in the list.The conversions back to
ListandArrayalso slow the code down for similar reasons
Update 2012/06/04:
As a work around, you COULD shadow the Seq module with iter and map functions that adds simple type checking and in the case of an array or list simply call the corresponding function in the Array or List module instead:
Whilst this approach will work to a certain extend, you should be careful with which functions you shadow. For instance, it’s not safe to shadow Seq.map because it can be used in conjunction with other functions such as Seq.takeWhile or Seq.take. In the base implementation, a line of code such as:
arr |> Seq.map incr |> Seq.take 3
will not map over every element in the source array.
With the shadowed version (see above) of Seq.map, however, this would first create a new array by applying the mapper function against every element in the source array before discarding all but the first three elements in the new array. This, as you can imagine, is far less efficient and requires much more memory space (for the new array) and defeats the purpose of using Seq module functions in most cases.
Whenever you’re ready, here are 4 ways I can help you:
- If you want a one-stop shop to help you quickly level up your serverless skills, you should check out my Production-Ready Serverless workshop. Over 20 AWS Heroes & Community Builders have passed through this workshop, plus 1000+ students from the likes of AWS, LEGO, Booking, HBO and Siemens.
- If you want to learn how to test serverless applications without all the pain and hassle, you should check out my latest course, Testing Serverless Architectures.
- If you’re a manager or founder and want to help your team move faster and build better software, then check out my consulting services.
- If you just want to hang out, talk serverless, or ask for help, then you should join my FREE Community.
Hi,
I don’t think you’re being fair on the Seq in combination with the List. Since the List is immutable, there’s no need to materialize the List in the last step “|> Seq.ToList”. You can just pass around the lazy Seq over the Immutable list and be sure that you will always get the same result.
The Array does not have that luxury, but this may not have to be an issue in most cases if there’s no concurrency involved.
@Gert-Jan – without the last Seq.toList step you will get a sequence back as opposed to a list, which is not the same as ‘lst |> List.map incr’ which returns a new list where each element is mapped from the source list.
The test was purely intended to show if there’s any difference in how fast simple iter and map operations are performed on array and lists, and when using the Seq.iter and Seq.map functions.
Nice tests! But your conclusion is misleading.
Your loop size is huge: 10,000,000! So the actual overhead for a single iteration is 10 million times less.
If you take a reasonable loop size, say 1000, then your timings are 10,000 times less.
So, your tests actually show, all things considered, the relative overhead for Seq, Loop, and Array are negligible.
@ray – it’s more about relative cost, actual impact depends upon usage in your application of course. The difference is negligible if you don’t have to deal with large collections or many many small collections on a regular basis.