c - निश्चित लंबाई 6 int सरणी का सबसे तेज़ प्रकार




algorithm optimization (16)

किसी अन्य स्टैक ओवरफ़्लो प्रश्न का उत्तर देना ( यह एक ) मैंने एक दिलचस्प उप-समस्या पर ठोकर खाई। 6 इंच की सरणी को सॉर्ट करने का सबसे तेज़ तरीका क्या है?

जैसा कि सवाल बहुत कम स्तर है:

  • हम यह नहीं मान सकते कि पुस्तकालय उपलब्ध हैं (और कॉल की कीमत भी है), केवल सादा सी
  • निर्देश पाइपलाइन खाली करने से बचने के लिए (जिसकी बहुत अधिक लागत है) हमें शायद शाखाओं, कूदों, और हर दूसरे प्रकार के नियंत्रण प्रवाह को तोड़ना चाहिए (जैसे अनुक्रम बिंदुओं के पीछे छुपाए गए और && या || )।
  • कमरा सीमित है और रजिस्टरों को कम करने और स्मृति उपयोग एक मुद्दा है, आदर्श रूप से जगह क्रम में शायद सबसे अच्छा है।

वास्तव में यह सवाल एक प्रकार का गोल्फ है जहां लक्ष्य स्रोत की लंबाई को कम करने के लिए नहीं बल्कि निष्पादन समय है। मैं इसे 'जेनिंग' कोड कहता हूं जैसा कि माइकल एब्राश और उसके अनुक्रमों द्वारा जेन ऑफ़ कोड ऑप्टिमाइज़ेशन पुस्तक के शीर्षक में उपयोग किया जाता है।

क्यों यह दिलचस्प है, कई परतें हैं:

  • उदाहरण सरल और आसान समझने और मापने में आसान है, इसमें बहुत सी कौशल शामिल नहीं है
  • यह समस्या के लिए एक अच्छा एल्गोरिदम की पसंद के प्रभाव दिखाता है, लेकिन संकलक और अंतर्निहित हार्डवेयर के प्रभाव भी दिखाता है।

यहां मेरा संदर्भ (बेवकूफ, अनुकूलित नहीं) कार्यान्वयन और मेरा परीक्षण सेट है।

#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);
}

कच्चे परिणाम

जैसे-जैसे वेरिएंट बड़े हो रहे हैं, मैंने उन सभी को टेस्ट सूट में इकट्ठा किया जो here पाए जा सकते here । केविन स्टॉक के लिए धन्यवाद, ऊपर दिखाए गए वास्तविक परीक्षणों की तुलना में थोड़ा कम बेकार है। आप इसे अपने पर्यावरण में संकलित और निष्पादित कर सकते हैं। मैं विभिन्न लक्ष्य आर्किटेक्चर / कंपाइलर्स पर व्यवहार से काफी रूचि रखता हूं। (ठीक है दोस्तों, इसे जवाब में डाल दें, मैं एक नए परिणाम के प्रत्येक योगदानकर्ता को +1 कर दूंगा)।

मैंने एक साल पहले डैनियल स्टुटज़बैक (गोल्फिंग के लिए) का जवाब दिया क्योंकि वह उस समय (सॉर्टिंग नेटवर्क) के सबसे तेज़ समाधान के स्रोत पर था।

लिनक्स 64 बिट्स, जीसीसी 4.6.1 64 बिट्स, इंटेल कोर 2 डुओ ई 8400, -ओ 2

  • Qsort लाइब्रेरी फ़ंक्शन पर डायरेक्ट कॉल: 68 9.38
  • निष्क्रिय कार्यान्वयन (सम्मिलन क्रम): 285.70
  • सम्मिलन क्रमबद्ध करें (डैनियल स्टुटज़बैक): 142.12
  • सम्मिलन अनलॉक क्रमबद्ध करें: 125.47
  • रैंक ऑर्डर: 102.26
  • रजिस्ट्रार के साथ रैंक ऑर्डर: 58.03
  • सॉर्टिंग नेटवर्क (डैनियल स्टुटज़बैक): 111.68
  • सॉर्टिंग नेटवर्क (पॉल आर): 66.36
  • फास्ट स्वैप के साथ सॉर्टिंग नेटवर्क 12: 58.86
  • सॉर्टिंग नेटवर्क 12 पुनर्वित्त स्वैप: 53.74
  • सॉर्टिंग नेटवर्क 12 पुन: व्यवस्थित सरल स्वैप: 31.54
  • रीर्डर्ड सॉर्टिंग नेटवर्क डब्ल्यू / फास्ट स्वैप: 31.54
  • रीर्डर्ड सॉर्टिंग नेटवर्क डब्ल्यू / फास्ट स्वैप वी 2: 33.63
  • इनलाइन बबल सॉर्ट (पाओलो बोनजिनी): 48.85
  • अनियंत्रित सम्मिलन क्रमबद्ध करें (पाओलो बोनज़ीनी): 75.30

