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

Question

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

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

Где я могу найти документацию для этой функции? Или лучше, как это было реализовано? Почему так много SZ `s в .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. Вы можете скачать it here.

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

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

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

SZ не подходит для одномерного нулевого размера, типа массива, который вы получите из объявления C# array []. Лучше известен как «вектор» на языке C#. Тяжело микро-оптимизирована, поскольку она так часто используется.

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 в различных именах методов относится к массивам, которые являются «S Ingle измерения, Z эро основы». Это то, что вы получите с, например:

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