Sortir tercepat dengan panjang tetap 6 int array

401

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?

kriss
sumber
2
Apakah Anda memiliki beberapa kendala pada int? Sebagai contoh, dapatkah kita berasumsi bahwa untuk setiap 2 x, y x-ydan x+ytidak akan menyebabkan underflow atau overflow?
Matthieu M.
3
Anda harus mencoba menggabungkan jaringan sortir 12-swap saya dengan fungsi branchless swap Paul. Solusinya meneruskan semua parameter sebagai elemen terpisah pada stack, bukan satu pointer ke array. Itu mungkin juga membuat perbedaan.
Daniel Stutzbach
2
Perhatikan bahwa implementasi rdtsc yang benar pada 64-bit adalah __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.
Paolo Bonzini
3
@ Tyler: Bagaimana Anda menerapkannya di tingkat perakitan tanpa cabang?
Loren Pechtel
4
@ Loren: CMP EAX, EBX; SBB EAX, EAXakan menempatkan 0 atau 0xFFFFFFFF di EAXtergantung pada apakah EAXlebih besar atau lebih kecil dari EBX, masing-masing. SBBadalah "kurangi dengan meminjam", mitra dari ADC("tambah dengan carry"); bit status yang Anda lihat adalah carry bit. Kemudian lagi, saya ingat itu ADCdan SBBmemiliki latensi & throughput yang mengerikan pada Pentium 4 vs ADDdan SUB, dan masih dua kali lebih lambat pada Core CPU. Sejak 80386 ada juga instruksi SETccconditional-store dan CMOVccconditional-move, tetapi mereka juga lambat.
j_random_hacker

Jawaban:

162

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:

static __inline__ int sort6(int *d){
        int i, j;
        for (i = 1; i < 6; i++) {
                int tmp = d[i];
                for (j = i; j >= 1 && tmp < d[j-1]; j--)
                        d[j] = d[j-1];
                d[j] = tmp;
        }
}

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:

static __inline__ int sort6(int * d){
#define SWAP(x,y) if (d[y] < d[x]) { int tmp = d[x]; d[x] = d[y]; d[y] = tmp; }
    SWAP(1, 2);
    SWAP(0, 2);
    SWAP(0, 1);
    SWAP(4, 5);
    SWAP(3, 5);
    SWAP(3, 4);
    SWAP(0, 3);
    SWAP(1, 4);
    SWAP(2, 5);
    SWAP(2, 4);
    SWAP(1, 3);
    SWAP(2, 3);
#undef SWAP
}
Daniel Stutzbach
sumber
9
+1: bagus, Anda melakukannya dengan 12 pertukaran alih-alih 13 di jaringan kode tangan saya dan yang diturunkan secara empiris di atas. Saya akan memberi Anda +1 lainnya jika saya bisa untuk tautan ke situs yang menghasilkan jaringan untuk Anda - sekarang di-bookmark.
Paul R
9
Ini adalah ide yang fantastis untuk fungsi penyortiran tujuan umum jika Anda mengharapkan sebagian besar permintaan menjadi array berukuran kecil. Gunakan pernyataan beralih untuk kasus yang ingin Anda optimalkan, menggunakan prosedur ini; biarkan case default menggunakan fungsi sortir perpustakaan.
Mark Ransom
5
@ Mark Fungsi sortir perpustakaan yang baik sudah memiliki jalur cepat untuk array kecil. Banyak perpustakaan modern akan menggunakan QuickSort rekursif atau MergeSort yang beralih ke InsertionSort setelah berulang ke n < SMALL_CONSTANT.
Daniel Stutzbach
3
@ Mark Yah, fungsi semacam pustaka C mengharuskan Anda menentukan operasi perbandingan melalui porter fungsi. Besarnya memanggil fungsi untuk setiap perbandingan sangat besar. Biasanya, itu masih cara paling bersih untuk pergi, karena ini jarang merupakan jalur kritis dalam program. Namun, jika itu adalah jalur kritis, kita benar-benar dapat mengurutkan lebih cepat jika kita tahu kita sedang menyortir bilangan bulat dan tepatnya 6 diantaranya. :)
Daniel Stutzbach
7
@ tgwh: XOR swap hampir selalu merupakan ide yang buruk.
Paul R
63

Berikut ini implementasi menggunakan jaringan penyortiran :

inline void Sort2(int *p0, int *p1)
{
    const int temp = min(*p0, *p1);
    *p1 = max(*p0, *p1);
    *p0 = temp;
}

inline void Sort3(int *p0, int *p1, int *p2)
{
    Sort2(p0, p1);
    Sort2(p1, p2);
    Sort2(p0, p1);
}

inline void Sort4(int *p0, int *p1, int *p2, int *p3)
{
    Sort2(p0, p1);
    Sort2(p2, p3);
    Sort2(p0, p2);  
    Sort2(p1, p3);  
    Sort2(p1, p2);  
}

inline void Sort6(int *p0, int *p1, int *p2, int *p3, int *p4, int *p5)
{
    Sort3(p0, p1, p2);
    Sort3(p3, p4, p5);
    Sort2(p0, p3);  
    Sort2(p2, p5);  
    Sort4(p1, p2, p3, p4);  
}

Anda benar-benar membutuhkan percabangan mindan maximplementasi yang sangat efisien untuk ini, karena itulah yang secara efektif didasari oleh kode ini - suatu urutan mindan maxoperasi (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

Paul R
sumber
1
Untuk beberapa peretasan bit untuk min / maks: graphics.stanford.edu/ ~
seander
1
@ Paul: dalam konteks penggunaan CUDA nyata, itu tentu jawaban terbaik. Saya akan memeriksa apakah itu juga (dan berapa banyak) dalam konteks golf x64 dan mempublikasikan hasilnya.
Kriss
1
Sort3akan lebih cepat (pada kebanyakan arsitektur, toh) jika Anda mencatat bahwa itu (a+b+c)-(min+max)adalah angka sentral.
Rex Kerr
1
@Rex: Begitu - itu terlihat bagus. Untuk arsitektur SIMD seperti AltiVec dan SSE itu akan menjadi jumlah siklus instruksi yang sama (maks dan min adalah instruksi siklus tunggal seperti menambah / mengurangi), tetapi untuk CPU skalar normal, metode Anda terlihat lebih baik.
Paul R
2
Jika saya membiarkan GCC mengoptimalkan menit dengan petunjuk langkah bersyarat saya mendapatkan 33% speedup: #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.
Paolo Bonzini
45

Karena ini adalah bilangan bulat dan perbandingannya cepat, mengapa tidak menghitung urutan peringkat masing-masing secara langsung:

inline void sort6(int *d) {
  int e[6];
  memcpy(e,d,6*sizeof(int));
  int o0 = (d[0]>d[1])+(d[0]>d[2])+(d[0]>d[3])+(d[0]>d[4])+(d[0]>d[5]);
  int o1 = (d[1]>=d[0])+(d[1]>d[2])+(d[1]>d[3])+(d[1]>d[4])+(d[1]>d[5]);
  int o2 = (d[2]>=d[0])+(d[2]>=d[1])+(d[2]>d[3])+(d[2]>d[4])+(d[2]>d[5]);
  int o3 = (d[3]>=d[0])+(d[3]>=d[1])+(d[3]>=d[2])+(d[3]>d[4])+(d[3]>d[5]);
  int o4 = (d[4]>=d[0])+(d[4]>=d[1])+(d[4]>=d[2])+(d[4]>=d[3])+(d[4]>d[5]);
  int o5 = 15-(o0+o1+o2+o3+o4);
  d[o0]=e[0]; d[o1]=e[1]; d[o2]=e[2]; d[o3]=e[3]; d[o4]=e[4]; d[o5]=e[5];
}
Rex Kerr
sumber
@Rex: dengan gcc -O1 di bawah 1000 siklus, cukup cepat tetapi lebih lambat dari penyortiran jaringan. Ada ide untuk memperbaiki kode? Mungkin jika kita bisa menghindari salinan array ...
kriss
@ Kriss: Ini lebih cepat daripada jaringan pengurutan untuk saya dengan -O2. Apakah ada alasan mengapa -O2 tidak baik-baik saja, atau lebih lambat untuk Anda di -O2 juga? Mungkin itu perbedaan dalam arsitektur mesin?
Rex Kerr
1
@Rex: maaf, saya melewatkan pola> vs> = pada pandangan pertama. Ini berfungsi dalam setiap kasus.
Kriss
3
@ Kriss: Aha. Itu tidak sepenuhnya mengejutkan - ada banyak variabel melayang-layang, dan mereka harus hati-hati dipesan dan di-cache dalam register dan sebagainya.
Rex Kerr
2
@Spoke 0+1+2+3+4+5=15Karena salah satu dari mereka tidak ada, 15 dikurangi jumlah sisanya yang hilang
Glenn Teitelbaum
35

Sepertinya 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).

#include <stdio.h>

