多線程編程的時候，使用無鎖結構會不會比有鎖結構更加快？

01-05

LINUX下網路編程。
我原來是使用的一個單線程的收發包模式，現在改成了多線程，一個線程收一個線程處理，但是兩個線程的數據訪問就是一個問題。我做了一個鏈表用比較複雜的方案不用鎖實現數據訪問和刪除，可是我最近一直在想如果用鎖的話會不會實現更好的效率，或者是效率沒有差別？
我想問下加鎖到底要消耗多少資源呢？不加鎖和加鎖區別有多大？
目前就兩個線程，但是每秒可能會有大量訪問。

我現在的結構是，一個線程收udp包，然後存進無鎖的鏈表，另外一個線程去鏈表取出數據作處理，並且銷毀使用過的節點。（為了保證不會出現原子問題，消耗節點的時候會保留最後的節點不銷毀，這樣兩個線程會相差一個節點保證不會同時訪問到）
http://pan.baidu.com/s/1kVqHjLl 還是放出了代碼，想要看源碼的可以拿去，我的代碼寫的很爛，有點不好意思見人，看多線程部分就可以了
測試結果放出
FPGA勻速發包 1400位元組每包

單線程
所有的操作通過select來進行
測試UDP接收效率接收速度 100MB 每秒丟包每秒 20 個左右
（特殊現象，速度變化似乎不會影響丟包數量丟包數量每秒20個遞增）
雙線程
一個線程接收，一個線程讀取數據，（建立鏈表使用的是malloc 和 free），低速時丟包不多

測試當UDP速度達到 50MB每秒時，似乎接近上限，此時丟包率1%以內
但是一旦速度超過50MB每秒，性能迅速惡化，接收速度依然穩定在49.98MB每秒。。。
鏈表沒有限制長度，此時鏈表最長大概也就300多吧，內存肯定沒有上線
雙線程（內存池結構）
鏈表節點是內存池中空節點取出的，不需要初始化，此時性能略有惡化。
但是當接收50MB每秒數據時候，丟包率到3%左右，速度再高丟包率也惡化了。

三線程（內存池列印信息單獨開一個線程）
性能急劇惡化。。。。。。丟包率上升到35%（列印的進程沒有休眠，似乎不太好）
=======================================
我估計由於我的程序效率低得原因是因為一個線程多數時候一直在while循環空等中佔用了過多了cpu資源，看來自己實現的無鎖結構還是不太好用啊。。。。。下一步打算加鎖，然後等待時候把進程休眠看看效果
→_→恩，代碼各路大神被批判一番，果然這兩天還是重寫代碼，感覺我的業餘代碼確實不能看，其實我自己也知道小毛病太多了，只是寫著寫著就懶得改。。
目前的地址池的代碼更爛，大概花了兩個小時寫出來的，容我重寫一遍吧。當然如何想要批判我一翻也可以拿去，辣眼睛。。←_←
-------------------------------------------------------------
這兩天寫完了一個帶鎖的內存池，下面是測試結果

我寫的無鎖結構確實有問題，速度比帶鎖的慢不少。。。不過是有bug。。因為我的pirnt測試信息時候要讀取長度時候要遍歷一遍鏈表，當鏈表超級長時候耗時很多。。。這部分被我注釋掉之後得到的就是上面的測試結果。
PS。藍線和紅線相差的是藍線直接釋放內存回內存池，紅線會memcpy出來再釋放內存。單寫雙讀總共三個線程，貌似速度相差很小，多個memcpy的操作速度還快一點我沒懂為什麼？
綠線是單寫單讀總共兩個線程
紫色線是我以前的鏈表結構
淺藍色線是malloc的時間曲線，沒有地址池