लिनक्स 64 बिट्स, जीसीसी 4.6.1 64 बिट्स, इंटेल कोर 2 डुओ ई 8400, -ओ 1

  • Qsort लाइब्रेरी फ़ंक्शन पर प्रत्यक्ष कॉल: 705.93
  • निष्क्रिय कार्यान्वयन (सम्मिलन क्रम): 135.60
  • सम्मिलन क्रमबद्ध करें (डैनियल स्टुटज़बैक): 142.11
  • सम्मिलन अनलॉक क्रमबद्ध करें: 126.75
  • रैंक ऑर्डर: 46.42
  • रजिस्ट्रार के साथ रैंक ऑर्डर: 43.58
  • सॉर्टिंग नेटवर्क (डैनियल स्टुटज़बैक): 115.57
  • सॉर्टिंग नेटवर्क (पॉल आर): 64.44
  • फास्ट स्वैप के साथ सॉर्टिंग नेटवर्क 12: 61.98
  • सॉर्टिंग नेटवर्क 12 पुनर्वित्त स्वैप: 54.67
  • सॉर्टिंग नेटवर्क 12 पुन: व्यवस्थित सरल स्वैप: 31.54
  • रीर्डर्ड सॉर्टिंग नेटवर्क डब्ल्यू / फास्ट स्वैप: 31.24
  • रीर्डर्ड सॉर्टिंग नेटवर्क डब्ल्यू / फास्ट स्वैप वी 2: 33.07
  • इनलाइन बबल सॉर्ट (पाओलो बोनजिनी): 45.7 9
  • अनियंत्रित सम्मिलन क्रमबद्ध करें (पाओलो बोनज़ीनी): 80.15

मैंने दोनों-ओ 1 और -ओ 2 परिणामों को शामिल किया क्योंकि आश्चर्यजनक रूप से कई कार्यक्रमों के लिए ओ 2 ओ 1 से कम कुशल है। मुझे आश्चर्य है कि विशिष्ट अनुकूलन का क्या प्रभाव है?

प्रस्तावित समाधानों पर टिप्पणियाँ

सम्मिलन क्रमबद्ध करें (डैनियल स्टुटज़बैक)

जैसा कि उम्मीद है कि शाखाओं को कम करना वास्तव में एक अच्छा विचार है।

सॉर्टिंग नेटवर्क (डैनियल स्टुटज़बैक)

सम्मिलन प्रकार से बेहतर है। मुझे आश्चर्य हुआ कि क्या बाहरी प्रभाव बाहरी पाश से बचने से नहीं मिला था। मैंने इसे अनलॉक किए गए सम्मिलन प्रकार से जांचने का प्रयास किया और वास्तव में हमें लगभग समान आंकड़े मिलते हैं (कोड here )।

सॉर्टिंग नेटवर्क (पॉल आर)

अब तक का सबसे अच्छा मैं जिस वास्तविक कोड का परीक्षण करता था वह here । अभी तक नहीं पता कि यह अन्य सॉर्टिंग नेटवर्क कार्यान्वयन के रूप में लगभग दो गुना तेजी से क्यों है। पैरामीटर गुजर रहा है? फास्ट अधिकतम?

फास्ट स्वैप के साथ सॉर्टिंग नेटवर्क 12 SWAP

