Dlaczego long jest wolniejszy niż int w x64 Java?

92

Używam systemu Windows 8.1 x64 z aktualizacją Java 7 45 x64 (bez zainstalowanej 32-bitowej wersji Java) na tablecie Surface Pro 2.

Poniższy kod zajmuje 1688 ms, gdy typ i jest długi i 109 ms, gdy i jest int. Dlaczego long (typ 64-bitowy) jest o rząd wielkości wolniejszy niż int na platformie 64-bitowej z 64-bitową maszyną JVM?

Moje jedyne spekulacje są takie, że procesorowi zajmuje więcej czasu, aby dodać 64-bitową liczbę całkowitą niż 32-bitową, ale wydaje się to mało prawdopodobne. Podejrzewam, że Haswell nie używa dodatków przenoszących tętnienia.

Przy okazji uruchamiam to w Eclipse Kepler SR1.

public class Main {

    private static long i = Integer.MAX_VALUE;

    public static void main(String[] args) {    
        System.out.println("Starting the loop");
        long startTime = System.currentTimeMillis();
        while(!decrementAndCheck()){
        }
        long endTime = System.currentTimeMillis();
        System.out.println("Finished the loop in " + (endTime - startTime) + "ms");
    }

    private static boolean decrementAndCheck() {
        return --i < 0;
    }

}

Edycja: Oto wyniki równoważnego kodu C ++ skompilowanego przez VS 2013 (poniżej), ten sam system. długi: 72265 ms int: 74656 ms Te wyniki były w 32-bitowym trybie debugowania.

W trybie wersji 64-bitowej: długi: 875 ms długi długi: 906 ms int: 1047 ms

Sugeruje to, że wynikiem, który zaobserwowałem, jest raczej dziwność optymalizacji JVM niż ograniczenia procesora.

#include "stdafx.h"
#include "iostream"
#include "windows.h"
#include "limits.h"

long long i = INT_MAX;

using namespace std;


boolean decrementAndCheck() {
return --i < 0;
}


int _tmain(int argc, _TCHAR* argv[])
{


cout << "Starting the loop" << endl;

unsigned long startTime = GetTickCount64();
while (!decrementAndCheck()){
}
unsigned long endTime = GetTickCount64();

cout << "Finished the loop in " << (endTime - startTime) << "ms" << endl;



}

Edycja: próbowałem tego ponownie w Java 8 RTM, bez znaczącej zmiany.

Techrocket9
źródło
8
Najbardziej prawdopodobnym podejrzanym jest konfiguracja, a nie procesor lub różne części maszyny JVM. Czy możesz wiarygodnie odtworzyć ten pomiar? Niepowtarzanie pętli, brak rozgrzewania JIT, używanie currentTimeMillis()uruchomionego kodu, który w trywialny sposób można całkowicie zoptymalizować itp. Cuchnie niewiarygodnymi wynikami.
1
Jakiś czas temu wykonywałem testy porównawcze, musiałem użyć longjako licznika pętli, ponieważ kompilator JIT zoptymalizował pętlę, gdy użyłem pliku int. Trzeba by spojrzeć na demontaż wygenerowanego kodu maszynowego.
Sam
7
To nie jest poprawny mikroznak i nie spodziewałbym się, że jego wyniki w jakikolwiek sposób odzwierciedlają rzeczywistość.
Louis Wasserman,
7
Wszystkie komentarze krytykujące OP za niepowodzenie w napisaniu prawidłowego mikroznaku Java są niewyobrażalnie leniwe. To jest rodzaj rzeczy, które bardzo łatwo jest rozgryźć, jeśli tylko spojrzysz i zobaczysz, co JVM robi z kodem.
tmyklebu,
2
@maaartinus: Zaakceptowana praktyka jest akceptowaną praktyką, ponieważ obejmuje listę znanych pułapek. W przypadku poprawnych testów porównawczych Java chcesz mieć pewność, że mierzysz odpowiednio zoptymalizowany kod, a nie zastępujesz go na stosie, i chcesz mieć pewność, że pomiary są na końcu czyste. OP znalazł zupełnie inny problem, a benchmark, który przedstawił, odpowiednio to wykazał. I, jak już wspomniano, przekształcenie tego kodu we właściwy test porównawczy Java w rzeczywistości nie usuwa tej dziwności. A czytanie kodu asemblera nie jest trudne.
tmyklebu

Odpowiedzi:

82

Moja JVM robi to w dość prosty sposób w pętli wewnętrznej, gdy używasz longs:

