qsort_b i qsort

Question

Pisanie programu, który demonstruje inny algorytm sortowania w C++ na Macu. Znalazłem dwie implementacje quicksort, qsort i qsort_b.

Pierwszy to oczywiście staroświecki, widziany wszędzie qsort. Ale istnieje qsort_b, który przyjmuje blok, a nie funkcję. Oto mój kod:

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

Widzę tutaj dużą różnicę prędkości, co powoduje tę różnicę. Rozumiem, że bloki są przeznaczone do przetwarzania równoległego, które w tym przypadku nie będą szybsze niż funkcje. Nie ma nic do równoległego procesu, prawda?

EDYCJA: Procedury heapsort_b(), mergesort_b() i qsort_b() są podobne do odpowiednich procedur bez sufiksu _b, należy oczekiwać, że porównawcze wywołanie zwrotne jest wskaźnikiem bloku zamiast wskaźnika funkcji. (FROM BSD MAN PAGE)

EDYCJA: Różnica prędkości. Gdy DATA to 1000000, qsort ukończył go w 146832 ns, z qsort_b, w 127391 ns. Jest to stosunkowo duża różnica, ponieważ jest o około 10% szybsza.

EDYCJA: Zmodyfikowałem kod, aby umożliwić uzyskanie większej liczby liczb całkowitych. Mój osobisty największy wynik testu to 100000000 liczb całkowitych, 28136278 (28s) vs. 23870078 (24s). To dla mnie ogromna różnica.

Answer 1

Objective-C Block to inny rodzaj zwierząt. Może się wydawać, że jest to MACRO (podstawienie przed kompilacją) i inline functions (kompilator mówi: "Jak najlepiej wyeliminować obciążenie związane z wywołaniem funkcji"), ale ogólna struktura jest znacznie bardziej odmienna niż te struktury.

Block przedmiotem ponadto stos Przedmiotem. Jedyny obiekt, który może zostać utworzony w stosie (przynajmniej bez niektórych sztuczek).

Po utworzeniu obiektu Block w stosie, kompilator dodaje wszystkie zmienne lokalne, zmienne blokowe, adresy zmiennych do odczytu/zapisu, do których się odwołuje, oraz wskaźnik do kodu wykonywalnego bloku. Tak więc nawet przed rozpoczęciem wykonywania, wszystko jest gotowe do obliczeń bez operacji na stosie.

To nie jest problem optymalizacji, a raczej atrybut Block. Nie ma żadnego obciążenia związanego z wywołaniem funkcji ze zmiennych stosu.

Jako odpowiedź na swoje pytanie, qsort() i qsort_b() nie ma żadnej różnicy, ale algorytmicznego opracowanej konstrukcji, bloku vs funkcji.

Answer 2

Wygląda dla mnie na różnicę w zakresie optymalizacji. W przypadku qsort_b kompilator prawdopodobnie podkreśla porównanie, podczas gdy qsort nie. Różnica jest narzutem wywołania funkcji na porównanie.