डैनियल स्टुटज़बैक द्वारा सुझाए गए अनुसार, मैंने अपने 12 स्वैप सॉर्टिंग नेटवर्क को शाखा रहित फास्ट स्वैप (कोड here ) के साथ जोड़ा। यह वास्तव में तेज़ है, अब तक एक छोटा सा मार्जिन (लगभग 5%) के साथ सबसे अच्छा है, जिसे 1 कम स्वैप का उपयोग करके उम्मीद की जा सकती है।

यह भी दिलचस्प है कि पीपीसी आर्किटेक्चर पर उपयोग किए जाने वाले सरल व्यक्ति की तुलना में शाखा रहित स्वैप (4 ​​गुना) कम कुशल लगता है।

कॉलिंग लाइब्रेरी qsort

एक और संदर्भ बिंदु देने के लिए मैंने लाइब्रेरी qsort (कोड here ) को कॉल करने के लिए सुझाए गए अनुसार भी कोशिश की। जैसा कि उम्मीद है कि यह बहुत धीमा है: 10 से 30 गुना धीमा ... क्योंकि यह नए परीक्षण सूट के साथ स्पष्ट हो गया है, मुख्य समस्या पहली कॉल के बाद पुस्तकालय का प्रारंभिक भार प्रतीत होता है, और यह अन्य के साथ इतनी खराब नहीं है संस्करण। यह मेरे लिनक्स पर 3 से 20 गुना धीमा है। कुछ आर्किटेक्चर पर दूसरों द्वारा परीक्षणों के लिए उपयोग किया जाता है, यह तेजी से लगता है (मैं वास्तव में उस से हैरान हूं, क्योंकि पुस्तकालय qsort एक अधिक जटिल एपीआई का उपयोग करता है)।

रैंक आदेश

रेक्स केर ने एक और पूरी तरह से अलग विधि का प्रस्ताव दिया: सरणी के प्रत्येक आइटम के लिए सीधे इसकी अंतिम स्थिति गणना करें। यह कुशल है क्योंकि कंप्यूटिंग रैंक ऑर्डर को शाखा की आवश्यकता नहीं है। इस विधि की कमी यह है कि सरणी की स्मृति की मात्रा (सरणी की एक प्रति और रैंक ऑर्डर स्टोर करने के लिए चर) लेती है। प्रदर्शन के परिणाम बहुत आश्चर्यजनक (और दिलचस्प) हैं। 32 बिट्स ओएस और इंटेल कोर 2 क्वाड ई 8300 के साथ मेरे संदर्भ आर्किटेक्चर पर, चक्र गणना 1000 से कम थी (जैसे शाखाकरण स्वैप के साथ सॉर्टिंग नेटवर्क)। लेकिन जब मेरे 64 बिट्स बॉक्स (इंटेल कोर 2 डुओ) पर संकलित और निष्पादित किया गया तो यह बहुत बेहतर प्रदर्शन किया: यह अब तक का सबसे तेज़ बन गया है। अंततः मुझे सही कारण पता चला। मेरा 32 बिट बॉक्स जीसीसी 4.4.1 और मेरे 64 बिट्स बॉक्स जीसीसी 4.4.3 का उपयोग करता है और आखिरी वाला इस विशेष कोड को अनुकूलित करने में बहुत बेहतर लगता है (अन्य प्रस्तावों के लिए बहुत कम अंतर था)।

अपडेट करें :

जैसा कि उपर्युक्त प्रकाशित आंकड़े दिखाते हैं कि इस प्रभाव को अभी भी जीसीसी के बाद के संस्करणों द्वारा बढ़ाया गया था और रैंक ऑर्डर लगातार किसी भी अन्य विकल्प के रूप में तेज़ी से दोगुना हो गया।

पुनर्नवीनीकरण स्वैप के साथ 12 सॉर्टिंग नेटवर्क

