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 todoubleis 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 theConvert.ToInt32part explained below, when dealing withOption 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# codereturn imin + (imax - imin) / 2;to VB.NET is:Return imin + (imax - imin) \ 2. Any other option would provoke automatic, intermediate conversions from/todouble, 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.ToInt32andMath.Floor); there are various comments in this code explaining the reasons for these calls (and confirming thatMath.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 theMath.Flooras the only right/uncommented line. - Also it is worthy to know that the only
Option Strict Oneffect (well... as explained in one of the answers below,Option Strict Ondoes not have any real performance effect per se; it just indicates the most adequate way to write the code: you can include the mentionedConvert.ToInt32withOption 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 theConvert.ToInt32bit) does affect the speed with respect to theOption Strict Offversion (i.e., without theConvert.ToInt32bit): 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 theConvert.ToInt32part 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).
- Both versions (VB.NET & C#) are identical with the sole exception
of the additional in-built calls in VB.NET inside