數據量是是這麼來的，總共多少個節點，每個節點是1000個位元組小段內存，時間是指跑一圈的平均時間，比如500就是，請求500w個節點，每個節點數據memcpy出來再釋放掉所用的時間
以上都是虛擬機2核cpu得到的數據，所以三線程比雙線程慢不少
-------------------------------
memcpy貌似並不是瓶頸啊。。另外大家說鏈表無鎖線程安全的事情，額，因為我這個無鎖結構只支持兩個線程，一個寫一個讀，所以其實問題不大
malloc圖已經補上了，300萬個節點差點跑了1分鐘，已經比地址池慢100倍以上了。malloc似乎10
w以內性能還行，40w之後直接指數上升了，另外malloc似乎第一次很慢後面速度會提高？
===========================================
結論：地址池確實很快很快，malloc確實很慢很慢，memcpy沒那麼不堪。鏈表的malloc確實很慢，大數據量時候malloc時間指數上升，地址池全部線性上升。

無鎖和有鎖在這個層面壓根沒有任何區別，或許無鎖還因為代碼質量速度不如有鎖。
無鎖結構還是要考慮臨界區的大小，如各位大神的回答，感覺作為一個新手確實學到很多。

具體情況需具體分析。

一部分朋友覺得用鎖會影響性能，其實鎖指令本身很簡單，影響性能的是鎖爭用（Lock Contention），什麼叫鎖爭用，就是你我都想進入臨界區，但只能有一個線程能進去，這樣就影響了並發度。可以去看看glibc中pthread_mutex_lock的源碼實現，在沒有contention的時候，就是一條CAS指令，內核都沒有陷入；在contention發生的時候，就選擇陷入內核然後睡覺，等待某個線程unlock後喚醒（詳見Futex）。

「只有一個線程在臨界區」這件事對lockfree也是成立的，只不過所有線程都可以進臨界區，最後只有一個線程可以make progress，其它線程再做一遍。

所以contention在有鎖和無鎖編程中都是存在的，那為什麼無鎖有些時候會比有鎖更快？他們的不同體現在拿不到鎖的態度：有鎖的情況就是睡覺，無鎖的情況就不斷spin。睡覺這個動作會陷入內核，發生context switch，這個是有開銷的，但是這個開銷能有多大呢，當你的臨界區很小的時候，這個開銷的比重就非常大。這也是為什麼臨界區很小的時候，換成lockfree性能通常會提高很多的原因。

再來看lockfree的spin，一般都遵循一個固定的格式：先把一個不變的值X存到某個局部變數A里，然後做一些計算，計算/生成一個新的對象，然後做一個CAS操作，判斷A和X還是不是相等的，如果是，那麼這次CAS就算成功了，否則再來一遍。如果上面這個loop裡面「計算/生成一個新的對象」非常耗時並且contention很嚴重，那麼lockfree性能有時會比mutex差。另外lockfree不斷地spin引起的CPU同步cacheline的開銷也比mutex版本的大。

lockfree的意義不在於絕對的高性能，它比mutex的優點是使用lockfree可以避免死鎖/活鎖，優先順序翻轉等問題。但是因為ABA problem、memory order等問題，使得lockfree比mutex難實現得多。

除非性能瓶頸已經確定，否則還是乖乖用mutex+condvar，等到以後出bug了就知道mutex的好了。如果一定要換lockfree，請一定要先profile，profile，profile！請確保時間花在刀刃上。

無鎖的會快，但是多線程網路編程不單單是有沒有鎖，這裡順便安利一下facebook開源代碼裡面thrift是怎麼做網路io的重點。最早的文章在這裡：https://code.facebook.com/posts/1468950976659943/

重點講到的是IOBuf，

chained memory buffer with views similar to BSD"s mbuf or Linux"s sk_buff. In earlier versions of Thrift, the same memory buffer was reused for all requests, but memory management quickly became tricky to use when we tried to update the buffer to send responses out of order.

你看先說的不是鎖不鎖的問題，反而先是確保不要複製。malloc裡面其實是有鎖的，多線程編程的時候，使用無鎖結構會不會比有鎖結構更加快？ - 姚冬的回答 - 知乎沒提到malloc鎖的問題但是提到了忌諱memcpy的問題。但是不管要不要memcpy都是需要一開始的buffer的。Facebook優化這個問題用到了調jemalloc

To reduce the performance impact of allocating new buffers, we allocate constant-sized buffers from JEMalloc to hit the thread-local buffer cache as often as possible.

