qsort_b et qsort

Question

Ecrire un programme qui démontre différents algorithmes de tri en C++ sur Mac. J'ai trouvé deux implémentations de quicksort, qsort et qsort_b.

Le premier est bien sûr le bon vieux qsort, que l'on voit partout. Mais il y a aussi qsort_b, qui prend un bloc plutôt qu'une fonction. Voici mon code :

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

Ici, je vois une grande différence de vitesse, quelle est la cause de cette différence ? D'après ce que j'ai compris, les blocs sont destinés au traitement parallèle, qui dans ce cas ne sera pas plus rapide que les fonctions. Il n'y a rien à traiter en parallèle, n'est-ce pas ?

EDIT : Les routines heapsort_b(), mergesort_b(), et qsort_b() sont comme les routines correspondantes sans le suffixe _b, sauf que le callback de comparaison est un pointeur de bloc au lieu d'un pointeur de fonction. ( DE LA PAGE DE MANUEL BSD )

EDIT : La différence de vitesse. Avec DATA à 1000000, qsort l'a terminé en 146832 ns, avec qsort_b, en 127391 ns. C'est une différence relativement importante si l'on considère que qsort est environ 10% plus rapide.

EDIT : J'ai modifié le code pour permettre d'avoir un tableau d'entiers encore plus grand. Mon plus gros résultat personnel est 100000000 entiers, 28136278 (28s) vs. 23870078 (24s). C'est une différence considérable pour moi.

Answer 1

Objectif-C Block est un animal d'un autre genre. Il peut sembler MACRO (substitution avant compilation), et inline functions (indiquant au compilateur "Faites de votre mieux pour éliminer les frais généraux liés aux appels de fonction. ), mais la structure générale est beaucoup plus différente de ces structures.

Le bloc est un objet En outre, a pile objet . Le seul objet qui peut être créé dans la pile (du moins sans astuces).

Lorsqu'un Block créé dans la pile, le compilateur ajoute toutes les variables locales, les variables du bloc, les adresses des variables en lecture/écriture qu'il référence et un pointeur vers le code exécutable du bloc. Ainsi, avant même de commencer l'exécution, tout est prêt pour le calcul sans aucune opération sur la pile.

Il ne s'agit donc pas d'une question d'optimisation, mais plutôt d'un attribut de la Block . Il n'y a pas de surcoût lié aux appels de fonction de PUSH y POP des variables de la pile.

Pour répondre à votre question, qsort() y qsort_b() n'a pas de différence algorithmique, mais la structure élaborée, bloc vs fonction .

Answer 2

Il me semble qu'il y a une différence d'optimisation. Avec qsort_b, le compilateur intègre probablement la comparaison, alors qu'avec qsort, il ne le fait pas. La différence réside dans le surcoût de l'appel de fonction par comparaison.