에 비전송: 배열 정렬 방법의 성능 비교 (중): Array. ort 구현 분석

어제 우 리 는 Array. ort 방법 과 LINQ 정렬 의 성능 을 비교 하여 LINQ 정렬 의 성능 이 Array. ort 방법 보다 큰 폭 으로 뒤 처 진 다 는 것 을 알 게 되 었 다.Array. ort 에 있어 서 성능 이 가장 높 은 것 은 그 중에서 Comparer. Default 를 비교 기의 과부하 방법 으로 사용 하 는 것 이다.앞의 말미 에 우 리 는 정렬 알고리즘 이 이미 하나의 표준 (빠 른 정렬) 에 가 까 워 졌 기 때문에 알고리즘 측면 에서 볼 때 Array. ort 방법 과 LINQ 정렬 에 있어 그렇게 큰 차이 가 있어 서 는 안 되 기 때문에 이들 의 성능 차 이 를 야기 하 는 원인 은 구체 적 인 실현 방식 의 문제 일 것 이 라 고 추측 했다.
. NET 프레임 워 크 코드 다운로드
비교적 실현 되 는 차이 인 만큼 코드 를 읽 는 것 은 직접적인 선택 이다.. NET 코드 를 읽 는 것 에 대해 서 는. NET Reflector 를 사용 하여 프레임 워 크 의 프로그램 집합 을 C \ # 코드 로 역 컴 파일 합 니 다. 친구 들 이 IL 을 관찰 하 는 것 을 좋아 하고 더 직접적 이 고 밑바닥 이 라 고 생각 하 는 것 을 제외 하지 않 습 니 다.그러나 나 는 대부분의 상황 에서 IL 이 볼 수 있 는 것 은 C \ # 에서 도 볼 수 있 고 C \ # 알 수 없 는 IL 도 도움 이 되 지 않 는 다 고 생각한다. 그래서 많은 'IL 이 문 제 를 발견 했다' 는 글 은 사실은 자신 과 자신 만 시원 하 다.
그러나. NET Reflector 는 프로그램 집합 을 매우 우수한 C \ # 코드 로 역 컴 파일 했 지만 이전의 많은 정 보 를 복구 할 수 없 었 다.예 를 들 어 부분 변수 이름 을 알 수 없 기 때문에 코드 의 도 를 이해 하 는 데 어려움 을 겪 었 다.예 를 들 어 가 독성 을 위해 우 리 는 일부 조건 문 구 를 나 누 어 쓸 수 있 고 C \ # 컴 파일 러 는 이 를 연결 할 수 있다.주석 등 분명히 제 거 될 것 은 말 할 것 도 없다.따라서 코드 를 직접 읽 을 수 있 는 상황 에서 나 는. NET Reflector 를 사용 하 는 경향 이 없다.
이것 은 쓸데없는 말 이 아 닙 니까? 그러나 일부 라 이브 러 리 는. NET 프레임 워 크 가 소스 코드 를 제공 하지 않 았 다 면 무슨 방법 이 있 습 니까?사실 마이크로소프트 도. NET 프레임 워 크 의 상당 부분 프로그램 집합 소스 코드 (거의 모든 v 2.0 프로그램 집합, 예 를 들 어 mscrolib, System, System, System. Web 등) 를 발 표 했 고 넷 마 스 다운 로 더 를 사용 하여 로 컬 에 직접 다운로드 할 수 있다.수행원 코드 가 발표 한 것 은 디 버 깅 이 편리 한 pdb 파일 도 있 지만 이것 은 또 다른 화제 입 니 다. 우 리 는 지금 소스 코드 에 만 관심 을 가지 고 있 습 니 다.
따라서, 나 는 당신 이 모든 마이크로소프트 가 제공 하 는 소스 코드 를 로 컬 에 다운로드 할 것 을 건의 합 니 다.. NET Reflector 의 역 컴 파일 결 과 를 알 수 없 을 때 소스 코드 인지 주석 이 포 함 된 소스 코드 인지 참고 하 세 요.
Array. ort 방법 구현
각 Array. ort 방법의 리 셋 은 최종 적 으로 아래 의 리 셋 에 의뢰 하여 실 행 됩 니 다.

public static void Sort(T[] array, int index, int length, IComparer comparer)
{
    ...
    if (length > 1)
    {
        // 
        // TrySZSort is still faster than the generic implementation.
        // The reason is Int32.CompareTo is still expensive than just using "". 
        // 
        if (comparer == null || comparer == Comparer.Default)
        {
            if (TrySZSort(array, null, index, index + length - 1))
            {
                return;
            }
        }
        ArraySortHelper.Default.Sort(array, index, length, comparer);
    }
}

우 리 는 논리 적 으로 Array. ort 방법 은 IComparer 형식의 비교 기 를 사용 하여 두 요소 의 크기 를 판단 한 다 는 것 을 알 고 있다.그러나 여기 서. NET 프레임 워 크 는 사용자 가 비교 기 를 제공 하지 않 거나 기본 비교 기 를 직접 사용 할 때 TrySZSort 방법 으로 정렬 하 는 '특례' 를 만 들 었 다.TrySZSort 방법 이 true 로 돌아 가면 정렬 이 완료 되 었 음 을 나타 내 고 바로 돌아 갑 니 다.false 로 돌아 가면 내 장 된 정렬 방법 으로 계속 처리 합 니 다.그렇다면 TrySZSort 는 어떻게 이 루어 졌 을 까?

private static extern bool TrySZSort(Array keys, Array items, int left, int right);

