Java: loop manual-tidak terbuka masih lebih cepat dari loop asli. Mengapa?

Pertimbangkan dua cuplikan kode berikut pada array dengan panjang 2:

boolean isOK(int i) {
    for (int j = 0; j < filters.length; ++j) {
        if (!filters[j].isOK(i)) {
            return false;
        }
    }
    return true;
}

dan

boolean isOK(int i) {
     return filters[0].isOK(i) && filters[1].isOK(i);
}

Saya akan berasumsi bahwa kinerja dua potong ini harus sama setelah pemanasan yang memadai.
Saya telah memeriksa ini menggunakan kerangka kerja pembandingan mikro JMH seperti yang dijelaskan misalnya di sini dan sini dan mengamati bahwa potongan kedua lebih dari 10% lebih cepat.

Pertanyaan: mengapa Java belum mengoptimalkan cuplikan pertama saya menggunakan teknik loop terbuka dasar?
Secara khusus, saya ingin memahami yang berikut:

1. Aku bisa dengan mudah menghasilkan kode yang optimal untuk kasus 2 filter dan masih dapat bekerja dalam kasus nomor lain dari filter (bayangkan pembangun sederhana):
   return (filters.length) == 2 ? new FilterChain2(filters) : new FilterChain1(filters). Bisakah JITC melakukan hal yang sama dan jika tidak, mengapa?
2. Dapatkah JITC mendeteksi bahwa ' filter.length == 2 ' adalah kasus yang paling sering dan menghasilkan kode yang optimal untuk kasus ini setelah beberapa pemanasan? Ini harus hampir seoptimal versi yang tidak dikontrol secara manual.
3. Dapatkah JITC mendeteksi bahwa contoh tertentu digunakan sangat sering dan kemudian menghasilkan kode untuk contoh khusus ini (yang diketahui bahwa jumlah filter selalu 2)?
   Memperbarui: mendapat jawaban bahwa JITC hanya berfungsi pada level kelas. OK mengerti.

Idealnya, saya ingin menerima jawaban dari seseorang dengan pemahaman mendalam tentang cara kerja JITC.

Detail menjalankan patok banding:

• Sudah mencoba versi terbaru Java 8 OpenJDK dan Oracle HotSpot, hasilnya mirip
• Bendera Java yang digunakan: -Xmx4g -Xms4g -server -Xbatch -XX: CICompilerCount = 2 (mendapat hasil yang sama tanpa bendera mewah juga)
• Ngomong-ngomong, saya mendapatkan rasio run time yang sama jika saya menjalankannya beberapa miliar kali dalam satu lingkaran (bukan melalui JMH), yaitu snippet kedua selalu jelas lebih cepat

Output patokan khas:

Mode Benchmark (filterIndex) Cnt Score Unit Kesalahan
LoopUnrollingBenchmark.runBenchmark 0 rata-rata 400 44,202 ± 0,224 ns / op
LoopMengontrolBenchmark.runBenchmark 1 avgt 400 38,347 ± 0,063 ns / op

