Apa perbedaan kinerja antara bilangan bulat ditandatangani dan ditandatangani? [Tutup]

42

Saya menyadari kinerja hit ketika mencampur int ditandatangani dengan pelampung.

Apakah lebih buruk untuk mencampur int unsigned dengan float?

Apakah ada hit ketika pencampuran ditandatangani / tidak ditandatangani tanpa mengapung?

Apakah ukuran yang berbeda (u32, u16, u8, i32, i16, i8) berpengaruh pada kinerja? Di platform mana?

Luis
sumber
2
Saya telah menghapus teks / tag khusus PS3, karena ini adalah pertanyaan yang bagus tentang arsitektur apa pun, dan jawabannya berlaku untuk semua arsitektur yang memisahkan bilangan bulat dan register titik mengambang, yang secara praktis semuanya.

Jawaban:

36

Denda besar dari pencampuran int (dalam bentuk apa pun) dan mengapung adalah karena ini ada dalam set register yang berbeda. Untuk berpindah dari satu set register ke set register yang lain, Anda harus menulis nilainya ke memori dan membacanya kembali, yang menimbulkan kios penarik beban .

Terjadi di antara berbagai ukuran atau keikutsertaan int membuat semuanya dalam set register yang sama, sehingga Anda terhindar dari penalti besar. Mungkin ada penalti yang lebih kecil karena perpanjangan tanda tangan, dll. Tetapi ini jauh lebih kecil dari pada load-hit-store.

selion
sumber
Artikel yang Anda tautkan menyatakan bahwa Prosesor Sel PS3 merupakan pengecualian untuk ini karena ternyata semuanya disimpan dalam set register yang sama (dapat ditemukan kira-kira di tengah artikel atau mencari "Sel").
bummzack
4
@bummzack: Itu hanya berlaku untuk SPE, bukan APD; SPE memiliki lingkungan titik apung yang sangat, eh, istimewa, dan para pemainnya masih relatif mahal. Juga, biayanya masih sama untuk bilangan bulat yang ditandatangani vs. yang tidak ditandatangani.
Itu artikel yang bagus dan penting untuk mengetahui tentang LHS (dan saya memilihnya untuk itu) tetapi pertanyaan saya adalah tentang hukuman terkait tanda itu. Saya tahu ini kecil dan mungkin dapat diabaikan, tetapi saya masih ingin melihat beberapa bilangan real atau referensi tentang mereka.
Luis
1
@Luis - Saya mencoba menemukan beberapa dokumentasi publik tentang ini tetapi tidak dapat menemukannya saat ini. Jika Anda memiliki akses ke dokumentasi Xbox360, ada whitepaper yang bagus oleh Bruce Dawson yang mencakup sebagian dari ini (dan ini sangat bagus secara umum).
celion
@Luis: Saya telah memposting analisis di bawah ini, tetapi jika itu memuaskan Anda, tolong beri jawaban Celion - semua yang dia katakan benar, semua yang saya lakukan adalah menjalankan GCC beberapa kali.
12

Saya menduga bahwa informasi tentang Xbox 360 dan PS3 secara khusus akan berada di belakang tembok yang berlisensi-pengembang, seperti kebanyakan detail tingkat rendah. Namun, kita dapat membuat program x86 yang setara dan membongkarnya untuk mendapatkan ide umum.

Pertama, mari kita lihat berapa biaya pelebaran yang tidak ditandatangani:

unsigned char x = 1;
unsigned int y = 1;
unsigned int z;
z = x;
z = y;

Bagian yang relevan dibongkar menjadi (menggunakan GCC 4.4.5):

    z = x;
  27:   0f b6 45 ff             movzbl -0x1(%ebp),%eax
  2b:   89 45 f4                mov    %eax,-0xc(%ebp)
    z = y;
  2e:   8b 45 f8                mov    -0x8(%ebp),%eax
  31:   89 45 f4                mov    %eax,-0xc(%ebp)