जीसीसी 4.4.3 के साथ रेक्स केर प्रस्ताव की अद्भुत दक्षता ने मुझे आश्चर्यचकित कर दिया: शाखा रहित सॉर्टिंग नेटवर्क की तुलना में 3 गुना अधिक मेमोरी उपयोग के साथ एक प्रोग्राम कैसे तेज हो सकता है? मेरी परिकल्पना यह थी कि लिखने के बाद इस तरह की पढ़ाई की कम निर्भरता थी, x86 के सुपरस्केकर निर्देश शेड्यूलर के बेहतर उपयोग की अनुमति। इसने मुझे एक विचार दिया: लेखन निर्भरताओं के बाद पढ़ने को कम करने के लिए स्वैप को पुन: क्रमबद्ध करें। अधिक सरलता से रखें: जब आप SWAP(1, 2); SWAP(0, 2); SWAP(1, 2); SWAP(0, 2); आपको दूसरे स्वैप करने से पहले पहले स्वैप को समाप्त करने की प्रतीक्षा करनी होगी क्योंकि दोनों एक सामान्य मेमोरी सेल तक पहुंच सकते हैं। जब आप SWAP(1, 2); SWAP(4, 5); SWAP(1, 2); SWAP(4, 5); प्रोसेसर दोनों समानांतर में निष्पादित कर सकते हैं। मैंने कोशिश की और यह अपेक्षित काम करता है, सॉर्टिंग नेटवर्क लगभग 10% तेज चल रहा है।

सरल स्वैप के साथ 12 सॉर्टिंग नेटवर्क

मूल पोस्ट के एक साल बाद स्टीनर एच। गुंडरसन ने सुझाव दिया कि हमें कंपाइलर को आउटमार्ट करने और स्वैप कोड को सरल रखने की कोशिश नहीं करनी चाहिए। यह वास्तव में एक अच्छा विचार है क्योंकि परिणामी कोड लगभग 40% तेज है! उन्होंने x86 इनलाइन असेंबली कोड का उपयोग करके हाथ से अनुकूलित एक स्वैप का प्रस्ताव भी दिया जो अभी भी कुछ और चक्रों को छोड़ सकता है। सबसे आश्चर्यजनक (यह प्रोग्रामर के मनोविज्ञान पर वॉल्यूम कहता है) यह है कि एक साल पहले इस्तेमाल किए गए किसी भी ने स्वैप के संस्करण की कोशिश नहीं की थी। मैं जिस कोड का परीक्षण करता था वह here । दूसरों ने सी फास्ट स्वैप लिखने के अन्य तरीकों का सुझाव दिया, लेकिन यह एक सभ्य संकलक के साथ सरल के समान प्रदर्शन करता है।

"सर्वश्रेष्ठ" कोड अब निम्नानुसार है:

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
}

अगर हम अपने परीक्षण सेट पर विश्वास करते हैं (और, हाँ यह काफी खराब है, तो यह केवल लाभ ही सरल, सरल और समझने में आसान है जिसे हम माप रहे हैं), परिणामी कोड के चक्रों की औसत संख्या 40 चक्रों से कम है ( 6 परीक्षण निष्पादित किए गए हैं)। इससे प्रत्येक चक्र को 4 चक्रों के औसत पर रखा जाता है। मैं उस आश्चर्यजनक तेज़ कहता हूं। कोई अन्य सुधार संभव है?


ऐसा लगता है कि मैं एक साल देर से पार्टी में गया, लेकिन यहां हम जाते हैं ...

जीसीसी 4.5.2 द्वारा उत्पन्न असेंबली को देखते हुए मैंने देखा कि प्रत्येक स्वैप के लिए लोड और स्टोर किए जा रहे हैं, जिनकी वास्तव में आवश्यकता नहीं है। रजिस्टरों में 6 मानों को लोड करना बेहतर होगा, उनको सॉर्ट करें, और उन्हें स्मृति में वापस स्टोर करें। मैंने स्टोर्स पर लोड जितना संभव हो सके उतने करीब होने का आदेश दिया कि रजिस्टरों की पहली आवश्यकता है और आखिरी बार इस्तेमाल किया जाता है। मैंने स्टीनर एच गंडर्सन के एसडब्ल्यूएपी मैक्रो का भी इस्तेमाल किया। अपडेट करें: मैंने पाओलो बोनजिनी के एसडब्ल्यूएपी मैक्रो पर स्विच किया जो जीसीसी गंडर्सन के समान कुछ में बदल जाता है, लेकिन जीसीसी निर्देशों को बेहतर तरीके से आदेश देने में सक्षम है क्योंकि उन्हें स्पष्ट असेंबली के रूप में नहीं दिया जाता है।