static inline void sort6_fast(int * d) {
#define SWAP(x,y) { int dx = x, dy = y, tmp; tmp = x = dx < dy ? dx : dy; y ^= dx ^ tmp; }
    register int x0,x1,x2,x3,x4,x5;
    x1 = d[1];
    x2 = d[2];
    SWAP(x1, x2);
    x4 = d[4];
    x5 = d[5];
    SWAP(x4, x5);
    x0 = d[0];
    SWAP(x0, x2);
    x3 = d[3];
    SWAP(x3, x5);
    SWAP(x0, x1);
    SWAP(x3, x4);
    SWAP(x1, x4);
    SWAP(x0, x3);
    d[0] = x0;
    SWAP(x2, x5);
    d[5] = x5;
    SWAP(x1, x3);
    d[1] = x1;
    SWAP(x2, x4);
    d[4] = x4;
    SWAP(x2, x3);
    d[2] = x2;
    d[3] = x3;

#undef SWAP
#undef min
#undef max
}

static __inline__ unsigned long long rdtsc(void)
{
    unsigned long long int x;
    __asm__ volatile ("rdtsc; shlq $32, %%rdx; orq %%rdx, %0" : "=a" (x) : : "rdx");
    return x;
}

void ran_fill(int n, int *a) {
    static int seed = 76521;
    while (n--) *a++ = (seed = seed *1812433253 + 12345);
}

#define NTESTS 4096
int main() {
    int i;
    int d[6*NTESTS];
    ran_fill(6*NTESTS, d);

    unsigned long long cycles = rdtsc();
    for (i = 0; i < 6*NTESTS ; i+=6) {
        sort6_fast(d+i);
    }
    cycles = rdtsc() - cycles;
    printf("Time is %.2lf\n", (double)cycles/(double)NTESTS);

    for (i = 0; i < 6*NTESTS ; i+=6) {
        if (d[i+0] > d[i+1] || d[i+1] > d[i+2] || d[i+2] > d[i+3] || d[i+3] > d[i+4] || d[i+4] > d[i+5])
            printf("d%d : %d %d %d %d %d %d\n", i,
                    d[i+0], d[i+1], d[i+2],
                    d[i+3], d[i+4], d[i+5]);
    }
    return 0;
}

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.

Clarkdale (i5-650)
==================
Direct call to qsort library function      635.14   575.65   581.61   577.76   521.12
Naive implementation (insertion sort)      538.30   135.36   134.89   240.62   101.23
Insertion Sort (Daniel Stutzbach)          424.48   159.85   160.76   152.01   151.92
Insertion Sort Unrolled                    339.16   125.16   125.81   129.93   123.16
Rank Order                                 184.34   106.58   54.74    93.24    94.09
Rank Order with registers                  127.45   104.65   53.79    98.05    97.95
Sorting Networks (Daniel Stutzbach)        269.77   130.56   128.15   126.70   127.30
Sorting Networks (Paul R)                  551.64   103.20   64.57    73.68    73.51
Sorting Networks 12 with Fast Swap         321.74   61.61    63.90    67.92    67.76
Sorting Networks 12 reordered Swap         318.75   60.69    65.90    70.25    70.06
Reordered Sorting Network w/ fast swap     145.91   34.17    32.66    32.22    32.18

Kentsfield (Core 2 Quad)
========================
Direct call to qsort library function      870.01   736.39   723.39   725.48   721.85
Naive implementation (insertion sort)      503.67   174.09   182.13   284.41   191.10
Insertion Sort (Daniel Stutzbach)          345.32   152.84   157.67   151.23   150.96
Insertion Sort Unrolled                    316.20   133.03   129.86   118.96   105.06
Rank Order                                 164.37   138.32   46.29    99.87    99.81
Rank Order with registers                  115.44   116.02   44.04    116.04   116.03
Sorting Networks (Daniel Stutzbach)        230.35   114.31   119.15   110.51   111.45
Sorting Networks (Paul R)                  498.94   77.24    63.98    62.17    65.67
Sorting Networks 12 with Fast Swap         315.98   59.41    58.36    60.29    55.15
Sorting Networks 12 reordered Swap         307.67   55.78    51.48    51.67    50.74
Reordered Sorting Network w/ fast swap     149.68   31.46    30.91    31.54    31.58

Sandy Bridge (i7-2600k)
=======================
Direct call to qsort library function      559.97   451.88   464.84   491.35   458.11
Naive implementation (insertion sort)      341.15   160.26   160.45   154.40   106.54
Insertion Sort (Daniel Stutzbach)          284.17   136.74   132.69   123.85   121.77
Insertion Sort Unrolled                    239.40   110.49   114.81   110.79   117.30
Rank Order                                 114.24   76.42    45.31    36.96    36.73
Rank Order with registers                  105.09   32.31    48.54    32.51    33.29
Sorting Networks (Daniel Stutzbach)        210.56   115.68   116.69   107.05   124.08
Sorting Networks (Paul R)                  364.03   66.02    61.64    45.70    44.19
Sorting Networks 12 with Fast Swap         246.97   41.36    59.03    41.66    38.98
Sorting Networks 12 reordered Swap         235.39   38.84    47.36    38.61    37.29
Reordered Sorting Network w/ fast swap     115.58   27.23    27.75    27.25    26.54

Nehalem (Xeon E5640)
====================
Direct call to qsort library function      911.62   890.88   681.80   876.03   872.89
Naive implementation (insertion sort)      457.69   236.87   127.68   388.74   175.28
Insertion Sort (Daniel Stutzbach)          317.89   279.74   147.78   247.97   245.09
Insertion Sort Unrolled                    259.63   220.60   116.55   221.66   212.93
Rank Order                                 140.62   197.04   52.10    163.66   153.63
Rank Order with registers                  84.83    96.78    50.93    109.96   54.73
Sorting Networks (Daniel Stutzbach)        214.59   220.94   118.68   120.60   116.09
Sorting Networks (Paul R)                  459.17   163.76   56.40    61.83    58.69
Sorting Networks 12 with Fast Swap         284.58   95.01    50.66    53.19    55.47
Sorting Networks 12 reordered Swap         281.20   96.72    44.15    56.38    54.57
Reordered Sorting Network w/ fast swap     128.34   50.87    26.87    27.91    28.02
Saham Kevin
sumber
Ide Anda tentang variabel register harus diterapkan ke solusi "Urutan Peringkat" Rex Kerr. Itu harus tercepat, dan mungkin kemudian -O3optimasi tidak akan menjadi kontra-produktif.
cdunn2001
1
@ cdunn2001 Saya baru saja mengujinya, saya tidak melihat peningkatan (kecuali beberapa siklus di -O0 dan -Os). Melihat ASM tampaknya gcc sudah berhasil mencari tahu untuk menggunakan register dan menghilangkan panggilan untuk memcpy.
Kevin Stock
Maukah Anda menambahkan versi swap sederhana ke suite uji Anda, saya kira itu bisa menarik untuk membandingkannya dengan perakitan swap cepat dioptimalkan dengan tangan.
Kriss
1
Kode Anda masih menggunakan swap Gunderson, jadi milik saya #define SWAP(x,y) { int oldx = x; x = x < y ? x : y; y ^= oldx ^ x; }.
Paolo Bonzini
@ Paolo Bonzini: Ya, saya bermaksud menambahkan test case dengan milik Anda, hanya saja belum sempat. Tapi saya akan menghindari perakitan inline.
Kriss
15

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 digunakanchar 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...

PUBLIC simd_sort_6

.DATA

ALIGN 16

pass1_shuffle   OWORD   0F0E0D0C0B0A09080706040503010200h
pass1_add       OWORD   0F0E0D0C0B0A09080706050503020200h
pass2_shuffle   OWORD   0F0E0D0C0B0A09080706030405000102h
pass2_and       OWORD   00000000000000000000FE00FEFE00FEh
pass2_add       OWORD   0F0E0D0C0B0A09080706050405020102h
pass3_shuffle   OWORD   0F0E0D0C0B0A09080706020304050001h
pass3_and       OWORD   00000000000000000000FDFFFFFDFFFFh
pass3_add       OWORD   0F0E0D0C0B0A09080706050404050101h
pass4_shuffle   OWORD   0F0E0D0C0B0A09080706050100020403h
pass4_and       OWORD   0000000000000000000000FDFD00FDFDh
pass4_add       OWORD   0F0E0D0C0B0A09080706050403020403h
pass5_shuffle   OWORD   0F0E0D0C0B0A09080706050201040300h
pass5_and       OWORD 0000000000000000000000FEFEFEFE00h
pass5_add       OWORD   0F0E0D0C0B0A09080706050403040300h
pass6_shuffle   OWORD   0F0E0D0C0B0A09080706050402030100h
pass6_add       OWORD   0F0E0D0C0B0A09080706050403030100h

.CODE

