循環中的函數指針

爲我的學士論文我寫了一個程序（用C語言）對大表進行排序，現在一切正常。但是，對於我的一些測試文件，該程序有點慢。爲了能夠更有效地存儲臨時數據，用戶可以爲表格的每一列指定數據類型。然後，輸入數據首先被解析成二進制格式，然後被排序並最終轉換回其文本形式。循環中的函數指針

對於每個數據類型，必須實現四個函數（編碼，解碼，gengthngth和比較），並且指向這些數據的指針存儲在每個列的數組中。因此，要對錶格中的某行執行任何操作，我必須爲循環中的每一行調用正確的函數，如果列相當短，這會有相當大的開銷。

作爲一個例子，這裏是我行比較功能（來自的qsort調用）的代碼：

int line_cmp(const void *p1,const void *p2) 
{ 
    int i,o1=0,o2=0,r; 

    for(i=0;i<opt.nocols;i++) 
     if((r=(*opt.cols[i].cmp)(*(char* const*)p1,&o1, 
           *(char* const*)p2,&o2))) 
      return r; 

    return 0; 
}

此功能通過所有列，如果被調用函數返回0以外的值（意爲不循環等於）返回值（就像qsort的要求一樣）。

現在我的問題是，如何優化這個（或類似的）函數（如果可能的話），特別是當所有的指針只設置一次，然後在整個程序期間從未改變？

編輯：我使用函數指針，以便第三人可以開發任意數據類型。這些將通過（dlopen等）加載。因此，我想不出一個通用的二進制格式來比較列，二進制數據只是我的程序的黑盒子。

來源

2011-04-01 sl0815

你所提供的代碼基本上是一個簡單的循環，每次通過一次調用。很難看到如何進一步優化。我猜你沒有發佈使用編碼，解碼和gengthngth功能的地方？ – 2011-04-01 12:09:00

@Jonathan Wood：我選擇這個功能作爲例子，因爲它是最長的。其他函數只是一個for和一個函數的調用。 – sl0815 2011-04-01 12:12:05

爲什麼你不使用分析工具來找出瓶頸所在。 – Milan 2011-04-01 12:21:14

您應該檢查您的代碼生成的彙編程序，但這裏您可能會遇到太多間接指針的問題，而且編譯器也必須重新加載opt的內容。

還取決於您的全局opt是如何定義的（const或不是）編譯器能夠優化多少。由於在迭代使用opt之間有函數調用，編譯器不知道該值是否已更改。

嘗試做這樣的事情

size_t nocols = opt.nocols 
columnType const*const myFunc = opt.cols;

，並使用nocols和myFunc[i].comp的循環。

來源

2011-04-01 13:45:57

嘗試過它，它減慢了10％和3％，這可能是由於測量公差（每次只進行5次測試）。然而，循環的彙編代碼較短，這使我相信，如果有很多列（測試文件有3列和30列），你的方式會更好。感謝您的回答。 – sl0815 2011-04-01 14:37:52

我在您發佈的功能中沒有看到有太多優化的空間。它只是一個for循環，每次都會調用一個函數。

調用函數指針是有效的。即使你有一個可用於比較所有項目類型的通用二進制格式，我懷疑這比調用當前類型特定的比較函數要快得多。

一個可能的想法是讓您的用戶定義函數比較所有列。這可以消除您發佈的函數中的for循環。雖然在專用功能中可能需要類似的循環，但減少一些呼叫可能會縮短一點時間。但是，如果一行可以有多個類型，那就行不通了。

除此之外，我懷疑可能做出的任何進一步優化都將成爲您未在此處發佈的代碼的一部分。我沒有足夠的信息知道可以在那裏做什麼，如果有的話。

來源

2011-04-01 13:13:53

將for循環移入類型特定的函數會使事情變得更糟，因爲比較從左向右移動，並在兩列發現不相等時停止。如果您將for循環向下移動一級，那麼當列2中的數據是另一種類型並且不相等時，我最終可以比較列1,3,4，...。我也沒有看到有任何改善的餘地，但是再一百萬隻眼睛看到兩個以上的改善。謝謝！ – sl0815 2011-04-01 13:26:08

使它併發，將您的設計升級到無鎖併發排序。也許無鎖定更像是一個主要的等級項目，如果你無法想象一個無鎖定的鎖定，那就去找一個鎖定的鎖定。

來源

2011-04-01 13:20:02

感謝您的建議，但排序已併發（雖然在更高層次上）。所以該程序已經使用了所有可用的處理能力。忘了在提問中提到這一點。 – sl0815 2011-04-01 13:30:05

是否可以切換到C++？

我在問，因爲C++ STL的模板排序算法通常會導致內聯比較和良好的性能提升。當比較簡單類型如int時，差異最爲明顯。

如果您必須與C保持聯繫，您可以嘗試使用快速排序源代碼，並嵌入直接比較調用。這將手動實現STL和模板自動爲您執行的操作。

在閱讀了您的編輯之後，我認爲如果沒有像並行排序這樣的根本性改變或要求用戶以更適合的格式提供數據，您無法真正加速排序。

還有一個想法：也許你可以按照單列連續排序加快排序。這可以從緩存局部性中獲益。

來源

2011-04-01 13:25:19

不，我不能切換到C++。這將意味着重寫4500行代碼。我已經嘗試了qsort的修改版本（內聯調用），但我無法測量任何效果。 – sl0815 2011-04-01 13:33:11

因爲你已經在分析，我假設你已經在使用編譯器優化了，是嗎？ – 2011-04-01 18:24:02

正確。 gcc -O3 -march = native – sl0815 2011-04-01 22:21:39

循環中的函數指針

回答

相關問題