|
和面向過程的 C 語言相比，其繼承者 C++ 不僅可以進行 C 語言的過程化程序設計，還可以進行以繼承和多態(tài)為特點的面向對象的程序設計。要論兩者上手的難易度，對此，有網友評價道，學好 C 只要 1 年，而學好 C++ 需要的可能不止 10 年。
然而這么多年過去了，C++ 卻一直未能取代 C，且在本文中，作者發(fā)現自己常用的庫，可以使用到的 C++ 特性越來越少，進而準備向 C 語言過渡。我最近經常使用 meshoptimizer 這個庫，隨著時間的推移，能用到的 C++ 庫的特性越來越少。截至目前，盡管其中仍包含一些 C ++ 特性，但整體上來看，其代碼已與 C 極為相似。（https://github.com/zeux/meshoptimizer）這些變化背后有很多原因，例如刪除 C++ 11 的要求可以確保任何人都能在任何平臺上編譯庫；刪除 std::vector 大大改進了未優(yōu)化構建的性能；刪除 algorithm 可以提升編譯速度等等。但是，我目前更改的這個代碼庫并沒有完全變成 C 語言的代碼。今天我們來探索這個特定算法，網格簡化器，后面簡稱為 simplifier.cpp，看看這個算法的全部 C ++ 實現的范圍，是否值得一直改進到 C 語言的版本。 這個網格簡化器，是通過多次調整以改善代碼的性能和質量的一種基于邊緣壓縮的二次曲面簡化算法的實現結果。該算法仍處于開發(fā)階段，但已投入相當大的努力。細節(jié)真的不那么重要，但它有助于理解結構和大?。?/span>- 整個算法在一個獨立的 .cpp 文件中實現，該文件幾乎有一千行代碼（撰寫本文時為 1004 行），包括注釋，空行，帶括號的行等。
- 該算法基本上只使用堆分配的數組作為數據結構，并使用原始指針。
我們將看一下實現的幾個變化過程，首先是從使用 C ++ 容器和算法的變化開始，這將有助于該算法，然后一次刪除一個 C ++ 特性并測試編譯速度和運行時的性能。我們使用了三種編譯器，分別是 gcc7.3、clang 6 和 msvc 2017，并將它們運行在 Core i7-8700K 上的 Windows 10 / Ubuntu 16.10 系統(tǒng)中。我們將通過編譯一個 .cpp 文件（debug 使用默認選項，release 使用 -O2）來測量編譯性能，并通過將 buddha.obj （1M 左右的三角形網格）簡化為其大小的 25％，用來測試運行時性能。在我們達到這一狀態(tài)之后，我們再來探究將代碼更改為純 C99。請注意，我完成這些實現的方式是通過獲取現在可以在存儲中看到的代碼，并將其更改為更慣用的 Modern C ++ [1]。但是，這些通常與之前版本的simplifier.cpp非常接近，不同之處在于現在可以直接比較變化。 我們開始的版本是來自 current meshoptimizer master 的原始 simplifier.cpp，具有以下修改：- 我們使用 std::unordered_set 取代原自定義的哈希表
- 我們使用 std::sort 取代原自定義的排序例程
從表中我們可以看出來這是一個很好的開始。我們可以看到性能在發(fā)布運行時非常的穩(wěn)定，簡化 1M 三角形網格用了 0.6 秒是一個很好的性能水平。通常在調試時或多或少基本都是合理的，除了一個明顯的例外 MSVC（MSVC STL在調試模式下的不良行為是一個強制函數會將從 meshoptimizer 中刪除所有 STL 的使用）。而在編譯時長方面基本都有所不同，但沒有特別奇怪的情況。為了正確看待編譯時長，Jonathan Blow 最近發(fā)布了一個帶有編譯器性能改進的視頻流（video stream with compiler performance improvements），他的游戲引擎和用他的新語言編寫的游戲在大約一秒內完成編譯和鏈接（編譯本身大約需要 0.9 秒）。這是在具有 100K 行的代碼庫上， 而我們的算法只有 1K 行代碼（當然我們的代碼中不包括 STL 雖然排除 STL 并不完全公平，但是加入 STL 計算代碼行也不完全公平，因為我們知道我們的算法完全可以在沒有任何 STL 依賴的情況下用 1K 行代碼來實現）。在編譯代碼時你會注意到 400 毫秒，即使它只有一個文件。而當我處理代碼的時候，這樣的事情會讓我不那么開心，因為有很多這樣的文件，累積的編譯性能可能會很差。這樣的情況是因為我們的實現對于 STL 依賴非常簡單，我們只使用其中三個算法/容器。讓我們看看當我們停止使用其中一個時會發(fā)生什么。我們基準測試的先前版本的秘密就在于 unordered_set 從來沒有在那個版本中存在過。雖然 meshoptimizer 最初使用的是 STL 容器和算法，但它從未使用過 std::unordered_set。因為根據以前的經驗，我預計性能不足以滿足我想要編寫的算法類型，但是有一個自定義替代方式就是使用二次探測在一個大的二維數組中實現，這類似于谷歌的 dense_hash_set 設計。它是我通常在不同的代碼庫中為不同的應用程序經常實現和使用的一種哈希表，所以我對它非常熟悉。在 simplifier.cpp 中的實現只有35行代碼 [2]，可見這個方式很容易插入并適應手頭的用例。讓我們看看當我們使用它時會發(fā)生什么。從結果上看，額外的 35 行用于手動實現的更好的哈希表是值得的。我們在整個版本，調試/發(fā)布以及編譯時長和運行時長方面都看到了顯著的性能提升。運行時長性能的最大提升是在 MSVC 編譯器上，我們快了 1.5 倍，事實上哈希表沒有被用作算法的核心部分，它僅僅是用于在算法開始之前建立各個頂點之間的唯一性關系。測試結果突顯了 std::unordered_set 不適用于起決定性能的重要工作，特別是那些插入量很大的工作負載。不幸的是，這不是一個實現缺陷，因此無法糾正，這個問題是無序容器的標準要求妨礙了更有效的實現。希望最后我們能夠在標準中得到一個更好的哈希表。在開發(fā) simplifier 的過程中，對各種網格的重復分析表明，大量時間都花在了 std::sort 上?，F在，std::sort 不是最快的排序算法，但它通常與自定義實現相比極具競爭力，并且在不改變問題的情況下很難被擊敗。在我的例子中，排序用于邊壓縮的數組，排序鍵是一個浮點錯誤值，所以很自然的是使用3遍基數排序，依次使用鍵的11位，11位和10位（浮點值為32位每次使用一部分用于排序）。但是，我們這里有一個有趣的替代方案，我們可以使用11位的排序鍵僅需進行1次基數排序 [3]。我們有一個 32 位的非負浮點值會發(fā)生什么;如果我們取前 12 位并忽略最前面的1位（因為第一位是一個符號位且始終為0），我們得到11位代表8位指數和3位尾數，這本質上給了我們一個近似的數值但卻存在一個嚴重的舍入錯誤。如果我們使用此值作為鍵進行排序，那么排序順序就不會完全按照完整的32位鍵進行排序。然而，在我們的例子中，我們需要排序以便能夠首先更好的基于啟發(fā)式算法處理邊壓縮，并且啟發(fā)式算法是一個粗略的近似過程，因此我們的排序帶來的額外錯誤并不明顯。這種技術在其他您不一定需要確切順序的領域中非常有用。一次基數排序的好處是它更快（你只需要對數據進行1次排序而不是 3 次?。┎⑶冶韧暾幕鶖蹬判蚋菀讓崿F，只需 36 行代碼 [4]。這次編譯時間的增加稍微適度。我們已經刪除了<algorithm> 標題，但它似乎并沒有對編譯時長產生非常顯著的好處，因為我們仍然存在 <vector>，并且可能兩者都提取了一些大 STL 頭文件。但是，對運行性能的影響非常顯著，特別是在 libstdc ++ 中的調試運行性能上（很可能 std::sort在調試中非常慢）此外在發(fā)布版本的收效上也同樣令人興奮。從這張圖表的結果中觀察不出來排序算法變得多么的快，與其他工作相比，它幾乎完全從配置文件中消失，然而整個算法“僅”運行速度快了 1.35 倍。但單純在排序代碼上測試得到的收效更好，在發(fā)布版本中從 117 毫秒減少到了 10 毫秒。有一個數字是我們尚未大幅度調整的，那就是使用 MSVC 在調試代碼所需的間。雖然很自然的會想到未經優(yōu)化的構建過程會比優(yōu)化后的慢，但是優(yōu)化后的代碼它們必須足夠快才行。有時你希望在有意義的輸入數據集上調試問題。有時你希望運行調試能夠進行全面檢查以通過你的測試，確保在發(fā)布版本中它們不會觸發(fā)任何可能在隱匿的 bug。有時你試圖調試程序的不同部分，但仍需要運行其余部分。程序員創(chuàng)造性地提出了許多變通方法，使問題不那么嚴重，例如你可以制作特殊的構建來實現一些優(yōu)化而不是全部，你也可以對不同的項目使用混合優(yōu)化設置，你可以使用 #pragma optimize 這樣的指令來暫時禁用有問題的部分的代碼的優(yōu)化，但所有的這些看起來像是臨時使用的補丁。讓我們嘗試用一個非常簡單的動態(tài)數組替換我們仍然使用的唯一 STL 組件 std::vector。我們的代碼中不需要 resize 或 push_back，所有數組都使用正確的大小進行初始化。我們的要求足夠低，我們這種 std::vector 的替代方式僅僅需要 40行代碼 [5]，并且主要由 operator[] 定義組成。上表中的結果相當的有趣。通過用我們自己的類型替換 std::vector ，我們不僅顯著提高了 MSVC 的調試性能，而且還減半了我們測試使用的幾個編譯器的編譯時間。gcc / clang 中的調試運行性能有點退步，我相信這是因為我的替換代碼中使用 assert 來對每個 operator[] 訪問執(zhí)行邊界檢查，而在 libc ++ 和 libstdc ++ 中，它們分別使用 _GLIBCXX_ASSERTIONS 和_LIBCPP_DEBUG 單獨定義來完成邊界檢查控制的。為 std::vector 的變量啟用這些定義會將兩個庫的調試運行時長提高到大約 1350 ms [6]，因此在啟用類似功能時，我們的替換代碼運行速度會更快。發(fā)布的性能整體來看也略有提高，這是因為對于我們代碼中的許多數組而言，std::vector 的構造函數執(zhí)行的默認初始化是多余的，因為我們無論如何都要填充數組。當然，使用 std::vector，你也可以 resize 那些大數組的大小，然后計算條目（這需要對每個條目進行冗余的默認初始化），或者 reserve 和 push_back（這需要更多的代碼來每個條目進行添加，而這個花銷是累加起來的）。與之相反的是，使用自定義容器，可以輕松地選擇跳過初始化。實際上，在我們的替換代碼中這是唯一的選項，因為如果需要，可以很輕松的手動添加 memset 設置數組大小。帶有邊界檢查的 operator[] 的自定義容器大部分都是成功的，但它并不能讓我滿意。在某些算法中，容器的額外成本仍然非常龐大。在一些算法中，內部函數將使用原始指針來最佳化發(fā)布的運行性能，這意味著無論如何都不會執(zhí)行邊界檢查。此外，算法輸入使用原始指針，需要仔細處理。由于在許多關鍵位置使用了原始指針，我會使用 Address Sanitizer 作為 CI 管道的一部分運行構建，偶爾也會在本地運行嘗試，因此我對缺少越界訪問感到安全。在沒有自定義可視化工具的情況下，調試器將無法顯示數組，更關鍵的是，在評估成員訪問權限時會遇到問題（這在 std::vector 中也是如此，因為這取決于調試器），這使得查看表達式更加復雜，調試也不那么愉快。現狀是既沒有提供完美的安全性，也沒有提供完美的性能，因此我決定嘗試使用原始指針。當然，容器的另一個好處是對內存泄漏的額外保護，由于我不是特別熱衷于記住釋放每個分配的指針，所以我創(chuàng)建了一個 meshopt_Allocator 類[7]。這個類可以分配大塊的類型數據并且會記住分配的每一個指針，在運行末尾階段，它將會刪除所有已分配的塊。這導致融合的分配器+數組的類被拆分為兩部分，一個是特殊的分配器類用于完成了內存管理任務，而對于數組而言一個原始指針就足夠了。Address Sanitizer，以及嚴格的測試和手動填寫的斷言聲明，這些將保持代碼正確。雖然我對這種權衡并不是百分之百滿意，但到目前為止它仍然運行良好。刪除與確定每個函數中是否應該使用原始指針、迭代器或容器相關的檢測的開銷是很有必要的。值得注意的是，使用 Address Sanitizer 構建的開銷是非常合理的，并且使用它會讓我感覺更安全，因為它會捕獲容器中的問題邊界檢查的超集。一旦我們切換到原始指針，我們的代碼中 C ++ 就剩不下多少了。偶爾還有一兩個模板（template），但實例化的數量足夠小，這樣我們可以僅為我們需要的每種類型復制代碼。meshoptimizer 使用了 C ++ 中的指針類型強制轉換和函數調用方式的強制轉換（例如int(v)），但 C 語言沒有這兩種強制轉化的方式，所以必須對代碼進行相應的調整。同樣，我們還遇到了一些其他的語法問題，但實際上在這一方面將代碼更改為 C 語言的版本并不難。這樣做的確需要更多的犧牲，還有就是 MSVC 的問題，要么我們必須使用 C89，要么將我們的 C99 代碼編譯為 C ++，除非我們愿意只支持最新的 MSVC 版本，但這樣做確實是可行的。在我們停止使用每個 C ++ 標準頭之后，這些真的重要嗎？對 gcc / clang 編譯時間有顯著影響，我們通過將代碼切換到 C 語言之后可以節(jié)省大約 40 ms。此時的真正區(qū)別在于標準頭文件上。例如simplifier.cpp 使用的 math.h 這個頭文件在 C ++模式下與 C 模式下相比實際上大了不少，一旦默認編譯模式設置為 C ++ 17 時，這種差異將會增加得更多：問題是 math.h 在 gcc / clang 編譯時會包含 cmath，cmath 會帶來很多 C ++ 機制進而增加運行成本，而在 libstdc ++ 中的 C ++ 17 中則會添加一連串新的特殊函數，這些函數卻很少有用，但無論如何都會使編譯速度變慢。在這種情況下，刪除對 math.h 的依賴很容易[8]：#ifdef __GNUC__
#define fabsf(x) __builtin_fabsf(x)
#define sqrtf(x) __builtin_sqrtf(x)
#else
#include <math.h>
#endif
就是上述這樣的方式一直到改成 C 語言版本的編譯時間。這絕對是 libstdc++ 和 libc++ 未來可以改進的領域。我認為對使用 C 的頭文件的而言，承擔 C++ 的包帶來的成本是不合理的。除了 math.h 問題之外，假設在編譯時間中 C 語言的代碼有意識的用到了 C++ 的子集，這樣的結果看起來 C 語言版本的代碼的編譯時間并不比 C++ 版本的快，所以這種情況的時候切換到 C 語言也不能保證 meshoptimizer 會更快。希望通過 simplifier.cpp 中的過去、現在和未來可能的變化進行探索是有用的。在制作 C / C ++ 庫時，重要的是要注意不僅僅只有代碼的正確性，而可移植性、編譯的簡易性、編譯時間、在調試和發(fā)布時的運行時間、可調試性等等，所有的這些都很重要，這些有助于減少庫和代碼貢獻者之間的沖突。C ++ 是一種無情的語言，但是，如果有足夠的時間和精力，就可以獲得良好的表現。前提是你愿意質疑一切，甚至包括有時被認為是極其常見的方法，例如 STL 或 CRT 的有效性或效率。我們在調試模式下在 gcc 中用了半秒的編譯時間，在 MSVC 中用了 36s 的運行時間，并以 gcc 的 100ms 編譯時間和 MSVC 上大約一秒的運行時間結束，這種方式使用起來更加愉快。當然，在 1K 行編譯 100ms 的前提下，并假設是線性關系，每 10K 行我們大約需要一整秒，這樣的結果仍然比其他一些語言慢得多，但這對于在單核上運行的完整構建來說并非完全不合理。為開發(fā)多年的大型代碼庫提供服務是一個更難的問題，這些將留給讀者作為練習了;）（https://gist.github.com/zeux/bf847986e0474cf48f61bb5749da38e4）可以獲得對 simplifier.cpp 的所有源修改；按照文章中描述的順序，它們依次是simplifiervsm.cpp、simplifiervs.cpp、simplifierv.cpp、simplifierb.cpp、simplifier.cpp、simplifier.c。[1]：去年，在工作中討論了 C ++，有人說“這是一個很好的 C++ 子集，一個擁有類的 C 語言”，我回答說“有一個更好的子集，擁有結構的 C 語言”。這就是大多數 meshoptimizer 源代碼的樣子，除了幾個模板。[2]：哈希表接口只有兩個函數，hashBuckets和hashLookup：simplifier.cpp:124 。[3]：使用 11 位是一個合理的選擇，因為它需要一個 2048 條目的直方圖，它需要 8 KB 并且可以輕松地適應 16 KB 的 L1 緩存。給定 32 KB L1 高速緩存，你可以將直方圖擴展到 12 位，但超出此范圍通常效率較低。你可以在 Pierre Terdiman 的 Radix Sort Revisited 文章中閱讀有關基數排序的更多信息（http://www./RadixSortRevisited.htm）。 [4]：sortEdgeCollapses 函數的完整實現可在此處獲得：simplifier.cpp:712（https://github.com/zeux/meshoptimizer/blob/c93ba0987baa84bd73b61edf1c0ba7ba2e48df4b/src/simplifier.cpp#L712）。[5]：這個類不再是 meshoptimizer 的一部分了，但你可以在這里查看較舊的稍長版本：meshoptimizer.h:605（https://github.com/zeux/meshoptimizer/blob/5b0d10bb3c0c174965b716dda3270bce4f3278b6/src/meshoptimizer.h#L605）。[6]：我在調查了調試中的奇怪性能差異后發(fā)現了這一點；我不愿重復所有先前測試用例的調試基準，所以我假設開銷是 std::vector 導致的額外的大約 30％。希望這不會改變一般情況。我不確定為什么默認情況下這些斷言沒有首先啟用，這似乎不是用戶友好的，但這應該反映了使用這些庫的默認體驗。[7]：所有 meshoptimizer 中的算法都使用了此類，可在此處獲得：meshoptimizer.h:662（https://github.com/zeux/meshoptimizer/blob/c93ba0987baa84bd73b61edf1c0ba7ba2e48df4b/src/meshoptimizer.h#L662）。[8]：這感覺就像補丁，而且我必須獨立地應用于多個源文件，所以現在我選擇不這樣做。但是，如果在修復此問題之前 C ++ 17 模式成為默認模式，我將不得不重新考慮，因為 2x 編譯時間損失有點太大了。
|