मैंने एक ही स्वैप ऑर्डर का इस्तेमाल किया क्योंकि रीडर्डर्ड स्वैप नेटवर्क सर्वश्रेष्ठ प्रदर्शन के रूप में दिया गया है, हालांकि बेहतर ऑर्डरिंग हो सकती है। अगर मुझे कुछ और समय मिल जाए तो मैं उत्पन्न कर दूंगा और क्रमपरिवर्तन का एक गुच्छा परीक्षण करूंगा।

मैंने 4000 से अधिक सरणी पर विचार करने के लिए परीक्षण कोड बदल दिया और प्रत्येक को क्रमबद्ध करने के लिए आवश्यक चक्रों की औसत संख्या दिखाएं। I5-650 पर मुझे ~ 34.1 चक्र / सॉर्ट (-O3 का उपयोग करके) मिल रहा है, मूल पुनर्नवीनीकरण सॉर्टिंग नेटवर्क की तुलना में ~ 65.3 चक्र / सॉर्ट (-O1, beats -O2 और -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;
}

मैंने टेस्ट सूट को प्रतिलिपि बनाने के लिए प्रतिलिपि बनाने और अधिक परीक्षण चलाने के लिए संशोधित किया (सीएमपी फ़ंक्शन को पूर्णांक ओवरफ़्लो को संभालने के लिए भी अपडेट किया गया था), यहां कुछ अलग आर्किटेक्चर के परिणाम दिए गए हैं। मैंने एएमडी सीपीयू पर परीक्षण करने का प्रयास किया लेकिन rdtsc X6 1100T पर उपलब्ध नहीं है।

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

किसी भी अनुकूलन के लिए, परीक्षण, परीक्षण, परीक्षण करना हमेशा सर्वोत्तम होता है। मैं कम से कम नेटवर्क और सम्मिलन क्रमबद्ध सॉर्ट करने की कोशिश करता हूं। अगर मैं सट्टेबाजी कर रहा था, तो मैं अपने अनुभव को पिछले अनुभव के आधार पर सम्मिलन प्रकार पर डाल दूंगा।

क्या आप इनपुट डेटा के बारे में कुछ जानते हैं? कुछ एल्गोरिदम कुछ प्रकार के डेटा के साथ बेहतर प्रदर्शन करेंगे। उदाहरण के लिए, सम्मिलन क्रम क्रमबद्ध या लगभग क्रमबद्ध डेटा पर बेहतर प्रदर्शन करता है, इसलिए यदि बेहतर-क्रमबद्ध डेटा का औसत-औसत मौका होता है तो यह बेहतर विकल्प होगा।

आपके द्वारा पोस्ट किया गया एल्गोरिदम एक प्रविष्टि प्रकार के समान है, लेकिन ऐसा लगता है कि आपने अधिक तुलना की लागत पर स्वैप की संख्या को कम कर दिया है। तुलना स्वैप की तुलना में कहीं अधिक महंगा है, हालांकि, शाखाएं निर्देश पाइपलाइन को रोक सकती हैं।

यहां एक सम्मिलन प्रकार कार्यान्वयन है:

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;
        }
}

यहां बताया गया है कि मैं एक सॉर्टिंग नेटवर्क कैसे बनाऊंगा। सबसे पहले, उचित लंबाई के नेटवर्क के लिए SWAP मैक्रोज़ का न्यूनतम सेट उत्पन्न करने के लिए इस साइट का उपयोग करें । एक समारोह में इसे लपेटना मुझे देता है:

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
}

परीक्षण कोड बहुत बुरा है; यह प्रारंभिक सरणी को ओवरफ्लो करता है (क्या लोग यहां कंपाइलर चेतावनियां पढ़ते हैं?), printf गलत तत्वों को प्रिंट कर रहा है, यह किसी भी अच्छे कारण के लिए rdtsc के लिए .byte का उपयोग करता है, केवल एक रन (!) है, इसमें कुछ भी नहीं है अंत परिणाम वास्तव में सही हैं (इसलिए कुछ निश्चित रूप से गलत में "ऑप्टिमाइज़" करना बहुत आसान है), शामिल परीक्षण बहुत प्राथमिक हैं (कोई ऋणात्मक संख्या नहीं है) और कंपाइलर को पूरे फ़ंक्शन को मृत कोड के रूप में छोड़ने से रोकने के लिए कुछ भी नहीं है।

