Menjawab pertanyaan Stack Overflow lainnya (yang ini ) saya menemukan sub-masalah yang menarik. Apa cara tercepat untuk mengurutkan array 6 bilangan bulat?
Karena tingkat pertanyaannya sangat rendah:
- kami tidak dapat menganggap perpustakaan tersedia (dan panggilan itu sendiri biayanya), hanya C biasa
- untuk menghindari pengosongan pipa instruksi (yang memiliki biaya yang sangat tinggi) kita mungkin harus meminimalkan cabang, lompatan, dan setiap jenis aliran kontrol lainnya (seperti yang tersembunyi di belakang titik urutan
&&
atau||
). - ruangan dibatasi dan meminimalkan register dan penggunaan memori adalah masalah, idealnya di tempat semacam itu mungkin yang terbaik.
Sungguh pertanyaan ini adalah semacam Golf di mana tujuannya bukan untuk meminimalkan panjang sumber tetapi waktu eksekusi. Saya menyebutnya kode 'Zening' seperti yang digunakan dalam judul buku Zen of Code optimisasi oleh Michael Abrash dan sekuelnya .
Adapun mengapa itu menarik, ada beberapa lapisan:
- contohnya sederhana dan mudah dipahami dan diukur, tidak banyak keterampilan C yang terlibat
- itu menunjukkan efek pilihan dari algoritma yang baik untuk masalah, tetapi juga efek dari kompiler dan perangkat keras yang mendasarinya.
Inilah implementasi referensi saya (naif, tidak dioptimalkan) dan set pengujian saya.
#include <stdio.h>
static __inline__ int sort6(int * d){
char j, i, imin;
int tmp;
for (j = 0 ; j < 5 ; j++){
imin = j;
for (i = j + 1; i < 6 ; i++){
if (d[i] < d[imin]){
imin = i;
}
}
tmp = d[j];
d[j] = d[imin];
d[imin] = tmp;
}
}
static __inline__ unsigned long long rdtsc(void)
{
unsigned long long int x;
__asm__ volatile (".byte 0x0f, 0x31" : "=A" (x));
return x;
}
int main(int argc, char ** argv){
int i;
int d[6][5] = {
{1, 2, 3, 4, 5, 6},
{6, 5, 4, 3, 2, 1},
{100, 2, 300, 4, 500, 6},
{100, 2, 3, 4, 500, 6},
{1, 200, 3, 4, 5, 600},
{1, 1, 2, 1, 2, 1}
};
unsigned long long cycles = rdtsc();
for (i = 0; i < 6 ; i++){
sort6(d[i]);
/*
* printf("d%d : %d %d %d %d %d %d\n", i,
* d[i][0], d[i][6], d[i][7],
* d[i][8], d[i][9], d[i][10]);
*/
}
cycles = rdtsc() - cycles;
printf("Time is %d\n", (unsigned)cycles);
}
Hasil mentah
Karena jumlah varian menjadi besar, saya mengumpulkan semuanya di ruang uji yang dapat ditemukan di sini . Tes yang sebenarnya digunakan sedikit lebih naif dari yang ditunjukkan di atas, terima kasih kepada Kevin Stock. Anda dapat mengkompilasi dan menjalankannya di lingkungan Anda sendiri. Saya cukup tertarik dengan perilaku arsitektur target / kompiler yang berbeda. (OK teman, taruh di jawaban, saya akan memberi +1 setiap kontributor dari hasil baru).
Saya memberikan jawaban kepada Daniel Stutzbach (untuk bermain golf) satu tahun yang lalu ketika ia menjadi sumber solusi tercepat saat itu (menyortir jaringan).
Linux 64 bit, gcc 4.6.1 64 bit, Intel Core 2 Duo E8400, -O2
- Panggilan langsung ke fungsi perpustakaan qsort: 689.38
- Implementasi naif (jenis penyisipan): 285.70
- Jenis Penyisipan (Daniel Stutzbach): 142.12
- Penyisipan Sortir Belum Terdaftar: 125,47
- Peringkat Pesanan: 102.26
- Urutan Peringkat dengan register: 58.03
- Penyortiran Jaringan (Daniel Stutzbach): 111.68
- Sorting Networks (Paul R): 66.36
- Sorting Networks 12 dengan Fast Swap: 58.86
- Sorting Networks 12 Swap dipesan ulang: 53.74
- Sorting Networks 12 Simple Swap yang disusun ulang: 31.54
- Reortered Sorting Network dengan swap cepat: 31.54
- Jaringan Penyortiran Reordered dengan swap cepat V2: 33.63
- Sortir Bubble Bergaris (Paolo Bonzini): 48.85
- Sortir Penyisipan Tidak Dikontrol (Paolo Bonzini): 75,30
Linux 64 bit, gcc 4.6.1 64 bit, Intel Core 2 Duo E8400, -O1
- Panggilan langsung ke fungsi perpustakaan qsort: 705.93
- Implementasi naif (jenis penyisipan): 135.60
- Jenis Penyisipan (Daniel Stutzbach): 142.11
- Penyisipan Sortir Belum Terdaftar: 126,75
- Peringkat Pesanan: 46,42
- Urutan Peringkat dengan register: 43,58
- Sorting Networks (Daniel Stutzbach): 115.57
- Sorting Networks (Paul R): 64.44
- Sorting Networks 12 dengan Fast Swap: 61.98
- Sorting Networks 12 Swap yang disusun ulang: 54.67
- Sorting Networks 12 Simple Swap yang disusun ulang: 31.54
- Jaringan Penyortiran Reordered dengan swap cepat: 31.24
- Reortered Sorting Network dengan swap cepat V2: 33.07
- Sortir Bubble Bergaris (Paolo Bonzini): 45,79
- Sortir Penyisipan Tidak Dikontrol (Paolo Bonzini): 80.15
Saya menyertakan hasil -O1 dan -O2 karena secara mengejutkan untuk beberapa program O2 kurang efisien daripada O1. Saya ingin tahu pengoptimalan spesifik apa yang memiliki efek ini?
Komentar tentang solusi yang diusulkan
Jenis Penyisipan (Daniel Stutzbach)
Seperti yang diharapkan meminimalkan cabang memang ide yang bagus.
Sorting Networks (Daniel Stutzbach)
Lebih baik daripada jenis penyisipan. Saya bertanya-tanya apakah efek utama tidak didapat dari menghindari loop eksternal. Saya mencobanya dengan memasukkan penyisipan tanpa gulungan untuk memeriksa dan memang kita mendapatkan kira-kira angka yang sama (kode ada di sini ).
Sorting Networks (Paul R)
Yang terbaik sejauh ini. Kode aktual yang saya gunakan untuk menguji ada di sini . Belum tahu mengapa ini hampir dua kali lebih cepat dari implementasi jaringan penyortiran lainnya. Melewati parameter? Max cepat?
Sorting Networks 12 SWAP dengan Fast Swap
Seperti yang disarankan oleh Daniel Stutzbach, saya menggabungkan 12 jaringan sortir swap-nya dengan swap cepat tanpa cabang (kode ada di sini ). Ini memang lebih cepat, yang terbaik sejauh ini dengan margin kecil (sekitar 5%) seperti yang bisa diharapkan menggunakan 1 swap lebih sedikit.
Menarik juga untuk memperhatikan bahwa swap tanpa cabang tampaknya jauh (4 kali) kurang efisien daripada yang sederhana jika menggunakan arsitektur PPC.
Memanggil Perpustakaan qsort
Untuk memberikan titik referensi lain saya juga mencoba seperti yang disarankan untuk memanggil perpustakaan qsort (kode ada di sini ). Seperti yang diharapkan itu jauh lebih lambat: 10 hingga 30 kali lebih lambat ... seperti yang terlihat jelas dengan test suite baru, masalah utama tampaknya menjadi beban awal perpustakaan setelah panggilan pertama, dan membandingkan tidak begitu buruk dengan yang lain Versi: kapan. Itu hanya antara 3 dan 20 kali lebih lambat di Linux saya. Pada beberapa arsitektur yang digunakan untuk tes oleh orang lain tampaknya bahkan lebih cepat (saya benar-benar terkejut dengan yang itu, karena perpustakaan qsort menggunakan API yang lebih kompleks).
Urutan peringkat
Rex Kerr mengusulkan metode lain yang sama sekali berbeda: untuk setiap item array menghitung langsung posisi akhirnya. Ini efisien karena urutan peringkat komputasi tidak perlu cabang. Kelemahan dari metode ini adalah dibutuhkan tiga kali jumlah memori array (satu salinan array dan variabel untuk menyimpan urutan peringkat). Hasil kinerja sangat mengejutkan (dan menarik). Pada arsitektur referensi saya dengan OS 32 bit dan Intel Core2 Quad E8300, jumlah siklus sedikit di bawah 1000 (seperti jaringan sortir dengan branching swap). Tetapi ketika dikompilasi dan dieksekusi pada kotak 64 bit saya (Intel Core2 Duo) kinerjanya jauh lebih baik: itu menjadi yang tercepat sejauh ini. Saya akhirnya menemukan alasan sebenarnya. Kotak 32 bit saya menggunakan gcc 4.4.1 dan kotak 64bits saya gcc 4.4.
perbarui :
Seperti gambar yang diterbitkan di atas menunjukkan efek ini masih ditingkatkan oleh versi gcc dan Urutan Peringkat kemudian secara konsisten dua kali lebih cepat dari alternatif lain.
Sorting Networks 12 dengan Swap yang disusun ulang
Efisiensi luar biasa dari proposal Rex Kerr dengan gcc 4.4.3 membuat saya bertanya-tanya: bagaimana mungkin sebuah program dengan penggunaan memori 3 kali lebih cepat dari pada jaringan sortir tanpa cabang? Hipotesis saya adalah bahwa ia memiliki sedikit ketergantungan dari jenis baca setelah menulis, memungkinkan untuk penggunaan yang lebih baik dari penjadwal instruksi superscalar x86. Itu memberi saya ide: mengatur ulang swap untuk meminimalkan membaca setelah menulis dependensi. Lebih sederhana: ketika Anda melakukannya, SWAP(1, 2); SWAP(0, 2);
Anda harus menunggu swap pertama selesai sebelum melakukan yang kedua karena keduanya mengakses sel memori yang sama. Saat Anda melakukannya SWAP(1, 2); SWAP(4, 5);
, prosesor dapat menjalankan keduanya secara paralel. Saya mencobanya dan berfungsi seperti yang diharapkan, jaringan sortasi berjalan sekitar 10% lebih cepat.
Sortasi Jaringan 12 dengan Simple Swap
Satu tahun setelah posting asli Steinar H. Gunderson menyarankan, bahwa kita tidak boleh mencoba mengakali kompiler dan menjaga kode swap sederhana. Ini memang ide yang bagus karena kode yang dihasilkan sekitar 40% lebih cepat! Dia juga mengusulkan swap yang dioptimalkan dengan tangan menggunakan kode perakitan inline x86 yang masih dapat meluangkan lebih banyak siklus. Yang paling mengejutkan (katanya volume pada psikologi programmer) adalah bahwa satu tahun yang lalu tidak ada yang digunakan mencoba versi swap. Kode yang saya gunakan untuk menguji ada di sini . Lainnya menyarankan cara lain untuk menulis swap cepat C, tetapi menghasilkan kinerja yang sama seperti yang sederhana dengan kompiler yang layak.
Kode "terbaik" sekarang adalah sebagai berikut:
static inline void sort6_sorting_network_simple_swap(int * d){
#define min(x, y) (x<y?x:y)
#define max(x, y) (x<y?y:x)
#define SWAP(x,y) { const int a = min(d[x], d[y]); \
const int b = max(d[x], d[y]); \
d[x] = a; d[y] = b; }
SWAP(1, 2);
SWAP(4, 5);
SWAP(0, 2);
SWAP(3, 5);
SWAP(0, 1);
SWAP(3, 4);
SWAP(1, 4);
SWAP(0, 3);
SWAP(2, 5);
SWAP(1, 3);
SWAP(2, 4);
SWAP(2, 3);
#undef SWAP
#undef min
#undef max
}
Jika kami yakin set pengujian kami (dan, ya itu sangat buruk, itu hanya manfaatnya pendek, sederhana dan mudah untuk memahami apa yang kami ukur), jumlah rata-rata siklus kode yang dihasilkan untuk satu jenis adalah di bawah 40 siklus ( 6 tes dijalankan). Itu menempatkan setiap swap pada rata-rata 4 siklus. Saya menyebutnya sangat cepat. Adakah perbaikan lain yang mungkin?
x-y
danx+y
tidak akan menyebabkan underflow atau overflow?__asm__ volatile (".byte 0x0f, 0x31; shlq $32, %%rdx; orq %%rdx, %0" : "=a" (x) : : "rdx");
karena rdtsc menempatkan jawabannya di EDX: EAX sementara GCC mengharapkannya dalam register 64-bit tunggal. Anda dapat melihat bug dengan kompilasi di -O3. Juga lihat di bawah ini komentar saya kepada Paul R tentang SWAP yang lebih cepat.CMP EAX, EBX; SBB EAX, EAX
akan menempatkan 0 atau 0xFFFFFFFF diEAX
tergantung pada apakahEAX
lebih besar atau lebih kecil dariEBX
, masing-masing.SBB
adalah "kurangi dengan meminjam", mitra dariADC
("tambah dengan carry"); bit status yang Anda lihat adalah carry bit. Kemudian lagi, saya ingat ituADC
danSBB
memiliki latensi & throughput yang mengerikan pada Pentium 4 vsADD
danSUB
, dan masih dua kali lebih lambat pada Core CPU. Sejak 80386 ada juga instruksiSETcc
conditional-store danCMOVcc
conditional-move, tetapi mereka juga lambat.Jawaban:
Untuk optimasi apa pun, selalu terbaik untuk menguji, menguji, menguji. Saya akan mencoba setidaknya menyortir jaringan dan jenis penyisipan. Jika saya bertaruh, saya akan menaruh uang saya pada jenis penyisipan berdasarkan pengalaman masa lalu.
Apakah Anda tahu sesuatu tentang data input? Beberapa algoritma akan bekerja lebih baik dengan jenis data tertentu. Misalnya, penyisipan berkinerja lebih baik pada dat yang diurutkan atau hampir diurutkan, jadi itu akan menjadi pilihan yang lebih baik jika ada peluang di atas rata-rata data yang hampir diurutkan.
Algoritma yang Anda poskan mirip dengan jenis penyisipan, tetapi sepertinya Anda telah meminimalkan jumlah swap dengan biaya lebih banyak perbandingan. Namun, perbandingan jauh lebih mahal daripada swap, karena cabang dapat menyebabkan pipa instruksi terhenti.
Berikut ini adalah implementasi semacam penyisipan:
Inilah cara saya membangun jaringan penyortiran. Pertama, gunakan situs ini untuk menghasilkan set minimal SWAP macro untuk jaringan dengan panjang yang sesuai. Membungkusnya dalam suatu fungsi memberi saya:
sumber
n < SMALL_CONSTANT
.Berikut ini implementasi menggunakan jaringan penyortiran :
Anda benar-benar membutuhkan percabangan
min
danmax
implementasi yang sangat efisien untuk ini, karena itulah yang secara efektif didasari oleh kode ini - suatu urutanmin
danmax
operasi (total masing-masing 13). Saya meninggalkan ini sebagai latihan untuk pembaca.Perhatikan bahwa implementasi ini cocok untuk vektorisasi (mis. SIMD - sebagian besar SIMD ISA memiliki petunjuk vektor / maks) dan juga untuk implementasi GPU (mis. CUDA - karena tanpa cabang tidak ada masalah dengan perbedaan warp dll).
Lihat juga: Implementasi algoritma cepat untuk mengurutkan daftar yang sangat kecil
sumber
Sort3
akan lebih cepat (pada kebanyakan arsitektur, toh) jika Anda mencatat bahwa itu(a+b+c)-(min+max)
adalah angka sentral.#define SWAP(x,y) { int dx = d[x], dy = d[y], tmp; tmp = d[x] = dx < dy ? dx : dy; d[y] ^= dx ^ tmp; }
. Di sini saya tidak menggunakan?: Untuk d [y] karena memberikan kinerja yang sedikit lebih buruk, tetapi hampir di kebisingan.Karena ini adalah bilangan bulat dan perbandingannya cepat, mengapa tidak menghitung urutan peringkat masing-masing secara langsung:
sumber
0+1+2+3+4+5=15
Karena salah satu dari mereka tidak ada, 15 dikurangi jumlah sisanya yang hilangSepertinya saya terlambat ke pesta setahun, tapi kita mulai ...
Melihat perakitan yang dihasilkan oleh gcc 4.5.2 saya mengamati bahwa banyak dan toko sedang dilakukan untuk setiap swap, yang sebenarnya tidak diperlukan. Akan lebih baik untuk memuat 6 nilai ke dalam register, mengurutkannya, dan menyimpannya kembali ke dalam memori. Saya memesan muatan di toko sedekat mungkin ke sana register pertama kali diperlukan dan terakhir digunakan. Saya juga menggunakan makro SWAP Steinar H. Gunderson. Pembaruan: Saya beralih ke makro SWAP Paolo Bonzini yang diubah oleh gcc menjadi sesuatu yang mirip dengan milik Gunderson, tetapi gcc dapat memesan instruksi dengan lebih baik karena tidak diberikan sebagai perakitan eksplisit.
Saya menggunakan urutan swap yang sama dengan jaringan swap yang dipesan ulang yang diberikan sebagai yang berkinerja terbaik, meskipun mungkin ada pemesanan yang lebih baik. Jika saya menemukan waktu lagi saya akan menghasilkan dan menguji banyak permutasi.
Saya mengubah kode pengujian untuk mempertimbangkan lebih dari 4000 array dan menunjukkan jumlah rata-rata siklus yang diperlukan untuk mengurutkan masing-masing. Pada i5-650 saya mendapatkan ~ 34,1 siklus / urut (menggunakan -O3), dibandingkan dengan jaringan pengurutan yang disusun ulang yang asli yang mendapatkan ~ 65,3 siklus / urut (menggunakan -O1, ketukan -O2 dan -O3).
Saya mengubah modifikasi test suite untuk juga melaporkan jam per sort dan menjalankan lebih banyak tes (fungsi cmp diperbarui untuk menangani integer overflow juga), berikut adalah hasil pada beberapa arsitektur yang berbeda. Saya mencoba pengujian pada AMD cpu tetapi rdtsc tidak dapat diandalkan pada X6 1100T yang saya miliki.
sumber
-O3
optimasi tidak akan menjadi kontra-produktif.#define SWAP(x,y) { int oldx = x; x = x < y ? x : y; y ^= oldx ^ x; }
.Saya menemukan pertanyaan ini dari Google beberapa hari yang lalu karena saya juga memiliki kebutuhan untuk dengan cepat mengurutkan array dengan panjang tetap 6 bilangan bulat. Namun dalam kasus saya, bilangan bulat saya hanya 8 bit (bukan 32) dan saya tidak memiliki persyaratan ketat hanya menggunakan C. Saya pikir saya akan membagikan temuan saya, kalau-kalau mereka mungkin membantu seseorang ...
Saya menerapkan varian semacam jaringan dalam perakitan yang menggunakan SSE untuk membuat vektor operasi perbandingan dan swap, sejauh mungkin. Dibutuhkan enam "melewati" untuk sepenuhnya mengurutkan array. Saya menggunakan mekanisme baru untuk secara langsung mengkonversi hasil PCMPGTB (perbandingan vektor) menjadi parameter acak untuk PSHUFB (vectorized swap), hanya menggunakan PADDB (penambahan vektor) dan dalam beberapa kasus juga instruksi PAND (bitwise AND).
Pendekatan ini juga memiliki efek samping menghasilkan a benar fungsi yang cabang. Tidak ada instruksi lompatan sama sekali.
Tampaknya implementasi ini sekitar 38% lebih cepat daripada implementasi yang saat ini ditandai sebagai opsi tercepat dalam pertanyaan ("Menyortir Jaringan 12 dengan Simple Swap"). Saya memodifikasi implementasi itu untuk digunakan
char
elemen array selama pengujian saya, untuk membuat perbandingan yang adil.Saya harus mencatat bahwa pendekatan ini dapat diterapkan ke berbagai ukuran array hingga 16 elemen. Saya berharap keunggulan kecepatan relatif atas alternatif tumbuh lebih besar untuk array yang lebih besar.
Kode ini ditulis dalam MASM untuk prosesor x86_64 dengan SSSE3. Fungsi ini menggunakan konvensi pemanggilan Windows x64 "baru". Ini dia...
Anda dapat mengkompilasi ini ke objek yang dapat dieksekusi dan menautkannya ke proyek C. Untuk instruksi tentang cara melakukan ini di Visual Studio, Anda dapat membaca artikel ini . Anda dapat menggunakan prototipe C berikut untuk memanggil fungsi dari kode C Anda:
sumber
pxor / pinsrd xmm4, mem, 0
, gunakan sajamovd
!Kode tes sangat buruk; itu melebihi array awal (bukankah orang-orang di sini membaca peringatan kompiler?), printf mencetak elemen yang salah, ia menggunakan .byte untuk rdtsc tanpa alasan yang bagus, hanya ada satu run (!), tidak ada yang memeriksa bahwa hasil akhirnya sebenarnya benar (sehingga sangat mudah untuk "mengoptimalkan" menjadi sesuatu yang agak salah), tes yang disertakan sangat sederhana (tidak ada angka negatif?) dan tidak ada yang menghentikan kompiler dari hanya membuang seluruh fungsi sebagai kode mati.
Yang sedang berkata, itu juga cukup mudah untuk meningkatkan pada solusi jaringan bitonic; cukup ubah item min / max / SWAP ke
dan itu keluar sekitar 65% lebih cepat untuk saya (Debian gcc 4.4.5 dengan -O2, amd64, Core i7).
sumber
Sementara saya sangat suka swap makro yang disediakan:
Saya melihat peningkatan (yang mungkin dilakukan oleh kompiler yang baik):
Kami mencatat cara kerja min dan max dan menarik sub-ekspresi umum secara eksplisit. Ini menghilangkan makro min dan maks sepenuhnya.
sumber
d[x]
bukanx
(sama untuky
), dand[y] < d[x]
untuk ketidaksetaraan di sini (ya, berbeda dari kode min / max).Jangan pernah mengoptimalkan min / maks tanpa pembandingan dan melihat perakitan yang dihasilkan kompiler yang sebenarnya. Jika saya membiarkan GCC mengoptimalkan min dengan instruksi pemindahan bersyarat, saya mendapatkan peningkatan kecepatan 33%:
(280 vs 420 siklus dalam kode tes). Melakukan maks dengan?: Kurang lebih sama, hampir hilang dalam kebisingan, tetapi di atas sedikit lebih cepat. SWAP ini lebih cepat dengan GCC dan Dentang.
Compiler juga melakukan pekerjaan luar biasa pada alokasi register dan analisis alias, secara efektif memindahkan d [x] ke variabel lokal dimuka, dan hanya menyalin kembali ke memori di akhir. Bahkan, mereka melakukannya bahkan lebih baik daripada jika Anda bekerja sepenuhnya dengan variabel lokal (seperti
d0 = d[0], d1 = d[1], d2 = d[2], d3 = d[3], d4 = d[4], d5 = d[5]
). Saya menulis ini karena Anda mengasumsikan optimasi yang kuat dan belum mencoba mengakali kompiler pada min / max. :)Omong-omong, saya mencoba Dentang dan GCC. Mereka melakukan optimasi yang sama, tetapi karena perbedaan penjadwalan keduanya memiliki beberapa variasi dalam hasil, tidak bisa mengatakan yang mana yang lebih cepat atau lebih lambat. GCC lebih cepat pada jaringan sortir, dentang jenis kuadratik.
Hanya untuk kelengkapan, jenis gelembung yang tidak terbuka dan jenis sisipan juga dimungkinkan. Ini adalah semacam gelembung:
dan ini adalah jenis sisipan:
Jenis penyisipan ini lebih cepat daripada milik Daniel Stutzbach, dan terutama bagus pada GPU atau komputer dengan predikasi karena ITER dapat dilakukan dengan hanya 3 instruksi (vs. 4 untuk SWAP). Sebagai contoh, inilah
t = d[2]; ITER(1); ITER(0);
baris dalam perakitan ARM:Untuk enam elemen, jenis penyisipan kompetitif dengan jaringan penyortiran (12 swap vs 15 iterasi saldo 4 instruksi / swap vs 3 instruksi / iterasi); semacam gelembung tentu saja lebih lambat. Tapi itu tidak akan menjadi kenyataan ketika ukurannya bertambah, karena jenis penyisipan adalah O (n ^ 2) sedangkan jaringan penyortiran adalah O (n log n).
sumber
Saya memindahkan test suite ke mesin arsitektur PPC yang tidak dapat saya identifikasi (tidak harus menyentuh kode, cukup tambahkan iterasi tes, gunakan 8 kasus uji untuk menghindari polusi hasil dengan mod dan ganti rdtsc spesifik x86):
Fungsi panggilan langsung ke perpustakaan qsort : 101
Implementasi naif (jenis penyisipan) : 299
Jenis Penyisipan (Daniel Stutzbach) : 108
Penyisipan Sortir Belum Terdaftar : 51
Sorting Networks (Daniel Stutzbach) : 26
Sorting Networks (Paul R) : 85
Sorting Networks 12 dengan Fast Swap : 117
Sorting Networks 12 Swap dipesan ulang : 116
Peringkat Pesanan : 56
sumber
subfc r5,r4,r3; subfe r6,r6,r6; andc r6,r5,r6; add r4,r6,r4; subf r3,r6,r3
. r3 / r4 adalah input, r5 / r6 adalah register awal, pada output r3 mendapatkan nilai minimum dan r4 mendapatkan nilai maksimal. Itu harus dapat dijadwalkan dengan tangan. Saya menemukannya dengan superoptimizer GNU, mulai dari urutan minimal 4-instruksi dan maksimum dan mencari secara manual untuk dua yang bisa digabungkan. Untuk input yang ditandatangani, tentu saja Anda dapat menambahkan 0x80000000 ke semua elemen di awal dan mengurangi lagi di akhir, dan kemudian bekerja seolah-olah mereka tidak ditandatangani.Swap XOR mungkin berguna dalam fungsi swapping Anda.
Jika dapat menyebabkan terlalu banyak perbedaan dalam kode Anda, tetapi jika Anda memiliki jaminan bahwa semua int Anda unik, ini bisa berguna.
sumber
x
dany
arahkan ke lokasi yang sama.Melihat ke depan untuk mencoba tangan saya ini dan belajar dari contoh-contoh ini, tetapi pertama-tama beberapa waktu dari 1.5 GHz PPC Powerbook G4 w / 1 GB DDR RAM. (Saya meminjam timer mirip rdtsc untuk PPC dari http://www.mcs.anl.gov/~kazutomo/rdtsc.html untuk pengaturan waktu.) Saya menjalankan program beberapa kali dan hasil absolut bervariasi tetapi hasilnya konsisten tetapi konsisten tes tercepat adalah "Penyisipan Sortir (Daniel Stutzbach)", dengan "Penyisipan Sortir Tidak Terbuka" yang kedua.
Inilah rangkaian waktu terakhir:
sumber
Inilah kontribusi saya untuk utas ini: shellsort celah 1, 4 yang dioptimalkan untuk vektor int 6-anggota (valp) yang berisi nilai-nilai unik.
Pada laptop HP dv7-3010so saya dengan Athlon M300 @ 2 Ghz dual-core (memori DDR2) dijalankan dalam siklus 165 jam. Ini adalah rata-rata yang dihitung dari pengaturan waktu setiap urutan unik (6! / 720 semuanya). Dikompilasi ke Win32 menggunakan OpenWatcom 1.8. Loop pada dasarnya adalah jenis penyisipan dan panjangnya 16 instruksi / 37 byte.
Saya tidak memiliki lingkungan 64-bit untuk dikompilasi.
sumber
Jika jenis penyisipan cukup kompetitif di sini, saya akan merekomendasikan mencoba shellsort. Saya khawatir 6 elemen mungkin terlalu sedikit untuk menjadi yang terbaik, tetapi mungkin patut dicoba.
Contoh kode, belum diuji, undebugged, dll. Anda ingin menyetel urutan inc = 4 dan inc - = 3 untuk menemukan yang optimal (coba inc = 2, inc - = 1 misalnya).
Saya tidak berpikir ini akan menang, tetapi jika seseorang memposting pertanyaan tentang menyortir 10 elemen, siapa tahu ...
Menurut Wikipedia ini bahkan dapat dikombinasikan dengan jaringan sortir: Pratt, V (1979). Shellsort dan jaringan sortir (Disertasi luar biasa dalam ilmu komputer). Karangan bunga. ISBN 0-824-04406-1
sumber
Saya tahu saya sangat terlambat, tetapi saya tertarik untuk bereksperimen dengan beberapa solusi yang berbeda. Pertama, saya membersihkan pasta itu, membuatnya mengkompilasi, dan memasukkannya ke dalam repositori. Saya menyimpan beberapa solusi yang tidak diinginkan sebagai jalan buntu sehingga yang lain tidak akan mencobanya. Di antara ini adalah solusi pertama saya, yang berusaha memastikan bahwa x1> x2 dihitung sekali. Setelah optimasi, tidak lebih cepat dari versi sederhana lainnya.
Saya menambahkan versi pengulangan urutan urutan peringkat, karena aplikasi saya sendiri dari penelitian ini adalah untuk mengurutkan 2-8 item, jadi karena ada sejumlah variabel argumen, diperlukan loop. Ini juga mengapa saya mengabaikan solusi jaringan penyortiran.
Kode tes tidak menguji bahwa duplikat ditangani dengan benar, jadi sementara solusi yang ada semuanya benar, saya menambahkan kasus khusus pada kode pengujian untuk memastikan bahwa duplikat ditangani dengan benar.
Kemudian, saya menulis semacam sisipan yang seluruhnya ada di register AVX. Pada mesin saya, 25% lebih cepat dari jenis insersi lainnya, tetapi 100% lebih lambat dari urutan peringkat. Saya melakukan ini murni untuk percobaan dan tidak memiliki harapan ini menjadi lebih baik karena percabangan dalam jenis penyisipan.
Kemudian, saya menulis semacam urutan peringkat menggunakan AVX. Ini cocok dengan kecepatan solusi urutan-peringkat lainnya, tetapi tidak lebih cepat. Masalahnya di sini adalah saya hanya bisa menghitung indeks dengan AVX, dan kemudian saya harus membuat tabel indeks. Ini karena perhitungannya berbasis tujuan daripada berbasis sumber. Lihat Mengubah dari Indeks Berbasis Sumber ke Indeks Berbasis Destinasi
Repo dapat ditemukan di sini: https://github.com/eyepatchParrot/sort6/
sumber
vmovmskps
pada vektor integer (dengan gips untuk menjaga intrinsik senang), menghindari kebutuhan untuk menggeser-kanan hasil bitscan (ffs
).cmpgt
hasil dengan mengurangkannya , alih-alih menutupinyaset1(1)
. mis.index = _mm256_sub_epi32(index, gt)
tidakindex -= -1 or 0;
eq = _mm256_insert_epi32(eq, 0, I)
bukan cara yang efisien untuk nol elemen jika dikompilasi sebagai tertulis (terutama untuk elemen di luar rendah 4, karenavpinsrd
hanya tersedia dengan tujuan XMM; indeks lebih tinggi dari 3 harus ditiru). Sebaliknya,_mm256_blend_epi32
(vpblendd
) dengan vektor memusatkan perhatian.vpblendd
adalah instruksi single-uop yang berjalan pada port apa saja, vs. shuffle yang membutuhkan port 5 pada CPU Intel. ( agner.org/optimize ).rot
vektor dengan pengocokan berbeda dari sumber yang sama, atau setidaknya menjalankan 2 rantai dep secara paralel yang Anda gunakan secara bergantian, alih-alih satu rantai dep tunggal melalui pengocokan jalur-lintasan (latensi 3 siklus). Itu akan meningkatkan ILP dalam satu jenis. 2 rantai dep membatasi jumlah konstanta vektor ke angka yang wajar, hanya 2: 1 untuk satu putaran, dan satu untuk 2 langkah rotasi digabungkan.Pertanyaan ini menjadi cukup lama, tetapi saya benar-benar harus menyelesaikan masalah yang sama hari ini: agoritma cepat untuk mengurutkan array kecil. Saya pikir itu akan menjadi ide yang baik untuk membagikan pengetahuan saya. Ketika saya pertama kali mulai dengan menggunakan jaringan penyortiran, saya akhirnya berhasil menemukan algoritma lain yang jumlah perbandingan dilakukan untuk mengurutkan setiap permutasi dari 6 nilai lebih kecil dari dengan jaringan penyortiran, dan lebih kecil dari dengan penyisipan jenis. Saya tidak menghitung jumlah swap; Saya kira kira-kira setara (mungkin kadang-kadang sedikit lebih tinggi).
Algoritma
sort6
menggunakan algoritmasort4
yang menggunakan algoritmasort3
. Berikut ini adalah implementasi dalam beberapa bentuk C ++ ringan (aslinya adalah template-berat sehingga dapat bekerja dengan iterator akses-acak dan fungsi perbandingan yang sesuai).Menyortir 3 nilai
Algoritme berikut adalah jenis penyisipan yang tidak digulung. Ketika dua swap (6 penugasan) harus dilakukan, ia menggunakan 4 penugasan sebagai gantinya:
Itu terlihat agak rumit karena pengurutan memiliki lebih atau kurang satu cabang untuk setiap permutasi yang mungkin dari array, menggunakan 2 ~ 3 perbandingan dan paling banyak 4 penugasan untuk mengurutkan ketiga nilai.
Mengurutkan 4 nilai
Panggilan yang satu ini
sort3
kemudian melakukan jenis penyisipan yang tidak terbuka dengan elemen terakhir dari array:Algoritma ini melakukan perbandingan 3 hingga 6 dan paling banyak 5 swap. Sangat mudah untuk membuka gulungan jenis penyisipan, tetapi kami akan menggunakan algoritma lain untuk jenis yang terakhir ...
Mengurutkan 6 nilai
Yang ini menggunakan versi yang belum dibuka dari apa yang saya sebut semacam penyisipan ganda . Namanya tidak terlalu bagus, tapi cukup deskriptif, ini cara kerjanya:
Setelah swap, elemen pertama selalu lebih kecil dari yang terakhir, yang berarti bahwa, ketika memasukkannya ke dalam urutan yang diurutkan, tidak akan ada lebih dari perbandingan N untuk memasukkan dua elemen dalam kasus terburuk: misalnya, jika elemen pertama telah disisipkan di posisi ke-3, maka yang terakhir tidak dapat disisipkan lebih rendah dari posisi ke-4.
Pengujian saya pada setiap permutasi 6 nilai pernah menunjukkan bahwa algoritma ini selalu melakukan perbandingan antara 6 dan 13. Saya tidak menghitung jumlah swap yang dilakukan, tetapi saya tidak berharap itu lebih tinggi dari 11 dalam kasus terburuk.
Saya harap ini membantu, walaupun pertanyaan ini mungkin tidak mewakili masalah aktual :)
EDIT: setelah meletakkannya di patokan yang disediakan, itu lebih lambat lebih lambat daripada kebanyakan alternatif yang menarik. Ini cenderung melakukan sedikit lebih baik daripada jenis penyisipan yang tidak gulungan, tapi cukup banyak. Pada dasarnya, ini bukan jenis terbaik untuk bilangan bulat tetapi bisa menarik untuk jenis dengan operasi perbandingan yang mahal.
sumber
operator<
untuk perbandingan. Selain jumlah objektif perbandingan dan swap, saya juga menghitung waktu algoritme saya; solusi ini adalah yang tercepat generik, tetapi saya memang merindukan @ RexKerr. Akan mencobanya :)-O3
. Saya kira saya akan mengadopsi strategi lain untuk perpustakaan pemilahan saya kemudian: menyediakan tiga jenis algoritma untuk memiliki baik perbandingan rendah, sejumlah rendah swap atau berpotensi kinerja terbaik. Setidaknya, apa yang terjadi akan transparan bagi pembaca. Terima kasih atas wawasan Anda :)Saya percaya ada dua bagian dari pertanyaan Anda.
Saya tidak akan terlalu khawatir tentang mengosongkan pipa (dengan asumsi x86 saat ini): prediksi cabang telah jauh. Yang saya khawatirkan adalah memastikan bahwa kode dan data sesuai dalam satu baris cache masing-masing (mungkin dua untuk kode). Setelah mengambil latensi rendah menyegarkan yang akan mengimbangi kios apa pun. Ini juga berarti bahwa loop batin Anda mungkin sekitar sepuluh instruksi atau lebih yang benar di mana seharusnya (ada dua loop batin yang berbeda dalam algoritma pengurutan saya, mereka masing-masing 10 instruksi / 22 byte dan 9/22 panjang). Dengan asumsi kode tidak mengandung div, Anda dapat yakin itu akan sangat cepat.
sumber
Saya tahu ini adalah pertanyaan lama.
Tetapi saya hanya menulis solusi berbeda yang ingin saya bagikan.
Menggunakan apa-apa selain MIN MAX bersarang,
Ini tidak cepat karena menggunakan 114 masing-masing,
bisa menguranginya menjadi 75 cukup sederhana seperti -> pastebin
Tapi kemudian itu bukan min max lagi.
Yang mungkin berhasil adalah melakukan min / max pada banyak integer sekaligus dengan AVX
Referensi PMINSW
EDIT:
Solusi urutan peringkat yang terinspirasi oleh Rex Kerr, Jauh lebih cepat daripada kekacauan di atas
sumber
int16_t
). Tetapi fungsi C Anda mengklaimnya mengurutkan arrayint
(yang 32-bit dalam semua implementasi C yang mendukungasm
sintaks itu). Apakah Anda mengujinya dengan hanya bilangan bulat positif kecil yang hanya memiliki 0 di bagian tinggi? Itu akan berhasil ... Untukint
Anda membutuhkan SSE4.1pmin/maxsd
(d = dword). felixcloutier.com/x86/pminsd:pminsq ataupminusd
untukuint32_t
.Saya menemukan bahwa setidaknya pada sistem saya, fungsi
sort6_iterator()
dansort6_iterator_local()
definisi di bawah keduanya berjalan setidaknya secepat, dan seringkali terasa lebih cepat, daripada pemegang rekor saat ini di atas:Saya melewati fungsi ini sebagai
std::vector
kode waktu saya.Saya menduga (dari komentar seperti ini dan di tempat lain) bahwa menggunakan iterator memberi g ++ jaminan tertentu tentang apa yang dapat dan tidak dapat terjadi pada memori yang dirujuk oleh iterator, yang sebaliknya tidak dimiliki dan jaminan inilah yang memungkinkan g ++ untuk lebih baik mengoptimalkan kode penyortiran (misalnya dengan pointer, kompiler tidak dapat memastikan bahwa semua pointer menunjuk ke lokasi memori yang berbeda). Jika saya ingat dengan benar, ini juga merupakan bagian dari alasan mengapa banyak algoritma STL, seperti
std::sort()
, umumnya memiliki kinerja yang sangat buruk.Selain itu,
sort6_iterator()
adalah beberapa kali (sekali lagi, tergantung pada konteks di mana fungsi ini dipanggil) secara konsisten mengungguli oleh fungsi menyortir berikut, yang salinan data ke variabel lokal sebelum menyortir mereka. 1 Perhatikan bahwa karena hanya ada 6 variabel lokal yang ditentukan, jika variabel lokal ini primitif maka kemungkinan besar mereka tidak pernah benar-benar disimpan dalam RAM dan sebaliknya hanya pernah disimpan dalam register CPU sampai akhir panggilan fungsi, yang membantu membuat penyortiran ini. berfungsi cepat. (Ini juga membantu bahwa kompiler mengetahui bahwa variabel lokal yang berbeda memiliki lokasi yang berbeda dalam memori).Perhatikan bahwa mendefinisikan
SWAP()
sebagai berikut beberapa kali menghasilkan kinerja yang sedikit lebih baik meskipun sebagian besar waktu menghasilkan kinerja yang sedikit lebih buruk atau perbedaan kinerja yang dapat diabaikan.Jika Anda hanya menginginkan algoritma pengurutan yang pada tipe data primitif, gcc -O3 konsisten dalam mengoptimalkan tidak peduli apa pun konteks panggilan ke fungsi pengurutan muncul dalam 1 lalu, tergantung pada bagaimana Anda mengirimkan input, coba salah satu dari dua berikut algoritma:
Atau jika Anda ingin meneruskan variabel dengan referensi, maka gunakan ini (fungsi di bawah ini berbeda dari yang di atas dalam 5 baris pertama):
Alasan menggunakan
register
kata kunci adalah karena ini adalah salah satu dari beberapa kali Anda tahu bahwa Anda menginginkan nilai-nilai ini dalam register. Tanparegister
, kompiler akan mencari tahu sebagian besar waktu tetapi kadang-kadang tidak. Menggunakanregister
kata kunci membantu menyelesaikan masalah ini. Namun, biasanya, jangan gunakanregister
kata kunci karena lebih cenderung memperlambat kode Anda daripada mempercepatnya.Juga, perhatikan penggunaan template. Hal ini dilakukan dengan sengaja karena, bahkan dengan
inline
kata kunci, fungsi template umumnya jauh lebih agresif dioptimalkan oleh gcc daripada fungsi vanilla C (ini ada hubungannya dengan gcc yang perlu berurusan dengan pointer fungsi untuk fungsi vanilla C tetapi tidak dengan fungsi template).sumber
Coba urutkan daftar yang diurutkan. :) Gunakan dua array. Tercepat untuk array kecil dan besar.
Jika Anda menyimpulkan, Anda hanya memeriksa di mana memasukkan. Nilai lebih besar lainnya yang tidak perlu Anda bandingkan (cmp = ab> 0).
Untuk 4 angka, Anda dapat menggunakan sistem 4-5 cmp (~ 4.6) atau 3-6 cmp (~ 4.9). Sortir gelembung menggunakan 6 cmp (6). Banyak cmp untuk kode besar angka lambat.
Kode ini menggunakan 5 cmp (bukan MSL sort):
if (cmp(arr[n][i+0],arr[n][i+1])>0) {swap(n,i+0,i+1);} if (cmp(arr[n][i+2],arr[n][i+3])>0) {swap(n,i+2,i+3);} if (cmp(arr[n][i+0],arr[n][i+2])>0) {swap(n,i+0,i+2);} if (cmp(arr[n][i+1],arr[n][i+3])>0) {swap(n,i+1,i+3);} if (cmp(arr[n][i+1],arr[n][i+2])>0) {swap(n,i+1,i+2);}
MSL prinsipal
9 8 7 6 5 4 3 2 1 0 89 67 45 23 01 ... concat two sorted lists, list length = 1 6789 2345 01 ... concat two sorted lists, list length = 2 23456789 01 ... concat two sorted lists, list length = 4 0123456789 ... concat two sorted lists, list length = 8
kode js
sumber
Sortir 4 item dengan cmp penggunaan == 0. Jumlah cmp adalah ~ 4.34 (FF asli memiliki ~ 4.52), tetapi membutuhkan waktu 3x dari daftar penggabungan. Tapi operasi cmp lebih baik, jika Anda memiliki angka besar atau teks besar. Edit: bug yang diperbaiki
Tes online http://mlich.zam.slu.cz/js-sort/x-sort-x2.htm
sumber
Mungkin aku am terlambat ke pesta, tapi setidaknya kontribusi saya adalah baru pendekatan.
swap
akan lebih tinggi (dari biayacompare
)SWAP()
dua elemen, siklus dikejar, hanya membutuhkan satu temp, dan satu (register-> register) swap (baru <- lama).Pembaruan: sedikit mengubah kode, beberapa orang menggunakan kompiler C ++ untuk mengkompilasi kode C ...
sumber
wsort6()
memiliki antarmuka yang benar.o1..o5
, tidak perlu untuke[6]
array temp kedua . Dan: mengkompilasi kode C pada kompiler C ++, dan menyalahkan kode?#include
. Memperbaikisumber
Nah, jika hanya 6 elemen dan Anda dapat memanfaatkan paralelisme, ingin meminimalkan percabangan bersyarat, dll. Mengapa Anda tidak menghasilkan semua kombinasi dan menguji pesanan? Saya berani mengatakan bahwa dalam beberapa arsitektur, itu bisa sangat cepat (selama Anda memiliki memori yang dialokasikan sebelumnya)
sumber
Berikut adalah tiga metode penyortiran khas yang mewakili tiga kelas yang berbeda dari Algoritma Penyortiran:
Tapi lihat diskusi Stefan Nelsson tentang algoritma penyortiran tercepat? di mana ia membahas solusi yang turun ke
O(n log log n)
.. periksa implementasinya di CAlgoritma Penyortiran Semi-Linier ini disajikan oleh sebuah makalah pada tahun 1995:
A. Andersson, T. Hagerup, S. Nilsson, dan R. Raman. Mengurutkan dalam waktu linier? Dalam Prosiding Simposium ACM Tahunan ke-27 tentang Teori Komputasi, halaman 427-436, 1995.
sumber