Kecepatan {n} kali lebih cepat daripada C

 (owen.cafe)
1 poin oleh GN⁺ 2023-07-07 | 1 komentar | Bagikan ke WhatsApp
  • Bahkan untuk loop C yang kecil, keluaran compiler tidak selalu yang terbaik; setelah menyesuaikan assembly x86_64 secara langsung, versi tanpa percabangan kondisional menjadi 6,73 kali lebih cepat daripada keluaran clang
  • Fungsi target memproses karakter dalam string dengan aturan 's' sebagai +1, 'p' sebagai -1, dan '\0' sebagai akhir; keluaran clang 16 membagi alur ini menjadi 3 percabangan kondisional
  • Setelah mengubah urutan percabangan, menata ulang basic block, dan mengganti lompatan dengan aritmetika, waktu eksekusi turun dari 3,23 detik menjadi 2,87 detik, dan pada tahap ini mencapai kecepatan yang sama dengan GCC 12
  • Versi tercepat menggunakan cmove untuk memilih nilai tambah per karakter di antara 0, 1, dan -1, lalu selalu menjalankan add, sehingga mencatat 0,48 detik dengan throughput 1,94GiB/s
  • Benchmark dijalankan pada AMD Ryzen 5 5625U dan Linux 6.1.33 dengan memproses daftar 1 juta karakter 'p'/'s' acak sebanyak 1000 kali, dan memakai hasil terbaik dari beberapa kali eksekusi

Fungsi uji dan keluaran compiler

  • Fungsi target menambah pointer string satu per satu sambil memperbarui integer res sesuai karakter
    • 's': res += 1
    • 'p': res -= 1
    • '\0': mengembalikan res
    • karakter lain: tidak berubah
  • Karena fungsinya kecil, titik awalnya adalah ekspektasi bahwa gcc atau clang bisa mengoptimalkannya dengan cukup baik, mungkin bahkan optimal
  • Assembly awal yang dihasilkan clang membagi empat kasus itu menjadi tiga percabangan kondisional (je, je, jne)
    • dimulai dengan res = 0
    • membaca karakter lalu memeriksa dulu apakah itu '\0'
    • kemudian membandingkan dengan 'p' dan 's'
  • Hasil awal clang
    • Waktu eksekusi: 3,23 detik
    • Throughput: 295,26MiB/s
  • GCC menghasilkan kode yang sedikit lebih banyak, tetapi sedikit lebih cepat

Memeriksa karakter yang umum lebih dulu daripada kondisi akhir yang jarang

  • Loop hanya berakhir saat menemukan karakter null-terminator '\0', dan dalam fungsi ini null-terminator muncul paling banyak satu kali
  • Keluaran clang memeriksa '\0' paling dulu, sehingga untuk setiap karakter 'p' dan 's' kondisi akhir diperiksa terlebih dahulu
  • Perubahan manual pertama adalah membalik urutan perbandingan agar 'p' dan 's' diperiksa lebih dulu
  • Hasil
    • Waktu eksekusi: 3,10 detik
    • Peningkatan kecepatan: 1,04 kali
    • Throughput: 307,64MiB/s

Menata ulang basic block dan mengurangi lompatan

  • Dua kasus yang umum, 'p' dan 's', sama-sama melompat kembali ke awal loop, jadi percabangan bisa dikurangi dengan menempatkan salah satu blok di atas loop
  • Jika blok 's' diletakkan tepat sebelum loop, setelah memproses 's' eksekusi bisa langsung mengalir masuk ke loop tanpa lompatan tambahan
  • Sebagai gantinya, saat fungsi mulai perlu ada satu lompatan ke loop untuk melewati blok 's'
    • lompatan saat awal fungsi hanya terjadi sekali
    • karakter 's' bisa muncul berkali-kali, jadi ini diperlakukan sebagai trade-off yang masuk akal
  • Hasil
    • Waktu eksekusi: 2,98 detik
    • Peningkatan kecepatan total: 1,08 kali
    • Throughput: 320,02MiB/s

