CODEWITHSUNDEEP
c#performancegenericsextension-methods
user2033412
user2033412

Reputation: 2109

Generic extension method is slower than non-generic extension method

I wrote an extension method for Lists that finds the index of a given value (or the next bigger value) in a sorted list.

public static int LinearSearch(this List<int> list, int startIndex, int value)
{
    for (int i = startIndex; i < list.Count; i++)
        if (list[i].CompareTo(value) >= 0)
            return i;

    return -1;
}

public static int LinearSearch<T>(this List<T> list, int startIndex, T value) where T : IComparable
{
    for (int i = startIndex; i < list.Count; i++)
        if (list[i].CompareTo(value) >= 0)
            return i;

    return -1;
}

As you see I wrote it once generic an once specifically for integers. If I comment out the int-specific version my code runs approximately much slower as if I prove both (given I work on int-lists).

How can I make the generic version as fast as the non-generic one? I don't want to copy and paste my code to get that performance for ints and longs.

The test runs 10,000,000 random queries on a sorted list of 1,000 integers.

LinearSearch took 9823 ms // generic
LinearSearch took 1553 ms // int-specific

Test-code for performance-measurements

class Program
{
    const int count = 1000;
    const int runs = 10_000_000;
    static List<int> list = new List<int>();
    static List<int> queries = new List<int>();

    static void Main(string[] args)
    {
        MeasureRuntime(CreateTestData);
        MeasureRuntime(LinearSearch);
    }

    private static void LinearSearch()
    {
        foreach (int query in queries)
            list.LinearSearch(query);
    }

    private static void CreateTestData()
    {
        Random random = new Random(0);
        list.Add(0);
        for (int i = 0; i < count; i++) list.Add(list[list.Count - 1] + random.Next(0, 10));
        for (int i = 0; i < runs; i++) queries.Add(random.Next(0, list.Count - 1));
    }

    private static void MeasureRuntime(Action action)
    {
        Stopwatch stopwatch = new Stopwatch();
        stopwatch.Start();
        action();
        stopwatch.Stop();
        Console.WriteLine($"{action.GetMethodInfo().Name} took {stopwatch.ElapsedMilliseconds} ms");
    }
}

Upvotes: 1

Views: 177

Answers (1)

user2033412
user2033412

Reputation: 2109

The problem was that I used the non-generic version IComparable instead of IComparable<T> which caused a performance-degregation. Now, using IComparable<T> the generic version runs as fast as the type-specific one.

public static int LinearSearch<T>(this List<T> list, int startIndex, T value) 
    where T : IComparable<T>
{
    for (int i = startIndex; i < list.Count; i++)
        if (list[i].CompareTo(value) >= 0)
            return i;

    return -1;
}

Upvotes: 4

Related Questions