qsort_b e qsort

Question

Scrittura di un programma che dimostra un diverso algoritmo di ordinamento in C++ su Mac. Ho trovato due implementazioni quicksort, qsort e qsort_b.

Il primo è naturalmente il qsort vecchio stile, visto ovunque. Ma c'è qsort_b, che accetta un blocco piuttosto che una funzione. Ecco il mio codice:

#include <cstdlib> 
#include <cstdio> 
#include <iostream> 
#include <cstdio> 
#include <ctime> 

#define DATA 1000000 

using namespace std; 

int compare(const void* a, const void* b) 
{ 
    return *(int*)a - *(int*)b; 
} 

int main(int argc, char *argv[]) 
{ 
    int* array = new int[DATA]; 

    srand(time(0)); 

    for (int i = 0 ; i < DATA ; ++ i) 
    { 
     array[i] = rand() % 2147483647; 
    } 

    clock_t begin = clock(); 

    qsort(array, DATA, sizeof(array[0]), compare); 
    //qsort_b(array, DATA, sizeof(array[0]), ^(const void* a, const void* b) { return *(int*)a - *(int*)b; }); 

    clock_t end = clock(); 

    cout << "Time it takes to sort " << DATA << " integers with quicksort: " << end - begin; 
} 

Qui vedo una grande differenza di velocità, che cosa sta causando tutta questa differenza. Per quanto ne so, i blocchi sono per l'elaborazione parallela, che in questo caso non sarà più veloce delle funzioni. Non c'è niente per il processo parallelo, vero?

MODIFICA: le routine heapsort_b(), mergesort_b() e qsort_b() sono come le routine corrispondenti senza il suffisso _b, si aspetta che il callback di confronto sia un puntatore a blocco invece di un puntatore a funzione. (FROM BSD MAN PAGE)

MODIFICA: la differenza di velocità. Con DATA pari a 1000000, qsort lo ha terminato in 146832 ns, con qsort_b, in 127391 ns. È una differenza relativamente grande considerando che è circa il 10% più veloce.

EDIT: Ho modificato il codice per rendere possibile disporre di un array ancora maggiore di numeri interi. Il mio più grande risultato del test personale sono 100000000 numeri interi, 28136278 (28 s) vs 23870078 (24 s). È una differenza considerevole per me.

Answer 1

Objective-C Block è un diverso tipo di animale. Potrebbe sembrare MACRO (sostituzione prima della compilazione) e inline functions (che dice al compilatore "Fai del tuo meglio per eliminare la funzione di chiamata in testa"), ma la struttura generale è molto più diversa da quelle strutture.

Block è un oggetto, inoltre, un pila oggetto. L'unico oggetto che può essere creato nello stack (almeno senza alcuni trucchi).

Quando un oggetto Block viene creato nello stack, il compilatore aggiunge tutte le variabili locali, le variabili di blocco, gli indirizzi delle variabili di lettura/scrittura a cui fa riferimento e un puntatore al codice eseguibile del blocco. Quindi, anche prima di iniziare a eseguire, tutto è pronto per il calcolo senza alcuna operazione di stack.

Quindi, non è un problema di ottimizzazione, piuttosto un attributo di Block. Non ha alcuna funzione chiamata overhead di PUSH e POP s di variabili stack.

Come risposta alla tua domanda, qsort() e qsort_b() non ha alcuna differenza algoritmico, ma la struttura elaborata, blocco vs funzione.

Answer 2

Sembra una differenza di ottimizzazione per me. Con qsort_b, il compilatore probabilmente incorpora il confronto, mentre con qsort no. La differenza è il sovraccarico della chiamata di funzione per confronto.