qsort_b和qsort

Question

在Mac上編寫一個在C++中演示不同排序算法的程序。我發現了兩個quicksort實現，qsort和qsort_b。

第一個當然是老式的，隨處可見的qsort。但有qsort_b，它採用一個塊而不是一個函數。這裏是我的代碼：

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

在這裏我看到很大的速度差異，是什麼導致所有的差異。就我的理解，塊是用於並行處理的，在這種情況下不會比函數更快。沒有什麼可以並行處理的，是嗎？編程：heapsort_b（），mergesort_b（）和qsort_b（）例程就像沒有_b後綴的相應例程，期望compar回調是塊指針而不是函數指針。 （FROM BSD MAN PAGE）

編輯：速度差。 DATA爲1000000時，qsort在146832 ns內完成，qsort_b在127391 ns內完成。考慮到它快10％左右，這是一個相當大的差異。

編輯：我編輯的代碼，使其有可能具有更大的整數數組。我個人最大的測試結果是1億整數，28136278（28秒）與23870078（24秒）。對我來說這是一個相當大的差異。

Answer 1

Objective-C Block是一種不同的動物。它可能看起來像MACRO（編譯前替換）和inline functions（告訴編譯器「盡你所能消除函數調用開銷」），但整體結構與這些結構有很大不同。

塊是對象，此外，一個堆對象。唯一允許在堆棧中創建的對象（至少沒有一些技巧）。

當在堆棧中創建一個Block對象時，編譯器會添加所有本地變量，塊變量，它引用的讀/寫變量的地址以及指向塊可執行代碼的指針。所以即使在開始執行之前，一切都準備好了，無需任何堆棧操作即可進行計算

所以，這不是一個優化問題，而是Block的一個屬性。它沒有任何函數調用開銷PUSH和POP s堆棧變量。

作爲一個回答你的問題，qsort()和qsort_b()沒有任何的算法差異，但精細的結構，塊VS函數。

Answer 2

看起來像我的優化差異。使用qsort_b，編譯器可能會內聯比較，而qsort則不會。差異是每比較函數調用的開銷。