Dlaczego ten kod Javy jest 6x szybszy od identycznego kodu C#?

Mam kilka różnych rozwiązań Project Euler problem 5 , ale różnica czasu wykonania między dwoma językami/platformami w tej konkretnej implementacji intryguje mnie. Nie robiłem żadnej optymalizacji z flagami kompilatora, po prostu javac (przez linię komend) i csc (przez Visual Studio).

Oto Kod Javy. Kończy się w 55ms. 

public class Problem005b
{
    public static void main(String[] args)
    {
        long begin = System.currentTimeMillis();
        int i = 20;
        while (true)
        {
            if (
                    (i % 19 == 0) &&
                    (i % 18 == 0) &&
                    (i % 17 == 0) &&
                    (i % 16 == 0) &&
                    (i % 15 == 0) &&
                    (i % 14 == 0) &&
                    (i % 13 == 0) &&
                    (i % 12 == 0) &&
                    (i % 11 == 0)
                )
            {
                break;
            }
            i += 20;
        }
        long end = System.currentTimeMillis();
        System.out.println(i);
        System.out.println(end-begin + "ms");
    }

}

Oto identyczny kod C#. Kończy się w 320ms 

using System;

namespace ProjectEuler05
{
    class Problem005
    {
        static void Main(String[] args)
        {
            DateTime begin = DateTime.Now;
            int i = 20;
            while (true)
            {
                if (
                        (i % 19 == 0) &&
                        (i % 18 == 0) &&
                        (i % 17 == 0) &&
                        (i % 16 == 0) &&
                        (i % 15 == 0) &&
                        (i % 14 == 0) &&
                        (i % 13 == 0) &&
                        (i % 12 == 0) &&
                        (i % 11 == 0)
                    )
                    {
                        break;
                    }
                i += 20;
            }
            DateTime end = DateTime.Now;
            TimeSpan elapsed = end - begin;
            Console.WriteLine(i);
            Console.WriteLine(elapsed.TotalMilliseconds + "ms");
        }
    }
}
Author: Zero Piraeus, 2011-05-10
Source

7 answers

Kluczem do Zbliżenia tych dwóch jest zapewnienie, że porównanie jest uczciwe.

Przede wszystkim zapewnienie, że koszty związane z uruchomieniem kompilacji debugowania, Ładowanie symboli pdb tak, jak to zrobiłeś.

Następnie należy upewnić się, że nie są naliczane koszty init. Oczywiście są to realne koszty i mogą mieć znaczenie dla niektórych osób, ale w tym przypadku interesuje nas sama pętla.

Następnie musisz poradzić sobie z zachowaniem platformy. Jeśli jesteś na 64bit komputer z systemem windows możesz być uruchomiony w trybie 32-bitowym lub 64-bitowym. W trybie 64-bitowym JIT różni się pod wieloma względami, często zmieniając uzyskany kod znacznie. W szczególności, zgaduję, że masz dostęp do dwukrotnie większej liczby rejestrów ogólnego przeznaczenia.

W tym przypadku wewnętrzna sekcja pętli, gdy naiwnie przetłumaczona na kod maszynowy, musiałaby załadować do rejestrów stałe używane w testach modulo. Jeśli nie ma wystarczających do przechowywania wszystkiego potrzebne w pętli, to musi je wypchnąć z pamięci. Nawet pochodzące z pamięci podręcznej level1 byłoby to znaczące trafienie w porównaniu do przechowywania tego wszystkiego w rejestrach.

W VS 2010 MS zmienił domyślny cel z anycpu na x86. Nie mam nic takiego jak zasoby lub wiedza klienta na temat MSFT, więc nie będę się starał zgadywać. Jednak każdy, kto patrzy na coś takiego jak analiza wydajności, którą robisz, powinien z pewnością spróbować obu.

Gdy te różnice są wyprasowane liczby wydają się o wiele bardziej rozsądne. Wszelkie dalsze różnice prawdopodobnie wymagają lepszego niż wykształcone domysły, zamiast tego potrzebowaliby zbadania rzeczywistych różnic w generowanym kodzie maszynowym.

Jest w tym kilka rzeczy, które myślę, że byłyby interesujące dla optymalizującego kompilatora.

  • ci, o których finnw już wspomniał:
    • opcja lcm interesująca, ale nie widzę, żeby kompilator przeszkadzał.
    • redukcja podziału do mnożenie i maskowanie.
      • Nie wiem wystarczająco dużo na ten temat, ale inni ludzie próbowali zauważ, że nazywają dzielnik na nowszych chipach Intela znacznie lepiej.
      • być może mógłbyś nawet zorganizować coś skomplikowanego, z SSE2.
      • z pewnością operacja modulo 16 jest gotowa do przekształcenia w maskę lub przesunięcie.
    • kompilator może zauważyć, że żaden z testów nie ma skutków ubocznych.
      • to może spekulacyjnie próbować aby ocenić kilka z nich na raz, na super skalarnym procesorze mogłoby to pompować rzeczy nieco szybciej, ale w dużym stopniu zależałoby od tego, jak dobrze układ kompilatorów współdziałał z silnikiem wykonawczym OO.
    • Jeśli ciśnienie rejestru było napięte, możesz zaimplementować stałe jako pojedynczą zmienną, ustawianą na początku każdej pętli, a następnie zwiększaną w miarę postępu.
[[0]} to wszystko są zupełne domysły i powinny być postrzegane jako próżne meandry. Jeśli chcesz wiedzieć zdemontować go.
 12
