inlining compareTo(int a,intb) { return a-b; }
Hello,
I am writing a class that implements the IDictionary<TKey,TValue> interface and it extensivly needs to compare two "TKey" types. (using Microsoft Visual C# 2008 Beta 2)
The problem is that the resulting assembly code in the common case, in which TKey is an integer is far from being optimized, and it is definitly not inlined (checked the release code after disabling the Suspend IT and Just My Code). I tried defining TKey as implements Comparable, and tried accepting an IComparator and tried with extension methods and with overriding an abstract compare method, and tried overriding a virtual function. The compare method is never inlined, there is always the method call instead of subtructing b from a. The best implementation was with abstract/virtual in which there was no extra dereferencing of a pointer and no stack push, just the method call overhead.
Is this becuase inlining has some problems with the unknown TKey type ?
Can't C# accept a "default" implementation for compare<TKey> and an "optimized-to-be-inlined-at-runtime" version for compare<int> ?
something like:
bool compare<int>(int a, int b) {return a-b;}
bool compare<TKey>(TKey a,TKey b) { return a.CompareTo(b);}
bool compare<TKey>(TKey a,TKey b,TComparator<TKey> c) { return c.Compare(a,b);}
or instead:
class MyDictionary<TKey,TValue>
{
bool Contains(Tkey k) { ... compare(k,node_k)... }
bool compare(TKey a ,TKey b) { return a.compareTo(b):}
}
class MyDictionaryInt<TValue> : MyDictionary<int,TValue>
{
override bool compare(int a ,int b) {return a-b; } //inlined not virtual
}
Is it necessary to "copy paste" the "Contains" implementation into MyDictionaryInt and then replace manually TKey with int - in order to get the comparison inlined ?
Regards,
Itai Frenkel
Hello Peter,
Below is a sample code that demonstrates the performance decrease.
The program asks the user for two numbers, compares them and displays whether a==b , a>b or a<b.
It calls two methods to comapre a and b: MyDictionaryInt.Test1() and MyDictionaryInt.Test2().
Test1() is the method I am using in my code today.
Test2() is the method that I would need to use if I want better performance (It's actually a copy of Test1(), but instead of calling the virtual method Compare(a,b) it calls Compare2(a,b) which is not virtual and is inlined ( replace the call to Compare2(a,b) with (a-b) to validate this claim).
Below is the output. The result varies, but Test1 is always 3 to 4 times slower than Test2.
So the question is - how to compile Test1() so it will match the performance of Test2().
a=2
b=1
a>b
Test1 Ticks=375
Test2 Ticks=94
Press any key to continue . . .
namespace TestIntCompare
{
public class MyDictionary<TKey,TValue>
where TKey : System.IComparable
{
virtual
protected
int
Compare(TKey x, TKey y){
return
x.CompareTo(y);}
public
int
Test1(TKey a,TKey b){
int
c = 0;const
int
count = 10000;for
(int
i = 0; i < count; i++){
for
(int
j = 0; j < count; j++){
c +=
this
.Compare(a, b);}
}
return
c;}
}
//MyDictionary
sealed
public
class
MyDictionaryInt<TValue> : MyDictionary<int
,TValue>{
public
int
Test2(int
a,int
b){
int
c = 0;const
int
count = 10000;for
(int
i = 0; i < count; i++){
for
(int
j = 0; j < count; j++){
c += Compare2(a,b);
//c += a - b;
}
}
return c;
}
private int Compare2(int x, int y)
{
return x - y;
}
override protected int Compare(int x, int y)
{
return x - y;
}
}
class Program
{
static
void
Main(string
[] args){
MyDictionaryInt<string
> aDictionary = new
MyDictionaryInt<string
>();System.
Console.Write("a="
);int
a = System.Convert.ToInt32(System.Console.ReadLine());System.
Console.Write("b="
);int
b = System.Convert.ToInt32(System.Console.ReadLine());int
c;int
tick1 = System.Environment.TickCount;c = aDictionary.Test1(a,b);
int
tick2 = System.Environment.TickCount;c = aDictionary.Test2(a,b);
int
tick3 = System.Environment.TickCount;if
(c == 0){
System.
Console.WriteLine("a==b"
);}
else
if
(c < 0){
System.
Console.WriteLine("a<b"
);}
else
{
System.
Console.WriteLine("a>b"
);}
System.
Console.WriteLine("Test1 Ticks="
+ (tick2 - tick1));System.
Console.WriteLine("Test2 Ticks="
+ (tick3 - tick2));}
}
}
Hello Greg,
It is my understanding that a generic class is not JITed unless TKey and TValue have concrete values or objects.
I've made a semantic change in the code, and replaced the virtual keyword with abstract.
When the JIT "compiles" MyDictionary<TKey,TValue>.Test1(TKey,TKey) into MyDictionaryInt<string>.Test1(int,int)
it implements the method within a sealed class. I am not looking for runtime polymorphism/overloading, but rather just-in-time compiling polymorphism/specialization. Theoretically speaking, it seams reasonable to inline the call to Compare(a,b) in the generic Test1 method, as it is being specialized in the context of IntMyDictionary.
Regards,
Itai
namespace TestIntCompare
{
public abstract class MyDictionary<TKey,TValue>
where TKey : System.IComparable
{
abstract
protected
int
Compare(TKey x, TKey y);public
int
Test1(TKey a,TKey b){
int
c = 0;const
int
count = 10000;for
(int
i = 0; i < count; i++){
for
(int
j = 0; j < count; j++){
c +=
this
.Compare(a, b);}
}
return
c;}
}
//MyDictionary
sealed
public
class
MyDictionaryInt<TValue> : MyDictionary<int
,TValue>{
public
int
Test2(int
a,int
b){
int
c = 0;const
int
count = 10000;for
(int
i = 0; i < count; i++){
for
(int
j = 0; j < count; j++){
c += Compare2(a,b);
//c += a - b;
}
}
return
c;}
private
int
Compare2(int
x, int
y){
return
x - y;}
override
protected
int
Compare(int
x, int
y){
return
x - y;}
}
class
Program {
static
void
Main(string
[] args){
MyDictionaryInt<string
> aDictionary = new
MyDictionaryInt<string
>();System.
Console.Write("a="
);int
a = System.Convert.ToInt32(System.Console.ReadLine());System.
Console.Write("b="
);int
b = System.Convert.ToInt32(System.Console.ReadLine());int
c;int
tick1 = System.Environment.TickCount;c = aDictionary.Test1(a,b);
int
tick2 = System.Environment.TickCount;c = aDictionary.Test2(a,b);
int
tick3 = System.Environment.TickCount;if
(c == 0){
System.
Console.WriteLine("a==b"
);}
else
if
(c < 0){
System.
Console.WriteLine("a<b"
);}
else
{
System.
Console.WriteLine("a>b"
);}
System.
Console.WriteLine("Test1 Ticks="
+ (tick2 - tick1));System.
Console.WriteLine("Test2 Ticks="
+ (tick3 - tick2));}
}
}
What Peter said.
Ultimately, what it sounds like you're looking for is an __inline macro for .NET, but it doesn't exist. The opposite does exist with [MethodImpl(MethodImplOptions.NoInlining)] because inlining could arguably affect the function of your application (one could look at GC.KeepAlive as an example of a method that needs this attribute, as otherwise it would be optimised away) whereas lack of inlining can't.
I'm not making any case as to whether the ability to indicate you'd like a function to be inlined or not is a good or bad thing, I'm just saying the way it is.
You could try the x64 JIT for interests sake; it has more optimisations than the x86 one.