simd_sort_6 PROC FRAME

    .endprolog

    ; pxor xmm4, xmm4
    ; pinsrd xmm4, dword ptr [rcx], 0
    ; pinsrb xmm4, byte ptr [rcx + 4], 4
    ; pinsrb xmm4, byte ptr [rcx + 5], 5
    ; The benchmarked 38% faster mentioned in the text was with the above slower sequence that tied up the shuffle port longer.  Same on extract
    ; avoiding pins/extrb also means we don't need SSE 4.1, but SSSE3 CPUs without SSE4.1 (e.g. Conroe/Merom) have slow pshufb.
    movd    xmm4, dword ptr [rcx]
    pinsrw  xmm4,  word ptr [rcx + 4], 2  ; word 2 = bytes 4 and 5


    movdqa xmm5, xmm4
    pshufb xmm5, oword ptr [pass1_shuffle]
    pcmpgtb xmm5, xmm4
    paddb xmm5, oword ptr [pass1_add]
    pshufb xmm4, xmm5

    movdqa xmm5, xmm4
    pshufb xmm5, oword ptr [pass2_shuffle]
    pcmpgtb xmm5, xmm4
    pand xmm5, oword ptr [pass2_and]
    paddb xmm5, oword ptr [pass2_add]
    pshufb xmm4, xmm5

    movdqa xmm5, xmm4
    pshufb xmm5, oword ptr [pass3_shuffle]
    pcmpgtb xmm5, xmm4
    pand xmm5, oword ptr [pass3_and]
    paddb xmm5, oword ptr [pass3_add]
    pshufb xmm4, xmm5

    movdqa xmm5, xmm4
    pshufb xmm5, oword ptr [pass4_shuffle]
    pcmpgtb xmm5, xmm4
    pand xmm5, oword ptr [pass4_and]
    paddb xmm5, oword ptr [pass4_add]
    pshufb xmm4, xmm5

    movdqa xmm5, xmm4
    pshufb xmm5, oword ptr [pass5_shuffle]
    pcmpgtb xmm5, xmm4
    pand xmm5, oword ptr [pass5_and]
    paddb xmm5, oword ptr [pass5_add]
    pshufb xmm4, xmm5

    movdqa xmm5, xmm4
    pshufb xmm5, oword ptr [pass6_shuffle]
    pcmpgtb xmm5, xmm4
    paddb xmm5, oword ptr [pass6_add]
    pshufb xmm4, xmm5

    ;pextrd dword ptr [rcx], xmm4, 0    ; benchmarked with this
    ;pextrb byte ptr [rcx + 4], xmm4, 4 ; slower version
    ;pextrb byte ptr [rcx + 5], xmm4, 5
    movd   dword ptr [rcx], xmm4
    pextrw  word ptr [rcx + 4], xmm4, 2  ; x86 is little-endian, so this is the right order

    ret

simd_sort_6 ENDP

END

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:

void simd_sort_6(char *values);
Joe Crivello
sumber
Akan interresting untuk membandingkan proposal Anda dengan proposal tingkat majelis lainnya. Kinerja implementasi yang dibandingkan tidak termasuk mereka. Bagaimanapun juga, menggunakan SSE terdengar bagus.
Kriss
Bidang lain dari penelitian masa depan adalah penerapan instruksi Intel AVX baru untuk masalah ini. Vektor 256-bit yang lebih besar cukup besar untuk memuat 8 DWORD.
Joe Crivello
1
Alih-alih pxor / pinsrd xmm4, mem, 0, gunakan saja movd!
Peter Cordes
14

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

#define SWAP(x,y) { int tmp; asm("mov %0, %2 ; cmp %1, %0 ; cmovg %1, %0 ; cmovg %2, %1" : "=r" (d[x]), "=r" (d[y]), "=r" (tmp) : "0" (d[x]), "1" (d[y]) : "cc"); }

dan itu keluar sekitar 65% lebih cepat untuk saya (Debian gcc 4.4.5 dengan -O2, amd64, Core i7).

Steinar H. Gunderson
sumber
Oke, kode tes buruk. Jangan ragu untuk memperbaikinya. Dan ya, Anda dapat menggunakan kode perakitan. Mengapa tidak berjalan sepenuhnya dan kode sepenuhnya menggunakan assembler x86? Ini mungkin sedikit kurang portabel tetapi mengapa repot-repot?
Kriss
Terima kasih telah memperhatikan limpahan array, saya memperbaikinya. Orang lain mungkin tidak menyadarinya karena mengklik tautan untuk menyalin / menempel kode, di mana tidak ada overflow.
Kriss
4
Anda bahkan tidak perlu assembler, sebenarnya; jika Anda hanya meninggalkan semua trik pintar, GCC akan mengenali urutan dan menyisipkan gerakan bersyarat untuk Anda: #define min (a, b) ((a <b)? a: b) #define max (a, b) ( (a <b)? b: a) #define SWAP (x, y) {int a = min (d [x], d [y]); int b = maks (d [x], d [y]); d [x] = a; d [y] = b; } Keluar mungkin beberapa persen lebih lambat dari varian asm inline, tapi itu sulit dikatakan mengingat kurangnya pembandingan yang tepat.
Steinar H. Gunderson
3
... dan akhirnya, jika angka Anda mengambang, dan Anda tidak perlu khawatir tentang NaN dll., GCC dapat mengonversikan ini ke minss / maxss instruksi SSE, yang belum ~ 25% lebih cepat. Moral: Jatuhkan trik bitfiddling pintar dan biarkan kompiler melakukan tugasnya. :-)
Steinar H. Gunderson
13

Sementara saya sangat suka swap makro yang disediakan:

#define min(x, y) (y ^ ((x ^ y) & -(x < y)))
#define max(x, y) (x ^ ((x ^ y) & -(x < y)))
#define SWAP(x,y) { int tmp = min(d[x], d[y]); d[y] = max(d[x], d[y]); d[x] = tmp; }

Saya melihat peningkatan (yang mungkin dilakukan oleh kompiler yang baik):

#define SWAP(x,y) { int tmp = ((x ^ y) & -(y < x)); y ^= tmp; x ^= tmp; }

Kami mencatat cara kerja min dan max dan menarik sub-ekspresi umum secara eksplisit. Ini menghilangkan makro min dan maks sepenuhnya.

phkahler
sumber
Itu membuat mereka mundur, perhatikan bahwa d [y] mendapatkan maks, yaitu x ^ (subekspresi umum).
Kevin Stock
Saya perhatikan hal yang sama; Saya pikir untuk implementasi Anda menjadi benar yang Anda inginkan, d[x]bukan x(sama untuk y), dan d[y] < d[x]untuk ketidaksetaraan di sini (ya, berbeda dari kode min / max).
Tyler
Saya mencoba dengan swap Anda, tetapi pengoptimalan lokal memiliki efek negatif pada tingkat yang lebih besar (saya kira itu memperkenalkan dependensi). Dan hasilnya lebih lambat dari swap lainnya. Tetapi seperti yang Anda lihat dengan solusi baru yang diajukan, memang ada banyak kinerja untuk mendapatkan swap yang optimal.
Kriss
12

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%:

#define SWAP(x,y) { int dx = d[x], dy = d[y], tmp; tmp = d[x] = dx < dy ? dx : dy; d[y] ^= dx ^ tmp; }

