Lists vs. Sequences: Concatenation

In my previous post, I presented some of the benefits of thinking in sequences rather than lists. This post will discuss a concrete example, concatenation of multiple series of elements.

The case is as follows. You have several series of elements and you would like to aggregate all the contained elements into one concatenated series. This resulting series is for iteration only and does not have to be mutable.

To solve the task using lists, one could write a method like this:

public static IList<T> ConcatenateLists<T>(params IList<T>[] lists)
{
	List<T> retList = new List<T>();
	foreach (var list in lists)
	{
		retList.AddRange(list);
	}
	return retList;
}

The elements of all the lists passed to the method are added to a result list which is ultimately returned to the caller. Semantically, there is absolutely nothing wrong with this method. It produces the expected result.

Consider, however, the performance of this method if the input lists contain a million elements altogether. The result list would need to contain one million elements. If you are lucky, the elements are of a reference type, requiring only storage for one million references. If the elements are of a value type, however, one million objects, including their data, would have to be copied to the result list. If each object holds a kilobyte of data, the result list will need to allocate an entire gigabyte of memory before the iteration can even begin!

Surely, a smarter approach would be beneficial. My proposal is to think in sequences. Since the resulting concatenation only needs to be iterated over, there is no specific need for the result of the method to be a list in the first place. A sequence is sufficient. Further, the input elements can be regarded as a series of sequences as well, yielding a method like follows:

public static IEnumerable<T> ConcatenateEnumerables<T>(params IEnumerable<T>[] enumerables)
{
	foreach (var enumerable in enumerables)
	{
		foreach (var item in enumerable)
		{
			yield return item;
		}
	}
}

Notice the yield return statement. As previously discussed, this facilitates lazy execution. If, for some reason, the caller decides it only needs the first ten elements, then the yield return statement is only executed ten times.

Consider again the scenario of a million kilobyte-sized value type elements being concatenated. This time, the caller will be served the sequence one element at a time, from already allocated memory, reusing a single kilobyte-sized variable through the entire iteration.

Evidently, thinking in sequences can lead to remarkable performance gains. Of course, you need to consider the requirements and determine whether a sequence will meet your needs. If, for any reason, the resulting series has to be manipulated as a list, consider still using sequences and relying on LINQ’s Enumerable.ToList<TSource> extension method to aggregate the elements into a list when needed.

Advertisements

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