I understand that we shouldn't duplicate code, but...

Lutoslaw

Uhm, well Microsoft certainly does not want to duplicate code. This is a dotPeek disassmbly the framework reference source code of a .NET 4.0 Tuple helper class

public static class Tuple
{
//...
internal static int CombineHashCodes(int h1, int h2)
{
return (h1 << 5) + h1 ^ h2;
}

internal static int CombineHashCodes(int h1, int h2, int h3)
{
  return Tuple.CombineHashCodes(Tuple.CombineHashCodes(h1, h2), h3);
}

internal static int CombineHashCodes(int h1, int h2, int h3, int h4)
{
  return Tuple.CombineHashCodes(Tuple.CombineHashCodes(h1, h2), Tuple.CombineHashCodes(h3, h4));
}

internal static int CombineHashCodes(int h1, int h2, int h3, int h4, int h5)
{
  return Tuple.CombineHashCodes(Tuple.CombineHashCodes(h1, h2, h3, h4), h5);
}

internal static int CombineHashCodes(int h1, int h2, int h3, int h4, int h5, int h6)
{
  return Tuple.CombineHashCodes(Tuple.CombineHashCodes(h1, h2, h3, h4), Tuple.CombineHashCodes(h5, h6));
}

internal static int CombineHashCodes(int h1, int h2, int h3, int h4, int h5, int h6, int h7)
{
  return Tuple.CombineHashCodes(Tuple.CombineHashCodes(h1, h2, h3, h4), Tuple.CombineHashCodes(h5, h6, h7));
}

internal static int CombineHashCodes(int h1, int h2, int h3, int h4, int h5, int h6, int h7, int h8)
{
  return Tuple.CombineHashCodes(Tuple.CombineHashCodes(h1, h2, h3, h4), Tuple.CombineHashCodes(h5, h6, h7, h8));
}

}

So... when you want to have a hash for a Tuple of 8 values, you get 7 function call overhead on a stack. Nice...

Greetings - Jacek

Brisingr Aerowing

Yikes! :wtf:

Attempting to load signature... A NullSignatureException was unhandled. Message: "No signature exists" All of the books in the world contain no more information than is broadcast as video in a single large American city in a single year. Not all bits have equal value. Carl Sagan

Lost User

They might get inlined.. I'm pretty sure the deepest one will be, at least. But yea, it's .. odd.

Lutoslaw

harold aptroot wrote:

They might get inlined.

7-level deep inlining algorithm in JIT? That would be impressive.

Greetings - Jacek

Robert Rohde

For the fun of it I tested your version against another version without the function calls. For this I just manually inlined all calls:

public static class Tuple2
{
internal static int CombineHashCodes(int h1, int h2, int h3, int h4, int h5, int h6, int h7, int h8)
{
var h12 = (h1 << 5) + h1 ^ h2;
var h34 = (h3 << 5) + h3 ^ h4;
var h1234 = (h12 << 5) + h12 ^ h34;
var h56 = (h5 << 5) + h5 ^ h6;
var h78 = (h7 << 5) + h7 ^ h8;
var h5678 = (h56 << 5) + h56 ^ h78;
return (h1234 << 5) + h1234 ^ h5678;
}
}