(Baris pertama sesuai dengan snippet pertama, baris kedua - ke baris kedua.

Kode benchmark lengkap:

public class LoopUnrollingBenchmark {

    @State(Scope.Benchmark)
    public static class BenchmarkData {
        public Filter[] filters;
        @Param({"0", "1"})
        public int filterIndex;
        public int num;

        @Setup(Level.Invocation) //similar ratio with Level.TRIAL
        public void setUp() {
            filters = new Filter[]{new FilterChain1(), new FilterChain2()};
            num = new Random().nextInt();
        }
    }

    @Benchmark
    @Fork(warmups = 5, value = 20)
    @BenchmarkMode(Mode.AverageTime)
    @OutputTimeUnit(TimeUnit.NANOSECONDS)
    public int runBenchmark(BenchmarkData data) {
        Filter filter = data.filters[data.filterIndex];
        int sum = 0;
        int num = data.num;
        if (filter.isOK(num)) {
            ++sum;
        }
        if (filter.isOK(num + 1)) {
            ++sum;
        }
        if (filter.isOK(num - 1)) {
            ++sum;
        }
        if (filter.isOK(num * 2)) {
            ++sum;
        }
        if (filter.isOK(num * 3)) {
            ++sum;
        }
        if (filter.isOK(num * 5)) {
            ++sum;
        }
        return sum;
    }


    interface Filter {
        boolean isOK(int i);
    }

    static class Filter1 implements Filter {
        @Override
        public boolean isOK(int i) {
            return i % 3 == 1;
        }
    }

    static class Filter2 implements Filter {
        @Override
        public boolean isOK(int i) {
            return i % 7 == 3;
        }
    }

    static class FilterChain1 implements Filter {
        final Filter[] filters = createLeafFilters();

        @Override
        public boolean isOK(int i) {
            for (int j = 0; j < filters.length; ++j) {
                if (!filters[j].isOK(i)) {
                    return false;
                }
            }
            return true;
        }
    }

    static class FilterChain2 implements Filter {
        final Filter[] filters = createLeafFilters();

        @Override
        public boolean isOK(int i) {
            return filters[0].isOK(i) && filters[1].isOK(i);
        }
    }

    private static Filter[] createLeafFilters() {
        Filter[] filters = new Filter[2];
        filters[0] = new Filter1();
        filters[1] = new Filter2();
        return filters;
    }

    public static void main(String[] args) throws Exception {
        org.openjdk.jmh.Main.main(args);
    }
}

TL; DR Alasan utama perbedaan kinerja di sini tidak terkait dengan loop membuka gulungan. Ini lebih merupakan spekulasi tipe dan cache inline .

Strategi membuka gulungan

Bahkan, dalam terminologi HotSpot, loop tersebut diperlakukan sebagai dihitung , dan dalam kasus tertentu JVM dapat membuka gulungannya. Namun tidak dalam kasus Anda.

HotSpot memiliki dua strategi membuka gulungan lingkaran: 1) membuka gulungan secara maksimal, yaitu menghapus loop sama sekali; atau 2) rekatkan beberapa iterasi berurutan bersama.

Membuka gulungan maksimal dapat dilakukan, hanya jika jumlah iterasinya diketahui .

  if (!cl->has_exact_trip_count()) {
    // Trip count is not exact.
    return false;
  }

Namun, dalam kasus Anda, fungsi dapat kembali lebih awal setelah iterasi pertama.

Sebagian membuka gulungan mungkin dapat diterapkan, tetapi kondisi berikut ini berhenti membuka gulungan:

  // Don't unroll if the next round of unrolling would push us
  // over the expected trip count of the loop.  One is subtracted
  // from the expected trip count because the pre-loop normally
  // executes 1 iteration.
  if (UnrollLimitForProfileCheck > 0 &&
      cl->profile_trip_cnt() != COUNT_UNKNOWN &&
      future_unroll_ct        > UnrollLimitForProfileCheck &&
      (float)future_unroll_ct > cl->profile_trip_cnt() - 1.0) {
    return false;
  }

Karena dalam kasus Anda jumlah perjalanan yang diharapkan kurang dari 2, HotSpot menganggap tidak layak untuk membuka dua iterasi. Perhatikan bahwa iterasi pertama diekstraksi menjadi pra-loop ( pengoptimalan pengelupasan loop ), jadi membuka gulungan memang tidak terlalu buatan di sini.

Jenis spekulasi

Dalam versi yang belum dibuka, ada dua invokeinterfacebytecode yang berbeda . Situs-situs ini memiliki dua profil tipe yang berbeda. Penerima pertama selalu Filter1, dan penerima kedua selalu Filter2. Jadi, Anda pada dasarnya memiliki dua situs panggilan monomorfik, dan HotSpot dapat dengan sempurna menyejajarkan kedua panggilan - disebut "inline cache" yang memiliki rasio hit 100% dalam kasus ini.

Dengan loop, hanya ada satu invokeinterfacebytecode, dan hanya satu tipe profil yang dikumpulkan. HotSpot JVM melihat itu filters[j].isOK()disebut 86% kali dengan Filter1penerima dan 14% kali dengan Filter2penerima. Ini akan menjadi panggilan bimorfik. Untungnya, HotSpot secara spekulatif dapat menyejajarkan panggilan bimorfik juga. Ini sejalan kedua target dengan cabang bersyarat. Namun, dalam hal ini rasio hit akan paling banyak 86%, dan kinerja akan menderita dari cabang yang salah duga terkait pada tingkat arsitektur.

Keadaan akan lebih buruk, jika Anda memiliki 3 filter atau lebih yang berbeda. Dalam hal ini isOK()akan menjadi panggilan megamorphic yang HotSpot tidak dapat inline sama sekali. Jadi, kode yang dikompilasi akan berisi panggilan antarmuka yang benar yang memiliki dampak kinerja yang lebih besar.

