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?
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.