（其實我至今都看不懂jemalloc那些參數怎麼調，什麼意思。。。）

超過一個IOBuf大小的請求列表連起來

These buffers are then chained together to become as large as needed, and freed when not needed, preventing some memory issues seen in previous Thrift servers where memory was pooled indefinitely.

然後最上層Linux api是epoll

現在回到PO主的問題，多線程的還是不多線程的，其實基本上facebook內部網路層面的代碼都是多線程的，但是為了讓多線程的代碼容易維護，會用到無鎖的SPSCQueue 或者MPMCQueue來確保代碼不要到處亂飛（其實MPMCQueue還是有鎖的，只是不在critical path上面，代碼轉在這裡https://github.com/facebook/folly/blob/master/folly/MPMCQueue.h。）What are the most commonly used thread-safe queue implementations in C++? 是quora上面Queue了討論，裡面有細講各種queue的實現以及效果，我不多說，我說多線程在這裡是怎麼做的（源代碼和文檔在這裡facebook/fbthrift）

- 你有一堆只負責io的線程，就負責往mpmcqueue裡面吧linux 的buffer變成iobuf，以及各種公司內部的邏輯（我記得還有加密一定是在io做的，deserialization不記得是不是了）

- 你有負責你自己業務邏輯的線程，這些線程就是從mpmcqueue裡面拿東西，然後執行你的邏輯

- io線程再負責把結果仍回去

回到PO主代碼，我公司電腦中文字元有問題所以注釋看不懂，

else { memcpy(newblock-&>data,buff,requstlen); newblock-&>datalen=requstlen; newblock-&>maxlen=requstlen; }

這個複製可以避開的，沒必要先放倒char再放到struct

get_firstblock 說實話我沒看懂，不過好像是把數據移到readbuff裡面然後就沒了，不過應該也不需要copy

select我不多說了，其他人有解釋為什麼要epoll

while loop你自己說了

多線程代碼我沒看到？！好想你從頭到尾就一個pthread_create，我沒看出來你加的是負責io還是cpu的thread

寫的比較快，輕噴，有意見記得評論我盡量回復。上班去了

用鏈表我感覺夠嗆，malloc和free咋整

你這麼糾結，還是直接把網卡mmap進用戶態進程地址空間自己寫網路協議棧吧

在目前的mutex實現前提下, 用lock-free一般不會更快. 它們都只能同時讓一個線程做有用的事, 在性能上不會有質的區別. 由於lock-free的代碼會明顯複雜, 性能還未必更高. 所以除非場景特殊, 用lock-free並不是個好主意.

更好的方法是減少數據共享, 比如你這裡分多個桶加鎖就行了, 性能會比單純用一套lock-free的數據結構更好. 在追求極限性能的場景中,一般考慮的是wait-free的演算法和容器, 這能讓所有線程同時做有用的事, 在關鍵代碼上相比加鎖和lock-free才有較大的區別.

個人認為更多的應該把精力放在架構上，無鎖和有鎖，你這樣測試估計不太可能測出什麼區別來，也不是流量越大，某種做法就更優的，你要知道無鎖和有鎖的實際差別到底在哪裡，不是那幾個指令的開銷，而是精確的掌控整個cpu調度體系的問題。

我們的目的應該是精確的控制cpu調度，在有限資源的情況下，如何更好的服務更多的客戶端（有鎖無鎖只是達成這個目標的手段而已）。

單台伺服器，cpu佔用過高過低都不優；內核頻繁切換是不優的；頻繁的競爭是不優的；無意義的內存佔用是不優的；客戶端得不到必要的反饋是不優的；不方便後期維護是不優的。

舉些例子來說，如果邏輯代碼很複雜，可能會嚴重的阻塞網路層，這時，無鎖沒有任何好處，處理不好反而會讓內存爆掉，有時，把阻塞反饋給客戶端是非常有必要的。

如果第三方IO導致阻塞很嚴重（等待其它伺服器的返回），cpu閑置率過高，這時不做特殊優化，估計也沒什麼差別，看你優化的方向了，如果是需要合併一些操作，個人覺得無鎖的會容易處理一些。