0x00007fdd859dbb80: test   %eax,0x5f7847a(%rip)  /* fun JVM hack */
0x00007fdd859dbb86: dec    %r11                  /* i-- */
0x00007fdd859dbb89: mov    %r11,0x258(%r10)      /* store i to memory */
0x00007fdd859dbb90: test   %r11,%r11             /* unnecessary test */
0x00007fdd859dbb93: jge    0x00007fdd859dbb80    /* go back to the loop top */

To oszukuje, trudne, kiedy używasz ints; Po pierwsze, jest pewna głupota, której nie rozumiem, ale wygląda jak konfiguracja dla rozwiniętej pętli:

0x00007f3dc290b5a1: mov    %r11d,%r9d
0x00007f3dc290b5a4: dec    %r9d
0x00007f3dc290b5a7: mov    %r9d,0x258(%r10)
0x00007f3dc290b5ae: test   %r9d,%r9d
0x00007f3dc290b5b1: jl     0x00007f3dc290b662
0x00007f3dc290b5b7: add    $0xfffffffffffffffe,%r11d
0x00007f3dc290b5bb: mov    %r9d,%ecx
0x00007f3dc290b5be: dec    %ecx              
0x00007f3dc290b5c0: mov    %ecx,0x258(%r10)   
0x00007f3dc290b5c7: cmp    %r11d,%ecx
0x00007f3dc290b5ca: jle    0x00007f3dc290b5d1
0x00007f3dc290b5cc: mov    %ecx,%r9d
0x00007f3dc290b5cf: jmp    0x00007f3dc290b5bb
0x00007f3dc290b5d1: and    $0xfffffffffffffffe,%r9d
0x00007f3dc290b5d5: mov    %r9d,%r8d
0x00007f3dc290b5d8: neg    %r8d
0x00007f3dc290b5db: sar    $0x1f,%r8d
0x00007f3dc290b5df: shr    $0x1f,%r8d
0x00007f3dc290b5e3: sub    %r9d,%r8d
0x00007f3dc290b5e6: sar    %r8d
0x00007f3dc290b5e9: neg    %r8d
0x00007f3dc290b5ec: and    $0xfffffffffffffffe,%r8d
0x00007f3dc290b5f0: shl    %r8d
0x00007f3dc290b5f3: mov    %r8d,%r11d
0x00007f3dc290b5f6: neg    %r11d
0x00007f3dc290b5f9: sar    $0x1f,%r11d
0x00007f3dc290b5fd: shr    $0x1e,%r11d
0x00007f3dc290b601: sub    %r8d,%r11d
0x00007f3dc290b604: sar    $0x2,%r11d
0x00007f3dc290b608: neg    %r11d
0x00007f3dc290b60b: and    $0xfffffffffffffffe,%r11d
0x00007f3dc290b60f: shl    $0x2,%r11d
0x00007f3dc290b613: mov    %r11d,%r9d
0x00007f3dc290b616: neg    %r9d
0x00007f3dc290b619: sar    $0x1f,%r9d
0x00007f3dc290b61d: shr    $0x1d,%r9d
0x00007f3dc290b621: sub    %r11d,%r9d
0x00007f3dc290b624: sar    $0x3,%r9d
0x00007f3dc290b628: neg    %r9d
0x00007f3dc290b62b: and    $0xfffffffffffffffe,%r9d
0x00007f3dc290b62f: shl    $0x3,%r9d
0x00007f3dc290b633: mov    %ecx,%r11d
0x00007f3dc290b636: sub    %r9d,%r11d
0x00007f3dc290b639: cmp    %r11d,%ecx
0x00007f3dc290b63c: jle    0x00007f3dc290b64f
0x00007f3dc290b63e: xchg   %ax,%ax /* OK, fine; I know what a nop looks like */

następnie sama rozwinięta pętla:

0x00007f3dc290b640: add    $0xfffffffffffffff0,%ecx
0x00007f3dc290b643: mov    %ecx,0x258(%r10)
0x00007f3dc290b64a: cmp    %r11d,%ecx
0x00007f3dc290b64d: jg     0x00007f3dc290b640

następnie kod rozłączenia dla rozwiniętej pętli, sam w sobie jest testem i prostą pętlą:

0x00007f3dc290b64f: cmp    $0xffffffffffffffff,%ecx
0x00007f3dc290b652: jle    0x00007f3dc290b662
0x00007f3dc290b654: dec    %ecx
0x00007f3dc290b656: mov    %ecx,0x258(%r10)
0x00007f3dc290b65d: cmp    $0xffffffffffffffff,%ecx
0x00007f3dc290b660: jg     0x00007f3dc290b654

Więc to idzie 16 razy szybciej dla ints, ponieważ JIT rozwinął intpętlę 16 razy, ale w ogóle jej nie rozwinął long.