(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 (sepertid0 = 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:

SWAP(0,1); SWAP(1,2); SWAP(2,3); SWAP(3,4); SWAP(4,5);
SWAP(0,1); SWAP(1,2); SWAP(2,3); SWAP(3,4);
SWAP(0,1); SWAP(1,2); SWAP(2,3);
SWAP(0,1); SWAP(1,2);
SWAP(0,1);

dan ini adalah jenis sisipan:

//#define ITER(x) { if (t < d[x]) { d[x+1] = d[x]; d[x] = t; } }
//Faster on x86, probably slower on ARM or similar:
#define ITER(x) { d[x+1] ^= t < d[x] ? d[x] ^ d[x+1] : 0; d[x] = t < d[x] ? t : d[x]; }
static inline void sort6_insertion_sort_unrolled_v2(int * d){
    int t;
    t = d[1]; ITER(0);
    t = d[2]; ITER(1); ITER(0);
    t = d[3]; ITER(2); ITER(1); ITER(0);
    t = d[4]; ITER(3); ITER(2); ITER(1); ITER(0);
    t = d[5]; ITER(4); ITER(3); ITER(2); ITER(1); ITER(0);

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:

    MOV    r6, r2
    CMP    r6, r1
    MOVLT  r2, r1
    MOVLT  r1, r6
    CMP    r6, r0
    MOVLT  r1, r0
    MOVLT  r0, r6

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).

Paolo Bonzini
sumber
1
Kurang lebih terkait: Saya mengirimkan laporan ke GCC sehingga dapat mengimplementasikan optimasi langsung di kompiler. Tidak yakin itu akan dilakukan, tetapi setidaknya Anda dapat mengikuti bagaimana itu berkembang.
Morwenn
11

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

jheriko
sumber
1
Sangat menarik. Sepertinya swap tanpa cabang adalah ide yang buruk pada PPC. Ini juga bisa menjadi efek terkait kompiler. Yang mana yang digunakan?
Kriss
Ini adalah cabang dari gcc compiler - min, max logic mungkin bukan branchless - saya akan memeriksa pembongkaran dan memberi tahu Anda, tetapi kecuali jika kompilernya cukup pintar termasuk sesuatu seperti x <y tanpa jika masih menjadi cabang - pada x86 / x64 instruksi CMOV mungkin menghindari ini, tetapi tidak ada instruksi untuk nilai titik tetap pada PPC, hanya float. Saya mungkin mencoba-coba ini besok dan memberi tahu Anda - saya ingat ada min / max branchless yang jauh lebih sederhana di sumber AVS Winamp, tapi iirc itu hanya untuk float - tetapi mungkin merupakan awal yang baik menuju pendekatan yang benar-benar tanpa cabang.
jheriko
4
Berikut ini adalah branchless min / max untuk PPC dengan input unsigned: 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.
Paolo Bonzini
7

Swap XOR mungkin berguna dalam fungsi swapping Anda.

void xorSwap (int *x, int *y) {
     if (*x != *y) {
         *x ^= *y;
         *y ^= *x;
         *x ^= *y;
     }
 }

Jika dapat menyebabkan terlalu banyak perbedaan dalam kode Anda, tetapi jika Anda memiliki jaminan bahwa semua int Anda unik, ini bisa berguna.

naj
sumber
1
xatau swap berfungsi untuk nilai yang sama juga ... x ^ = y set x ke 0, y ^ = x meninggalkan y sebagai y (== x), x ^ = y set x ke y
jheriko
11
Saat tidak berfungsi adalah kapan xdan yarahkan ke lokasi yang sama.
hobbs
Lagi pula ketika digunakan dengan menyortir jaringan kita tidak pernah memanggil dengan x dan y menunjuk ke lokasi yang sama. Masih ada cara untuk menghindari pengujian yang lebih besar untuk mendapatkan efek yang sama dengan swap tanpa cabang. Saya punya ide untuk mencapainya.
Kriss
5

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:

**Direct call to qsort library function** : 164
**Naive implementation (insertion sort)** : 138
**Insertion Sort (Daniel Stutzbach)**     : 85
**Insertion Sort Unrolled**               : 97
**Sorting Networks (Daniel Stutzbach)**   : 457
**Sorting Networks (Paul R)**             : 179
**Sorting Networks 12 with Fast Swap**    : 238
**Sorting Networks 12 reordered Swap**    : 236
**Rank Order**                            : 116
Nico
sumber
4

Inilah kontribusi saya untuk utas ini: shellsort celah 1, 4 yang dioptimalkan untuk vektor int 6-anggota (valp) yang berisi nilai-nilai unik.

void shellsort (int *valp)
{      
  int c,a,*cp,*ip=valp,*ep=valp+5;

  c=*valp;    a=*(valp+4);if (c>a) {*valp=    a;*(valp+4)=c;}
  c=*(valp+1);a=*(valp+5);if (c>a) {*(valp+1)=a;*(valp+5)=c;}

  cp=ip;    
  do
  {
    c=*cp;
    a=*(cp+1);
    do
    {
      if (c<a) break;

      *cp=a;
      *(cp+1)=c;
      cp-=1;
      c=*cp;
    } while (cp>=valp);
    ip+=1;
    cp=ip;
  } while (ip<ep);
}

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.

Olof Forshell
sumber
bagus. Aku akan menambahkannya ke lagi testsuite
kriss
3

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).

static __inline__ int sort6(int * d) {
    char j, i;
    int tmp;
    for (inc = 4; inc > 0; inc -= 3) {
        for (i = inc; i < 5; i++) {
            tmp = a[i];
            j = i;
            while (j >= inc && a[j - inc] > tmp) {
                a[j] = a[j - inc];
                j -= inc;
            }
            a[j] = tmp;
        }
    }
}

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

gcp
sumber
jangan ragu untuk mengusulkan beberapa implementasi :-)
kriss
Proposal ditambahkan. Selamat menikmati bug.
gcp
3

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.

static inline void sort6_insertion_sort_avx(int* d) {
    __m256i src = _mm256_setr_epi32(d[0], d[1], d[2], d[3], d[4], d[5], 0, 0);
    __m256i index = _mm256_setr_epi32(0, 1, 2, 3, 4, 5, 6, 7);
    __m256i shlpermute = _mm256_setr_epi32(7, 0, 1, 2, 3, 4, 5, 6);
    __m256i sorted = _mm256_setr_epi32(d[0], INT_MAX, INT_MAX, INT_MAX,
            INT_MAX, INT_MAX, INT_MAX, INT_MAX);
    __m256i val, gt, permute;
    unsigned j;
     // 8 / 32 = 2^-2
#define ITER(I) \
        val = _mm256_permutevar8x32_epi32(src, _mm256_set1_epi32(I));\
        gt =  _mm256_cmpgt_epi32(sorted, val);\
        permute =  _mm256_blendv_epi8(index, shlpermute, gt);\
        j = ffs( _mm256_movemask_epi8(gt)) >> 2;\
        sorted = _mm256_blendv_epi8(_mm256_permutevar8x32_epi32(sorted, permute),\
                val, _mm256_cmpeq_epi32(index, _mm256_set1_epi32(j)))
    ITER(1);
    ITER(2);
    ITER(3);
    ITER(4);
    ITER(5);
    int x[8];
    _mm256_storeu_si256((__m256i*)x, sorted);
    d[0] = x[0]; d[1] = x[1]; d[2] = x[2]; d[3] = x[3]; d[4] = x[4]; d[5] = x[5];
#undef ITER
}

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

static inline void sort6_rank_order_avx(int* d) {
    __m256i ror = _mm256_setr_epi32(5, 0, 1, 2, 3, 4, 6, 7);
    __m256i one = _mm256_set1_epi32(1);
    __m256i src = _mm256_setr_epi32(d[0], d[1], d[2], d[3], d[4], d[5], INT_MAX, INT_MAX);
    __m256i rot = src;
    __m256i index = _mm256_setzero_si256();
    __m256i gt, permute;
    __m256i shl = _mm256_setr_epi32(1, 2, 3, 4, 5, 6, 6, 6);
    __m256i dstIx = _mm256_setr_epi32(0,1,2,3,4,5,6,7);
    __m256i srcIx = dstIx;
    __m256i eq = one;
    __m256i rotIx = _mm256_setzero_si256();
#define INC(I)\
    rot = _mm256_permutevar8x32_epi32(rot, ror);\
    gt = _mm256_cmpgt_epi32(src, rot);\
    index = _mm256_add_epi32(index, _mm256_and_si256(gt, one));\
    index = _mm256_add_epi32(index, _mm256_and_si256(eq,\
                _mm256_cmpeq_epi32(src, rot)));\
    eq = _mm256_insert_epi32(eq, 0, I)
    INC(0);
    INC(1);
    INC(2);
    INC(3);
    INC(4);
    int e[6];
    e[0] = d[0]; e[1] = d[1]; e[2] = d[2]; e[3] = d[3]; e[4] = d[4]; e[5] = d[5];
    int i[8];
    _mm256_storeu_si256((__m256i*)i, index);
    d[i[0]] = e[0]; d[i[1]] = e[1]; d[i[2]] = e[2]; d[i[3]] = e[3]; d[i[4]] = e[4]; d[i[5]] = e[5];
}

Repo dapat ditemukan di sini: https://github.com/eyepatchParrot/sort6/

revs
sumber
1
Anda dapat menggunakan vmovmskpspada vektor integer (dengan gips untuk menjaga intrinsik senang), menghindari kebutuhan untuk menggeser-kanan hasil bitscan ( ffs).
Peter Cordes
1
Anda dapat menambahkan secara kondisional berdasarkan cmpgthasil dengan mengurangkannya , alih-alih menutupinya set1(1). mis. index = _mm256_sub_epi32(index, gt)tidakindex -= -1 or 0;
Peter Cordes
1
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, karena vpinsrdhanya tersedia dengan tujuan XMM; indeks lebih tinggi dari 3 harus ditiru). Sebaliknya, _mm256_blend_epi32( vpblendd) dengan vektor memusatkan perhatian. vpblenddadalah instruksi single-uop yang berjalan pada port apa saja, vs. shuffle yang membutuhkan port 5 pada CPU Intel. ( agner.org/optimize ).
Peter Cordes
1
Selain itu, Anda dapat mempertimbangkan membuat rotvektor 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.
Peter Cordes
2

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 sort6menggunakan algoritma sort4yang menggunakan algoritma sort3. 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:

void sort3(int* array)
{
    if (array[1] < array[0]) {
        if (array[2] < array[0]) {
            if (array[2] < array[1]) {
                std::swap(array[0], array[2]);
            } else {
                int tmp = array[0];
                array[0] = array[1];
                array[1] = array[2];
                array[2] = tmp;
            }
        } else {
            std::swap(array[0], array[1]);
        }
    } else {
        if (array[2] < array[1]) {
            if (array[2] < array[0]) {
                int tmp = array[2];
                array[2] = array[1];
                array[1] = array[0];
                array[0] = tmp;
            } else {
                std::swap(array[1], array[2]);
            }
        }
    }
}

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 sort3kemudian melakukan jenis penyisipan yang tidak terbuka dengan elemen terakhir dari array:

void sort4(int* array)
{
    // Sort the first 3 elements
    sort3(array);

    // Insert the 4th element with insertion sort 
    if (array[3] < array[2]) {
        std::swap(array[2], array[3]);
        if (array[2] < array[1]) {
            std::swap(array[1], array[2]);
            if (array[1] < array[0]) {
                std::swap(array[0], array[1]);
            }
        }
    }
}

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:

  • Urutkan semuanya kecuali elemen pertama dan terakhir dari array.
  • Tukar elemen pertama dan elemen array jika yang pertama lebih besar dari yang terakhir.
  • Masukkan elemen pertama ke dalam urutan yang diurutkan dari depan lalu elemen terakhir dari belakang.

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.

void sort6(int* array)
{
    // Sort everything but first and last elements
    sort4(array+1);

    // Switch first and last elements if needed
    if (array[5] < array[0]) {
        std::swap(array[0], array[5]);
    }

    // Insert first element from the front
    if (array[1] < array[0]) {
        std::swap(array[0], array[1]);
        if (array[2] < array[1]) {
            std::swap(array[1], array[2]);
            if (array[3] < array[2]) {
                std::swap(array[2], array[3]);
                if (array[4] < array[3]) {
                    std::swap(array[3], array[4]);
                }
            }
        }
    }

    // Insert last element from the back
    if (array[5] < array[4]) {
        std::swap(array[4], array[5]);
        if (array[4] < array[3]) {
            std::swap(array[3], array[4]);
            if (array[3] < array[2]) {
                std::swap(array[2], array[3]);
                if (array[2] < array[1]) {
                    std::swap(array[1], array[2]);
                }
            }
        }
    }
}

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.

Morwenn
sumber
Ini bagus. Karena masalah terpecahkan sudah puluhan tahun, mungkin sama tua dengan pemrograman C, bahwa pertanyaannya sekarang sudah hampir 5 tahun kelihatannya tidak terlalu relevan.
Kriss
Anda harus melihat bagaimana jawaban lain diatur waktunya. Intinya adalah bahwa dengan perbandingan penghitungan dataset kecil atau bahkan perbandingan dan swap tidak benar-benar mengatakan seberapa cepat suatu algoritma (pada dasarnya menyortir 6 int selalu O (1) karena O (6 * 6) adalah O (1)). Solusi tercepat yang diusulkan sebelumnya adalah segera menemukan posisi masing-masing nilai menggunakan perbandingan besar (oleh RexKerr).
Kriss
@ Kriss Apakah ini yang tercepat sekarang? Dari hasil pembacaan saya, pendekatan jaringan sortir adalah yang tercepat, yang buruk. Itu juga benar bahwa solusi saya berasal dari perpustakaan umum saya dan bahwa saya tidak selalu membandingkan bilangan bulat, juga tidak selalu menggunakan 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 :)
Morwenn
Solusi oleh RexKerr (Urutan Peringkat) menjadi yang tercepat pada arsitektur X86 sejak compiler gcc 4.2.3 (dan pada gcc 4.9 menjadi hampir dua kali lebih cepat daripada yang terbaik kedua). Tapi itu sangat tergantung pada optimisasi kompiler dan mungkin tidak benar pada arsitektur lain.
Kriss
@ Kriss Itu menarik untuk diketahui. Dan saya memang bisa lebih banyak perbedaan lagi dengan -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 :)
Morwenn
1

Saya percaya ada dua bagian dari pertanyaan Anda.

  • Yang pertama adalah menentukan algoritma yang optimal. Hal ini dilakukan - setidaknya dalam kasus ini - dengan mengulangi setiap pemesanan yang mungkin (tidak ada banyak) yang memungkinkan Anda untuk menghitung min, maks, rata-rata dan standar deviasi dari perbandingan dan swap. Siapkan juga satu atau dua runner-up.
  • Yang kedua adalah mengoptimalkan algoritma. Banyak yang bisa dilakukan untuk mengonversi contoh kode buku teks menjadi mean dan bersandar pada algoritma kehidupan nyata. Jika Anda menyadari bahwa suatu algoritma tidak dapat dioptimalkan sejauh yang diperlukan, cobalah runner-up.

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.

Olof Forshell
sumber
Saya tidak yakin bagaimana memahami jawaban Anda. Pertama saya tidak mengerti sama sekali algoritma apa yang Anda usulkan? Dan bagaimana itu bisa optimal jika Anda harus mengulang melalui 720 kemungkinan pemesanan (jawaban yang ada membutuhkan waktu kurang dari 720 siklus). Jika Anda memiliki input acak, saya tidak dapat membayangkan (bahkan pada tingkat teoretis) bagaimana prediksi cabang dapat berkinerja lebih baik dari 50-50 kecuali jika tidak peduli sama sekali pada data input. Juga sebagian besar solusi bagus yang sudah diusulkan kemungkinan akan bekerja dengan data dan kode sepenuhnya dalam cache. Tapi mungkin saya salah paham jawaban Anda. Pikiran menunjukkan beberapa kode?
Kriss
Yang saya maksudkan adalah hanya ada 720 (6!) Kombinasi berbeda dari 6 integer dan dengan menjalankan semuanya melalui algoritma kandidat Anda dapat menentukan banyak hal seperti yang saya sebutkan - itulah bagian teoretisnya. Bagian praktisnya adalah menyelaraskan algoritma tersebut agar berjalan dalam siklus clock sesedikit mungkin. Titik awal saya untuk menyortir 6 integer adalah shellsort 1, 4 gap. Kesenjangan 4 membuka jalan bagi prediksi cabang yang baik di celah 1.
Olof Forshell
Shellsort 1, 4 gap untuk 6! kombinasi unik (dimulai dengan 012345 dan berakhir dengan 543210) akan memiliki kasus terbaik dari 7 perbandingan dan 0 pertukaran dan yang terburuk dari 14 perbandingan dan 10 pertukaran. Kasus rata-rata adalah sekitar 11,14 perbandingan dan 6 pertukaran.
Olof Forshell
1
Saya tidak mendapatkan "distribusi acak reguler" - yang saya lakukan adalah menguji setiap kombinasi yang mungkin dan menentukan statistik min / rata-rata / maks. Shellsort adalah serangkaian jenis penyisipan peningkatan yang berkurang sedemikian rupa sehingga kenaikan akhir - 1 - tidak banyak bekerja dibandingkan jika dilakukan sendirian seperti dalam jenis penyisipan murni. Untuk menghitung jam, algoritma saya membutuhkan rata-rata 406 siklus jam dan ini termasuk mengumpulkan statistik dan melakukan dua panggilan ke rutinitas penyortiran aktual - satu untuk setiap celah. Ini ada pada ponsel Athlon M300, kompiler OpenWatcom.
Olof Forshell
1
"distribusi acak reguler" berarti setiap kombinasi data aktual yang diurutkan mungkin tidak memiliki probabilitas yang sama. Jika setiap kombinasi tidak memiliki probabilitas yang sama, statistik Anda akan rusak karena rata-rata perlu memperhitungkan berapa kali distribusi yang diberikan akan terjadi. Untuk hitungan jam, jika Anda mencoba implementasi lain semacam ini (tautan yang disediakan di atas) dan menjalankannya pada sistem pengujian Anda, kami akan memiliki dasar untuk perbandingan dan melihat seberapa baik kinerja yang Anda pilih.
kriss
1

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

#include <stdio.h>

static __inline__ int MIN(int a, int b){
int result =a;
__asm__ ("pminsw %1, %0" : "+x" (result) : "x" (b));
return result;
}
static __inline__ int MAX(int a, int b){
int result = a;
__asm__ ("pmaxsw %1, %0" : "+x" (result) : "x" (b));
return result;
}
static __inline__ unsigned long long rdtsc(void){
  unsigned long long int x;
__asm__ volatile (".byte 0x0f, 0x31" :
  "=A" (x));
  return x;
}

#define MIN3(a, b, c) (MIN(MIN(a,b),c))
#define MIN4(a, b, c, d) (MIN(MIN(a,b),MIN(c,d)))

