Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

C# code

static int KEY_NOT_FOUND = -1;
private void Form1_Load(object sender, EventArgs e)
{
    int[] A = createArray(1, 100000);

    Stopwatch sw1 = performCalcs(1, A);
    Stopwatch sw2 = performCalcs(2, A);

    TimeSpan lag = TimeSpan.FromTicks(sw1.Elapsed.Ticks - sw2.Elapsed.Ticks);
}

public static int[] createArray(int minVal, int maxVal)
{
    if (minVal >= maxVal) return null; 

    int[] A = new int[maxVal - minVal + 1];

    int i = -1;
    for (int curVal = minVal; curVal <= maxVal; curVal++)
    {
        i = i + 1;
        A[i] = curVal;
    }

    return A;
}

private Stopwatch performCalcs(int curFunction, int[] A)
{
    Stopwatch sw = new Stopwatch();
    int max = 10000;
    int count = 0;

    sw.Start();

    while (count < max)
    {
        count = count + 1;
        if (curFunction == 1) binary_search_improved2(A, 222, 0, A.Length - 1);
        else binary_search(A, 222, 0, A.Length - 1);
    }

    sw.Stop();

    return sw;
}

private static int binary_search_improved2(int[] A, int key, int imin, int imax)
{
    if (imax < imin) return KEY_NOT_FOUND;
    int imid;
    while (true)
    {
        imid = imin + ((imax - imin) >> 1);
        if (imin == imax || A[imid] == key) return imid;
        if (A[imid] < key) imin = imid;
        else imax = imid;
    }
}

private static int binary_search(int[] A, int key, int imin, int imax)
{
    if (imax < imin)
        return KEY_NOT_FOUND;
    else
    {
        int imid = midpoint(imin, imax);

        if (A[imid] > key)
            return binary_search(A, key, imin, imid - 1);
        else if (A[imid] < key)
            return binary_search(A, key, imid + 1, imax);
        else
            return imid;
    }
}

private static int midpoint(int imin, int imax)
{
    return imin + ((imax - imin) / 2);
}

VB.NET code

 Shared KEY_NOT_FOUND As Integer = -1
 Private Sub Form1_Load(sender As System.Object, e As System.EventArgs) Handles MyBase.Load

     Dim A() As Integer = createArray(1, 100000)

     Dim sw1 As Stopwatch = performCalcs(1, A)
     Dim sw2 As Stopwatch = performCalcs(2, A)

     Dim lag As TimeSpan = TimeSpan.FromTicks(sw1.Elapsed.Ticks - sw2.Elapsed.Ticks)

 End Sub

 Public Shared Function createArray(minVal As Integer, maxVal As Integer) As Integer()

     If (minVal >= maxVal) Then Return Nothing

     Dim A(maxVal - minVal) As Integer
     Dim i As Integer = -1

     For curVal As Integer = minVal To maxVal
         i = i + 1
         A(i) = curVal
     Next

     Return A

 End Function

 Private Function performCalcs(curFunction As Integer, A() As Integer) As Stopwatch

     Dim sw As Stopwatch = New Stopwatch
     Dim max As Integer = 10000
     Dim count As Integer = 0

     sw.Start()

     While (count < max)

         count = count + 1
         If curFunction = 1 Then
             binary_search_improved2(A, 222, 0, A.Length - 1)
         Else
             binary_search(A, 222, 0, A.Length - 1)
         End If

     End While

     sw.Stop()

     Return sw

 End Function

 Private Shared Function binary_search_improved2(A() As Integer, key As Integer, imin As Integer, imax As Integer) As Intege

     If imax < imin Then Return KEY_NOT_FOUND

     Dim imid As Integer
     While True

         imid = imin + ((imax - imin) >> 1)
         If imin = imax OrElse A(imid) = key Then Return imid
         If A(imid) < key Then
             imin = imid
         Else
             imax = imid
         End If

     End While

     Return imid 'Never reached; just to avoid the warning

 End Function

 Private Shared Function binary_search(A() As Integer, key As Integer, imin As Integer, imax As Integer) As Integer

     If imax < imin Then
         Return KEY_NOT_FOUND
     Else
         Dim imid As Integer = midpoint(imin, imax)

         If A(imid) > key Then
             Return binary_search(A, key, imin, imid - 1)
         ElseIf A(imid) < key Then
             Return binary_search(A, key, imid + 1, imax)
         Else
             Return imid
         End If

     End If

 End Function

 Private Shared Function midpoint(imin As Integer, imax As Integer) As Integer

     Return imin + Convert.ToInt32(Math.Floor((imax - imin) / 2))
    'Return imin + Math.Floor((imax - imin) / 2)

    'The one being used is the "Strict On alternative", as suggested by ChrisW
    'In "one-run" the performance is undoubtedly better; but when testing for multiple runs,
    'it is still unclear which version is 100% better: the first option seems to get more instable

     'Also note that for the given value 222 (within a 1-100000 consecutive array), you can also use:
     'Return imin + (imax - imin) / 2

    'This is faster but does not work always as the C# version (and the lag continues being there anyway)

 End Function

