Czy współczesne języki OO mogą konkurować z wydajnością sklepu macierzy C ++?

Właśnie zauważyłem, że każdy współczesny język programowania OO, który jestem przynajmniej w pewnym stopniu zaznajomiony (który jest w zasadzie tylko Javą, C # i D) pozwala na tablice kowariantne. Oznacza to, że tablica łańcuchowa jest tablicą obiektową:

Object[] arr = new String[2];   // Java, C# and D allow this

Macierze kowariantne są dziurą w systemie typu statycznego. Umożliwiają błędy typu, których nie można wykryć podczas kompilacji, dlatego każdy zapis do tablicy musi być sprawdzany w czasie wykonywania:

arr[0] = "hello";        // ok
arr[1] = new Object();   // ArrayStoreException

To wydaje się być strasznym spadkiem wydajności, jeśli robię wiele sklepów z tablicami.

C ++ nie ma tablic kowariantnych, więc nie ma potrzeby przeprowadzania takiej kontroli środowiska uruchomieniowego, co oznacza, że ​​nie ma ograniczenia wydajności.

Czy przeprowadzono analizę w celu zmniejszenia liczby koniecznych kontroli środowiska wykonawczego? Na przykład, jeśli powiem:

arr[1] = arr[0];

można argumentować, że sklep nie może zawieść. Jestem pewien, że istnieje wiele innych możliwych optymalizacji, o których nawet nie myślałem.

Czy współczesne kompilatory faktycznie wykonują tego rodzaju optymalizacje, czy też muszę żyć z faktem, że na przykład Quicksort zawsze wykonuje O (n log n) niepotrzebne kontrole środowiska wykonawczego?

Czy współczesne języki OO mogą uniknąć narzutów generowanych przez obsługę macierzy alternatywnych?

D nie ma tablic kowariantnych. Pozwalało im to przed najnowszą wersją ( dmd 2.057 ), ale ten błąd został naprawiony.

Tablica w D jest w rzeczywistości strukturą ze wskaźnikiem i długością:

struct A(T)
{
    T* ptr;
    size_t length;
}

Sprawdzanie granic odbywa się normalnie podczas indeksowania tablicy, ale jest usuwane podczas kompilacji -release. Tak więc w trybie wydania nie ma rzeczywistej różnicy wydajności między tablicami w C / C ++ i tablicami w D.

Tak, jedną z kluczowych optymalizacji jest:

sealed class Foo
{
}

W języku C # ta klasa nie może być nadtypem dla żadnego typu, więc można uniknąć sprawdzania tablicy typu Foo.

I na drugie pytanie, w F # tablice alternatywne nie są dozwolone (ale myślę, że kontrola pozostanie w CLR, chyba że okaże się to zbędne w optymalizacji w czasie wykonywania)

let a = [| "st" |]
let b : System.Object[] = a // Fails

https://stackoverflow.com/questions/7339013/array-covariance-in-f

Nieco powiązany problem to sprawdzanie granic tablic. To może być ciekawa (ale stara) lektura na temat optymalizacji przeprowadzonych w CLR (kowariancja jest również wymieniona 1 miejsce): http://blogs.msdn.com/b/clrcodegeneration/archive/2009/08/13/array-bounds -check-elimination-in-the-clr.aspx

Odpowiedź Java:

Rozumiem, że tak naprawdę nie przetestowałeś kodu, prawda? Zasadniczo 90% wszystkich dynamicznych rzutowań w Javie jest bezpłatnych, ponieważ JIT może je pominąć (szybki przykład powinien być tego dobrym przykładem), a reszta to jedna ld/cmp/brsekwencja, która jest absolutnie przewidywalna (jeśli nie, to dlaczego, do cholery, Twój kod rzuca wszystkie te dynamiczne wyjątki obsady?).

Obciążenie wykonujemy znacznie wcześniej niż rzeczywiste porównanie, gałąź jest poprawnie przewidywana w 99,9999% (utworzona statystyka!) Wszystkich przypadków, więc nie blokujemy potoku (zakładając, że nie uderzymy w pamięć obciążeniem, jeśli nie dobrze, co będzie zauważalne, ale i tak konieczne jest obciążenie). Stąd koszt wynosi 1 cykl zegara, JIT JIT nie może w ogóle uniknąć kontroli.

Jakieś koszty ogólne? Jasne, ale wątpię, czy kiedykolwiek to zauważysz ...

Aby wesprzeć moją odpowiedź, zobacz blog Dr. Cliff Click omawiający wydajność Java vs. C.

D nie zezwala na tablice kowariantne.

void main()
{
    class Foo {}
    Object[] a = new Foo[10];
}  

/* Error: cannot implicitly convert expression (new Foo[](10LU)) of type Foo[]
to Object[] */

Jak mówisz, byłoby to dziurą w systemie typów, aby to umożliwić.

Możesz zostać wybaczony za błąd, ponieważ ten błąd został właśnie naprawiony w najnowszym DMD, wydanym 13 grudnia.

Dostęp do tablicy w D jest tak samo szybki jak w C lub C ++.

Z testu, który zrobiłem na tanim laptopie, różnica między używaniem int[]a Integer[]wynosi około 1,0 ns. Różnica prawdopodobnie wynika z dodatkowej kontroli typu.

Zasadniczo obiekty są używane tylko dla logiki wyższego poziomu, gdy nie liczy się każda ns. Jeśli musisz zapisywać każdą ns, unikałbym używania konstrukcji wyższego poziomu, takich jak Obiekty. Same zadania prawdopodobnie będą bardzo małym czynnikiem w każdym prawdziwym programie. np. utworzenie nowego obiektu na tym samym komputerze to 5 ns.

Połączenia do porównania Prawdopodobnie będą znacznie droższe, szczególnie jeśli używasz złożonego obiektu, takiego jak String.

Pytałeś o inne współczesne języki OO? Cóż, Delphi unika tego problemu całkowicie, będąc stringprymitywnym, a nie obiektem. Tak więc tablica ciągów jest dokładnie tablicą ciągów i niczym więcej, a wszelkie operacje na nich są tak szybkie, jak to tylko możliwe, w kodzie natywnym, bez narzutu sprawdzania typu.

Jednak tablice łańcuchowe nie są używane bardzo często; Programiści Delphi faworyzują TStringListklasę. Przy minimalnym obciążeniu zapewnia zestaw metod grup strunowych, które są przydatne w tak wielu sytuacjach, że klasa została porównana do szwajcarskiego scyzoryka. Dlatego idiomatyczne jest używanie obiektu listy ciągów zamiast tablicy ciągów.

Podobnie jak w przypadku innych obiektów, problem nie istnieje, ponieważ w Delphi, podobnie jak w C ++, tablice nie są kowariantne, aby zapobiec opisywanym tutaj typom otworów systemowych.

czy też muszę żyć z faktem, że na przykład Quicksort zawsze wykonuje O (n log n) niepotrzebne kontrole środowiska wykonawczego?

Wydajność procesora nie jest monotoniczna, co oznacza, że ​​dłuższe programy mogą być szybsze niż te krótsze (jest to zależne od procesora i jest tak w przypadku popularnych architektur x86 i amd64). Jest więc możliwe, że program wykonujący sprawdzanie ograniczeń na tablicach jest w rzeczywistości szybszy niż program wywnioskowany z poprzedniego, usuwając te sprawdzanie powiązań.

Przyczyną tego zachowania jest to, że sprawdzanie granic modyfikuje wyrównanie kodu w pamięci, modyfikuje częstotliwość trafień w pamięci podręcznej itp.

Tak więc, żyj z faktem, że Quicksort zawsze wykonuje O (n log n) fałszywe kontrole i optymalizuje po profilowaniu.

Scala to język OO, który ma niezmienne, a nie kowariantne tablice. Jest ukierunkowany na JVM, więc nie ma tam żadnej wygranej wydajności, ale pozwala uniknąć błędnych cech wspólnych zarówno dla Javy, jak i C #, które zagrażają ich bezpieczeństwu typu ze względu na kompatybilność wsteczną.