ऐसा कहा जा रहा है, बिटोनिक नेटवर्क समाधान पर सुधार करना भी बहुत आसान है; बस न्यूनतम / अधिकतम / SWAP सामान को बदलें

#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"); }

और यह मेरे लिए लगभग 65% तेज आता है (डेबियन जीसीसी 4.4.5 के साथ -ओ 2, एमडी 64, कोर i7)।


मैंने कुछ दिनों पहले Google से इस प्रश्न पर ठोकर खाई क्योंकि मुझे 6 पूर्णांक की निश्चित लंबाई सरणी को त्वरित रूप से क्रमबद्ध करने की आवश्यकता भी थी। मेरे मामले में, मेरे पूर्णांक केवल 8 बिट्स (32 के बजाय) हैं और मुझे केवल सी का उपयोग करने की सख्त आवश्यकता नहीं है। मैंने सोचा कि मैं अपने निष्कर्षों को किसी भी तरह से साझा करूंगा, अगर वे किसी के लिए सहायक हो सकते हैं ...

मैंने असेंबली में एक नेटवर्क प्रकार का एक संस्करण लागू किया जो एसएसई का उपयोग तुलनात्मक और स्वैप संचालन को संभव बनाने के लिए संभव बनाता है। सरणी को पूरी तरह से सॉर्ट करने में छह "पास" लगते हैं। मैंने पीएसएचयूएफबी (वेक्टरिज्ड स्वैप) के लिए पैरामीटर को घुमाने के लिए पीसीएमपीजीटीबी (वेक्टरिज्ड तुलना) के परिणामों को सीधे रूपांतरित करने के लिए एक उपन्यास तंत्र का उपयोग किया, केवल एक पीएडीडीबी (वेक्टरिज्ड एड) का उपयोग करके और कुछ मामलों में भी एक पैंड (बिटवाईड और) निर्देश।

इस दृष्टिकोण में वास्तव में शाखा रहित कार्य करने का दुष्प्रभाव भी था। कोई भी कूद निर्देश नहीं हैं।

