Dlaczego przetwarzanie posortowanej tablicy jest wolniejsze niż nieposortowanej tablicy?

Mam listę 500000 losowo wygenerowanych Tuple<long,long,string>obiektów, na których wykonuję proste wyszukiwanie „pomiędzy”:

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

Gdy generuję losową tablicę i uruchamiam wyszukiwanie 100 losowo wygenerowanych wartości x, wyszukiwanie kończy się w ciągu około czterech sekund. Wiedząc jednak o wielkich cudach sortowania podczas wyszukiwania , postanowiłem posortować moje dane - najpierw Item1, potem Item2, a na końcu Item3- przed uruchomieniem moich 100 wyszukiwań. Spodziewałem się, że posortowana wersja będzie działać nieco szybciej ze względu na przewidywanie gałęzi: pomyślałem, że gdy dojdziemy do punktu, w którym Item1 == xwszystkie dalsze kontrole t.Item1 <= xpoprawnie przewidują gałąź jako „brak wzięcia”, przyspieszając tylną część Szukaj. Ku mojemu zaskoczeniu, wyszukiwanie zajęło dwa razy więcej czasu na posortowanej tablicy !

Próbowałem zmienić kolejność, w jakiej przeprowadzałem eksperymenty, i użyłem innego źródła dla generatora liczb losowych, ale efekt był taki sam: wyszukiwania w nieposortowanej tablicy przebiegały prawie dwa razy szybciej niż wyszukiwania w tej samej tablicy, ale posortowane!

Czy ktoś ma dobre wytłumaczenie tego dziwnego efektu? Poniżej znajduje się kod źródłowy moich testów; Używam .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)

Podczas korzystania z nieposortowanej listy dostęp do wszystkich krotek uzyskuje się w kolejności pamięci . Zostały one przydzielone kolejno w pamięci RAM. Procesory uwielbiają sekwencyjnie uzyskiwać dostęp do pamięci, ponieważ mogą spekulacyjnie zażądać następnej linii pamięci podręcznej, aby zawsze była obecna w razie potrzeby.

Podczas sortowania listy ustawiasz ją w losowej kolejności, ponieważ klucze sortowania są generowane losowo. Oznacza to, że dostęp do pamięci dla krotek jest nieprzewidywalny. Procesor nie może wstępnie pobrać pamięci i prawie każdy dostęp do krotki to brak pamięci podręcznej.

To dobry przykład konkretnej zalety zarządzania pamięcią GC : struktury danych, które zostały wspólnie przydzielone i są używane razem, działają bardzo dobrze. Mają doskonałą lokalizację odniesienia .

W tym przypadku kara za pominięcie pamięci podręcznej przewyższa zapisaną karę przewidywania oddziału .

Spróbuj zmienić na struct-tuple. Spowoduje to przywrócenie wydajności, ponieważ w środowisku wykonawczym nie musi wystąpić dereferencja wskaźnika, aby uzyskać dostęp do elementów krotkowych.

Chris Sinclair zauważa w komentarzach, że „dla TotalCount około 10 000 lub mniej, posortowana wersja działa szybciej ”. Wynika to z faktu, że mała lista mieści się całkowicie w pamięci podręcznej procesora . Dostęp do pamięci może być nieprzewidywalny, ale cel jest zawsze w pamięci podręcznej. Wierzę, że wciąż jest niewielka kara, ponieważ nawet ładowanie z pamięci podręcznej zajmuje kilka cykli. Nie wydaje się to jednak problemem, ponieważ procesor może żonglować wieloma zaległymi obciążeniami , zwiększając w ten sposób przepustowość. Ilekroć procesor trafi w oczekiwanie na pamięć, nadal przyspiesza w strumieniu instrukcji, aby w kolejce wykonać tyle operacji pamięci, ile może. Ta technika służy do ukrywania opóźnień.

Tego rodzaju zachowanie pokazuje, jak trudno jest przewidzieć wydajność nowoczesnych procesorów. Fakt, że jesteśmy tylko dwa razy wolniej przechodząc z sekwencyjnego do losowego dostępu do pamięci, mówi mi, ile się dzieje pod osłonami, aby ukryć opóźnienie pamięci. Dostęp do pamięci może zatrzymać procesor na 50-200 cykli. Biorąc pod uwagę tę liczbę, można się spodziewać, że program stanie się> 10x wolniejszy podczas wprowadzania losowych dostępów do pamięci.

LINQ nie wie, czy twoja lista jest posortowana czy nie.

Ponieważ parametr Count z predykatem jest metodą rozszerzenia dla wszystkich elementów IEnumerable, myślę, że nawet nie wie, czy działa na kolekcji z wydajnym dostępem losowym. Po prostu sprawdza każdy element, a Usr wyjaśnił, dlaczego wydajność spadła.

Aby wykorzystać zalety wydajności posortowanej tablicy (takie jak wyszukiwanie binarne), musisz wykonać trochę więcej kodowania.