CODEWITHSUNDEEP
c#icomparableicomparablet
Dieter Meemken
Dieter Meemken

Reputation: 1967

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

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?

Upvotes: 5

Views: 926

Answers (4)

Yuval Itzchakov
Yuval Itzchakov

Reputation: 149518

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.

Upvotes: 10

user743382
user743382

Reputation:

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.

Upvotes: 2

Avinash Jain
Avinash Jain

Reputation: 7606

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.

Upvotes: 2

Blindy
Blindy

Reputation: 67352

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

Upvotes: 3

Related Questions