Menghapus satu lompatan tak bersyarat dengan aritmetika

  • Untuk menghilangkan jmp tak bersyarat yang kembali ke loop dari blok p:, digunakan aritmetika
  • Satu kali pengurangan bisa dibuat setara dengan sub eax, 2 lalu inc eax, sehingga setelah memproses 'p' eksekusi mengalir ke blok 's'
  • Dengan cara ini, satu lagi instruksi percabangan berhasil dihapus
  • Hasil
    • Waktu eksekusi: 2,87 detik
    • Peningkatan kecepatan total: 1,12 kali
    • Throughput: 332,29MiB/s
  • Pada titik ini performanya sama dengan kode yang dihasilkan GCC 12
    • Kode GCC 12 juga berjalan dalam 2,87 detik
    • Versi yang ditulis manual memiliki 13 instruksi
    • Keluaran GCC memiliki 19 instruksi
    • Kode GCC tampaknya melakukan unroll loop dan sampai batas tertentu menggunakan ulang case block

Mengganti percabangan kondisional dengan cmove

  • Jika percabangan kondisional adalah bottleneck, maka percabangan itu sendiri bisa dihapus tanpa bergantung pada branch predictor
  • Versi tercepat menggunakan cmove, yaitu conditional move jika sama
  • Aturan kerjanya sederhana
    • nilai default adalah 0
    • jika karakter saat ini adalah 's', nilainya 1
    • jika karakter saat ini adalah 'p', nilainya -1
    • pada setiap iterasi, nilai yang dipilih selalu ditambahkan ke res
  • Pendekatan ini menghilangkan banyak panah pada control-flow graph
  • Hasil
    • Waktu eksekusi: 0,48 detik
    • Peningkatan kecepatan total: 6,73 kali
    • Throughput: 1,94GiB/s
  • Pada assembly untuk loop C yang ringkas dan ditulis langsung, optimisasi yang tidak diotomatisasi compiler ini menghasilkan peningkatan kecepatan lebih dari 6 kali

Upaya menghemat register dan eksperimen tambahan yang gagal

  • Juga dicoba versi yang memakai sete pada x86_64 untuk mengatur register 1-byte secara kondisional menjadi 0 atau 1
  • Versi ini menghilangkan penggunaan r8d, tetapi lebih lambat daripada versi yang hanya memakai cmov
  • Hasil
    • Waktu eksekusi: 0,51 detik
    • Peningkatan kecepatan total: 6,33 kali
    • Throughput: 1,83GiB/s
  • Menggunakan register lebih sedikit atau operasi 8-bit alih-alih operasi 32-bit ternyata tidak membuatnya lebih cepat
  • Percobaan tambahan juga menurunkan performa
    • unroll loop pada versi terbaik: lebih lambat
    • menyelaraskan awal loop ke batas 16 byte: lebih lambat
    • di GNU assembler, menambahkan .align <bytes> sebelum label dapat menyisipkan nop

Lingkungan benchmark dan kode

  • Daftar kode tersedia di GitHub
  • Lingkungan benchmark
    • OS: Linux 6.1.33
    • CPU: AMD Ryzen 5 5625U with Radeon Graphics
    • CPU family 25, 6 core, 2 thread per core, 1 socket
    • clang: 16.0.1
    • gcc: 12.2.0
  • Versi C dikompilasi dengan -march=native agar dapat menghasilkan kode yang sesuai dengan CPU tertentu
  • Benchmark menggunakan daftar 1 juta karakter acak yang terdiri dari 'p' dan 's'
    • setiap versi fungsi memproses daftar ini 1000 kali
    • setiap versi dijalankan beberapa kali dan hasil terbaik dipilih
  • Artikel lanjutan ditautkan sebagai part two

Bacaan terkait