static __inline__ void sort6(int * in) {
  const int A=in[0], B=in[1], C=in[2], D=in[3], E=in[4], F=in[5];

  in[0] = MIN( MIN4(A,B,C,D),MIN(E,F) );

  const int
  AB = MAX(A, B),
  AC = MAX(A, C),
  AD = MAX(A, D),
  AE = MAX(A, E),
  AF = MAX(A, F),
  BC = MAX(B, C),
  BD = MAX(B, D),
  BE = MAX(B, E),
  BF = MAX(B, F),
  CD = MAX(C, D),
  CE = MAX(C, E),
  CF = MAX(C, F),
  DE = MAX(D, E),
  DF = MAX(D, F),
  EF = MAX(E, F);

  in[1] = MIN4 (
  MIN4( AB, AC, AD, AE ),
  MIN4( AF, BC, BD, BE ),
  MIN4( BF, CD, CE, CF ),
  MIN3( DE, DF, EF)
  );

  const int
  ABC = MAX(AB,C),
  ABD = MAX(AB,D),
  ABE = MAX(AB,E),
  ABF = MAX(AB,F),
  ACD = MAX(AC,D),
  ACE = MAX(AC,E),
  ACF = MAX(AC,F),
  ADE = MAX(AD,E),
  ADF = MAX(AD,F),
  AEF = MAX(AE,F),
  BCD = MAX(BC,D),
  BCE = MAX(BC,E),
  BCF = MAX(BC,F),
  BDE = MAX(BD,E),
  BDF = MAX(BD,F),
  BEF = MAX(BE,F),
  CDE = MAX(CD,E),
  CDF = MAX(CD,F),
  CEF = MAX(CE,F),
  DEF = MAX(DE,F);

  in[2] = MIN( MIN4 (
  MIN4( ABC, ABD, ABE, ABF ),
  MIN4( ACD, ACE, ACF, ADE ),
  MIN4( ADF, AEF, BCD, BCE ),
  MIN4( BCF, BDE, BDF, BEF )),
  MIN4( CDE, CDF, CEF, DEF )
  );


  const int
  ABCD = MAX(ABC,D),
  ABCE = MAX(ABC,E),
  ABCF = MAX(ABC,F),
  ABDE = MAX(ABD,E),
  ABDF = MAX(ABD,F),
  ABEF = MAX(ABE,F),
  ACDE = MAX(ACD,E),
  ACDF = MAX(ACD,F),
  ACEF = MAX(ACE,F),
  ADEF = MAX(ADE,F),
  BCDE = MAX(BCD,E),
  BCDF = MAX(BCD,F),
  BCEF = MAX(BCE,F),
  BDEF = MAX(BDE,F),
  CDEF = MAX(CDE,F);

  in[3] = MIN4 (
  MIN4( ABCD, ABCE, ABCF, ABDE ),
  MIN4( ABDF, ABEF, ACDE, ACDF ),
  MIN4( ACEF, ADEF, BCDE, BCDF ),
  MIN3( BCEF, BDEF, CDEF )
  );

  const int
  ABCDE= MAX(ABCD,E),
  ABCDF= MAX(ABCD,F),
  ABCEF= MAX(ABCE,F),
  ABDEF= MAX(ABDE,F),
  ACDEF= MAX(ACDE,F),
  BCDEF= MAX(BCDE,F);

  in[4]= MIN (
  MIN4( ABCDE, ABCDF, ABCEF, ABDEF ),
  MIN ( ACDEF, BCDEF )
  );

  in[5] = MAX(ABCDE,F);
}

