C# collection performance: Are Hashset and Dictionary> the fastest collections for this purpose?

Question

I've parsed a grid of Excel data and built up an object model. There's 32 columns and 100,000 rows. I've been asked to check for rows with duplicate data and report them. For my implementation I'm doing the following:

1. Using Tasks I'm building an array of Tuple with row id and concatenated cell contents.
2. I loop through the resultant array and using a HashSet, I try to insert the concatenated value into the HashSet:
3. If HashSet.Add() passes, I create a new entry in my Dictionary> result set for it.
4. If HashSet.Add() fails I add that row id to the existing entry in my my Dictionary> result set

Step 1 takes 0.09s, while the rest is taking 822s to process :/ Can anyone spot where I can chop this time down with a more appropriate choice of collections or algorithms?

Code is below:

var results = new Dictionary<string, IList<int>>(numberOfRows);
var hashSet = new HashSet<string>();
var duplicateErrors = new List<string>();

for (var row = firstRow; row <= lastRow; row++)
{
    var row1 = row;
    taskArray[count++] =
    Task<Tuple<int, string>>.Factory.StartNew(() => GetCompleteRowData(row1, tableRawDataHolders));
}

foreach (var task in taskArray)
{
    if (hashSet.Add(task.Result.Item2))
    {
        results.Add(task.Result.Item2, new List<int>() { task.Result.Item1 });
    }
    else
    {
        results[task.Result.Item2].Add(task.Result.Item1);
    }
}

and

public Tuple<int, string> GetCompleteRowData(int row, IEnumerable<ITableRawDataHolder> tableRawDataHolders)
    {
        return new Tuple<int, string>(row, string.Join("",
            tableRawDataHolders.Where(c => c.Row == row).Select(c => c.Value).ToArray()));
    }

and

public class TableRawDataHolder : ITableRawDataHolder
{
    public int Row { get; }
    public int Column { get; }
    public string Value { get; }

    public TableRawDataHolder(int row, int column, string value)
    {
        Row = row;
        Column = column;
        Value = value;
    }
}

Answer 1

In this situation issue is not in Dictionary or Hashset performance.

Overhead comes from the way you read your data in GetCompleteRowData and work with tasks.

• It seems you enumerate full collection each time when you need to get next record converted.
• For every next record you create a task that itself adds some small overhead. Until task is ended it just waits when you use task.Result.
• Also it is not clear how fast your ITableRawDataHolder returns data.

To demonstrate pure hashset/dictionary performance I've created test where I iterate through array of already prepared Tuples. This code takes just 32ms on my machine (i7 quad core).

const Int32 numberOfRows = 200000;
var inputData = GetInputData(numberOfRows);
var results = new Dictionary<string, IList<int>>(numberOfRows);
var hashSet = new HashSet<string>();

var sw = Stopwatch.StartNew();
foreach (var dataItem in inputData)
{
    if (hashSet.Add(dataItem.Item2))
    {
        results.Add(dataItem.Item2, new List<int>() {dataItem.Item1});
    }
    else
    {
        results[dataItem.Item2].Add(dataItem.Item1);
    }
}
Console.WriteLine(sw.ElapsedMilliseconds);

Here is how I generate test data (it includes some actual duplicates)

private static List<Tuple<int, String>> GetInputData (int numberOfRows)
{
    var result = new List<Tuple<int, String>>(numberOfRows);
    var rnd = new Random();
    for (var i = 0; i < numberOfRows; i++)
    {
        // Once in 100 records we'll have not unique value
        if (result.Count > 0 && rnd.Next(100)%1 == 0)
        {
            result.Add(new Tuple<int, string>(i,  result[rnd.Next(result.Count)].Item2));
        }
        else
            result.Add(new Tuple<int, string>(i, Guid.NewGuid().ToString()));
    }
    return result;
}