1 komentar

 
GN⁺ 2023-07-07
Opini Hacker News

  • Kesimpulan yang benar lebih dekat ke jump bisa jauh lebih lambat daripada aritmetika kondisional, bukan assembly tulis tangan 6 kali lebih cepat daripada C
    Bahkan di C, tanpa memakai switch dan cukup menanganinya dengan satu atau dua if, efek yang sama bisa didapat dengan mudah. Setelah fungsi C diubah menjadi pola seperti tambah jika s, kurang jika p, dan selesai jika \0, kecepatannya naik 5,5 kali lipat, dan pada contoh eksekusi turun dari 3,58 detik menjadi 0,65 detik

    • Bagus. Di bagian 2, C ditulis ulang lagi dan memperoleh peningkatan kecepatan 12x: https://owen.cafe/posts/the-same-speed-as-c/
      Seperti yang dikatakan orang lain, setelah input disesuaikan algoritmenya juga bisa divektorisasi. Saya melihat ini sebagai latihan edukatif, dan sungguh berharap tidak sampai turun ke assembly tanpa alasan yang cukup kuat
    • Pernyataan jump lebih lambat daripada aritmetika kondisional benar jika jump tersebut tidak bisa diprediksi. Jika jump dapat diprediksi, jump justru lebih cepat
      Linus juga pernah menulis panjang lebar bahwa cmov tidak berguna pada branch yang bisa diprediksi: https://yarchive.net/comp/linux/cmov.html
    • Penasaran menggunakan versi GCC yang mana. Di Ubuntu dan Windows hasil performanya sama, dan pada gcc (Ubuntu 9.4.0-1ubuntu1~20.04.1) 9.4.0, lone dan ltwo sama-sama sekitar 3,58 detik
    • Saya penasaran apakah mengganti switch menjadi beberapa if selalu lebih cepat. Saya juga ingin tahu mulai dari berapa banyak kemungkinan switch menjadi lebih cepat, dan jika konsisten, sepertinya ini seharusnya masuk ke optimisasi compiler
    • Rasanya compiler juga semestinya bisa melakukan transformasi sebesar ini

  • Menurut saya kode aslinya tidak ditulis dengan cara yang ramah compiler. Jika ditulis seperti result += *s == 's'; result -= *s == 'p';, compiler akan menghasilkan kode sete/cmov tanpa branch yang sesuai, dan kecepatannya hampir sama dengan assembly yang dioptimalkan dalam artikel
    Hanya saja compiler tidak melakukan unrolling loop atau vektorisasi. Jika ukuran string dilewatkan terpisah sehingga iterasi berjalan sambil mengetahui size, compiler bisa mengetahui ukuran loop lalu melakukan unrolling, dan jika memungkinkan juga memakai instruksi AVX-512. Pada input besar ini jauh lebih cepat, meski saya malas membenchmark sendiri. Jika Anda programmer C yang tidak melacak panjang string, silakan saja, tetapi menurut saya sungguh tidak boleh begitu: https://godbolt.org/z/rde51zMd8

    • Versi yang ramah compiler ada di bagian 2: https://owen.cafe/posts/the-same-speed-as-c/
      Versi itu mencapai 3.88GiB/s. Saya sengaja tidak sampai ke vektorisasi; saya ingin menjaga cakupan masalah tetap kecil sambil menunjukkan tip dan trik assembly dalam artikel. Nanti masih ada ruang untuk menulis artikel lanjutan tentang memberi padding pada string input dan melakukan vektorisasi pada algoritme
    • Ada satu baris penting yang hilang dari kodenya: /* DON’T REFACTOR THIS FOR READABILITY IT WILL SLOW DOWN */
    • Di Nim tampaknya juga bisa terpicu dengan cara berikut: aktifkan {.overflowChecks:off.}, lalu iterasi input dan tambahkan jika 's' == c, kurangi jika 'p' == c
      Di Apple M1 ada peningkatan kecepatan sekitar 5x, dan saat pemeriksaan overflow tetap aktif, hasilnya hanya sekitar 2x lebih cepat dibanding versi C dasar. Selalu bagus untuk mengetahui pola yang efektif dalam memicu optimisasi SIMD
    • Apakah maksud “sungguh tidak boleh begitu” adalah bahwa kita tidak boleh tidak melacak panjang string?

  • Dari sudut pandang yang lebih dekat ke pakar optimisasi, saya mungkin akan menyelesaikan masalah ini dengan cara yang sepenuhnya berbeda. Di komputer saya, versi C awal memproses 389MB per detik, dan jika assembly dalam artikel memberi peningkatan 6,2x yang sama, itu berarti sekitar 2,4GB per detik
    Pada buffer panjang, versi C++ ini menembus 24GB per detik di komputer saya: https://gist.github.com/Const-me/3ade77faad47f0fbb0538965ae7...
    Tanpa assembly, berbasis intrinsic AVX2, kecepatannya 61x lebih tinggi dibanding versi asli

    • Menarik. Daripada menyimpan counter di register ymm, sepertinya prolog bisa divektorisasi memakai movemask dan popcnt
      Ini kode yang belum diuji jadi masih perlu benchmark, tetapi tampaknya bisa didekati dengan membuat mask s, p, dan \0, lalu memakai tzcnt dan bzhi untuk menghitung bit sampai akhir string
    • Sekadar penasaran, saya ingin tahu apakah ini juga bisa dilakukan dengan std::experimental::simd: https://en.cppreference.com/w/cpp/experimental/simd
    • Akan bagus jika ini ditulis ulang dalam bentuk yang kompatibel dengan repositori @414owen
    • Saya penasaran materi yang bagus untuk belajar dan berlatih AVX

  • Kode ini tampaknya memang sangat cocok untuk SIMD. Jika prototipenya bisa diubah agar menerima panjang eksplisit, akan mudah membaca dan memproses 16 byte sekaligus
    Hasil perbandingannya bisa langsung dijumlahkan dan dikurangkan, dan mungkin memang layak hanya dengan memanggil strlen() di awal fungsi untuk mendapatkan panjang eksplisit

  • Saya sempat membuat implementasi vektorisasi RISC-V dengan cepat. Pendekatannya membaca string dengan rvv, mencari posisi \0, lalu menghitung jumlah s dan p dengan vcpop
    Di Mangopi MQ Pro (C906, rv64gc + rvv 0.7.1, panjang vektor 128 bit), switch mencapai 0,19 Bytes/Cycle, implementasi C berbasis tabel 0,17 Bytes/Cycle, dan rvv 1,57 Bytes/Cycle, lalu turun ke 1,35 setelah sekitar 30KiB. Jika pointer disejajarkan ke halaman dan vl tidak lebih besar dari ukuran halaman, bisa mencapai 2/1,7 Bytes/Cycle

    • Agar benar-benar tepat, load-nya harus berupa fault-only-first load. rvv punya fitur ini; kalau tidak, bisa gagal saat byte nol berada tepat sebelum akhir memori yang dialokasikan

  • Ini tampaknya sifat khas arsitektur x86. Karena biaya untuk tidak melakukan branch sangat murah, branch jadi terlihat relatif mahal: https://wordsandbuttons.online/challenge_your_performance_in...
    Namun pada prosesor lain belum tentu begitu: https://wordsandbuttons.online/using_logical_operators_for_l...
    Pertanyaan yang lebih besar adalah mengapa C dibutuhkan secara umum. Jika ingin menyetel secara manual agar berjalan sebaik mungkin pada perangkat keras tertentu, maka C adalah alat yang salah, dan yang dibutuhkan adalah assembly serta sistem makro yang layak. Tujuan awal C adalah mempermudah pemindahan kode level sistem dari satu platform ke platform lain, dan hilangnya efisiensi dalam proses itu memang sudah diharapkan. Ini mirip menulis puisi Hindi dalam Esperanto lalu menerjemahkannya otomatis ke bahasa yang diinginkan, alih-alih menerjemahkan puisi Hindi ke Urdu. Anda tidak akan mendapatkan dua puisi yang hebat, tetapi akan cepat mendapatkan dua terjemahan berkualitas rendah, dan itulah peran C

  • Jika dibangun dengan FDO/PGO, branch dan penataan ulang blok memang bisa terjadi. Tanpa FDO, kompiler tidak tahu seberapa sering tiap branch akan dipilih. Dalam beberapa kasus, FDO juga bisa mengaktifkan cmov
    Namun apakah cmov lebih efektif daripada test/jump biasa sangat bergantung pada seberapa bisa diprediksinya branch, dan biasanya cmov bekerja lebih baik ketika branch sangat sulit diprediksi. Jika cmov membuatnya 6 kali lebih cepat, saya menduga input pengujiannya berupa string acak yang hampir seluruhnya terdiri dari s dan p. Itu bukan salah, tetapi tulisan itu terasa agak menyesatkan karena memanfaatkan sifat data yang tidak disebutkan secara eksplisit dan mengkhususkan benchmark untuk itu

    • Kode pengujian ada di sini: https://github.com/414owen/blog-code/blob/master/02-the-same...
      Memilih 's' atau 'p' secara acak, dan selain 's', 'p', serta null terminator, karakter lain tidak mungkin muncul. Jika sifat input ini diketahui, optimisasi yang terlalu pintar seperti result += (1 | *s++) - 'r'; juga dimungkinkan. Kodenya terlalu cerdik, tetapi ini menunjukkan dengan sangat jelas inti soal memanfaatkan sifat data
    • Di dalam string, '\0' hanya bisa ditemui paling banyak sekali karena fungsi akan mengembalikan nilai saat itu, sedangkan karakter lain bisa muncul berkali-kali. Informasi ini tampaknya bisa diakses kompiler bahkan tanpa PGO
      Tentu PGO membantu, dan di komputer saya hasilnya 2,80 detik, lebih baik daripada kode di akhir bagian Rearranging blocks. Inputnya dijelaskan di Benchmarking setup dan juga ada di repositorinya: https://github.com/414owen/blog-code/blob/master/01-six-time...
      Di bagian 2 yang ditautkan di bawah artikel, kode C dibuat secepat mungkin dan mengalahkan semua assembly di artikel ini. Saya tidak pernah bilang menulis assembly pasti ide yang bagus; saya menganggap optimisasi dan menafsirkan output kompiler sebagai tantangan yang menarik sekaligus kesempatan belajar yang baik

  • Sepertinya saya membuat versi yang lebih cepat daripada artikel ini dan artikel lanjutannya. Namun ada biayanya, yaitu versi ini dikhususkan untuk kasus string yang hanya terdiri dari 's' dan 'p'
    Karena benchmark juga hanya menguji string yang terdiri dari 's' dan 'p', menurut saya ini tetap adil. Intinya, saat karakter berikutnya adalah s, kita ingin menambah res sebanyak 1, tetapi res += c - 'r' gagal karena bernilai 1 untuk s namun -2 untuk p. Namun jika 'p' - 'r' dipandang sebagai bilangan tak bertanda, akan terjadi underflow sehingga carry flag disetel, dan adc pada x64 menjumlahkan dua register bersama carry flag. Jadi dua cmp, cmov bisa diganti dengan satu sub, adc. Versi ini 1,08 kali lebih cepat daripada versi C di artikel lanjutan, dan 1,66 kali lebih cepat daripada x64-7 yang lama. Tentu saja ini masih bisa ditingkatkan lagi dengan SWAR/SIMD

    • Pendekatan yang menarik. Sepertinya saya seharusnya menjelaskan bahwa assembly yang agak sederhana di 02-the-same-speed-as-c/loop-5.x64.s adalah versi tercepat yang saya miliki
      Di komputer saya, loop-5.x64.s menghasilkan 0,244 detik, sedangkan implementasi di atas 0,422 detik. Saya tidak tahu persis mengapa perbedaannya sebesar itu, karena secara tampilan implementasi di atas terlihat lebih cepat. Jadi memang harus selalu dibenchmark pada perangkat keras yang benar-benar akan menjalankannya
    • Cara yang lebih sederhana adalah menjumlahkan semua elemen array lalu di akhir mengurangkan 'p' * len, kemudian membaginya dengan ('s' - 'p') untuk mendapatkan jumlah s. Jumlah p adalah len - s_count
      Penjumlahan awal juga mudah divektorkan. Jika tidak ada kesalahan, ini seharusnya bekerja, dan satu-satunya masalah adalah kemungkinan overflow pada akumulasi. Saya tidak cukup termotivasi untuk membenchmarknya sendiri. Edit: saya melewatkan bagian yang berkurang saat melihat s, jadi hasil akhirnya adalah p_count - s_count

  • strlen() kemungkinan sudah diimplementasikan dengan cukup cepat, dan jika ukuran buffer diketahui, kompiler bisa melakukan vektorisasi otomatis pada loop internal
    Memang, kode len = strlen(buf) lalu loop for yang menambahkan (buf[i] == 's') - (buf[i] == 'p') akan divektorkan otomatis: https://gcc.godbolt.org/z/qYfadPYoq

  • Dulu saya pernah menulis decoder UTF-8 Common Lisp yang menargetkan SBCL. Sebenarnya sudah ada decoder bawaan, jadi ini hanya untuk latihan
    Selain optimisasi mudah yang jelas, hampir semua peningkatan performa datang dari menata ulang kode agar kompiler menghasilkan instruksi cmov* alih-alih branch

    • Saya penasaran contoh bagaimana Anda mengubah kodenya. Dan apakah Anda berulang kali melakukan disassembly fungsi untuk melihat apakah instruksi yang benar digunakan, atau justru memastikan peningkatannya benar-benar nyata lewat benchmark
    • Jika branch bisa diprediksi dengan benar, branch kemungkinan besar lebih cepat daripada conditional move. Ini karena branch tidak menambah panjang critical path
      Decoder UTF-8 biasanya banyak dijalankan pada input yang seluruhnya ASCII. Saya penasaran input seperti apa yang dipakai untuk benchmark