int main(int argc, char ** argv) {
  int d[6][6] = {
    {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 (int i = 0; i < 6; i++) {
    sort6(d[i]);
  }
  cycles = rdtsc() - cycles;
  printf("Time is %d\n", (unsigned)cycles);

  for (int i = 0; i < 6; i++) {
    printf("d%d : %d %d %d %d %d %d\n", i,
     d[i][0], d[i][1], d[i][2],
     d[i][3], d[i][4], d[i][5]);
  }
}

EDIT:
Solusi urutan peringkat yang terinspirasi oleh Rex Kerr, Jauh lebih cepat daripada kekacauan di atas

static void sort6(int *o) {
const int 
A=o[0],B=o[1],C=o[2],D=o[3],E=o[4],F=o[5];
const unsigned char
AB = A>B, AC = A>C, AD = A>D, AE = A>E,
          BC = B>C, BD = B>D, BE = B>E,
                    CD = C>D, CE = C>E,
                              DE = D>E,
a =          AB + AC + AD + AE + (A>F),
b = 1 - AB      + BC + BD + BE + (B>F),
c = 2 - AC - BC      + CD + CE + (C>F),
d = 3 - AD - BD - CD      + DE + (D>F),
e = 4 - AE - BE - CE - DE      + (E>F);
o[a]=A; o[b]=B; o[c]=C; o[d]=D; o[e]=E;
o[15-a-b-c-d-e]=F;
}
PrincePolka
sumber
1
selalu senang melihat solusi baru. Sepertinya beberapa optimasi mudah dimungkinkan. Pada akhirnya itu mungkin tidak terbukti sangat berbeda dari Sorting Networks.
Kriss
Ya jumlah MIN dan MAX mungkin dapat dikurangi, misalnya MIN (AB, CD) berulang beberapa kali, tetapi mengurangi mereka banyak akan sulit saya pikir. Saya menambahkan kasus uji Anda.
PrincePolka
pmin / maxsw beroperasi pada bilangan bulat bertanda 16-bit yang dikemas ( int16_t). Tetapi fungsi C Anda mengklaimnya mengurutkan array int(yang 32-bit dalam semua implementasi C yang mendukung asmsintaks itu). Apakah Anda mengujinya dengan hanya bilangan bulat positif kecil yang hanya memiliki 0 di bagian tinggi? Itu akan berhasil ... Untuk intAnda membutuhkan SSE4.1 pmin/maxsd(d = dword). felixcloutier.com/x86/pminsd:pminsq atau pminusduntuk uint32_t.
Peter Cordes
1

Saya menemukan bahwa setidaknya pada sistem saya, fungsi sort6_iterator()dan sort6_iterator_local()definisi di bawah keduanya berjalan setidaknya secepat, dan seringkali terasa lebih cepat, daripada pemegang rekor saat ini di atas:

#define MIN(x, y) (x<y?x:y)
#define MAX(x, y) (x<y?y:x)

template<class IterType> 
inline void sort6_iterator(IterType it) 
{
#define SWAP(x,y) { const auto a = MIN(*(it + x), *(it + y)); \
  const auto b = MAX(*(it + x), *(it + y)); \
  *(it + x) = a; *(it + 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
}

Saya melewati fungsi ini sebagai std::vectorkode 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, sepertistd::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).

template<class IterType> 
inline void sort6_iterator_local(IterType it) 
{
#define SWAP(x,y) { const auto a = MIN(data##x, data##y); \
  const auto b = MAX(data##x, data##y); \
  data##x = a; data##y = b; }
//DD = Define Data
#define DD1(a)   auto data##a = *(it + a);
#define DD2(a,b) auto data##a = *(it + a), data##b = *(it + b);
//CB = Copy Back
#define CB(a) *(it + a) = data##a;

  DD2(1,2)    SWAP(1, 2)
  DD2(4,5)    SWAP(4, 5)
  DD1(0)      SWAP(0, 2)
  DD1(3)      SWAP(3, 5)
  SWAP(0, 1)  SWAP(3, 4)
  SWAP(1, 4)  SWAP(0, 3)   CB(0)
  SWAP(2, 5)  CB(5)
  SWAP(1, 3)  CB(1)
  SWAP(2, 4)  CB(4)
  SWAP(2, 3)  CB(2)        CB(3)
#undef CB
#undef DD2
#undef DD1
#undef SWAP
}

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.

#define SWAP(x,y) { const auto a = MIN(data##x, data##y); \
  data##y = MAX(data##x, data##y); \
  data##x = a; }

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:

template<class T> inline void sort6(T it) {
#define SORT2(x,y) {if(data##x>data##y){auto a=std::move(data##y);data##y=std::move(data##x);data##x=std::move(a);}}
#define DD1(a)   register auto data##a=*(it+a);
#define DD2(a,b) register auto data##a=*(it+a);register auto data##b=*(it+b);
#define CB1(a)   *(it+a)=data##a;
#define CB2(a,b) *(it+a)=data##a;*(it+b)=data##b;
  DD2(1,2) SORT2(1,2)
  DD2(4,5) SORT2(4,5)
  DD1(0)   SORT2(0,2)
  DD1(3)   SORT2(3,5)
  SORT2(0,1) SORT2(3,4) SORT2(2,5) CB1(5)
  SORT2(1,4) SORT2(0,3) CB1(0)
  SORT2(2,4) CB1(4)
  SORT2(1,3) CB1(1)
  SORT2(2,3) CB2(2,3)
#undef CB1
#undef CB2
#undef DD1
#undef DD2
#undef SORT2
}

Atau jika Anda ingin meneruskan variabel dengan referensi, maka gunakan ini (fungsi di bawah ini berbeda dari yang di atas dalam 5 baris pertama):

template<class T> inline void sort6(T& e0, T& e1, T& e2, T& e3, T& e4, T& e5) {
#define SORT2(x,y) {if(data##x>data##y)std::swap(data##x,data##y);}
#define DD1(a)   register auto data##a=e##a;
#define DD2(a,b) register auto data##a=e##a;register auto data##b=e##b;
#define CB1(a)   e##a=data##a;
#define CB2(a,b) e##a=data##a;e##b=data##b;
  DD2(1,2) SORT2(1,2)
  DD2(4,5) SORT2(4,5)
  DD1(0)   SORT2(0,2)
  DD1(3)   SORT2(3,5)
  SORT2(0,1) SORT2(3,4) SORT2(2,5) CB1(5)
  SORT2(1,4) SORT2(0,3) CB1(0)
  SORT2(2,4) CB1(4)
  SORT2(1,3) CB1(1)
  SORT2(2,3) CB2(2,3)
#undef CB1
#undef CB2
#undef DD1
#undef DD2
#undef SORT2
}

Alasan menggunakan registerkata kunci adalah karena ini adalah salah satu dari beberapa kali Anda tahu bahwa Anda menginginkan nilai-nilai ini dalam register. Tanpa register, kompiler akan mencari tahu sebagian besar waktu tetapi kadang-kadang tidak. Menggunakan registerkata kunci membantu menyelesaikan masalah ini. Namun, biasanya, jangan gunakan registerkata kunci karena lebih cenderung memperlambat kode Anda daripada mempercepatnya.

Juga, perhatikan penggunaan template. Hal ini dilakukan dengan sengaja karena, bahkan dengan inlinekata 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).

  1. Sementara menentukan waktu berbagai fungsi penyortiran, saya perhatikan bahwa konteks (yaitu kode di sekitarnya) tempat pemanggilan fungsi penyortiran memiliki dampak signifikan pada kinerja, yang kemungkinan disebabkan oleh fungsi yang diuraikan dan kemudian dioptimalkan. Misalnya, jika program itu cukup sederhana maka biasanya tidak ada banyak perbedaan dalam kinerja antara melewati fungsi penyortiran pointer dibandingkan melewati iterator; jika tidak menggunakan iterator biasanya menghasilkan kinerja yang jauh lebih baik dan tidak pernah (setidaknya dalam pengalaman saya sejauh ini) kinerja yang lebih buruk. Saya menduga ini mungkin karena g ++ dapat secara global mengoptimalkan kode yang cukup sederhana.
Matthew K.
sumber
0

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

function sortListMerge_2a(cmp)	
{
var step, stepmax, tmp, a,b,c, i,j,k, m,n, cycles;
var start = 0;
var end   = arr_count;
//var str = '';
cycles = 0;
if (end>3)
	{
	stepmax = ((end - start + 1) >> 1) << 1;
	m = 1;
	n = 2;
	for (step=1;step<stepmax;step<<=1)	//bounds 1-1, 2-2, 4-4, 8-8...
		{
		a = start;
		while (a<end)
			{
			b = a + step;
			c = a + step + step;
			b = b<end ? b : end;
			c = c<end ? c : end;
			i = a;
			j = b;
			k = i;
			while (i<b && j<c)
				{
				if (cmp(arr[m][i],arr[m][j])>0)
					{arr[n][k] = arr[m][j]; j++; k++;}
				else	{arr[n][k] = arr[m][i]; i++; k++;}
				}
			while (i<b)
				{arr[n][k] = arr[m][i]; i++; k++;
}
			while (j<c)
				{arr[n][k] = arr[m][j]; j++; k++;
}
			a = c;
			}
		tmp = m; m = n; n = tmp;
		}
	return m;
	}
else
	{
	// sort 3 items
	sort10(cmp);
	return m;
	}
}

Peter
sumber
0

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

function sort4DG(cmp,start,end,n) // sort 4
{
var n     = typeof(n)    !=='undefined' ? n   : 1;
var cmp   = typeof(cmp)  !=='undefined' ? cmp   : sortCompare2;
var start = typeof(start)!=='undefined' ? start : 0;
var end   = typeof(end)  !=='undefined' ? end   : arr[n].length;
var count = end - start;
var pos = -1;
var i = start;
var cc = [];
// stabilni?
cc[01] = cmp(arr[n][i+0],arr[n][i+1]);
cc[23] = cmp(arr[n][i+2],arr[n][i+3]);
if (cc[01]>0) {swap(n,i+0,i+1);}
if (cc[23]>0) {swap(n,i+2,i+3);}
cc[12] = cmp(arr[n][i+1],arr[n][i+2]);
if (!(cc[12]>0)) {return n;}
cc[02] = cc[01]==0 ? cc[12] : cmp(arr[n][i+0],arr[n][i+2]);
if (cc[02]>0)
    {
    swap(n,i+1,i+2); swap(n,i+0,i+1); // bubble last to top
    cc[13] = cc[23]==0 ? cc[12] : cmp(arr[n][i+1],arr[n][i+3]);
    if (cc[13]>0)
        {
        swap(n,i+2,i+3); swap(n,i+1,i+2); // bubble
        return n;
        }
    else    {
    cc[23] = cc[23]==0 ? cc[12] : (cc[01]==0 ? cc[30] : cmp(arr[n][i+2],arr[n][i+3]));  // new cc23 | c03 //repaired
        if (cc[23]>0)
            {
            swap(n,i+2,i+3);
            return n;
            }
        return n;
        }
    }
else    {
    if (cc[12]>0)
        {
        swap(n,i+1,i+2);
        cc[23] = cc[23]==0 ? cc[12] : cmp(arr[n][i+2],arr[n][i+3]); // new cc23
        if (cc[23]>0)
            {
            swap(n,i+2,i+3);
            return n;
            }
        return n;
        }
    else    {
        return n;
        }
    }
return n;
}
peter
sumber
1
Kasus penggunaan sedikit berbeda dari konteks awal pertanyaan. Dengan rincian jenis tetap panjang dan menghitung cmp swap tidak cukup. Aku bahkan tidak akan terkejut jika itu bukan jenis yang sebenarnya yang akan menghabiskan waktu, tetapi sesuatu yang sama sekali berbeda dari tipe panggilan () di init. Saya tidak tahu bagaimana melakukan mesure waktu jam aktual menggunakan Javascript. Mungkin dengan simpul?
Kriss
0

Mungkin aku am terlambat ke pesta, tapi setidaknya kontribusi saya adalah baru pendekatan.

  • Kode harus benar - benar diuraikan
  • bahkan jika digarisbawahi, ada terlalu banyak cabang
  • bagian analisis pada dasarnya adalah O (N (N-1)) yang tampaknya OK untuk N = 6
  • kode dapat lebih efektif jika biayaswap akan lebih tinggi (dari biaya compare)
  • Saya percaya pada fungsi statis yang diuraikan.
  • Metode ini terkait dengan sort-rank
    • alih-alih peringkat, peringkat relatif (offset) digunakan.
    • jumlah peringkat adalah nol untuk setiap siklus dalam kelompok permutasi apa pun.
    • alih-alih menggunakan 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 ...

#include <stdio.h>

#if WANT_CHAR
typedef signed char Dif;
#else
typedef signed int Dif;
#endif

static int walksort (int *arr, int cnt);
static void countdifs (int *arr, Dif *dif, int cnt);
static void calcranks(int *arr, Dif *dif);

int wsort6(int *arr);

void do_print_a(char *msg, int *arr, unsigned cnt)
{
fprintf(stderr,"%s:", msg);
for (; cnt--; arr++) {
        fprintf(stderr, " %3d", *arr);
        }
fprintf(stderr,"\n");
}

void do_print_d(char *msg, Dif *arr, unsigned cnt)
{
fprintf(stderr,"%s:", msg);
for (; cnt--; arr++) {
        fprintf(stderr, " %3d", (int) *arr);
        }
fprintf(stderr,"\n");
}

static void inline countdifs (int *arr, Dif *dif, int cnt)
{
int top, bot;

for (top = 0; top < cnt; top++ ) {
        for (bot = 0; bot < top; bot++ ) {
                if (arr[top] < arr[bot]) { dif[top]--; dif[bot]++; }
                }
        }
return ;
}
        /* Copied from RexKerr ... */
static void inline calcranks(int *arr, Dif *dif){

dif[0] =     (arr[0]>arr[1])+(arr[0]>arr[2])+(arr[0]>arr[3])+(arr[0]>arr[4])+(arr[0]>arr[5]);
dif[1] = -1+ (arr[1]>=arr[0])+(arr[1]>arr[2])+(arr[1]>arr[3])+(arr[1]>arr[4])+(arr[1]>arr[5]);
dif[2] = -2+ (arr[2]>=arr[0])+(arr[2]>=arr[1])+(arr[2]>arr[3])+(arr[2]>arr[4])+(arr[2]>arr[5]);
dif[3] = -3+ (arr[3]>=arr[0])+(arr[3]>=arr[1])+(arr[3]>=arr[2])+(arr[3]>arr[4])+(arr[3]>arr[5]);
dif[4] = -4+ (arr[4]>=arr[0])+(arr[4]>=arr[1])+(arr[4]>=arr[2])+(arr[4]>=arr[3])+(arr[4]>arr[5]);
dif[5] = -(dif[0]+dif[1]+dif[2]+dif[3]+dif[4]);
}

static int walksort (int *arr, int cnt)
{
int idx, src,dst, nswap;

Dif difs[cnt];

#if WANT_REXK
calcranks(arr, difs);
#else
for (idx=0; idx < cnt; idx++) difs[idx] =0;
countdifs(arr, difs, cnt);
#endif
calcranks(arr, difs);

#define DUMP_IT 0
#if DUMP_IT
do_print_d("ISteps ", difs, cnt);
#endif

nswap = 0;
for (idx=0; idx < cnt; idx++) {
        int newval;
        int step,cyc;
        if ( !difs[idx] ) continue;
        newval = arr[idx];
        cyc = 0;
        src = idx;
        do      {
                int oldval;
                step = difs[src];
                difs[src] =0;
                dst = src + step;
                cyc += step ;
                if(dst == idx+1)idx=dst;
                oldval = arr[dst];
#if (DUMP_IT&1)
                fprintf(stderr, "[Nswap=%d] Cyc=%d Step=%2d Idx=%d  Old=%2d New=%2d #### Src=%d Dst=%d[%2d]->%2d <-- %d\n##\n"
                        , nswap, cyc, step, idx, oldval, newval
                        , src, dst, difs[dst], arr[dst]
                        , newval  );
                do_print_a("Array ", arr, cnt);
                do_print_d("Steps ", difs, cnt);
#endif

                arr[dst] = newval;
                newval = oldval;
                nswap++;
                src = dst;
                } while( cyc);
        }

return nswap;
}
/*************/
int wsort6(int *arr)
{
return walksort(arr, 6);
}
wildplasser
sumber
terlihat seperti semacam gelembung. Berpotensi menjadi pesaing yang baik untuk implementasi paling lambat, tetapi masih bisa menarik untuk diketahui jika bekerja pada kode membuat banyak perbedaan. Harap masukkan kode Anda dalam format yang sama dengan yang lain, sehingga kami dapat menjalankan patokan di atasnya.
Kriss
@kriss en.wikipedia.org/wiki/Permutation_group Ini tentu bukan semacam gelembung: kode mendeteksi siklus dalam permutasi yang diberikan, dan berjalan siklus ini, menempatkan setiap elemen di tempat terakhirnya. Fungsi terakhir wsort6()memiliki antarmuka yang benar.
Sambil
@ Joop: saya buruk, tidak ada semacam gelembung memang. Yang dikatakan dalam konteks saya masih mengharapkan kode menjadi jauh lebih buruk daripada implementasi saat ini. Omong-omong solusi Urutan Peringkat optimal mengenai jumlah swap karena langsung menemukan posisi akhir setiap item. Juga tidak jelas apakah walksort bahkan berfungsi ketika kita menghapus hipotesis bahwa semua angka yang diurutkan berbeda seperti di sini. Untuk benchmark kode kita harus melacak kode. Juga karena saya biasanya mengkompilasi pada kompiler C ++, kode tidak akan berfungsi karena OP menyebut variabel "baru" (dan itu merusak penyorotan sintaks).
Kriss
Metode ini sangat dekat dengan urutan peringkat, hanya tugas akhir dilakukan di tempat . Terlepas dari peringkat o1..o5, tidak perlu untuk e[6]array temp kedua . Dan: mengkompilasi kode C pada kompiler C ++, dan menyalahkan kode?
Sambil
@ Greybeard: terima kasih, saya menambahkan spasi sebelumnya #include. Memperbaiki
wildplasser
0
//Bruteforce compute unrolled count dumbsort(min to 0-index)
void bcudc_sort6(int* a)
{
    int t[6] = {0};
    int r1,r2;

    r1=0;
    r1 += (a[0] > a[1]);
    r1 += (a[0] > a[2]);
    r1 += (a[0] > a[3]);
    r1 += (a[0] > a[4]);
    r1 += (a[0] > a[5]);
    while(t[r1]){r1++;}
    t[r1] = a[0];

    r2=0;
    r2 += (a[1] > a[0]);
    r2 += (a[1] > a[2]);
    r2 += (a[1] > a[3]);
    r2 += (a[1] > a[4]);
    r2 += (a[1] > a[5]);
    while(t[r2]){r2++;} 
    t[r2] = a[1];

    r1=0;
    r1 += (a[2] > a[0]);
    r1 += (a[2] > a[1]);
    r1 += (a[2] > a[3]);
    r1 += (a[2] > a[4]);
    r1 += (a[2] > a[5]);
    while(t[r1]){r1++;}
    t[r1] = a[2];

    r2=0;
    r2 += (a[3] > a[0]);
    r2 += (a[3] > a[1]);
    r2 += (a[3] > a[2]);
    r2 += (a[3] > a[4]);
    r2 += (a[3] > a[5]);
    while(t[r2]){r2++;} 
    t[r2] = a[3];

    r1=0;
    r1 += (a[4] > a[0]);
    r1 += (a[4] > a[1]);
    r1 += (a[4] > a[2]);
    r1 += (a[4] > a[3]);
    r1 += (a[4] > a[5]);
    while(t[r1]){r1++;}
    t[r1] = a[4];

    r2=0;
    r2 += (a[5] > a[0]);
    r2 += (a[5] > a[1]);
    r2 += (a[5] > a[2]);
    r2 += (a[5] > a[3]);
    r2 += (a[5] > a[4]);
    while(t[r2]){r2++;} 
    t[r2] = a[5];

    a[0]=t[0];
    a[1]=t[1];
    a[2]=t[2];
    a[3]=t[3];
    a[4]=t[4];
    a[5]=t[5];
}

static __inline__ void sort6(int* a)
{
    #define wire(x,y); t = a[x] ^ a[y] ^ ( (a[x] ^ a[y]) & -(a[x] < a[y]) ); a[x] = a[x] ^ t; a[y] = a[y] ^ t;
    register int t;

    wire( 0, 1); wire( 2, 3); wire( 4, 5);
    wire( 3, 5); wire( 0, 2); wire( 1, 4);
    wire( 4, 5); wire( 2, 3); wire( 0, 1); 
    wire( 3, 4); wire( 1, 2); 
    wire( 2, 3);

    #undef wire
}
FrantzelasG
sumber
Terlepas dari kecepatan, apakah Anda yakin itu berfungsi? Dalam sortasi bruteforce loop Anda meragukan. Menurut saya mereka tidak akan berfungsi jika kita memiliki nol dalam nilai yang diurutkan.
Kriss
1
t [6] array diinisialisasi ke 0x0. Jadi tidak masalah di mana dan jika kunci bernilai 0x0 akan ditulis.
FranG
-1

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)

GClaramunt
sumber
9
Ada 720 pemesanan, dan versi cepatnya berada di bawah 100 siklus. Sekalipun paralelisme masif dapat menjadi pengungkit, pada skala waktu sekecil itu biaya pembuatan dan sinkronisasi utas kemungkinan akan melebihi biaya hanya menyortir array pada satu inti.
Kevin Stock
-3

Berikut adalah tiga metode penyortiran khas yang mewakili tiga kelas yang berbeda dari Algoritma Penyortiran:

Insertion Sort: Θ(n^2)

Heap Sort: Θ(n log n)

Count Sort: Θ(3n)

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 C

Algoritma 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.

Khaled A Khunaifer
sumber
8
Ini menarik tetapi tidak penting. Big-intended dimaksudkan untuk menyembunyikan faktor konstan dan menunjukkan tren ketika ukuran masalah (n) membesar. Masalahnya di sini adalah sepenuhnya tentang ukuran masalah tetap (n = 6) dan mempertimbangkan faktor-faktor konstan.
Kriss
@kriss Anda benar, perbandingan saya asimptotik, jadi perbandingan praktis akan menunjukkan apakah lebih cepat atau tidak untuk kasus itu
Khaled.K
4
Anda tidak dapat menyimpulkan, karena setiap algoritma berbeda menyembunyikan konstanta multiplikasi K yang berbeda (dan juga konstanta aditif C). yaitu: k0, c0 untuk jenis penyisipan, k1, c1 untuk jenis tumpukan dan sebagainya. Semua konstanta itu sebenarnya berbeda (Anda bisa mengatakan dalam istilah fisik bahwa setiap algoritma memiliki "koefisien gesekan" sendiri), Anda tidak dapat menyimpulkan suatu algoritma sebenarnya lebih cepat dalam kasus ini (atau kasus n tetap).
Kriss