Photo by Maksym Kaharlytskyi

This is a follow up to my previous post about sorting (really) large files using c#.

The problem

We have the following CSV file:

FirstName,LastName,FullName,Username,Email,UniqueIndex,Id,ProfilePicture
Hector,Reichel,Hector Reichel,Hector92,[email protected],Value 0,adf1cf72-40eb-4596-b809-b509ffdcd1b7,https://cloudflare-ipfs.com/ipfs/Qmd3W5DuhgHirLHGVixi6V76LhCkZUz6pnFt5AJBiyvHye/avatar/417.jpg
Lamar,Schmeler,Lamar Schmeler,Lamar76,[email protected],Value 1,a29fd784-c554-4301-b689-e678df358cc7,https://cloudflare-ipfs.com/ipfs/Qmd3W5DuhgHirLHGVixi6V76LhCkZUz6pnFt5AJBiyvHye/avatar/434.jpg
Pearl,Rosenbaum,Pearl Rosenbaum,Pearl.Rosenbaum54,[email protected],Value 2,3f77c9b3-820b-4afd-8dbc-fb72dc4f81d3,https://cloudflare-ipfs.com/ipfs/Qmd3W5DuhgHirLHGVixi6V76LhCkZUz6pnFt5AJBiyvHye/avatar/945.jpg
Guido,Wolf,Guido Wolf,Guido53,[email protected],Value 3,12618f37-e4eb-4c62-9a8f-104d77bea283,https://cloudflare-ipfs.com/ipfs/Qmd3W5DuhgHirLHGVixi6V76LhCkZUz6pnFt5AJBiyvHye/avatar/500.jpg
Alexis,Schneider,Alexis Schneider,Alexis_Schneider40,[email protected],Value 4,df7b9351-a049-4fa3-a4ea-b753bc6df517,https://cloudflare-ipfs.com/ipfs/Qmd3W5DuhgHirLHGVixi6V76LhCkZUz6pnFt5AJBiyvHye/avatar/660.jpg

In my previous post I sorted the file based on the whole line. Example:

FirstName,LastName,FullName,Username,Email,UniqueIndex,Id,ProfilePicture
Alexis,Schneider,Alexis Schneider,Alexis_Schneider40,[email protected],Value 4,df7b9351-a049-4fa3-a4ea-b753bc6df517,https://cloudflare-ipfs.com/ipfs/Qmd3W5DuhgHirLHGVixi6V76LhCkZUz6pnFt5AJBiyvHye/avatar/660.jpg
Guido,Wolf,Guido Wolf,Guido53,[email protected],Value 3,12618f37-e4eb-4c62-9a8f-104d77bea283,https://cloudflare-ipfs.com/ipfs/Qmd3W5DuhgHirLHGVixi6V76LhCkZUz6pnFt5AJBiyvHye/avatar/500.jpg
Hector,Reichel,Hector Reichel,Hector92,[email protected],Value 0,adf1cf72-40eb-4596-b809-b509ffdcd1b7,https://cloudflare-ipfs.com/ipfs/Qmd3W5DuhgHirLHGVixi6V76LhCkZUz6pnFt5AJBiyvHye/avatar/417.jpg
Lamar,Schmeler,Lamar Schmeler,Lamar76,[email protected],Value 1,a29fd784-c554-4301-b689-e678df358cc7,https://cloudflare-ipfs.com/ipfs/Qmd3W5DuhgHirLHGVixi6V76LhCkZUz6pnFt5AJBiyvHye/avatar/434.jpg
Pearl,Rosenbaum,Pearl Rosenbaum,Pearl.Rosenbaum54,[email protected],Value 2,3f77c9b3-820b-4afd-8dbc-fb72dc4f81d3,https://cloudflare-ipfs.com/ipfs/Qmd3W5DuhgHirLHGVixi6V76LhCkZUz6pnFt5AJBiyvHye/avatar/945.jpg

Now, I want to be able to sort the file based on a column value instead, example:
Sorted on the LastName column