Aby uzyskać kompletność, oto kod, który faktycznie wypróbowałem:

public class foo136 {
  private static int i = Integer.MAX_VALUE;
  public static void main(String[] args) {
    System.out.println("Starting the loop");
    for (int foo = 0; foo < 100; foo++)
      doit();
  }

  static void doit() {
    i = Integer.MAX_VALUE;
    long startTime = System.currentTimeMillis();
    while(!decrementAndCheck()){
    }
    long endTime = System.currentTimeMillis();
    System.out.println("Finished the loop in " + (endTime - startTime) + "ms");
  }

  private static boolean decrementAndCheck() {
    return --i < 0;
  }
}

Zrzuty montażowe zostały wygenerowane przy użyciu opcji -XX:+UnlockDiagnosticVMOptions -XX:+PrintAssembly. Zwróć uwagę, że musisz zepsuć swoją instalację JVM, aby ta działała również dla Ciebie; musisz umieścić jakąś losową bibliotekę współdzieloną dokładnie we właściwym miejscu, inaczej się nie powiedzie.

tmyklebu
źródło
9
OK, więc net-net nie oznacza, że longwersja jest wolniejsza, ale raczej intwersja jest szybsza. To ma sens. Prawdopodobnie nie włożono aż tyle wysiłku w tworzenie longwyrażeń optymalizacji JIT .
Hot Licks
1
... wybacz moją ignorancję, ale co to jest „funrolled”? Wydaje mi się, że nie mogę nawet poprawnie wygooglować tego terminu i dlatego po raz pierwszy musiałem kogoś zapytać, co oznacza słowo w Internecie.
BrianH
1
@BrianDHall gccużywa -fjako przełącznika wiersza poleceń dla „flagi”, a unroll-loopsoptymalizację włącza się mówiąc -funroll-loops. Po prostu używam „unroll” do opisania optymalizacji.
chrylis
4
@BRPocock: Kompilator Java nie może, ale JIT z pewnością może.
tmyklebu
1
Żeby było jasne, to nie "zabawiało" tego. Rozwinął go ORAZ przekonwertował rozwiniętą pętlę na i-=16, co oczywiście jest 16x szybsze.
Aleksandr Dubinsky
22

Stos JVM jest definiowany za pomocą słów , których rozmiar jest szczegółem implementacji, ale musi mieć co najmniej 32 bity szerokości. Program implementujący JVM może używać słów 64-bitowych, ale kod bajtowy nie może na tym polegać, dlatego operacje na wartościach longlub doublemuszą być obsługiwane ze szczególną ostrożnością. W szczególności instrukcje rozgałęzienia JVM integer są zdefiniowane dokładnie na typie int.

W przypadku twojego kodu demontaż jest pouczający. Oto kod bajtowy intwersji skompilowanej przez Oracle JDK 7:

private static boolean decrementAndCheck();
  Code:
     0: getstatic     #14  // Field i:I
     3: iconst_1      
     4: isub          
     5: dup           
     6: putstatic     #14  // Field i:I
     9: ifge          16
    12: iconst_1      
    13: goto          17
    16: iconst_0      
    17: ireturn       

Zwróć uwagę, że JVM załaduje wartość twojego static i(0), odejmie jeden (3-4), powieli wartość na stosie (5) i włoży ją z powrotem do zmiennej (6). Następnie wykonuje gałąź porównania z zerem i zwraca.

Wersja z rozszerzeniem longjest nieco bardziej skomplikowana:

private static boolean decrementAndCheck();
  Code:
     0: getstatic     #14  // Field i:J
     3: lconst_1      
     4: lsub          
     5: dup2          
     6: putstatic     #14  // Field i:J
     9: lconst_0      
    10: lcmp          
    11: ifge          18
    14: iconst_1      
    15: goto          19
    18: iconst_0      
    19: ireturn       

Po pierwsze, gdy maszyna JVM powiela nową wartość na stosie (5), musi zduplikować dwa słowa stosu. W twoim przypadku jest całkiem możliwe, że nie jest to droższe niż jego powielenie, ponieważ JVM może swobodnie używać 64-bitowego słowa, jeśli jest to wygodne. Jednak zauważysz, że logika gałęzi jest tutaj dłuższa. JVM nie ma instrukcji porównywania a longz zerem, więc musi włożyć stałą 0Lna stos (9), zrobić ogólne longporównanie (10), a następnie rozgałęzić wartość tego obliczenia.