If you run both pieces of code, you would see that the C# lag is always smaller (and that the difference is pretty notable). Also you would see that the first functions (optimised version of binary search relying on a loop) are always more or less equivalent in both languages and that all the differences are provoked by the second ones (standard, recursive binary search algorithm from Wikipedia).

The question is: why is there a so big difference between both languages in the recursive version?

UPDATE

If the reliance on midpoint is replaced with the corresponding bitwise operation (imin + ((imax - imin) >> 1)), the differences between both codes seem to disappear and thus, the true responsible seems to be the division. This fact can be confirmed by replacing the recursive function with a loop performing just divisions: the VB.NET version would always be slower (?!). Note that this update has resulted from a pretty quick, small test; the exact origin of the performance differences between both codes is still not clear.

SOLUTION

Both answers have delivered the right solution (well... pointed to the right direction; the final solution came from a comment to this post), although they also include further (not always too relevant and even completely wrong) information, which might avoid future readers to get a clear enough picture. Additionally, this question comes from a different "testing framework" and I want to comment the (different) conclusions from it. That's why I am not writing my answer: I do accept as the right answer one of the posted ones (as far as both deliver the right solution, I marked the one which IMO contains a higher amount of relevant information); this is just a summary for future readers.

  • The notable performance difference between both posted codes would disappear by removing the division in midpoint (e.g., by replacing it with the aforementioned bitwise alternative). The reason for this, as explained in the answers below, is that when using the / operator with integers in VB.NET, an internal, automatic conversion to double is performed every time. As said above, you might avoid this by relying on the shift operator, for example. Update: as rightly pointed out by ChrisW in a comment to this question, the right VB.NET operator for integer division is \ (honestly, I rarely use it; equivalent to the Convert.ToInt32 part explained below, when dealing with Option Strict Off; this kind of situations prove that what might seem evident is really not... -> I will start using both alternatives every time from now on). After performing more proper tests, I have confirmed that this operator delivers exactly the same performance than its C# version, also that the generated ILs are identical. After some preliminary tests yesterday, I observed a pretty bad performance with this operator; but this was due to have performed quick, simple tests, not too adequate to accurately assess what is really happening under so highly-variable conditions (also I wasn't expecting this operator, which I do never use, to be so influential). Thus, the right answer to the question is: the relevant performance lag between the original codes was provoked by using the wrong integer division operator. The right conversion of the C# code return imin + (imax - imin) / 2; to VB.NET is: Return imin + (imax - imin) \ 2. Any other option would provoke automatic, intermediate conversions from/to double, what under these conditions ("tick level") would be enough to output notable differences between both languages.
  • This code comes from a different testing framework, where it has also been observed a performance lag while dealing with recursion/loops (this is the reason for the original title of this question). On the other hand, the posted codes cannot replicate this situation and, in the aforementioned external code, the effects from this issue are not too important (and the code is big and its behaviour difficult to be emulated with a simplistic code like the one here). Thus, I have changed the title of this post and focused the problem here on the division. In any case, I did have observed this problem at various points during the development and I am reasonably sure that there might also be an independent (i.e., not related with the division part) recursion/loops "miscoordination VB.NET-C#". I will let this here as a warning for anyone interested in investigating this issue further.
  • Just to make everything clear regarding some of the posted suggestions:
    • Both versions (VB.NET & C#) are identical with the sole exception of the additional in-built calls in VB.NET inside midpoint (e.g., Convert.ToInt32 and Math.Floor); there are various comments in this code explaining the reasons for these calls (and confirming that Math.Floor (or equivalent) is required to deliver the same results than C# every time). In any case, note that all the testing has been done without these calls (Return imin + (imax - imin) / 2, which does deliver the same results than C#, under this specific input conditions: array of consecutive integers upto 100000 and 222 as target value); on the other hand, this is valid just to test the exact conditions and get a better insight into the problem, but it is NOT the valid conversion from the C# code, that's why, I have preferred to let the Math.Floor as the only right/uncommented line.
    • Also it is worthy to know that the only Option Strict On effect (well... as explained in one of the answers below, Option Strict On does not have any real performance effect per se; it just indicates the most adequate way to write the code: you can include the mentioned Convert.ToInt32 with Option Strict On/Off: the second alternative allows you to choose what to do and the first one forces you to use it) on this code (e.g., forcing to add the Convert.ToInt32 bit) does affect the speed with respect to the Option Strict Off version (i.e., without the Convert.ToInt32 bit): the first alternative is appreciably faster. On the other hand, I have done some tests with multiple calls to this code (i.e., multiple, consecutive time measurements) which seem to indicate that the Convert.ToInt32 part increases the instability (i.e., big increases/decreases in time between different calls). In any case, this issue hasn't been adequately tested and thus this comment represents a mere warning for any future interested reader (like the recursion/loop mention above).
share|improve this question
    
Pure speculation: I'm guessing it has something to do with compiler optimization, and you could verify by examining the CLR that each generates. Microsoft had experience in writing optimizing compilers for C syntax, but I doubt they ever spent much effort in optimizations for VB syntax. –  Comintern Feb 22 at 17:58
    
@Comintern As a pure speculative approach, sounds reasonable. But what I find more difficult to understand is the fact the problem only occurs under specific conditions (recursion). In the optimised version (with loops) the VB.NET is as quick as the C# one (even, quicker, at some points). –  varocarbas Feb 22 at 18:01
    
@Comintern Thanks. Note that there was a small error in my original post. The wrong timings are 800-900; not 7000. –  varocarbas Feb 22 at 18:21
    
I'm not an expert here and I didn't download your code. So this is just an idea. The performance can from version 1 of the binary search and version 2 could be partly due to less code branching in version 2. Another thing is that the recursive function requires, pushing and popping new frames on the stack. This thread on stack overflow on branch prediction may be somewhat related: stackoverflow.com/questions/11227809/… –  Mark At Ramp51 Feb 22 at 20:28
1  
You said, "Thus integer division is ALWAYS slower in VB.NET than in C#". But VB.NET vs C# integer division suggests that VB.NET does support an integer division operator, which is \ instead of / ... I suggest you test the performance of (and/or compare the IL of) that operator. –  ChrisW Feb 23 at 10:02
show 9 more comments

2 Answers

up vote 4 down vote accepted

Your improvedBinary.vbproj specifies ...

<PropertyGroup>
  <OptionStrict>Off</OptionStrict>
</PropertyGroup>

... and your comment to Comintern said,

VB.NET with Strict Off (the case in this code), does allow you to write a function without return statement (although shows a warning).

Beware that this comment on StackOverflow says,

I agree, but with one small caveat: if you have Option Strict off, you're essentially doing extra conversions everywhere, which often makes code significantly slower. You can't make this same mistake with C#, which can lead to performance improvements if you rewrite VB.NET code in C#.

With Option Strict On, type conversions (which affect performance) are more apparent.

Microsoft's description of the Option Strict Statement warns that implicit type conversions affect performance. It doesn't explicitly mention conversion from double to int (it talks more about conversion from Object), but using Strict Off allowed you to ignore conversions from double to int, which nevertheless affect performance.


A difference between the C# and VB.NET version is that the VB.NET version includes Math.Floor and (depending on whether Option Strict is enabled) Convert.ToInt32.

It would be more like the C# version if you used using VB.NET's \ integer division operator instead, which doesn't convert to double.

If you do convert to double, according to Cleanest way to convert a Double or Single to Integer, without rounding VB.NET has (unlike C#) no fast way to convert double to int.


I also suggest that, instead of guessing, you look at the emitted IL (perhaps using ILSpy) to see what the differences are between your C# and VB.NET versions.


There may be things you can do to make your performance timing more accurate and reliable:

   if (A[imid] > key)
        // return binary_search(A, key, imin, imid - 1);
        return binary_search(A, key, imin, imax - 1);
    else if (A[imid] < key)
        // return binary_search(A, key, imid + 1, imax);
        return binary_search(A, key, imin + 1, imax);
    else
        return imid;
share|improve this answer
add comment

Now that we have code to review - the first issue that I see is that you are not comparing identical source code, and that makes it impossible to get an accurate benchmark. The problem is likely this line in the VB source that isn't in the C# source:

Return imid 'Never reached; just to avoid the warning

The C# code doesn't have a return statement outside of the loop. I don't have VB.NET installed in Visual Studio so I can't test it, but this is probably defeating optimization code in the compiler because it assumes that the return instruction can be reached. In fact, C# will give you a different warning if it is include in its source and warn you that unreachable code is detected if you include the corresponding code:

return imid; //Never reached; gives warning "Unreachable code detected".

This illustrates the second issue - you are not actually benchmarking the code itself, but the performance of each of the underlying compilers. Assuming that the syntax is analogous between the two languages doesn't mean that it compiles the same in the C# compiler as it does in the VB.NET compiler. In fact, the different warnings between the two compilers make this quite obvious. Remember, just because the IDE is the same doesn't mean it does the same thing when you compile it. A proper benchmark has to be compiled under the same conditions. This is essentially like comparing benchmarks between identical C code compiled with gcc and Visual Studio.

I am curious how similar the compilers are though - try removing the return instruction (or adding one in the C# code), ignore the warnings, run the benchmarks again.

EDIT:

Finally had time to look at the IL, and the recursion doesn't have anything to do with the performance - both of them have exactly the same IL:

default int32 binary_search_improved2 (int32[] A, int32 key, int32 imin, int32 imax)  cil managed 
    {
        // Method begins at RVA 0x6598
    // Code size 46 (0x2e)
    .maxstack 3
    .locals init (
        int32   V_0)
    IL_0000:  ldarg.3 
    IL_0001:  ldarg.2 
    IL_0002:  bge.s IL_000a

    IL_0004:  ldsfld int32 improvedBinary._Standard::KEY_NOT_FOUND
    IL_0009:  ret 
    IL_000a:  ldarg.2 
    IL_000b:  ldarg.3 
    IL_000c:  ldarg.2 
    IL_000d:  sub 
    IL_000e:  ldc.i4.1 
    IL_000f:  shr 
    IL_0010:  add 
    IL_0011:  stloc.0 
    IL_0012:  ldarg.2 
    IL_0013:  ldarg.3 
    IL_0014:  beq.s IL_001c

    IL_0016:  ldarg.0 
    IL_0017:  ldloc.0 
    IL_0018:  ldelem.i4 
    IL_0019:  ldarg.1 
    IL_001a:  bne.un.s IL_001e

    IL_001c:  ldloc.0 
    IL_001d:  ret 
    IL_001e:  ldarg.0 
    IL_001f:  ldloc.0 
    IL_0020:  ldelem.i4 
    IL_0021:  ldarg.1 
    IL_0022:  bge.s IL_0029

    IL_0024:  ldloc.0 
    IL_0025:  starg.s 2
    IL_0027:  br.s IL_000a

    IL_0029:  ldloc.0 
    IL_002a:  starg.s 3
    IL_002c:  br.s IL_000a

    } // end of method _Standard::binary_search_improved2

The differences are in the midpoint function:

C#:

ldarg.0 
ldarg.1 
ldarg.0 
sub 
ldc.i4.2 
div 
add 
ret 

VB:

ldarg.0
conv.r8
ldarg.1
ldarg.0
sub.ovf
conv.r8
ldc.r8
div
call       float64 [mscorlib]System.Math::Floor(float64)
add
call       float64 [mscorlib]System.Math::Round(float64)
conv.ovf.i4
ret
share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.