Lebih lanjut tentang spekulatif inlining dalam artikel The Black Magic of (Java) Method Dispatch .

Kesimpulan

Untuk melakukan panggilan virtual / antarmuka sebaris, HotSpot JVM mengumpulkan profil tipe per panggilan bytecode. Jika ada panggilan virtual dalam satu lingkaran, hanya akan ada satu jenis profil untuk panggilan itu, tidak masalah apakah loop itu tidak terbuka atau tidak.

Untuk mendapatkan yang terbaik dari pengoptimalan panggilan virtual, Anda harus memisahkan loop secara manual, terutama untuk tujuan pemisahan tipe profil. HotSpot tidak dapat melakukan ini secara otomatis sejauh ini.

Loop yang disajikan kemungkinan berada di bawah kategori loop "tidak dihitung", yang merupakan loop yang jumlah iterasinya tidak dapat ditentukan pada waktu kompilasi atau pada saat run time. Bukan hanya karena argumen @Andreas tentang ukuran array tetapi juga karena kondisional secara acak break(yang dulu ada di benchmark Anda ketika saya menulis posting ini).

Kompiler canggih tidak mengoptimalkannya secara agresif, karena membuka gulungan yang tidak terhitung sering melibatkan duplikasi dan juga kondisi keluar loop, yang dengan demikian hanya meningkatkan kinerja run-time jika optimisasi kompiler berikutnya dapat mengoptimalkan kode yang tidak gulungan. Lihat makalah 2017 ini untuk detail di mana mereka membuat proposal cara membuka gulungan barang juga.

Dari berikut ini, bahwa asumsi Anda tidak berpendapat bahwa Anda melakukan semacam "membuka gulungan manual" dari loop. Anda mempertimbangkannya sebagai teknik membuka gulungan dasar untuk mengubah iterasi pada array dengan kondisional break ke &&ekspresi boolean berantai. Saya akan menganggap ini sebagai kasus yang agak istimewa dan akan terkejut menemukan pengoptimal hot-spot melakukan refactoring kompleks dengan cepat. Di sini mereka sedang mendiskusikan apa yang sebenarnya bisa dilakukan, mungkin referensi ini menarik.

Ini akan mencerminkan lebih dekat mekanisme membuka gulungan kontemporer dan mungkin masih jauh dari apa yang tampak seperti kode mesin terbuka:

if (! filters[0].isOK(i))
{
   return false;
} 
if(! filters[1].isOK(i))
{
   return false;
}
return true;

Anda menyimpulkan, bahwa karena satu bagian kode berjalan lebih cepat daripada bagian kode lainnya, loop tidak terbuka. Bahkan jika itu terjadi, Anda masih bisa melihat perbedaan runtime karena Anda membandingkan implementasi yang berbeda.

Jika Anda ingin mendapatkan kepastian lebih lanjut, ada penganalisa / visualisasi jitwatch dari operasi Jit yang sebenarnya termasuk kode mesin (github) (slide presentasi) . Jika ada sesuatu untuk dilihat pada akhirnya saya akan mempercayai mata saya sendiri lebih dari pendapat apa pun tentang apa yang JIT boleh atau tidak lakukan secara umum, karena setiap kasus memiliki kekhasannya. Di sini mereka khawatir tentang kesulitan untuk sampai pada pernyataan umum untuk kasus-kasus tertentu sejauh menyangkut JIT dan memberikan beberapa tautan menarik.

Karena sasaran Anda adalah runtime minimum, a && b && c ...formulir tersebut kemungkinan yang paling efisien, jika Anda tidak ingin bergantung pada harapan untuk membuka gulungan, setidaknya lebih efisien daripada yang disajikan sebelumnya. Tetapi Anda tidak dapat memilikinya dengan cara yang umum. Dengan komposisi fungsional java.util.Fungsi ada overhead besar lagi (setiap Fungsi adalah kelas, setiap panggilan adalah metode virtual yang perlu dikirim). Mungkin dalam skenario seperti itu mungkin masuk akal untuk menumbangkan tingkat bahasa dan menghasilkan kode byte khusus saat runtime. Di sisi lain &&logika membutuhkan percabangan dalam tingkat kode byte juga dan mungkin setara dengan if / return (yang juga tidak dapat dihasilkan tanpa overhead).