Where is this TrySZBinarySearch implemented? [closed]

Question

Closed. This question does not meet Stack Overflow guidelines. It is not currently accepting answers.

---

We don’t allow questions seeking recommendations for books, tools, software libraries, and more. You can edit the question so it can be answered with facts and citations.

Closed 6 years ago.

Improve this question

Whilst I was studying some micro performance techniques, I encountered, in the array.cs file, in the .net framework an external reference to a function for binary searches.

private static extern bool TrySZBinarySearch(Array sourceArray, int sourceIndex, int count, Object value, out int retVal); 

Where can I find documentation for this function? Or better, how it was implemented? Why is there so many SZ`s in the .net?

private static extern bool TrySZIndexOf(Array sourceArray, int sourceIndex, int count, Object value, out int retVal); 

private static extern bool TrySZLastIndexOf(Array sourceArray, int sourceIndex, int count, Object value, out int retVal);

sealed class SZArrayHelper { ... }

etc

Answer 1

    [System.Security.SecurityCritical]  // auto-generated
    [ResourceExposure(ResourceScope.None)]
    [MethodImplAttribute(MethodImplOptions.InternalCall)]
    [ReliabilityContract(Consistency.WillNotCorruptState, Cer.MayFail)]
    private static extern bool TrySZBinarySearch(Array sourceArray, 
        int sourceIndex, int count, Object value, out int retVal);

That's the declaration as retrieved from the Reference Source. Which has the vast majority of the source code of the .NET framework. You can download it here.

Methods that are attributed with [MethodImpl(MethodImplOptions.InternalCall)] are written in C++ and included in the CLR. Source code for the CLR is available as well from SSCLI20, a shared source version of the CLR meant to help getting .NET ported to other operating systems. It is a bit dated since it was released at the .NET 2.0 time frame but lots of primary helper functions are still accurate. You can download it here.

You'll find TrySZBinarySearch back in clr/src/vm/ecall.cpp, the first place to look for InternalCall methods. You'll see it maps to the ArrayHelper::TrySZBinarySearch() C++ method which you'll find back in clr/src/vm/comarrayhelper.cpp

Nothing terribly interesting about it, just a plain binary search algorithm that's specialized for the various simple value types. You'll find the reason it was written in C++ instead of C# in this answer.

SZ is short for single-dimension zero-based, the kind of array you'll get from a C# array[] declaration. Better known as "vector" in C# speak. Heavily micro-optimized since it is so commonly used.

UPDATE: easier to see today with the CoreCLR source code provided at github, the function is here.

Answer 2

[MethodImplAttribute(MethodImplOptions.InternalCall)]

... on the method declaration indicates that this is implemented as a native method (i.e. typically C++/assembly), not in .NET (e.g. C#). You'll find the implementation in the SSCLI at clr\src\vm\comarrayhelpers.cpp (leaving the look into further calls as an exercise for the reader - Hans Passant already explained what you'll find better than I could):

FCIMPL5(FC_BOOL_RET, ArrayHelper::TrySZBinarySearch, ArrayBase * array, UINT32 index, UINT32 count, Object * value, INT32 * retVal)
    WRAPPER_CONTRACT;
    STATIC_CONTRACT_SO_TOLERANT;

    VALIDATEOBJECTREF(array);
    _ASSERTE(array != NULL);

    if (array->GetRank() != 1 || array->GetLowerBoundsPtr()[0] != 0)
        FC_RETURN_BOOL(FALSE);

    _ASSERTE(retVal != NULL);
    _ASSERTE(index <= array->GetNumComponents());
    _ASSERTE(count <= array->GetNumComponents());
    _ASSERTE(array->GetNumComponents() >= index + count);
    *retVal = 0xdeadbeef;  // Initialize the return value.
    // value can be NULL, but of course, will not be in primitive arrays.
    TypeHandle arrayTH = array->GetArrayElementTypeHandle();
    const CorElementType arrayElType = arrayTH.GetVerifierCorElementType();
    if (!CorTypeInfo::IsPrimitiveType(arrayElType))
        FC_RETURN_BOOL(FALSE);
    // Handle special case of looking for a NULL object in a primitive array.
    if (value == NULL) {
        *retVal = -1;
        FC_RETURN_BOOL(TRUE);
    }

    TypeHandle valueTH = value->GetTypeHandle();
    if (arrayTH != valueTH)
        FC_RETURN_BOOL(FALSE);

    switch(arrayElType) {
    case ELEMENT_TYPE_I1:
        *retVal = ArrayHelpers<I1>::BinarySearchBitwiseEquals((I1*) array->GetDataPtr(), index, count, *(I1*)value->UnBox());
        break;

    case ELEMENT_TYPE_U1:
    case ELEMENT_TYPE_BOOLEAN:
        *retVal = ArrayHelpers<U1>::BinarySearchBitwiseEquals((U1*) array->GetDataPtr(), index, count, *(U1*)value->UnBox());
        break;

    case ELEMENT_TYPE_I2:
        *retVal = ArrayHelpers<I2>::BinarySearchBitwiseEquals((I2*) array->GetDataPtr(), index, count, *(I2*)value->UnBox());
        break;

    case ELEMENT_TYPE_U2:
    case ELEMENT_TYPE_CHAR:
        *retVal = ArrayHelpers<U2>::BinarySearchBitwiseEquals((U2*) array->GetDataPtr(), index, count, *(U2*)value->UnBox());
        break;

    case ELEMENT_TYPE_I4:
        *retVal = ArrayHelpers<I4>::BinarySearchBitwiseEquals((I4*) array->GetDataPtr(), index, count, *(I4*)value->UnBox());
        break;

    case ELEMENT_TYPE_U4:
        *retVal = ArrayHelpers<U4>::BinarySearchBitwiseEquals((U4*) array->GetDataPtr(), index, count, *(U4*)value->UnBox());
        break;

    case ELEMENT_TYPE_R4:
        *retVal = ArrayHelpers<R4>::BinarySearchBitwiseEquals((R4*) array->GetDataPtr(), index, count, *(R4*)value->UnBox());
        break;

    case ELEMENT_TYPE_I8:
        *retVal = ArrayHelpers<I8>::BinarySearchBitwiseEquals((I8*) array->GetDataPtr(), index, count, *(I8*)value->UnBox());
        break;

    case ELEMENT_TYPE_U8:
        *retVal = ArrayHelpers<U8>::BinarySearchBitwiseEquals((U8*) array->GetDataPtr(), index, count, *(U8*)value->UnBox());
        break;

    case ELEMENT_TYPE_R8:
        *retVal = ArrayHelpers<R8>::BinarySearchBitwiseEquals((R8*) array->GetDataPtr(), index, count, *(R8*)value->UnBox());
        break;

    case ELEMENT_TYPE_I:
    case ELEMENT_TYPE_U:
        // In V1.0, IntPtr & UIntPtr are not fully supported types.  They do 
        // not implement IComparable, so searching & sorting for them should
        // fail.  In V1.1 or V2.0, this should change.  --                                   
        FC_RETURN_BOOL(FALSE);

    default:
        _ASSERTE(!"Unrecognized primitive type in ArrayHelper::TrySZBinarySearch");
        FC_RETURN_BOOL(FALSE);
    }
    FC_RETURN_BOOL(TRUE);
FCIMPLEND

The SZ in the various methods names refers to arrays that are "Single dimension, Zero based". That's what you'll get with e.g.:

int[] myArray;

or

MyObject[] myArray;

... As opposed to the other, more general, kind of array in .NET, which can be multiple dimensions:

int[,] myArray;

... or may have a different lower bound than 0:

// Creates a single-dimensional array of size 10 with a lower bound of 5
// - as far as I recall C# doesn't have any dedicated declaration for this.
// It's mainly there to support other languages:
Array myArray = Array.CreateInstance(
   typeof(int), 
   new int[] { 10 }, 
   new int[] { 5 }
);

SZ arrays are more performant and more optimized, so generally preferred. Which is why you'll see so many references to them in the CLR code (and hence the reason for the check of rank and lower bound early in the above code).