4

在我研究一些微性能技术时,我在array.cs 文件中,在 .net 框架中遇到了对二进制搜索函数的外部引用。

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

我在哪里可以找到此功能的文档?或者更好的是,它是如何实施的?为什么.net中有这么多SZ?

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

4

2 回答 2

6
    [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 框架的绝大部分源代码。你可以在这里下载。

使用 [MethodImpl(MethodImplOptions.InternalCall)] 属性的方法是用 C++ 编写的,并包含在 CLR 中。CLR 的源代码也可从 SSCLI20 获得,这是一个 CLR 的共享源版本,旨在帮助将 .NET 移植到其他操作系统。由于它是在 .NET 2.0 时间范围内发布的,所以它有点过时了,但许多主要的辅助函数仍然是准确的。你可以在这里下载。

您会在 clr/src/vm/ecall.cpp 中找到 TrySZBinarySearch,这是查找 InternalCall 方法的第一个位置。您会看到它映射到 ArrayHelper::TrySZBinarySearch() C++ 方法,您可以在 clr/src/vm/comarrayhelper.cpp 中找到该方法

没有什么特别有趣的,只是一个简单的二进制搜索算法,专门用于各种简单的值类型。您会在这个答案中找到它是用 C++ 而不是 C# 编写的原因。

SZ 是从零开始的单维数组的缩写,您将从 C# array[] 声明中获得这种数组。在 C# 中更好地称为“向量”。由于它非常常用,因此进行了大量的微优化。

更新:今天使用 github 提供的 CoreCLR 源代码更容易看到,函数在这里

于 2013-08-16T17:50:01.383 回答
1
[MethodImplAttribute(MethodImplOptions.InternalCall)]

... 在方法声明上表明这是作为本机方法(即通常是 C++/程序集)实现的,而不是在 .NET 中(例如 C#)。您可以在 clr\src\vm\comarrayhelpers.cpp 的SSCLI中找到该实现(将进一步的调用留给读者作为练习 - Hans Passant 已经解释了您会发现的内容比我做得更好):

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名称指的是“维,基于零”的数组。这就是你会得到的,例如:

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 代码中看到如此多的引用它们的原因(因此也是在上述代码的早期检查等级和下限的原因)。

于 2013-08-16T17:50:04.750 回答