Oto dwa prawdopodobne scenariusze:

  • Maszyna JVM dokładnie śledzi ścieżkę kodu bajtowego. W tym przypadku wykonuje więcej pracy w longwersji, wypychając i wstawiając kilka dodatkowych wartości, a te znajdują się na wirtualnym zarządzanym stosie , a nie na rzeczywistym stosie procesora wspomaganego sprzętowo. W takim przypadku po rozgrzewce nadal będzie widoczna znacząca różnica w wydajności.
  • JVM zdaje sobie sprawę, że może zoptymalizować ten kod. W takim przypadku optymalizacja praktycznie niepotrzebnej logiki wypychania / porównywania zajmuje więcej czasu. W takim przypadku po rozgrzewce zobaczysz bardzo małą różnicę w wydajności.

Zalecam napisanie poprawnego mikroznaku, aby wyeliminować efekt uruchomienia JIT, a także wypróbowanie tego z warunkiem końcowym, który nie jest zerowy, aby zmusić JVM do wykonania tego samego porównania, intktóre robi z long.

chrylis-ostrożnie optymistycznie-
źródło
1
@Katona Niekoniecznie. Szczególnie maszyny JVM HotSpot klienta i serwera to zupełnie różne implementacje, a Ilya nie wskazała wyboru serwera (domyślnie klient jest 32-bitowy).
chrylis
1
@tmyklebu Problem polega na tym, że benchmark mierzy kilka różnych rzeczy naraz. Użycie niezerowego warunku końcowego zmniejsza liczbę zmiennych.
chrylis
1
@tmyklebu Chodzi o to, że PO miał zamiar porównać prędkość przyrostów, ubytków i porównań między wartościami całkowitymi a długimi. Zamiast tego (zakładając, że ta odpowiedź jest poprawna) mierzyli tylko porównania i tylko względem 0, co jest przypadkiem szczególnym. Co więcej, sprawia, że ​​pierwotny benchmark wprowadza w błąd - wygląda na to, że mierzy trzy ogólne przypadki, podczas gdy w rzeczywistości mierzy jeden, konkretny przypadek.
yshavit
1
@tmyklebu Nie zrozum mnie źle, zagłosowałem za pytaniem, tą odpowiedzią i twoją odpowiedzią. Ale nie zgadzam się z twoim stwierdzeniem, że @chrylis dostosowuje wzorzec, aby przestać mierzyć różnicę, którą próbuje zmierzyć. OP może mnie poprawić, jeśli się mylę, ale nie wygląda na to, że próbują mierzyć tylko / przede wszystkim == 0, co wydaje się być nieproporcjonalnie dużą częścią wyników testu porównawczego. Wydaje mi się bardziej prawdopodobne, że OP próbuje zmierzyć bardziej ogólny zakres operacji, a ta odpowiedź wskazuje, że punkt odniesienia jest mocno wypaczony w stosunku do tylko jednej z tych operacji.
yshavit
2
@tmyklebu Wcale nie. Jestem za zrozumieniem przyczyn. Ale po ustaleniu, że jedną z głównych przyczyn jest to, że wzorzec był wypaczony, nie jest nieprawidłowa zmiana wzorca w celu usunięcia pochylenia, a także zagłębienie się i zrozumienie tego odchylenia (na przykład, że może to umożliwić bardziej wydajne kod bajtowy, który może ułatwić rozwijanie pętli itp.). Dlatego głosowałem za zarówno tą odpowiedzią (która zidentyfikowała przekrzywienie), jak i twoją (która zagłębia się w skośność bardziej szczegółowo).
yshavit
8

Podstawową jednostką danych w wirtualnej maszynie języka Java jest słowo. Wybór odpowiedniego rozmiaru słowa pozostaje po wdrożeniu maszyny JVM. W implementacji maszyny JVM należy wybrać minimalny rozmiar słowa wynoszący 32 bity. Może wybrać większy rozmiar słowa, aby zwiększyć wydajność. Nie ma też żadnego ograniczenia, że ​​64-bitowa JVM powinna wybierać tylko słowo 64-bitowe.

Podstawowa architektura nie przewiduje, że rozmiar słowa również powinien być taki sam. JVM odczytuje / zapisuje dane słowo po słowie. To jest powód, dlaczego to może być trwa dłużej dla długi niż int .

Tutaj możesz znaleźć więcej informacji na ten sam temat.

Vaibhav Raj
źródło
4

Właśnie napisałem test porównawczy za pomocą suwmiarki .

Te wyniki są dość spójne z oryginalnego kodu: a ~ 12x SpeedUp za korzystanie intprzez long. Z pewnością wygląda na to, że rozwija się pętla zgłoszona przez tmyklebu lub coś bardzo podobnego.

timeIntDecrements         195,266,845.000
timeLongDecrements      2,321,447,978.000