ऐसा प्रतीत होता है कि यह कार्यान्वयन कार्यान्वयन से लगभग 38% तेज है जिसे वर्तमान में प्रश्न में सबसे तेज़ विकल्प ("सरल स्वैप के साथ सॉर्टिंग नेटवर्क 12) के रूप में चिह्नित किया गया है। तुलनात्मक निष्पक्ष बनाने के लिए, मैंने अपने परीक्षण के दौरान char सरणी तत्वों का उपयोग करने के लिए कार्यान्वयन को संशोधित किया।

मुझे ध्यान रखना चाहिए कि इस दृष्टिकोण को 16 तत्वों तक किसी भी सरणी आकार पर लागू किया जा सकता है। मैं बड़े सरणी के लिए बड़े होने के विकल्पों पर सापेक्ष गति लाभ की अपेक्षा करता हूं।

एसएसएसई 3 के साथ x86_64 प्रोसेसर के लिए एमएएसएम में कोड लिखा गया है। फ़ंक्शन "नया" विंडोज एक्स 64 कॉलिंग सम्मेलन का उपयोग करता है। यह रहा...

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

आप इसे निष्पादन योग्य ऑब्जेक्ट में संकलित कर सकते हैं और इसे अपने सी प्रोजेक्ट में लिंक कर सकते हैं। विजुअल स्टूडियो में ऐसा करने के निर्देशों के लिए, आप इस आलेख को पढ़ सकते हैं। आप अपने सी कोड से फ़ंक्शन को कॉल करने के लिए निम्न सी प्रोटोटाइप का उपयोग कर सकते हैं:

void simd_sort_6(char *values);

An XOR swap may be useful in your swapping functions.

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

The if may cause too much divergence in your code, but if you have a guarantee that all your ints are unique this could be handy.


Here are three typical sorting methods that represent three different classes of Sorting Algorithms:

Insertion Sort: Θ(n^2)

Heap Sort: Θ(n log n)

Count Sort: Θ(3n)

But check out Stefan Nelsson discussion on the fastest sorting algorithm? where he discuss a solution that goes down to O(n log log n) .. check out its implementation in C

This Semi-Linear Sorting algorithm was presented by a paper in 1995:

A. Andersson, T. Hagerup, S. Nilsson, and R. Raman. Sorting in linear time? In Proceedings of the 27th Annual ACM Symposium on the Theory of Computing, pages 427-436, 1995.


I believe there are two parts to your question.

  • The first is to determine the optimal algorithm. This is done - at least in this case - by looping through every possible ordering (there aren't that many) which allows you to compute exact min, max, average and standard deviation of compares and swaps. Have a runner-up or two handy as well.
  • The second is to optimize the algorithm. A lot can be done to convert textbook code examples to mean and lean real-life algorithms. If you realize that an algorithm can't be optimized to the extent required, try a runner-up.

I wouldn't worry too much about emptying pipelines (assuming current x86): branch prediction has come a long way. What I would worry about is making sure that the code and data fit in one cache line each (maybe two for the code). Once there fetch latencies are refreshingly low which will compensate for any stall. It also means that your inner loop will be maybe ten instructions or so which is right where it should be (there are two different inner loops in my sorting algorithm, they are 10 instructions/22 bytes and 9/22 long respectively). Assuming the code doesn't contain any divs you can be sure it will be blindingly fast.


I found that at least on my system, the functions sort6_iterator() and sort6_iterator_local() defined below both ran at least as fast, and frequently noticeably faster, than the above current record holder:

#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
}

I passed this function a std::vector 's iterator in my timing code. I suspect that using iterators gives g++ certain assurances about what can and can't happen to the memory that the iterator refers to, which it otherwise wouldn't have and it is these assurances that allow g++ to better optimize the sorting code (which if I remember correctly, is also part of the reason why so many std algorithms, such as std::sort() , generally have such obscenely good performance). However, while timing I noticed that the context (ie surrounding code) in which the call to the sorting function was made had a significant impact on performance, which is likely due to the function being inlined and then optimized. For instance, if the program was sufficiently simple then there usually wasn't much of a difference in performance between passing the sorting function a pointer versus passing it an iterator; otherwise using iterators usually resulted in noticeably better performance and never (in my experience so far at least) any noticeably worse performance. I suspect that this may be because g++ can globally optimize sufficiently simple code.

Moreover, sort6_iterator() is some times (again, depending on the context in which the function is called) consistently outperformed by the following sorting function:

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
}

Note that defining SWAP() as follows some times results in slightly better performance although most of the time it results in slightly worse performance or a negligible difference in performance.

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

If you just want a sorting algorithm that gcc -O3 is consistently good at optimizing then, depending on how you pass the input, try one of the following two algorithms:

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
}

या

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
}

The reason for using the register keyword is because this is one of the few times that you know that you want these values in registers. Without register , the compiler will figure this out most of the time but sometimes it doesn't. Using the register keyword helps solve this issue. Normally, however, don't use the register keyword since it's more likely to slow your code than speed it up.

Also, note the use of templates. This is done on purpose since, even with the inline keyword, template functions are generally much more aggressively optimized by gcc than vanilla C functions (this has to do with gcc needing to deal with function pointers for vanilla C functions but not with template functions).


I know this is an old question.

But I just wrote a different kind of solution I want to share.
Using nothing but nested MIN MAX,

It's not fast as it uses 114 of each,
could reduce it to 75 pretty simply like so -> pastebin

But then it's not purely min max anymore.

What might work is doing min/max on multiple integers at once with AVX

PMINSW reference

#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]);
  }
}

संपादित करें:
Rank order solution inspired by Rex Kerr's, Much faster than the mess above

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;
}

