Difference between IComparable and IComparable<T> in this search method

Question

I know that there is a big difference between IComparable and IComparable<T> in general, see this, but in this search method it will not make any difference, or will it?

public static int Search<T>(List<T> a, T target) where T : IComparable
{
    for (int i = 0; i < a.Count; i++)
    {
        if (target.CompareTo(a[i]) == 0)
            return i;
    }
    return -1;
}

compared to:

public static int Search<T>(List<T> a, T target) where T : IComparable<T>
{
    ...
}

Both will work and give the same result, or not?

Trinette

Answer 1

Both will work and give the same result, or not?

Let's look at what the compiler emits for both search methods:

Search:
IL_0000:  ldc.i4.0    
IL_0001:  stloc.0     // i
IL_0002:  br.s        IL_0025
IL_0004:  ldarga.s    01 
IL_0006:  ldarg.0     
IL_0007:  ldloc.0     // i
IL_0008:  callvirt    06 00 00 0A 
IL_000D:  box         03 00 00 1B <---- Notice this!
IL_0012:  constrained. 03 00 00 1B 
IL_0018:  callvirt    System.IComparable.CompareTo
IL_001D:  brtrue.s    IL_0021
IL_001F:  ldloc.0     // i
IL_0020:  ret         
IL_0021:  ldloc.0     // i
IL_0022:  ldc.i4.1    
IL_0023:  add         
IL_0024:  stloc.0     // i
IL_0025:  ldloc.0     // i
IL_0026:  ldarg.0     
IL_0027:  callvirt    08 00 00 0A 
IL_002C:  blt.s       IL_0004
IL_002E:  ldc.i4.m1   
IL_002F:  ret         

SearchGeneric:
IL_0000:  ldc.i4.0    
IL_0001:  stloc.0     // i
IL_0002:  br.s        IL_0020
IL_0004:  ldarga.s    01 
IL_0006:  ldarg.0     
IL_0007:  ldloc.0     // i
IL_0008:  callvirt    06 00 00 0A 
IL_000D:  constrained. 03 00 00 1B 
IL_0013:  callvirt    09 00 00 0A 
IL_0018:  brtrue.s    IL_001C
IL_001A:  ldloc.0     // i
IL_001B:  ret         
IL_001C:  ldloc.0     // i
IL_001D:  ldc.i4.1    
IL_001E:  add         
IL_001F:  stloc.0     // i
IL_0020:  ldloc.0     // i
IL_0021:  ldarg.0     
IL_0022:  callvirt    08 00 00 0A 
IL_0027:  blt.s       IL_0004
IL_0029:  ldc.i4.m1   
IL_002A:  ret    

If you look carefully, you'll see that the main difference is the fact that each call in Search, prior to invoking CompareTo has to box the value (this is notable with the box operation), as the non-generic version accepts a object type.

Let's try to analyze the performance differences between the two using a value type. I'm going to use BenchmarkDotNet, which is a little (and truly awesome) benchmarking framework, which takes care of JITing, CPU warmup, etc.

Test:

[BenchmarkTask(platform: BenchmarkPlatform.X86)]
[BenchmarkTask(platform: BenchmarkPlatform.X64)]
public class Test
{
    private readonly List<int> list = Enumerable.Range(0, 1000000).ToList();

    [Benchmark]
    public void TestSearch()
    {
        Search(list, 999999);
    }

    [Benchmark]
    public void TestSearchGeneric()
    {
        SearchGeneric(list, 999999);
    }

    public static int Search<T>(List<T> a, T target) where T : IComparable
    {
        for (int i = 0; i < a.Count; i++)
        {
            if (target.CompareTo(a[i]) == 0)
                return i;
        }
        return -1;
    }
    public static int SearchGeneric<T>(List<T> a, T target) where T : IComparable<T>
    {
        for (int i = 0; i < a.Count; i++)
        {
            if (target.CompareTo(a[i]) == 0)
                return i;
        }
        return -1;
    }
}

Results:

***** Competition: Finish  *****

BenchmarkDotNet=v0.7.8.0
OS=Microsoft Windows NT 6.1.7601 Service Pack 1
Processor=Intel(R) Core(TM) i7-4600U CPU @ 2.10GHz, ProcessorCount=4
HostCLR=MS.NET 4.0.30319.42000, Arch=32-bit
Type=Test  Mode=Throughput  Jit=HostJit  .NET=HostFramework


            Method | Platform |    AvrTime |    StdDev |   op/s |
------------------ |--------- |----------- |---------- |------- |
        TestSearch |      X64 | 35.8065 ms | 3.3439 ms |  27.93 |
 TestSearchGeneric |      X64 |  4.6427 ms | 0.3075 ms | 215.40 |
        TestSearch |      X86 | 26.4876 ms | 1.4776 ms |  37.75 |
 TestSearchGeneric |      X86 |  6.6500 ms | 0.1664 ms | 150.38 |

***** Competition: End *****

See that the non-generic method incurring the boxing operation is more than 4x slower on x86 and more than 8x slower on x64. This can have a an impact on your applications performance.

I would generally not use the non-generic IComparable, which is mainly around for backwards compatibility to the days prior to generics. Note that another not-less important factor is the type safety which you gain with generics.

Smitt

Answer 2

It's a huge difference, the first method is boxing value types for no reason.

Ventage

@DieterMeemken, only for value types – Carrolcarroll

@DieterMeemken, not just for value types, using IEnumerable will also result in casts to get the right objects out. That's another performance penalty. – Ventage

Answer 3

The first one (i.e. IComparable) implement not the generic type and is not related to the type used for parent class, but the second one (i.e. IComparable<T>) is Type safe where you can use only the type that you have specified for parent class.

Lutenist

But the comparing will work with both the same way, or not? – Trinette

Answer 4

The biggest difference should be obvious: the version where T : IComparable can be used with types that implement IComparable. The version where T : IComparable<T> can be used with types that implement IComparable<T>. Commonly used types that implement IComparable but not IComparable<T> are the various System.Tuple<...> generic types, as well as all enumeration types.

Machmeter

So there is only a difference in the possible types i can use for T? – Trinette

Functionally, yes. There's no rule saying that a type that implements IComparable also has to implement IComparable<T>, or vice versa. Performance-wise, there can also be a difference, as pointed out by Blindy, but that should be a secondary concern: if the IComparable<T> version would be faster, except you can't call it, it's not of much use to you. – Machmeter