Jadi pada dasarnya sama - dalam satu kasus kita memindahkan byte, yang lain kita memindahkan kata. Berikutnya:

signed char x = 1;
signed int y = 1;
signed int z;
z = x;
z = y;

Berubah menjadi:

   z = x;
  11:   0f be 45 ff             movsbl -0x1(%ebp),%eax
  15:   89 45 f4                mov    %eax,-0xc(%ebp)
    z = y;
  18:   8b 45 f8                mov    -0x8(%ebp),%eax
  1b:   89 45 f4                mov    %eax,-0xc(%ebp)

Jadi biaya perpanjangan tanda adalah berapa pun biaya movsbldaripada movzbltingkat sub-instruksi. Itu pada dasarnya mustahil untuk diukur pada prosesor modern karena cara kerja prosesor modern. Segala sesuatu yang lain, mulai dari kecepatan memori untuk caching ke apa yang ada di dalam pipa sebelumnya, akan mendominasi runtime.

Dalam ~ 10 menit saya menulis tes ini, saya bisa dengan mudah menemukan bug kinerja nyata, dan segera setelah saya mengaktifkan tingkat optimasi kompiler, kode menjadi tidak dapat dikenali untuk tugas-tugas mudah seperti itu.

Ini bukan Stack Overflow, jadi saya harap tidak ada orang di sini yang akan mengklaim optimasi mikro tidak masalah. Game sering kali bekerja pada data yang sangat besar dan sangat numerik, sehingga perhatian yang cermat terhadap percabangan, gips, penjadwalan, perataan struktur, dan sebagainya dapat memberikan peningkatan yang sangat kritis. Siapa pun yang telah menghabiskan banyak waktu untuk mengoptimalkan kode PPC mungkin memiliki setidaknya satu cerita horor tentang load-hit-store. Tetapi dalam kasus ini, itu benar-benar tidak masalah. Ukuran penyimpanan tipe integer Anda tidak memengaruhi kinerja, asalkan itu sejajar dan pas dalam register.

pengguna744
sumber
2
(CW karena ini benar-benar hanya sebuah komentar pada jawaban celion, dan karena saya ingin tahu perubahan kode apa yang mungkin dilakukan orang untuk membuatnya lebih ilustratif.)
Informasi tentang CPU PS3 tersedia dan secara hukum tersedia, jadi diskusi tentang hal-hal CPU yang berkaitan dengan PS3 tidak menjadi masalah. Hingga Sony menghapus dukungan OtherOS, siapa pun dapat menggunakan Linux pada PS3 dan memprogramnya. GPU itu terlarang, tetapi CPU (termasuk SPE) baik-baik saja. Bahkan tanpa dukungan OtherOS Anda dapat dengan mudah mengambil GCC yang sesuai dan melihat seperti apa gen-gen itu.
JasonD
@Jason: Saya menandai pos saya sebagai CW jadi jika seseorang melakukan ini mereka dapat memberikan informasi. Namun, siapa pun yang memiliki akses ke kompiler GameOS resmi Sony - yang benar-benar satu-satunya yang penting - mungkin dilarang melakukannya.
Sebenarnya integer yang ditandatangani lebih mahal pada PPC IIRC. Itu memang memiliki hit kinerja kecil, tetapi ada ... juga banyak rincian PPU / SPU PS3 di sini: jheriko-rtw.blogspot.co.uk/2011/07/ps3-ppuspu-docs.html dan di sini: jheriko-rtw.blogspot.co.uk/2011/03/ppc-instruction-set.html . Penasaran seperti apa kompiler GameOS ini? Apakah itu GCC compier atau yang SNC? Selain dari hal-hal yang disebutkan, perbandingan yang ditandatangani memiliki overhead ketika berbicara tentang mengoptimalkan loop yang paling dalam. Saya tidak memiliki akses ke dokumen yang menggambarkan hal ini - dan bahkan jika saya lakukan ...
jheriko
4