이것 은 extern 방법 으로 그것 이 CLR 에 의 해 직접 실현 되 었 다 는 것 을 설명 한다. 우 리 는 그것 의 구체 적 인 알고리즘 이나 의 도 를 알 수 없다.주석 에서 알 수 있 듯 이 이 방법의 목적 은 성능 을 향상 시 키 는 것 이다.IComparer 의 compare 방법 을 사용 하여 비교 할 때마다 가상 방법의 호출 에 해당 하 며, CLR 은 편 이 량 을 계산 해 야 하 며, 내 연 될 수 없습니다.이 디 테 일 은 int 의 크기 를 직접 비교 하 는 것 에 비해 비교적 큰 비용 이 든다.TrySZSort 라 는 외부 방법 으로 정렬 하면 특정 상황 에서 의 실행 효율 을 높이 는 데 도움 이 된다.
따라서 TrySZSort 의 역할 을 추정 할 자신 이 있 을 것 이다.TrySZSort 방법 은 직접 비교 할 수 있 는 네 이 티 브 형식 (예 를 들 어 int 등) 을 정렬 하 는 역할 을 합 니 다. 배열 에 있 는 요소 의 유형 을 지원 할 수 없다 는 것 을 알 게 되면 false 로 돌아 갑 니 다. 그렇지 않 으 면 정렬 하고 true 로 돌아 갑 니 다.TrySZSort 가 false 로 돌아 가면 ArraySortHelper 를 사용 하여 정렬 합 니 다.그 중의 실현 은 바로 표준 (정말 표준) 의 빠 른 정렬 입 니 다. 관심 이 있 으 면 그 중의 코드 를 스스로 읽 을 수 있 습 니 다.
주의해 야 할 것 은 Array 는 System 네 임 스페이스 에 정 의 된 형식 이 고, Array SortHelper 는 System. collections. Generic 네 임 스페이스 에 정 의 됩 니 다.마이크로소프트 가 제공 하 는 소스 코드 를 읽 을 때 귀 찮 은 점 은 바로 내 비게 이 션 이 쉽 지 않다 는 것 이다. 예 를 들 어 Array Sort Helper 류 는 나 로 하여 금 쉽게 찾 을 수 있 게 한다.그러나 사실 우 리 는. NET Reflector 의 강력 한 네 비게 이 션 기능 에 맞 춰 특정한 유형의 위 치 를 신속하게 찾 은 다음 에 해당 하 는 파일 을 직접 찾 을 수 있다.물론 파일 내용 을 색인 하면 'class Array SortHelper' 와 같은 키 워드 를 찾 을 수도 있 고 특정 파일 을 빨리 찾 을 수도 있 습 니 다.
Array. ort 기타 과부하 성능
이상, 우 리 는 왜 Comparer. Default 를 비교 기로 사용 할 때 성능 이 가장 높 은 지 이미 알 고 있 습 니 다. int 유형 에 있어 서 Array. ort 방법 은 가장 빠 른 TrySZSort 방법 으로 정렬 하기 때 문 입 니 다.만약 에 우리 가 사용자 정의 Int32Comparer 를 사용 하여 비교 하면 Compare 방법 으로 호출 된 비용 은 피 할 수 없 으 며 실험 결과 에 따라 Int32Comparer 를 사용 하 는 실행 시간 이 전자 보다 80% 증가 하 는 것 도 받 아들 일 수 있다.
그렇다면 의뢰 를 사용 해 정렬 할 때 왜 Int32Comparer 보다 느 릴 까?코드 를 보십시오.

public static void Sort(T[] array, Comparison comparison)
{
    ...
    IComparer comparer = new FunctorComparer(comparison);
    Sort(array, comparer);
}

사실 이 유 는 간단 하 다. 왜냐하면. NET 프레임 워 크 는 Functor Comparer 를 사용 하여 comparison 의뢰 를 봉 인 했 기 때문이다.이렇게 매번 비교 할 때, 그것 은 Int32Comparer 에 비해 위탁 집행 비용 을 증가 시 켰 다. 이것 은 또 하나의 가상 방법의 호출 에 해당 한다. 주 소 를 찾 아야 하기 때문에 내 연 될 수 없다.
이로써 우 리 는 Array. ort 각 과부하 의 실현 방식 을 분 석 했 고 세 가지 Array. ort 과부하 성능 에 다른 원인 이 있 음 을 알 게 되 었 다.마침 얼마 전 강 민 형 은 int 타 입 이 아 닌 Person 타 입 을 사용 해 비교 할 때 도 LINQ 정렬 이 빠르다 고 답 했다. 이 를 통 해 두 가지 방법의 성능 과 유형 도 관계 가 있다 고 생각 했다.당신 은 이 견해 가 정확 하 다 고 생각 합 니까?사실 실현 적 으로 볼 때 Array. ort 는 거의 가장 좋 은 방법 이다.반면, LINQ 정렬 은 추가 시퀀스 를 생 성하 기 때문에 성능 이 Array. ort 를 초과 하려 는 것 은 거의 불가능 하 다.그런데 정말 그런 가?
그럼 이 테스트 결 과 는... 저도 Person 류 테스트 를 썼어 요 (http://gist.github.com/282796), 역시 Array. ort 가 빠 릅 니 다.그렇다면 왜 두 결 과 는 다 를 까?이것 은 토론 할 만 한 문제 다.
관련 글

배열 정렬 방법의 성능 비교 (1): 주의사항 및 시험

배열 정렬 방법의 성능 비교 (2): Array. ort 실현 분석

배열 정렬 방법의 성능 비교 (3): LINQ 정렬 실현 분석