如果各方面都很平衡，但邏輯上需要完全的序列化，我也會傾向於無鎖。

所以，有鎖無鎖取決於你整體的考量，總會有阻塞點或者瓶頸，針對性的解決最關鍵的點，在效率優先的情況下考慮效率，在穩定性優先的情況下優先穩定性。

鎖+隊列可以支持線程間每秒上千萬個消息通信。

是否有所影響，在於你的網路庫（以及網路硬體）能否支持上千萬個消息讀寫。

後者嘛，我覺得很難。

我以前也做過接收FPGA高速發包的上位機程序。我那時候場景是這樣：下位機FPGA，千兆直連網路，上位機Windows。

一開始用Qt的network開發，丟包丟到慘不忍睹，注意Qt在Windows下的底層就是select。後來換ASIO，發現也沒好多少。於是再下一個，最後換了WinPcap（題主是Linux，不適用），問題解決。

中間遇到過很多坑，但是總體來說，做到以下幾點基本沒問題：

1.單線程收，反正我沒上多線程，也只開了一個進程就搞定了

2.上不上鎖無所謂，不要發生鎖爭奪就可以

3.緩衝區一次準備好，也就是說要事先分配，不要動態new或者malloc。因為動態分配內存都是有開銷的，再細微的開銷，對於UDP這樣性質和FPGA這樣高速設備，數量上來了肯定就會丟。

4.在接收的時候不做任何數據處理，注意是不做任何的數據處理，只管把數據memcpy到準備好的緩衝區里，然後馬上回去繼續接收，等一輪接收結束再拖走整個緩衝區去處理。

最後做出來，千兆網路大約跑到600M的樣子（很慚愧沒跑滿），UDP包在和大小不是1472這個最大值，因為FPGA那裡存儲邏輯的問題被改過，不過也是1000以上，具體不記得了。

至於丟包嘛，每輪發送30MB數據，也就是每輪大約3萬個包。大約10輪裡面會有1輪發生丟包，可能丟幾個或者幾十個，其他全能接到（0丟包）。

當然更快

但是你要玩就要玩整套，隊列要無鎖，喚醒要無鎖，task節點內存管理也要無鎖，必要的場景下，這些都可以做，性能秒掉基於鎖的實現

無鎖不一定快，阻塞不一定是壞事，重要的是利用好片上資源，降低有效計算外的通信開銷。Happy Hacking :p

不如跑個測試

sometimes.

既然是 UDP，為什麼不多個線程讀同一個 socket，這樣就不需要隊列了。

你這線程就幾個競爭一般般，通常來說無鎖的確會好一點。用什麼鏈表，幹嘛不用環形緩衝（ringbuffer）。

快不快這種問題，在Windows的VS里，只是一個按鈕的事情。遇到這種問題，覺得搞Linux的很可憐。

加個 SpinLock 也不費多少資源。

---------2016-12-8---------

看過你代碼之後……我覺得……你不如用個現成的網路庫來試試……

---------原答案---------

得看實際情況，你可以做壓力測試，看看無鎖和有鎖情況下的性能。

如果業務邏輯部分不是性能瓶頸的話，我的解決方案是N個I/O線程，一個工人線程這樣的結構，用無鎖隊列做通信，或者環形緩衝區。要發揮多核優勢的話，用網關+多進程單線程工人，加上消息隊列中間件。

一般都是無鎖的快。但無鎖和有鎖的界限其實不是很清楚。

加鎖本身的開銷並不大，關鍵是鎖互斥時候的等待時間非常大。

另外告訴你一個秘密，自己實現的無鎖數據結構90%都是錯誤的。

既然是linux 為何不摒棄Socket 而不自己做協議棧或者自己封裝網卡驅動？

做windows被綁手綁腳。。。。linux還不是想怎麼搞就怎麼搞，何況還有。。。各種開源協議棧。。。。

帶寬是個不容忽視的瓶頸

鏈表實現的無鎖化，在密集型響應時更有優勢，free和malloc的問題可以通過內存池的方式解決，或者通過指針方式。套接字接收那部分，做得工作越少，大多數情況下會有優勢。