Operasi integer yang ditandatangani bisa lebih mahal di hampir semua arsitektur. Misalnya, pembagian dengan konstanta lebih cepat ketika tidak ditandatangani, misalnya:

unsigned foo(unsigned a) { return a / 1024U; }

akan dioptimalkan untuk:

unsigned foo(unsigned a) { return a >> 10; }

Tapi...

int foo(int a) { return a / 1024; }

akan mengoptimalkan untuk:

int foo(int a) {
  return (a + 1023 * (a < 0)) >> 10;
}

atau pada sistem di mana percabangan murah,

int foo(int a) {
  if (a >= 0) return a >> 10;
  else return (a + 1023) >> 10;
}

Sama berlaku untuk modulo. Ini juga berlaku untuk non-kekuatan-of-2 (tetapi contohnya lebih kompleks). Jika arsitektur Anda tidak memiliki pembagian perangkat keras (misalnya sebagian besar ARM), pembagian non-konstanta yang tidak ditandatangani juga lebih cepat.

Secara umum, memberi tahu kompiler bahwa angka negatif tidak dapat dihasilkan akan membantu optimalisasi ekspresi, terutama yang digunakan untuk terminasi loop dan kondisi lainnya.

Adapun int ukuran yang berbeda, ya ada sedikit dampak tetapi Anda harus menimbang vs memindahkan sedikit memori. Saat ini Anda mungkin mendapatkan lebih banyak dengan mengakses lebih sedikit memori daripada kehilangan dari ekspansi ukuran. Anda sangat jauh ke optimasi mikro pada saat itu.

John Ripley
sumber
Saya mengedit kode yang dioptimalkan untuk lebih mencerminkan apa yang sebenarnya dihasilkan GCC, bahkan pada -O0. Memiliki cabang menyesatkan ketika tes + lea memungkinkan Anda melakukannya tanpa cabang.
2
Di x86, mungkin. Pada ARMv7 itu hanya dieksekusi secara bersyarat.
John Ripley
3

Operasi dengan int yang ditandatangani atau tidak ditandatangani memiliki biaya yang sama pada prosesor saat ini (x86_64, x86, powerpc, arm). Pada prosesor 32 bit, u32, u16, u8 s32, s16, s8 harus sama. Anda dapat memiliki penalti dengan penyelarasan yang buruk.

Tetapi mengkonversi int ke float atau float ke int adalah operasi yang mahal. Anda dapat dengan mudah menemukan implementasi yang dioptimalkan (SSE2, Neon ...).

Poin paling penting mungkin adalah akses memori. Jika data Anda tidak sesuai dengan cache L1 / L2, Anda akan kehilangan lebih banyak siklus daripada konversi.

Ellis
sumber
2

Jon Purdy mengatakan di atas (saya tidak bisa berkomentar) bahwa unsigned mungkin lebih lambat karena tidak bisa meluap. Saya tidak setuju, aritmatika unsigned adalah modulo 2 moular sederhana untuk jumlah bit dalam kata. Operasi yang ditandatangani pada prinsipnya dapat mengalami luapan, tetapi biasanya dimatikan.

Terkadang Anda dapat melakukan hal-hal yang pintar (tetapi tidak terlalu mudah dibaca) seperti mengemas dua atau lebih item data ke dalam sebuah int, dan mendapatkan beberapa operasi per instruksi (aritmatika saku). Tetapi Anda harus mengerti apa yang Anda lakukan. Tentu saja MMX memungkinkan Anda untuk melakukan ini secara alami. Tetapi kadang-kadang menggunakan ukuran kata yang didukung HW terbesar dan pengemasan data secara manual memberi Anda implementasi tercepat.