FirstName,LastName,FullName,Username,Email,UniqueIndex,Id,ProfilePicture
Hector,Reichel,Hector Reichel,Hector92,[email protected],Value 0,adf1cf72-40eb-4596-b809-b509ffdcd1b7,https://cloudflare-ipfs.com/ipfs/Qmd3W5DuhgHirLHGVixi6V76LhCkZUz6pnFt5AJBiyvHye/avatar/417.jpg
Pearl,Rosenbaum,Pearl Rosenbaum,Pearl.Rosenbaum54,[email protected],Value 2,3f77c9b3-820b-4afd-8dbc-fb72dc4f81d3,https://cloudflare-ipfs.com/ipfs/Qmd3W5DuhgHirLHGVixi6V76LhCkZUz6pnFt5AJBiyvHye/avatar/945.jpg
Lamar,Schmeler,Lamar Schmeler,Lamar76,[email protected],Value 1,a29fd784-c554-4301-b689-e678df358cc7,https://cloudflare-ipfs.com/ipfs/Qmd3W5DuhgHirLHGVixi6V76LhCkZUz6pnFt5AJBiyvHye/avatar/434.jpg
Alexis,Schneider,Alexis Schneider,Alexis_Schneider40,[email protected],Value 4,df7b9351-a049-4fa3-a4ea-b753bc6df517,https://cloudflare-ipfs.com/ipfs/Qmd3W5DuhgHirLHGVixi6V76LhCkZUz6pnFt5AJBiyvHye/avatar/660.jpg
Guido,Wolf,Guido Wolf,Guido53,[email protected],Value 3,12618f37-e4eb-4c62-9a8f-104d77bea283,https://cloudflare-ipfs.com/ipfs/Qmd3W5DuhgHirLHGVixi6V76LhCkZUz6pnFt5AJBiyvHye/avatar/500.jpg

My ExternalMergeSorter already has support for custom sorting like this by passing in a custom IComparer<string>.

The only thing we need to do is to create our own implementation of the IComparer<string> and then enable it like this:

var unsortedFile = File.OpenRead("MyUnsortedFile.csv");
var targetFile = File.OpenRead("MySortedFile.csv");
var options = new ExternalMergeSorterOptions
{
    Sort = new ExternalMergeSortSortOptions
    {
        // This is our custom comparer
        Comparer = new CsvColumnSorter()
    }
};
var sorter = new ExternalMergeSorter(options);

await sorter.Sort(unsortedFile, targetFile);

Implementations

It's easy to implement the IComparer<string> interface.

public class CsvColumnSorter : IComparer<string>
{
    public int Compare(string x, string y)
    {
        // return -1 (or less) if x < y
        // return 1 (or more) if y > x
        // return 0 if x == y
    }
}

I can think of at least 3 different ways of implementing the comparer, two "bad" and one "awesome" way of doing this. Bad as in slow and "allocaty".
Let's start with the "bad" ones.
Note: I will skip most of the error handling in my implementations, escaping of chars and what not will not be taken into consideration since my CSV files are well formated. If you need functionality like this you will need to extend my implementations or use a library like CSVHelper or something similar.

String.Split

/// <summary>
/// Don't use this code.
/// </summary>
public class CsvColumnSorter_StringSplit : IComparer<string>
{
    private readonly int _column;
    private readonly char _separator;

    public CsvColumnSorter_StringSplit(int column, char separator = ',')
    {
        _column = column;
        _separator = separator;
    }

    public int Compare(string? x, string? y)
    {
        if (x == null && y != null)
        {
            return -1;
        }

        if (y == null && x != null)
        {
            return 1;
        }

        if (x == null || y == null)
        {
            return 0;
        }

        var xColumn = GetColumnValue(x);
        var yColumn = GetColumnValue(y);

        return Comparer<string>.Default.Compare(xColumn, yColumn);
    }

    private string GetColumnValue(string value)
    {
        var columns = value.Split(_separator);
        if (columns.Length < _column)
        {
            throw new ArgumentOutOfRangeException($"Found fewer columns than expected. Actual: {columns.Length}, Expected: {_column}");
        }

        return columns[_column - 1];
    }
}

Usage

var unsortedFile = File.OpenRead("MyUnsortedFile.csv");
var targetFile = File.OpenRead("MySortedFile.csv");
var options = new ExternalMergeSorterOptions
{
    Sort = new ExternalMergeSortSortOptions
    {
        // Sort on the LastName column (second column)
        Comparer = new CsvColumnSorter_StringSplit(2) 
    }
};
var sorter = new ExternalMergeSorter(options);

await sorter.Sort(unsortedFile, targetFile);

This code works but it is slow and inefficient. In the GetColumnValue method it splits the string using the separator, thus allocating an array = not good, we can do better.

Substring

/// <summary>
/// Don't use this code
/// </summary>
public class CsvColumnSorter_Substring : IComparer<string>
{
	private readonly int _column;
	private readonly char _separator;

	public CsvColumnSorter_Substring(int column, char separator = ',')
	{
		_column = column;
		_separator = separator;
	}