Author: ShuggyCoUk,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2011-05-11 20:55:02
  1. aby wykonać kod czasowy, należy użyć StopWatch klasy.
  2. ponadto, musisz uwzględnić JIT, runtime itp., Więc pozwól testowi uruchomić wystarczającą ilość razy (jak 10,000, 100,000 razy) i uzyskać jakąś średnią. Ważne jest, aby uruchamiać kod wiele razy, a nie program. Więc napisz metodę i zapętl w głównej metodzie, aby uzyskać pomiary.
  3. Usuń wszystkie elementy debugujące z zestawów i pozwól, aby Kod działał stand-alone w release build
 39
Author: Femaref,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2011-05-10 15:37:06

Istnieje kilka możliwych optymalizacji. Może Java JIT je wykonuje, a CLR nie.

Optymalizacja #1:

(x % a == 0) && (x % b == 0) && ... && (x % z == 0)

Jest równoważne 

(x % lcm(a, b, ... z) == 0)

Więc w twoim przykładzie łańcuch porównawczy może zostać zastąpiony przez 

if (i % 232792560 == 0) break;

(ale oczywiście, jeśli już obliczyłeś LCM, nie ma sensu uruchamiać programu w pierwszej kolejności!)

Optymalizacja #2:

To także "odpowiednik": {]} 

if (i % (14549535 * 16)) == 0 break;

Lub 

if ((i % 16 == 0) && (i % 14549535 == 0)) break;

Pierwszy podział można zastąpić maską i porównać do zera: 

if (((i & 15) == 0) && (i % 14549535 == 0)) break;

Drugi podział można zastąpić mnożeniem przez odwrotność modularną: 

final long LCM = 14549535;
final long INV_LCM = 8384559098224769503L; // == 14549535**-1 mod 2**64
final long MAX_QUOTIENT = Long.MAX_VALUE / LCM;
// ...
if (((i & 15) == 0) &&
    (0 <= (i>>4) * INV_LCM) &&
    ((i>>4) * INV_LCM < MAX_QUOTIENT)) {
    break;
}

Jest mało prawdopodobne, że JIT używa tego, ale nie jest to tak naciągane, jak mogłoby się wydawać - niektóre kompilatory C implementują w ten sposób odejmowanie wskaźników.

 23
Author: finnw,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2011-05-10 16:32:25

Jest to zbyt krótkie zadanie, aby zrobić odpowiedni czas. Musisz uruchomić oba co najmniej 1000 razy i zobaczyć, co się stanie. Wygląda na to, że uruchamiasz je z linii poleceń, w którym to przypadku prawdopodobnie porównujesz Kompilatory JIT dla obu. Spróbuj umieścić oba przyciski w prostym GUI i mieć tę pętlę przycisku na tym co najmniej kilkaset razy przed zwróceniem czasu, który upłynął. Nawet ignorując kompilację JIT, czas może być odrzucony przez ziarnistość systemu operacyjnego scheduler.

Oh, I z powodu JIT... policz tylko drugi wynik naciśnięcia przycisku. :)

 2
Author: darron,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2011-05-10 15:29:32

Być może dlatego, że budowa DateTimeobiektów jest znacznie droższa niż System.currentTimeMillis.

 1
Author: BertNase,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2011-05-10 15:17:54

W Javie używałbym systemu.nanoTime (). Każdy test, który trwa mniej niż 2 sekundy, powinien być przeprowadzany dłużej. Warto zauważyć, że Java jest całkiem dobra w optymalizacji nieefektywnego kodu lub kodu, który nic nie robi. Ciekawszym testem byłoby zoptymalizowanie kodu.

Próbujesz uzyskać rozwiązanie, które możesz określić bez użycia pętli. czyli problem, który byłby zrobiony lepiej w inny sposób.

Chcesz otrzymać iloczyn czynników od 11 do 20, które są 2,2,2,2,3,3,5,7,11,13,17,19. Pomnóż je razem i masz odpowiedź.

 1
Author: Peter Lawrey,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2011-05-10 15:38:49

(przeniesiony z OP)

Zmiana celu z x86 na anycpu obniżyła średni czas wykonania do 84ms na run, z 282ms. może powinienem podzielić to na drugi wątek?

UPDATE:
Dzięki Femaref poniżej who zwrócił uwagę na pewne problemy testowe i rzeczywiście, po jego sugestiach, czasy są niższe, co wskazuje, że czas konfiguracji maszyny wirtualnej był znaczący w Javie, ale prawdopodobnie nie w C#. W C# to symbole debugowania, które były znaczące.

Zaktualizowałem mój kod, aby uruchomić każdą pętlę 10,000 razy, a na końcu wypisać tylko średnie ms. Jedyną istotną zmianą, jaką dokonałem, była wersja C#, w której przełączyłem się na [StopWatch class] [3] w celu uzyskania większej rozdzielczości. Zatrzymałem się na milisekundach, bo to wystarczy.

Wyniki:
Zmiany w testach nie wyjaśniają, dlaczego Java jest (nadal) o wiele szybsza od C#. Wydajność C# była lepsza, ale można to wyjaśnić całkowicie usuwając debugowanie symbole. Jeśli przeczytasz[Mike Two] [4] i wymienię się komentarzami dołączonymi do tego OP, zobaczysz, że dostałem średnio ~280ms w pięciu uruchomieniach kodu C# po prostu przechodząc z debugowania na Release.

Liczby:

  • pętla zliczania 10 000 niezmodyfikowanego kodu Java dała mi średnio 45 MS (w porównaniu do 55 ms)
    • W przeciwieństwie do klasy StopWatch, w C# 10,000 pętli zliczania kodu dało mi średnio 282ms (w dół z 320ms)

wszystko to pozostawia różnicę niewyjaśnione. W rzeczywistości różnica się pogorszyła. Java przeszła z ~5.8 x szybsza do ~6.2 x szybsza.

 1
Author: Robert Harvey,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2017-05-23 12:26:09