Hati-hati dengan penyelarasan data. Pada sebagian besar implementasi HW, beban yang tidak selaras dan toko lebih lambat. Natural alignment, artinya untuk mengucapkan kata 4byte, alamatnya adalah kelipatan empat, dan alamat kata delapan byte harus kelipatan delapan byte. Ini dibawa ke SSE (128bit mendukung penyelarasan 16byte). AVX akan segera memperpanjang ukuran register "vektor" ini menjadi 256bit kemudian 512bit. Dan load / store yang selaras akan lebih cepat daripada yang tidak selaras. Untuk Geek HW, operasi memori yang tidak selaras mungkin merentang hal-hal seperti cacheline dan bahkan batas halaman, yang harus diperhatikan oleh HW.


sumber
1

Adalah sedikit lebih baik untuk menggunakan bilangan bulat yang ditandatangani untuk indeks loop, karena limpahan yang ditandatangani tidak didefinisikan dalam C, sehingga kompiler akan menganggap bahwa loop tersebut memiliki kasus sudut yang lebih sedikit. Ini dikendalikan oleh "-fstrict-overflow" gcc (diaktifkan secara default) dan efeknya mungkin sulit untuk diketahui tanpa membaca output rakitan.

Selain itu, x86 berfungsi lebih baik jika Anda tidak mencampur tipe, karena dapat menggunakan operan memori. Jika harus mengonversi jenis (tanda atau nol ekstensi) itu berarti memuat eksplisit dan penggunaan register.

Tetap dengan int untuk variabel lokal dan sebagian besar ini akan terjadi secara default.

alex aneh
sumber
0

Seperti yang ditunjukkan oleh celion, overhead dari konversi antara int dan float sebagian besar berkaitan dengan penyalinan dan konversi nilai antara register. Satu-satunya overhead int unsigned di dalam dan dari diri mereka berasal dari perilaku sampul dijamin mereka, yang mengharuskan sejumlah pengecekan overflow dalam kode yang dikompilasi.

Pada dasarnya tidak ada overhead dalam mengkonversi antara bilangan bulat yang ditandatangani dan tidak ditandatangani. Ukuran integer yang berbeda mungkin (sangat kecil) lebih cepat atau lebih lambat untuk diakses tergantung pada platform. Secara umum, ukuran bilangan bulat yang paling dekat dengan ukuran kata platform akan menjadi yang tercepat untuk diakses, tetapi perbedaan kinerja keseluruhan tergantung pada banyak faktor lain, terutama ukuran cache: jika Anda menggunakan uint64_tsemua yang Anda butuhkan uint32_t, itu mungkin pastikan bahwa kurang dari data Anda akan muat dalam cache sekaligus, dan Anda mungkin dikenakan beberapa beban overhead.

Agak terlalu berlebihan untuk memikirkan hal ini. Jika Anda menggunakan tipe yang sesuai untuk data Anda, hal-hal yang seharusnya bekerja dengan baik, dan jumlah daya yang akan diperoleh dengan memilih tipe berdasarkan arsitektur dapat diabaikan.

Jon Purdy
sumber
Apa yang dimaksud dengan pemeriksaan luapan? Kecuali Anda maksud level lebih rendah dari assembler, kode untuk menambahkan dua int identik pada kebanyakan sistem, dan tidak benar-benar lebih lama pada beberapa yang menggunakan misalnya magnitudo tanda. Hanya berbeda.
@ JoWreschnig: Sial. Sepertinya saya tidak dapat menemukannya, tetapi saya tahu saya telah melihat contoh-contoh berbagai keluaran assembler yang berbeda untuk perilaku sampul yang ditentukan, setidaknya pada platform tertentu. Satu-satunya tulisan terkait yang dapat saya temukan: stackoverflow.com/questions/4712315/…
Jon Purdy
Output assembler yang berbeda untuk perilaku sampul yang berbeda adalah karena kompiler dapat membuat optimisasi dalam kasus yang ditandatangani itu, misalnya jika b> 0 maka a + b> a, karena overflow yang ditandatangani tidak ditentukan (dan dengan demikian tidak dapat diandalkan). Ini benar-benar situasi yang sangat berbeda.