I ported the test suite to a PPC architecture machine I can not identify (didn't have to touch code, just increase the iterations of the test, use 8 test cases to avoid polluting results with mods and replace the x86 specific rdtsc):

Direct call to qsort library function : 101

Naive implementation (insertion sort) : 299

Insertion Sort (Daniel Stutzbach) : 108

Insertion Sort Unrolled : 51

Sorting Networks (Daniel Stutzbach) : 26

Sorting Networks (Paul R) : 85

Sorting Networks 12 with Fast Swap : 117

Sorting Networks 12 reordered Swap : 116

Rank Order : 56


Looking forward to trying my hand at this and learning from these examples, but first some timings from my 1.5 GHz PPC Powerbook G4 w/ 1 GB DDR RAM. (I borrowed a similar rdtsc-like timer for PPC from http://www.mcs.anl.gov/~kazutomo/rdtsc.html for the timings.) I ran the program a few times and the absolute results varied but the consistently fastest test was "Insertion Sort (Daniel Stutzbach)", with "Insertion Sort Unrolled" a close second.

Here's the last set of times:

**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

Maybe I am late to the party, but at least my contribution is a new approach.

  • The code really should be inlined
  • even if inlined, there are too many branches
  • the analysing part is basically O(N(N-1)) which seems OK for N=6
  • the code could be more effective if the cost of swap would be higher (irt the cost of compare )
  • I trust on static functions being inlined.
  • The method is related to rank-sort
    • instead of ranks, the relative ranks (offsets) are used.
    • the sum of the ranks is zero for every cycle in any permutation group.
    • instead of SWAP() ing two elements, the cycles are chased, needing only one temp, and one (register->register) swap (new <- old).

Update: changed the code a bit, some people use C++ compilers to compile C code ...

#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);
}

Sort 4 items with usage cmp==0. Numbers of cmp is ~4.34 (FF native have ~4.52), but take 3x time than merging lists. But better less cmp operations, if you have big numbers or big text. Edit: repaired bug

Online test 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;
}

This question is becoming quite old, but I actually had to solve the same problem these days: fast agorithms to sort small arrays. I thought it would be a good idea to share my knowledge. While I first started by using sorting networks, I finally managed to find other algorithms for which the total number of comparisons performed to sort every permutation of 6 values was smaller than with sorting networks, and smaller than with insertion sort. I didn't count the number of swaps; I would expect it to be roughly equivalent (maybe a bit higher sometimes).

The algorithm sort6 uses the algorithm sort4 which uses the algorithm sort3 . Here is the implementation in some light C++ form (the original is template-heavy so that it can work with any random-access iterator and any suitable comparison function).

Sorting 3 values

The following algorithm is an unrolled insertion sort. When two swaps (6 assignments) have to be performed, it uses 4 assignments instead:

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]);
            }
        }
    }
}

It looks a bit complex because the sort has more or less one branch for every possible permutation of the array, using 2~3 comparisons and at most 4 assignments to sort the three values.

Sorting 4 values

This one calls sort3 then performs an unrolled insertion sort with the last element of the 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]);
            }
        }
    }
}

This algorithm performs 3 to 6 comparisons and at most 5 swaps. It is easy to unroll an insertion sort, but we will be using another algorithm for the last sort...

Sorting 6 values

This one uses an unrolled version of what I called a double insertion sort . The name isn't that great, but it's quite descriptive, here is how it works:

  • Sort everything but the first and the last elements of the array.
  • Swap the first and the elements of the array if the first is greater than the last.
  • Insert the first element into the sorted sequence from the front then the last element from the back.

After the swap, the first element is always smaller than the last, which means that, when inserting them into the sorted sequence, there won't be more than N comparisons to insert the two elements in the worst case: for example, if the first element has been insert in the 3rd position, then the last one can't be inserted lower than the 4th position.

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]);
                }
            }
        }
    }
}

My tests on every permutation of 6 values ever show that this algorithms always performs between 6 and 13 comparisons. I didn't compute the number of swaps performed, but I don't expect it to be higher than 11 in the worst case.

I hope that this helps, even if this question may not represent an actual problem anymore :)

EDIT: after putting it in the provided benchmark, it is cleary slower than most of the interesting alternatives. It tends to perform a bit better than the unrolled insertion sort, but that's pretty much it. Basically, it isn't the best sort for integers but could be interesting for types with an expensive comparison operation.


Well, if it's only 6 elements and you can leverage parallelism, want to minimize conditional branching, etc. Why you don't generate all the combinations and test for order? I would venture that in some architectures, it can be pretty fast (as long as you have the memory preallocated)


While I really like the swap macro provided:

#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; }

I see an improvement (which a good compiler might make):

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

We take note of how min and max work and pull the common sub-expression explicitly. This eliminates the min and max macros completely.






gpgpu