정렬된 배열 처리가 정렬되지 않은 배열보다 느린 이유는 무엇입니까?

정렬된 배열 처리가 정렬되지 않은 배열보다 느린 이유는 무엇입니까?

는 무작위로 을 가지고 있습니다.Tuple<long,long,string>검색을 : "사이" 검색:

var data = new List<Tuple<long,long,string>>(500000);
...
var cnt = data.Count(t => t.Item1 <= x && t.Item2 >= x);

무작위 배열을 생성하고 무작위로 생성된 100개의 값에 대한 검색을 실행할 때x약 4초 안에 검색이 완료됩니다.하지만 정렬이 검색에 큰 도움이 된다는 것을 알고 있었기 때문에, 먼저 데이터를 정렬하기로 결정했습니다.Item1 다음에 때까지로Item2으로 리고마침에 의해.Item3검색을 에. 100개의 검색을 실행합니다.분기 예측 때문에 정렬된 버전이 조금 더 빨리 수행될 것으로 예상했습니다. 일단 우리가 이 지점에 도달하면,Item1 == x『 』 『 』 『 』의 모든 검사t.Item1 <= x분기를 "no take"로 올바르게 예측하여 검색의 꼬리 부분을 가속화합니다.놀랍게도, 정렬된 배열에서 검색하는 데 두 배의 시간이 걸렸습니다!

실험을 실행한 순서대로 전환하고 난수 생성기에 다른 시드를 사용했지만 결과는 동일합니다. 정렬되지 않은 배열의 검색이 동일한 배열의 검색보다 거의 두 배 빨리 실행되었지만 정렬되었습니다!

이 이상한 효과에 대해 잘 설명할 수 있는 사람이 있습니까?테스트의 소스 코드는 다음과 같습니다. 를 사용하고 있습니다.NET 4.0.

---

private const int TotalCount = 500000;
private const int TotalQueries = 100;
private static long NextLong(Random r) {
    var data = new byte[8];
    r.NextBytes(data);
    return BitConverter.ToInt64(data, 0);
}
private class TupleComparer : IComparer<Tuple<long,long,string>> {
    public int Compare(Tuple<long,long,string> x, Tuple<long,long,string> y) {
        var res = x.Item1.CompareTo(y.Item1);
        if (res != 0) return res;
        res = x.Item2.CompareTo(y.Item2);
        return (res != 0) ? res : String.CompareOrdinal(x.Item3, y.Item3);
    }
}
static void Test(bool doSort) {
    var data = new List<Tuple<long,long,string>>(TotalCount);
    var random = new Random(1000000007);
    var sw = new Stopwatch();
    sw.Start();
    for (var i = 0 ; i != TotalCount ; i++) {
        var a = NextLong(random);
        var b = NextLong(random);
        if (a > b) {
            var tmp = a;
            a = b;
            b = tmp;
        }
        var s = string.Format("{0}-{1}", a, b);
        data.Add(Tuple.Create(a, b, s));
    }
    sw.Stop();
    if (doSort) {
        data.Sort(new TupleComparer());
    }
    Console.WriteLine("Populated in {0}", sw.Elapsed);
    sw.Reset();
    var total = 0L;
    sw.Start();
    for (var i = 0 ; i != TotalQueries ; i++) {
        var x = NextLong(random);
        var cnt = data.Count(t => t.Item1 <= x && t.Item2 >= x);
        total += cnt;
    }
    sw.Stop();
    Console.WriteLine("Found {0} matches in {1} ({2})", total, sw.Elapsed, doSort ? "Sorted" : "Unsorted");
}
static void Main() {
    Test(false);
    Test(true);
    Test(false);
    Test(true);
}

---

Populated in 00:00:01.3176257
Found 15614281 matches in 00:00:04.2463478 (Unsorted)
Populated in 00:00:01.3345087
Found 15614281 matches in 00:00:08.5393730 (Sorted)
Populated in 00:00:01.3665681
Found 15614281 matches in 00:00:04.1796578 (Unsorted)
Populated in 00:00:01.3326378
Found 15614281 matches in 00:00:08.6027886 (Sorted)

정렬되지 않은 목록을 사용하는 경우 모든 튜플이 메모리 순서로 액세스됩니다.메모리에 연속적으로 할당되었습니다. CPU는 다음 캐시 라인을 추측적으로 요청할 수 있기 때문에 메모리에 순차적으로 액세스하는 것을 좋아합니다. 필요할 때 항상 이 라인이 존재합니다.

목록을 정렬할 때 정렬 키가 임의로 생성되므로 목록을 임의 순서로 정렬합니다.즉, 튜플 멤버에 대한 메모리 액세스를 예측할 수 없습니다.CPU는 메모리를 미리 가져올 수 없으며 태플에 대한 거의 모든 액세스가 캐시 누락입니다.

이것은 GC 메모리 관리의 특정 이점에 대한 좋은 예입니다. 함께 할당되고 함께 사용되는 데이터 구조는 매우 잘 수행됩니다.그들은 참고할 만한 장소를 가지고 있습니다.

이 경우 캐시 누락으로 인한 페널티가 저장된 분기 예측 페널티보다 큽니다.

로 바꿔보세요.struct-tuple. 이렇게 하면 실행 시 튜플 멤버에 액세스하기 위해 포인터 참조 해제가 발생할 필요가 없으므로 성능이 복원됩니다.

Chris Sinclair는 코멘트에서 "TotalCount 약 10,000 이하의 경우 정렬된 버전이 더 빨리 수행됩니다."라고 언급합니다.이는 작은 목록이 CPU 캐시에 완전히 들어맞기 때문입니다.메모리 액세스는 예측할 수 없지만 대상은 항상 캐시에 있습니다.캐시에서 로드하는 데도 주기가 좀 걸리기 때문에 여전히 약간의 페널티가 있다고 생각합니다.그러나 CPU가 여러 미결 부하를 저글링하여 처리량을 증가시킬 수 있기 때문에 문제가 되지 않는 것 같습니다.CPU가 메모리 대기에 도달할 때마다 명령 스트림에서 가능한 한 많은 메모리 작업을 대기열에 저장하기 위해 속도를 높입니다.이 기법은 지연 시간을 숨기기 위해 사용됩니다.

이러한 동작은 최신 CPU의 성능을 예측하는 것이 얼마나 어려운지 보여줍니다.순차적 메모리 액세스에서 랜덤 메모리 액세스로 전환할 때 속도가 2배밖에 느리지 않다는 사실은 메모리 지연 시간을 숨기기 위해 커버 아래에서 얼마나 많은 작업이 진행되고 있는지 알려줍니다.메모리 액세스는 CPU를 50-200 사이클 동안 지연시킬 수 있습니다.그 숫자를 고려할 때 무작위 메모리 액세스를 도입할 때 프로그램이 10배 이상 느려질 것으로 예상할 수 있습니다.

LINQ는 목록이 정렬되었는지 여부를 알 수 없습니다.

술어 매개 변수가 있는 카운트는 모든 IE 숫자에 대한 확장 방법이기 때문에 효율적인 랜덤 액세스로 컬렉션 위에서 실행되고 있는지조차 알 수 없다고 생각합니다.따라서 모든 요소를 확인하기만 하면 Usr은 성능이 저하된 이유를 설명했습니다.

정렬된 배열(이진 검색 등)의 성능 이점을 활용하려면 코딩을 조금 더 해야 합니다.

언급URL : https://stackoverflow.com/questions/14023988/why-is-processing-a-sorted-array-slower-than-an-unsorted-array