To jest mój kod; zauważ, że używa świeżo utworzonej migawki programu caliper, ponieważ nie mogłem wymyślić, jak kodować w porównaniu z ich obecną wersją beta.

package test;

import com.google.caliper.Benchmark;
import com.google.caliper.Param;

public final class App {

    @Param({""+1}) int number;

    private static class IntTest {
        public static int v;
        public static void reset() {
            v = Integer.MAX_VALUE;
        }
        public static boolean decrementAndCheck() {
            return --v < 0;
        }
    }

    private static class LongTest {
        public static long v;
        public static void reset() {
            v = Integer.MAX_VALUE;
        }
        public static boolean decrementAndCheck() {
            return --v < 0;
        }
    }

    @Benchmark
    int timeLongDecrements(int reps) {
        int k=0;
        for (int i=0; i<reps; i++) {
            LongTest.reset();
            while (!LongTest.decrementAndCheck()) { k++; }
        }
        return (int)LongTest.v | k;
    }    

    @Benchmark
    int timeIntDecrements(int reps) {
        int k=0;
        for (int i=0; i<reps; i++) {
            IntTest.reset();
            while (!IntTest.decrementAndCheck()) { k++; }
        }
        return IntTest.v | k;
    }
}
tucuxi
źródło
1

Dla przypomnienia, ta wersja wykonuje prymitywną „rozgrzewkę”:

public class LongSpeed {

    private static long i = Integer.MAX_VALUE;
    private static int j = Integer.MAX_VALUE;

    public static void main(String[] args) {

        for (int x = 0; x < 10; x++) {
            runLong();
            runWord();
        }
    }

    private static void runLong() {
        System.out.println("Starting the long loop");
        i = Integer.MAX_VALUE;
        long startTime = System.currentTimeMillis();
        while(!decrementAndCheckI()){

        }
        long endTime = System.currentTimeMillis();

        System.out.println("Finished the long loop in " + (endTime - startTime) + "ms");
    }

    private static void runWord() {
        System.out.println("Starting the word loop");
        j = Integer.MAX_VALUE;
        long startTime = System.currentTimeMillis();
        while(!decrementAndCheckJ()){

        }
        long endTime = System.currentTimeMillis();

        System.out.println("Finished the word loop in " + (endTime - startTime) + "ms");
    }

    private static boolean decrementAndCheckI() {
        return --i < 0;
    }

    private static boolean decrementAndCheckJ() {
        return --j < 0;
    }

}

Całkowity czas poprawia się o około 30%, ale stosunek między nimi pozostaje mniej więcej taki sam.

Hot Licks
źródło
@TedHopp - próbowałem zmienić limity pętli w moim i pozostały one zasadniczo niezmienione.
Hot Licks
@ Techrocket9: Otrzymuję podobne liczby (20 intrazy szybciej) z tym kodem.
tmyklebu
1

Do akt:

jeśli używam

boolean decrementAndCheckLong() {
    lo = lo - 1l;
    return lo < -1l;
}

(zmieniono „l--” na „l = l - 1l”) długa wydajność poprawia się o ~ 50%

R.Moeller
źródło
0

Nie mam 64-bitowej maszyny do testowania, ale dość duża różnica sugeruje, że działa coś więcej niż tylko nieco dłuższy kod bajtowy.

Widzę bardzo bliskie czasy dla long / int (4400 vs 4800 ms) na moim 32-bitowym 1.7.0_45.

To tylko przypuszczenie , ale mocno podejrzewam, że jest to efekt kary za niewspółosiowość pamięci. Aby potwierdzić / zaprzeczyć podejrzeniu, spróbuj dodać publiczny static int dummy = 0; przed oświadczeniem i. Spowoduje to obniżenie i o 4 bajty w układzie pamięci i może sprawić, że będzie odpowiednio wyrównany w celu uzyskania lepszej wydajności. Potwierdzono, że nie powoduje problemu.

EDYTOWAĆ: Powodem tego jest to, że maszyna wirtualna może nie zmieniać kolejności pól w wolnym czasie, dodając wypełnienie dla optymalnego wyrównania, ponieważ może to kolidować z JNI (Nie dotyczy).

Durandal
źródło
VM pewnością jest dozwolone, aby zmienić kolejność pól i dodać wyściółką.
Hot Licks
JNI musi uzyskiwać dostęp do obiektów za pomocą tych irytujących, powolnych metod dostępu, które i tak wymagają kilku nieprzezroczystych uchwytów, ponieważ GC może się zdarzyć podczas działania kodu natywnego. Zmiana kolejności pól i dodanie dopełnienia jest bardzo darmowe.
tmyklebu