	public int Compare(string? x, string? y)
	{
		if (x == null && y != null)
		{
			return -1;
		}

		if (y == null && x != null)
		{
			return 1;
		}

		if (x == null || y == null)
		{
			return 0;
		}

		var xColumn = GetColumnValue(x);
		var yColumn = GetColumnValue(y);

		return string.Compare(xColumn, yColumn, StringComparison.OrdinalIgnoreCase);
	}

	private string GetColumnValue(string value)
	{
		var columnCounter = 1;
		var columnStartIndex = 0;
		for (var i = 0; i < value.Length; i++)
		{
			if (value[i].Equals(_separator))
			{
				columnCounter++;
				continue;
			}

			if (columnCounter != _column)
			{
				continue;
			}

			columnStartIndex = i;
			break;
		}

		var columnLength = 0;
		var slice = value[columnStartIndex..];
		for (var i = 0; i < slice.Length; i++)
		{
			if (slice[i] != _separator)
			{
				columnLength++;
			}
			else
			{
				break;
			}
		}

		return value.Substring(columnStartIndex, columnLength);
	}
}

Now we are using Substring instead of String.Split. This is much better in terms of allocations (no array), but we are still allocating a new string when doing the actual .Substring call. We can do better.

Span

public class CsvColumnSorter_Span : IComparer<string>
{
	private readonly int _column;
	private readonly char _separator;

	public CsvColumnSorter_Span(int column, char separator = ',')
	{
		_column = column;
		_separator = separator;
	}

	public int Compare(string? x, string? y)
	{
		if (x == null && y != null)
		{
			return -1;
		}

		if (y == null && x != null)
		{
			return 1;
		}

		if (x == null || y == null)
		{
			return 0;
		}

		var xColumn = GetColumnValue(x);
		var yColumn = GetColumnValue(y);

		return xColumn.CompareTo(yColumn, StringComparison.OrdinalIgnoreCase);
	}

	private ReadOnlySpan<char> GetColumnValue(string value)
	{
		var span = value.AsSpan();
		var columnCounter = 1;
		var columnStartIndex = 0;
		for (var i = 0; i < span.Length; i++)
		{
			if (span[i].Equals(_separator))
			{
				columnCounter++;
				continue;
			}

			if (columnCounter != _column)
			{
				continue;
			}

			columnStartIndex = i;
			break;
		}

		var columnLength = 0;
		var slice = span[columnStartIndex..];
		for (var i = 0; i < slice.Length; i++)
		{
			if (slice[i] != _separator)
			{
				columnLength++;
			}
			else
			{
				break;
			}
		}

		return span.Slice(columnStartIndex, columnLength);
	}
}

We are now turning our string into a Span. This is key to achieve the least amount of allocations. Instead of creating a new string instance, we are returning a Slice of the string. The slice is of type ReadOnlySpan<char> and it "points to" the section of the original string that we are interested in, column number 2.

Benchmarks

BenchmarkDotNet

BenchmarkDotNet=v0.13.0, OS=Windows 10.0.22000
AMD Ryzen 9 3900X, 1 CPU, 24 logical and 12 physical cores
.NET SDK=6.0.100-preview.6.21355.2
  [Host]   : .NET 6.0.0 (6.0.21.35212), X64 RyuJIT
  .NET 6.0 : .NET 6.0.0 (6.0.21.35212), X64 RyuJIT

Job=.NET 6.0  Runtime=.NET 6.0  InvocationCount=1
UnrollFactor=1

|      Method |     Mean |     Error |    StdDev | Ratio | RatioSD | Gen 0 | Gen 1 | Gen 2 | Allocated |
|------------ |---------:|----------:|----------:|------:|--------:|------:|------:|------:|----------:|
| StringSplit | 5.040 us | 0.0811 us | 0.1601 us |  1.00 |    0.00 |     - |     - |     - |   7,288 B |
|   Substring | 2.700 us | 0.0539 us | 0.1012 us |  0.54 |    0.02 |     - |     - |     - |   5,000 B |
|        Span | 2.220 us | 0.0717 us | 0.1902 us |  0.45 |    0.04 |     - |     - |     - |     208 B |

Here we can clearly see that the first implementation using String.Split performs the worst when it comes to speed and allocation (because of the array of strings).
The Substring runs a bit slower compared to the Span implementation but it also allocates much more. Span ftw! :)

"Real world scenario" - 10 million rows

String.Split

stringsplit-10-million-rows

Substring

substring-10-million-rows

Span

span-10-million-rows

Span performs twice as fast as the Substring implementation when dealing with 10 million rows. The String.Split approach is more than twice as slow as the Substring implementation.

The span implementation can be found on GitHub.