Just to be sure to optimize performance I even removed temp variables where possible (possible meaning "without having to calculate the same thing twice):

public static class Tuple3
{
internal static int CombineHashCodes(int h1, int h2, int h3, int h4, int h5, int h6, int h7, int h8)
{
var h12 = (h1 << 5) + h1 ^ h2;
var h34 = (h3 << 5) + h3 ^ h4;
var h1234 = (h12 << 5) + h12 ^ h34;
var h56 = (h5 << 5) + h5 ^ h6;
return (h1234 << 5) + h1234 ^ ((h56 << 5) + h56 ^ ((h7 << 5) + h7 ^ h8));
}
}

I tested your .NET disassembly code against this and the results show nearly no performance difference for my first alternative and only a minor (10-15% slower!!!) difference for the second one (can anybody tell me why this one is slower?!?). As the .NET code is clearly better readable and maintainable I would say they did everything correct. Here my test code:

static void Main(string[] args)
{
var sw1 = new Stopwatch();
var sw2 = new Stopwatch();
var sw3 = new Stopwatch();
var res = 0;

        for (int j = 0; j < 3; j++)
        {
            Console.WriteLine("{0}. run", j + 1);

            sw1.Reset();
            res = 0;
            sw1.Start();
            for (int i = 0; i < 10000000; i++)
                res += Tuple1.CombineHashCodes(i, i, i, i, i, i, i, i);
            sw1.Stop();
            Console.WriteLine("Test 1: {0}  Time: {1}", res, sw1.Elapsed);

            sw2.Reset();
            res = 0;
            sw2.Start();
            for (int i = 0; i < 10000000; i++)
                res += Tuple2.CombineHashCodes(i, i, i, i, i, i, i, i);
            sw2.St

Lutoslaw

Did you try to wrap a whole thing in a unchecked { } block? You could try to make JIT compile your methods before testing:

int i = 1;
Tuple1.CombineHashCodes(i, i, i, i, i, i, i, i);
sw1.Reset();
res = 0;
sw1.Start();
for (i = 0; i < 10000000; i++)
res += Tuple1.CombineHashCodes(i, i, i, i, i, i, i, i);
sw1.Stop();
Console.WriteLine("Test 1: {0} Time: {1}", res, sw1.Elapsed);

internal static int CombineHashCodes(int h1, int h2, int h3, int h4, int h5, int h6, int h7, int h8)
{

unchecked{
var h12 = (h1 << 5) + h1 ^ h2;
var h34 = (h3 << 5) + h3 ^ h4;
var h1234 = (h12 << 5) + h12 ^ h34;
var h56 = (h5 << 5) + h5 ^ h6;
var ret = (h1234 << 5) + h1234 ^ ((h56 << 5) + h56 ^ ((h7 << 5) + h7 ^ h8));

}return ret;
}

Also, I would change the testing code:

sw1.start
for (int j = 0; j < 1000; j++)
{

// test method 1
}
sw1.stop
sw2...
for (int j = 0; j < 1000; j++)
{

// test method 2
}
sw3...
for (int j = 0; j < 1000; j++)
{

// test method 3
}

Greetings - Jacek

Robert Rohde

1. The arithmetic overflow check is completely disabled in my solution (which ist the default setting; at least for VS 2010 console apps). Otherwise my whole test wouldn't work because I add so many large numbers that an OverflowException would occur. 2. Regarding the JIT: Thats why I made 3 (the for j loop) seperately stopped complete test runs. I always ignore the first result.

Johann Gerell

Try swapping the order of the tests in as many ways as there are permutations, since the JITting cost is mostly payed at the first invocations.

Time you enjoy wasting is not wasted time - Bertrand Russel

Lutoslaw

OK. I have also posted a suggestion about increasing a number of tests and averaging results. Did you try it?

Greetings - Jacek

ClockMeister

I suspect your disassembly utility may not understand the "params" form in a C# call. I seriously doubt that Microsoft would write it the way your utility is showing it. It's more likely coded like this: internal static int CombineHashCodes(params int[] h) int returnHash = 0; { for (int i=0; i<h.length; ++i) { returnHash = (returnHash << 5) + returnHash ^ h[i]; } } return returnHash; } // ... or something like that! Although I would suspect that combining 8 hash codes is going to overflow a 32-bit int ... but you get my point! -Max :-)

Bruce Patin

When you declare your own temporary variables, you save the JIT compiler or runtime the time needed to generate them itself where necessary. That might explain the speed difference.

alcexhim

Is the "params" keyword not just "syntactic sugar" for passing an arbitrary number of parameters into what is really just an array? When you write something like:

void f(params int[] values)
{
// do something with values
}
void g()
{
f(3, 4, 5, 6);
f(new int[] { 3, 4, 5, 6 });
}

The two calls to "f" do exactly the same thing, the first just looks neater. I'd imagine multiple functions with different numbers of "value" arguments wouldn't be generated by the compiler, because (correct me if I'm wrong) it's more efficient to pass an array of values than to pass the values on the stack individually. Even if the disassembler didn't understand the presence of the "params" keyword, the function signature would still have a single "int[]" parameter, wouldn't it? since the compiler didn't actually go through and generate separate functions for those parameters.

ClockMeister

alcexhim wrote:

Even if the disassembler didn't understand the presence of the "params" keyword, the function signature would still have a single "int[]" parameter, wouldn't it? since the compiler didn't actually go through and generate separate functions for those parameters.

That's probably true, of course. Perhaps Microsoft did code it with eight different entry points like that. If I was the manager over the person that did that, though, said person would be on the unemployment line or in a remedial C# class! What if I have nine arguments to pass? SOL I guess! The params argument is, yes I'm sure, syntactical "sugar" as you state but nevertheless it's still preferable than generating eight separate signatures, wouldn't you agree? It also makes life a little easier coding the call to the function. You might actually want to pass multiple arguments (in differing numbers of arguments) in different sections of code and not be constrained to create the array from the calling code. This would be particularly true if your code is passing constants in the formal parameter list. Either way, though, it's just another convenient little shortcut provided by the language. -cb

TRK3

If that is implemented in F# originally (or was compiled by a compiler that supports tail recursion), then there is no additional funciton overhead. In fact, if the code is reordered correctly, it's faster than a loop. The guy who wrote it probably knew a lot more about what he was doing than it appears at first glance.

Richard Deeming

Nope - the original code from the framework reference source is:

// From System.Web.Util.HashCodeCombiner
internal static int CombineHashCodes(int h1, int h2) {
return (((h1 << 5) + h1) ^ h2);
}

internal static int CombineHashCodes(int h1, int h2, int h3) {
return CombineHashCodes(CombineHashCodes(h1, h2), h3);
}

internal static int CombineHashCodes(int h1, int h2, int h3, int h4) {
return CombineHashCodes(CombineHashCodes(h1, h2), CombineHashCodes(h3, h4));
}

internal static int CombineHashCodes(int h1, int h2, int h3, int h4, int h5) {
return CombineHashCodes(CombineHashCodes(h1, h2, h3, h4), h5);
}

internal static int CombineHashCodes(int h1, int h2, int h3, int h4, int h5, int h6) {
return CombineHashCodes(CombineHashCodes(h1, h2, h3, h4), CombineHashCodes(h5, h6));
}

internal static int CombineHashCodes(int h1, int h2, int h3, int h4, int h5, int h6, int h7) {
return CombineHashCodes(CombineHashCodes(h1, h2, h3, h4), CombineHashCodes(h5, h6, h7));
}

internal static int CombineHashCodes(int h1, int h2, int h3, int h4, int h5, int h6, int h7, int h8) {
return CombineHashCodes(CombineHashCodes(h1, h2, h3, h4), CombineHashCodes(h5, h6, h7, h8));
}

The original code from System.Web.Util.HashCodeCombiner is:

internal static int CombineHashCodes(int h1, int h2) {
return ((h1 << 5) + h1) ^ h2;
}

internal static int CombineHashCodes(int h1, int h2, int h3) {
return CombineHashCodes(CombineHashCodes(h1, h2), h3);
}

internal static int CombineHashCodes(int h1, int h2, int h3, int h4) {
return CombineHashCodes(CombineHashCodes(h1, h2), CombineHashCodes(h3, h4));
}

internal static int CombineHashCodes(int h1, int h2, int h3, int h4, int h5) {
return CombineHashCodes(CombineHashCodes(h1, h2, h3, h4), h5);
}

Good job they put all those helpful comments in to explain their choice! ;P

"These people looked deep within my soul and assigned me a number based on the order in which I joined." - Homer

ClockMeister

Sheesh! So much for code elegance!

Robert Rohde

I really don't see why this should make a difference here, but to avoid a big discussion on how the JIT works I rewrote my tests. First I make one test run just for the JIT. Then I make 1000 test runs for each test case and in each test run 10.000.000 calls to CombineHashCodes are done. Here the results:

Test 1: -1607204864 Time Avg: 00:00:00.0281418 (100,00%)
Test 2: -1607204864 Time Avg: 00:00:00.0281436 (100,01%)
Test 3: -1607204864 Time Avg: 00:00:00.0312717 (111,12%)

I feel the JIT optimizer does inline those nested calls exactly as I did. Here the complete code:

class Program
{
static void Main(string[] args)
{
var sw1 = new Stopwatch();
var sw2 = new Stopwatch();
var sw3 = new Stopwatch();
var res1 = 0;
var res2 = 0;
var res3 = 0;

    res1 = Test1(sw1, res1);
    res2 = Test2(sw2, res2);
    res3 = Test3(sw3, res3);
    //first run is for the JIT -> Reset stopwatches
    sw1.Reset();
    sw2.Reset();
    sw3.Reset();

    int noOfRuns = 1000;
    for (int j = 0; j < noOfRuns; j++)
    {
        res1 = Test1(sw1, res1);
        res2 = Test2(sw2, res2);
        res3 = Test3(sw3, res3);
    }

    var avg1 = sw1.Elapsed.Ticks / noOfRuns;
    var avg2 = sw2.Elapsed.Ticks / noOfRuns;
    var avg3 = sw3.Elapsed.Ticks / noOfRuns;

    Console.WriteLine("Test 1: {0}  Time Avg: {1} ({2:f2}%)", res1, new TimeSpan(avg1), 100.0);
    Console.WriteLine("Test 2: {0}  Time Avg: {1} ({2:f2}%)", res2, new TimeSpan(avg2), avg2 \* 100.0 / avg1);
    Console.WriteLine("Test 3: {0}  Time Avg: {1} ({2:f2}%)", res3, new TimeSpan(avg3), avg3 \* 100.0 / avg1);

    Console.ReadLine();
}

private static int Test3(Stopwatch sw3, int res3)
{
    res3 = 0;
    sw3.Start();
    for (int i = 0; i < 10000000; i++)
        res3 += Tuple3.CombineHashCodes(i, i, i, i, i, i, i, i);
    sw3.Stop();
    return res3;
}

private static int Test2(Stopwatch sw2, int res2)
{
    res2 = 0;
    sw2.Start();
    for (int i = 0; i < 10000000; i++)
        res2 += Tuple2.CombineHashCodes(i, i, i, i, i, i, i, i);
    sw2.Stop();
    return res2;
}

private static int Test1(Stopwatch sw1, int res1)
{
    res1 = 0;
    sw1.Start();
    for (int i = 0; i < 10000000; i++)

Robert Rohde

Quote:

If I was the manager over the person that did that, though, said person would be on the unemployment line or in a remedial C# class!

Don't be so fast with such statements. Have you tested your approach? I made a quick test and the params keyword introduces a really big performance penalty (more than factor 5, probably even 10). The reason is probably that for each call an array must be instantiated. If I was your manager, and you would implement it that way although it could be done more than 5 times faster, than you would probably be on the unemployment line ;). Also note that this functions are internal functions of the generic Tuple classes. Tuple has at most 8 generic type parameters (and as a consequence 8 properties where hash codes might get combined), so combining 9 hash codes is really not an issue here.

ClockMeister

Robert Rohde wrote:

Don't be so fast with such statements. Have you tested your approach? I made a quick test and the params keyword introduces a really big performance penalty (more than factor 5, probably even 10). The reason is probably that for each call an array must be instantiated.

LOL ... I hadn't thought about that! Good point. No ... I hadn't gone through a rigorous test of the code performance. If the performance loss in my approach is that bad then, yes, it's better to have the eight entry points. I stand corrected. Too bad, though, that a convenient construct like that isn't optimized for performance because it is an obvious case where you would want to use something like that. I'm sure it could be optimized. Doesn't seem like it would be hard to get it to assemble down to a simple stack pointer movement to make room for the params argument. Whatever ... ;-) -CB :-)