Где реализован этот TrySZBinarySearch?

Question

Пока я изучал некоторые методы микропроцессора, я обнаружил в файле array.cs в платформе.net внешнюю ссылку на функцию для бинарного поиска.

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

Где я могу найти документацию для этой функции? Или лучше, как это было реализовано? Почему в.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 { ... }

так далее

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);

Это объявление, полученное из справочного источника. Который имеет подавляющее большинство исходного кода.NET Framework. Вы можете скачать его здесь.

Методы, которые приписываются с помощью [MethodImpl(MethodImplOptions.InternalCall)], написаны на C++ и включены в CLR. Исходный код для CLR также доступен из SSCLI20, совместно используемой исходной версии CLR, предназначенной для переноса.NET на другие операционные системы. Это немного устарело, так как оно было выпущено в период времени.NET 2.0, но многие основные вспомогательные функции все еще точны. Вы можете скачать его здесь.

Вы найдете TrySZBinarySearch обратно в clr/src/vm/ecall.cpp, первом месте для поиска методов InternalCall. Вы увидите, что он отображается на метод ArrayHelper::TrySZBinarySearch() C++, который вы найдете в файле clr/src/vm/comarrayhelper.cpp.

Ничего страшного в этом нет, просто простой алгоритм двоичного поиска, специализированный для различных простых типов значений. В этом ответе вы найдете причину, по которой он был написан на C++ вместо C#.

SZ - это сокращение от одномерного, начинающегося с нуля, типа массива, который вы получите из объявления C# array[]. Лучше известный как "вектор" в C# говорят. Сильно микрооптимизирован, поскольку он так широко используется.

ОБНОВЛЕНИЕ: сегодня легче увидеть с исходным кодом CoreCLR, предоставленным на github, функция здесь.

Answer 2

[MethodImplAttribute(MethodImplOptions.InternalCall)]

... в объявлении метода указывается, что он реализован как собственный метод (т. е. обычно C++/ сборка), а не в.NET (например, C#). Вы найдете реализацию в SSCLI по адресу clr\src\vm\comarrayhelpers.cpp (оставляя рассмотрение дальнейших вызовов в качестве упражнения для читателя - Ханс Пассант уже объяснил, что вы найдете лучше, чем я мог):

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

SZ в различных методах имена относятся к массивам, которые имеют "одно измерение, основанное на Z ero". Вот что вы получите, например:

int[] myArray;

или же

MyObject[] myArray;

... В отличие от другого, более общего вида массива в.NET, который может иметь несколько измерений:

int[,] myArray;

... или может иметь другую нижнюю границу, чем 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 более производительны и более оптимизированы, поэтому обычно предпочтительнее. Вот почему вы увидите так много ссылок на них в коде CLR (и, следовательно, причина проверки ранга и нижней границы в начале кода выше).