面試 C++ 被人問你是如何優化你的代碼的,該從哪些方面進行回答?
類似問題:
面試 C# 被人問你是如何優化你的代碼的,該從哪些方面進行回答? - 編程
召喚 @grapeotProfiling帝正確思路:1)Profile,找出性能瓶頸
2)針對性地修改代碼、演算法、甚至框架,以解決瓶頸
3)如果性能還是不滿意,回到1。反正我問別人如何優化的時候如果沒聽到profile這一步後面的答案再精彩也基本fail了。圖源:Optimizing software in C++ : An optimization guide for Windows, Linux and Mac platforms
這個問題,可能需要分很多,我先寫一個大概,有空再來好好更新,或者我後面寫一篇專欄文章介紹一下每一條的原因。
1. 通用優化方面
如選用正確的數據結構與演算法
2. C++設計方面
如利用好STL容器;考慮使用引用替代指針;考慮使用二次構造;考慮限制異常;避免運行時的類型識別等3. C++語言優化方面
考慮使用初始化列表,而非構造函數內賦值;以引用傳遞class參數;避免C89中的變數先聲明再賦值,而是變數使用時直接初始化等;考慮使用inline;意識到virtual functions的開銷;模版元編程;constexpr的使用;RVO與右值引用等在臨時返回值的應用;nothrow等4. 編譯器優化方面 考慮使用編譯器提供的特定優化選項,如XL編譯器的-qhot(實力廣告)看大家說的都很抽象,我來回答一個具體的例子吧,算是當年學生時代的時候的一些做法,僅供初學者借鑒。各位大神請繞道。
幾年前,塞班剛開始沒落,可以用的軟體越來越少。但是基本的幾個大廠的軟體還夠用,我也沒在意,直到有一天迷上了小說,並且發現了一個名叫epub的電子書格式,第一次發現電子書也可以用排版和圖片還有章節等。但是奮力尋找塞班上epub的閱讀軟體,一個個都像是半成品一樣,不是難用就是有bug。查閱了epub的規範後,我覺得我可以自己做一個,當時也是通過在尋找電子書軟體的時候認識了做Qt 塞班貼吧的作者,從他那裡學到了qt qml開發在塞班上的技術。於是我著手去做這樣一個軟體。
學生時代第一次做真正的軟體,難免會出現各種奇葩的寫法啊,比如一個函數一兩百行,寫到最後發現不行了才拆分。但是說到優化,當年碰到了兩個優化問題。
一個是列表,我都不知道我從哪裡找來了一本幾百個目錄的epub,然後生成目錄列表的時候卡住了,當然當時我寫的時候是沒有ListView這種概念的,第一個版本只是不停的優化生成的時間,能裁剪的操作都裁剪,然後在正常的epub最多幾十個目錄的情況下能一兩秒出來,我就覺得滿足了。當然後來用上了ListView部分載入的技術後,直接就瞬開了。
第二個是最重要的一個部分,就是html格式的正文部分如何恰好的鋪滿一整個屏幕。當時最初期的想法是一個字一個字的加,然後不斷的算高度,看看是不是超過屏幕了,然而這樣算出來生成一頁需要一秒鐘,想想翻一頁要一秒鐘,簡直不能忍受。於是我看看怎麼去優化這個代碼,首先是估算出一個預設值,這個值大概是可以把屏幕鋪的差不多的字數(塞班當年基本就640*320這個解析度)。然後以這個值開始做加法或者減法,發現速度提升到了半秒,還是沒法忍受。這個時候,算字高還是依賴文本控制項內容改變後高度自己改變來得到的,由於qml並不是編譯性質的語言,結果就是非常慢,然後我找到了C++的 API,直接在C++裡面可以得到文本高度,這個時候速度提升到了0.3秒。雖然可以用了,但是我覺得還是比較卡頓。想來想去,發現平均每次翻頁要計算20次才能得到結果,突然就想到了二分法去定位最終的字數值,當年還不怎麼會寫二分法查找,夾雜在幾百行的xml解析的代碼中,調試了好久終於將計算次數縮小了75%以上,這個時候翻一頁也就0.2秒以下,自己使用的時候已經感覺不到卡頓了。
這個軟體後來上架了塞班的商店,得到了不少的好評,可惜的是我後來很快就換成了android機,那些年苦苦等我更新版本的同志們,對不住了。
上面的經歷,雖然說是非常普通非常簡單,但是完完全全是在沒有知乎,沒有其他人幫助的情況下自己去想,自己去做得到的結果。面試鵝廠的時候,技術面我就是拿這個軟體來講自己的優化歷程,雖然很簡單,但是從這裡起步,我覺得足夠了。1.優化流程2.優化演算法3.優化代碼
隨便說2句吧:
1. 格式優化簡單的說就是把代碼中冗餘,冗長,長嵌套,缺乏注釋,可讀性差,不合規範的地方重新改正過來,增強代碼的可維護性,可讀性2. 結構優化
也就是重構,把之前架構設計,模塊設計不合理的地方修正過來,重新設計符合需求的架構和模塊結構,解耦和,梳理繼承關係,模塊功能拆分等等。3. 效率優化主要針對2方面的效率:時間和空間。時間上通過函數分析工具之類的工具把熱點函數進行重寫以提高效率。空間方面主要是及時釋放不必要的內存空間,檢查內存泄露,檢查結構體是否聲明太多多餘內存等。首先確定優化的原因,目標,理想效果,然後尋找一條可以完成此任務的道路。
後面找路子就方法多多了。不過先確定那幾個前提是非常重要的。基本上所有的性能瓶頸都發生在循環上,所以:1, 找出循環2, 把循環內不變的東西請出循環3, 削弱循環內的計算強度
4, 減少循環次數
剛好這兩天對自己負責的一個模塊做了優化,說說過程吧
模塊功能: 產品是手機端貼吧類產品,我負責的是後台模塊,提供介面,用於分頁拉取帖子數據。由於手機屏幕小,流量金貴,帖子分條展示,手機查看是上下滑動等特性,分頁拉取是最好的選擇。
模塊架構: 帖子數據是落地到db的,一條記錄保存一個帖子信息,一次拉取N條數據。很自然想到的就是邏輯層--cache層--db存儲這樣的三層架構。因為要連接資料庫,這裡只能做同步svr,使用多線程處理並發請求。
上線後的問題: 根據上面的架構設計,很快代碼實現,並發布上線。問題來了,前端經常反饋超時,拉取不到數據,查看監控發現一個問題,請求量時不時會掉下來,這是很不正常的現象。
排查原因: 查看其他指標,發現請求量並不大,每分鐘才幾千(這裡的帖子數據並不是首頁數據,是比較靠後的數據),看機器負載也不高,可以排除過載的情況。 再看緩存命中率,發現緩存命中率很低,只有20%左右命中緩存,導致80%的請求直接到資料庫去查詢,這對於資料庫壓力是比較大的,根據二八原則,緩存命中率至少要達到80%才比較有效,大概問題就是這個了,接下來就是如何解決這個問題。
解決問題: 先說一下這裡緩存設計方案,使用stl裡面的map,每個吧每一頁作為一個key,對應數據作為value,map元素個數固定,當緩存滿了淘汰第一個元素,每個元素定期更新。
1.首先想到問題的是緩存數據太少,導致很多請求還需要到資料庫拉取,通過計算機器內存,以及每條帖子數據的大小,發現確實可以把緩存數據量加大,實行之,觀察後發現效果並不明顯。。。可能熱點數據沒有很好的cache住?
2.考慮到第一點的結論,以及業務本身特點,這批帖子數據比較靠後,被更新的概率比較小,而且延遲看到更新也不太能感知到,即不要求數據的強一致性,於是就增大了緩存的時間,由原來的5分鐘更新改為15分鐘更新。觀察數據,發現命中率有一定提升,但還是不夠好,大概30%左右。。。 我擦,想來想去都不知道是什麼原因,畢竟這個帖子列表的數據請求也是比較符合二八原則的,為什麼就是不能命中緩存呢??
3.只能上機器看看有沒有什麼異常,查看日誌,剛開始並沒有發現什麼問題,盯著滾動的日誌流水,總感覺有什麼地方不太對,隨便拿了一個case到頁面去模擬請求,發現確實很慢,再仔細看這個參數,好想有點不對,一個很小的吧,怎麼會拉取那麼後的數據,頁數竟然是9000多,手動是很難翻到這麼後的頁面,況且也沒有那麼多數據,再查看日誌,發現這種請求確實有點多,於是加了一個參數檢驗,如果請求的頁數太大,直接返回,發布上線,優化效果還是很明顯的,緩存命中率達到60%。這裡主要是對一些業務細節的思考,剛開始並沒有注意到這個問題,這種請求到資料庫,需要遍歷很多記錄,大大增加了處理時間,導致線程阻塞,無法處理其他請求,問題解決。
4. 但是並沒有達到最好的效果,上面提到至少要有%80的緩存命中率才算比較有效的,考慮可能是緩存滿的時候淘汰策略不夠好,為了快速上線,最早使用的是簡單淘汰第一個元素的方法,很可能把比較熱的數據給淘汰了,於是學習了LRU演算法,淘汰最近最少使用的元素,網上搜了一下代碼,有一個同學已經實現了,原理很簡單,再使用一個map保存每個元素最近使用時間,當需要淘汰的時候,從保存時間的map里取第一個元素(第一個元素的時間最小,既對應數據最老),再從數據緩存中剔除對應元素即可。在學習過程中,突然想到一個問題,保存數據的key是根據吧id+頁數,我們的吧id越小越多人訪問,而且同一個吧裡面頁數越小的數據越多人訪問,因此key越小的數據其實越熱門,所以每次只需淘汰最後一個元素(吧id最大頁數最大),這樣就可以很接近LRU演算法,而且不需要再存儲一個map,果斷實驗了一下,效果duang duang duang~~~緩存命中率達到85%。
總結:1,不管多牛逼的架構設計,都要結合業務場景進行分析,最適合業務的架構才是最好的架構2. 學會計算資源,包括內存,cpu,負載,資料庫負載等,根據資源設計架構3. 演算法是靈活的,根據業務場景優化演算法4. 熟悉你使用的組件機智,如果早點想到map的關聯特性以及排序,可能早就解決了這個問題。這是個陷阱!!! 作為一個合格的程序員,自己提交的代碼肯定是當前最優的,即使不是最優的,也是因為技能不足或對整體了解不足或目標不同。在沒有需求變化之前,代碼沒有優化的必要。
泛泛而談面試官應該不會接受吧, 並且也從來沒有說優化一段代碼 就開始改結構 優化代碼(改成內聯, 優化循環等),而一定是遇到具體的問題了, 結合具體問題分析解決.
結合遇到過的例子,假定和面試官談簡述一下,權當自己總結了.
1. 我遇到了什麼問題?
分散式環境上,演算法A由於採用了遞歸演算法, 大數據量下本來其他業務幾分鐘搞定的事情,它耗費動輒幾個小時,效率太差。
2. 梳理流程原因分析解決方案
演算法A所在進程運行演算法的數據源分別從其他子板匯聚而來,然後運行演算法。從兩個方面考慮優化,演算法:需要遍曆數據組合且數據源條數本來就是不確定的,遞歸改不了循環,演算法好像都動不了, 流程優化:最終匯聚到演算法A上面執行演算法, 是否可以在匯聚之前分別算好, 最後把結果匯聚一下? 最終敲定了這種方案,效率提升了一個數量級. 思路是比較簡單的,就是個拆分而已.3. 引入了什麼問題?又是怎麼解決的
本來順序執行的東西, 耗時分攤到別的進程去了,那主線程就阻塞的等待了,萬一有個進程遲遲沒返回,那豈不是掛了? ;不同的板子配置和能力不一樣, 是否有超時機制/內存監控等管理?等等問題。和c++一樣, 好多實踐都是解決新特性所引入的坑,所有的方案都會帶來點意想不到的意外。
簡化太多,真實面試如果面試官感興趣,可以用流程圖描述, 可以愉快的聊30min。 水平還是比較初級, 如果能從問題識別 profiler分析 演算法設計實現,全端搞定,那可聊就太多了.當然是profile 精確地profile 不要猜 程序大多耗在意想不到的地方 親身經驗 隨口說的都是胡扯
這問題好傻,應該沒人這樣問吧。。。
心裡要一直有線程模型和內存拷貝這兩根弦。注意cpu密集和阻塞的地方對程序的影響。學會profile。持續重構提高代碼的可讀性,擴展性,以及效率。
吐槽一下我覺得寫c++的人,很容易要麼過度抽象(什麼都要弄成通用的,或是什麼庫都要自己封一層),要麼完全不抽象。推薦閱讀:
※為什麼 C++ 標準不明確二進位介面 (ABI) 標準?
※關於Qt性能的損失,有沒有一個可以量化的概念?
※Qt 框架哪些方面效率高,哪些方面效率低?
※C++單元測試如何實施?
※各位都是怎麼進行單元測試的?