Linux पाइप कितनी तेज़ है? (2022)

 (mazzo.li)
1 पॉइंट द्वारा GN⁺ 2023-10-06 | 1 टिप्पणियां | WhatsApp पर शेयर करें
  • Linux पाइप throughput को perf और kernel path analysis से ट्रैक करके, साधारण write/read आधारित 3.7GiB/s implementation को अंत में 62.5GiB/s तक बढ़ाया गया
  • Bottleneck की शुरुआत इस बात से होती है कि पाइप 4KiB page references रखने वाले ring buffer की तरह काम करती है, और copy, page allocation, lock, wait/wakeup की लागत भी साथ में चुकानी पड़ती है
  • vmsplice और splice user memory और kernel buffer के बीच copy कम करते हैं, जिससे throughput क्रमशः 12.7GiB/s, 32.8GiB/s तक बढ़ता है
  • इसके बाद virtual address range को struct page में बदलने की लागत प्रमुख हो जाती है, और 2MiB huge page इस्तेमाल करने पर page table traversal का बोझ घटकर throughput 51.0GiB/s तक पहुंचता है
  • अंतिम optimization SPLICE_F_NONBLOCK और busy loop throughput को और बढ़ाते हैं, लेकिन ready state का इंतज़ार करते समय CPU core को लगातार occupy रखते हैं

प्रयोग का लक्ष्य और baseline performance

  • लक्ष्य यह देखना है कि Linux में Unix pipe कैसे implement होती है, और pipe में data लिखने व पढ़ने वाले test program को चरणों में optimize करना है
  • प्रयोग का environment Intel Skylake i7-8550U CPU और Linux 5.17 है; Linux की internal implementation लगातार बदलती रहती है, इसलिए numbers environment के हिसाब से बदल सकते हैं
  • शुरुआती बिंदु ऐसा program है जो write और read system calls से 256KiB buffer को बार-बार pipe में भेजता है
    • write वही 256KiB buffer लगातार लिखता है
    • read कुल 10GiB पढ़ता है और throughput print करता है
    • code pipes-speed-test में है
  • comparison target के रूप में इस्तेमाल किया गया highly optimized FizzBuzz program, pv measurement में लगभग 36.2GiB/s output करता है
    • FizzBuzz L2 cache size जितने 256KiB blocks इस्तेमाल करता है
    • यह experiment भी वही 256KiB block इस्तेमाल करता है, लेकिन output content compute किए बिना pipe IO की upper limit के करीब value देखना चाहता है
  • पहली implementation का result इस प्रकार है
    • ./write | ./read
    • 3.7GiB/s, 256KiB buffer, 40960 iterations, कुल 10GiB transfer

write और read धीमे क्यों हैं

  • perf record -g और perf report से देखने पर write side के समय का लगभग 47% pipe_write में खर्च होता है
  • pipe_write के अंदर copy_page_from_iter और __alloc_pages का बड़ा हिस्सा होता है
    • data copy
    • page allocation
    • scheduling
    • wait/wakeup
    • lock acquire/release
  • Linux pipe page references रखने वाला ring buffer है
    • pipe_inode_info में head, tail, और pipe_buffer array होते हैं
    • pipe_buffer में struct page *page, offset, len होते हैं
    • x86-64 में सामान्य page size 4KiB है
    • default ring buffer slot count 16 है, और उदाहरण की 8-slot pipe अधिकतम 32KiB रख सकती है
  • head write end को, और tail read end को दर्शाता है
    • pipe भर जाए तो write block होता है
    • pipe खाली हो तो read block होता है
  • pipe_write आम तौर पर इस क्रम में आगे बढ़ता है
    • pipe पहले से भरी हो तो space मिलने तक इंतज़ार करता है
    • current head जिस buffer की ओर इशारा कर रहा है उसमें space हो तो पहले उसे भरता है
    • empty slot और बचा हुआ data हो तो नया page allocate करके भरता है और head update करता है
  • pipe_read इसके उलट pages consume करता है, पूरी तरह read हुए pages release करता है और tail update करता है
  • इस path में हर page दो बार copy होता है
    • user memory से kernel में एक बार
    • kernel से user memory में फिर एक बार
  • copy 4KiB page unit में होती है, और बीच में synchronization व page allocation/freeing मिलते रहते हैं
  • उसी machine पर single-thread sequential RAM read लगभग 16GiB/s था, और pipe path की complexity को देखते हुए write/read का करीब 4 गुना धीमा होना हैरान करने वाला नहीं है

vmsplice और splice से copy कम करना

  • fast IO में user memory और kernel buffer के बीच copy cost bottleneck बन सकती है
  • Linux pipe से जुड़ी zero-copy movement के लिए system calls देता है
    • splice: pipe और file descriptor के बीच data move करता है
    • vmsplice: user memory से pipe में data move करता है
  • vmsplice pipe में डालने वाले buffer को struct iovec array से specify करता है
    • return value pipe में असल में गए bytes की संख्या है
    • pipe ring buffer size limit के कारण requested पूरा size एक बार में नहीं जा सकता
  • vmsplice user memory को copy किए बिना pipe से जोड़ता है, इसलिए read side द्वारा उस data को consume करने से पहले buffer reuse न हो, इसका ध्यान रखना जरूरी है
  • FizzBuzz program इसके लिए double buffering इस्तेमाल करता है
    • 256KiB buffer को दो 128KiB halves में बांटता है
    • pipe size 128KiB सेट करके 4KiB pages के आधार पर 32 slots बनाता है
    • दोनों half buffers को बारी-बारी से भरता है और vmsplice से pipe में डालता है
  • test program असल में buffer contents दोबारा नहीं लिखता, लेकिन real output generation program के लिए जरूरी structure जैसा double buffering बनाए रखता है
  • write को vmsplice से बदलने पर throughput 12.7GiB/s हो जाता है
    • copy amount आधा हो जाता है
    • write/read की तुलना में 3x से अधिक improvement
  • read side को भी splice से बदलने पर सभी copies हट जाती हैं और throughput 32.8GiB/s तक पहुंचता है
  • हालांकि, vmsplice की safety पर ध्यान देना जरूरी है
    • page फिर splice होने पर lifetime बढ़ सकती है
    • SPLICE_F_GIFT के बिना भी यह unsafe है या नहीं, यह स्पष्ट नहीं है
    • zero-copy pipe को safely इस्तेमाल करने के लिए खास सावधानी चाहिए

iov_iter_get_pages और page conversion cost

  • vmsplice और splice लागू करने के बाद perf में vmsplice path का time बड़ा दिखता है
    • iov_iter_get_pages
    • __mutex_lock.constprop.0
    • add_to_pipe
  • iov_iter_get_pages, vmsplice को दिए गए struct iovec की virtual memory range को pipe द्वारा रखी जा सकने वाली struct page list में बदलता है
  • process physical memory address नहीं बल्कि virtual address इस्तेमाल करता है
    • CPU page table के जरिए virtual address को physical address में translate करता है
    • x86-64 में सामान्य page size 4KiB है
    • x86-64 page table को 4-level, हर level पर 512-way tree structure के रूप में समझाया जाता है
  • pipe का pipe_buffer struct page को reference करता है
    • struct page kernel की physical page और संबंधित metadata handle करने वाली core structure है
    • इसलिए vmsplice को input virtual memory range को physical page references में बदलना पड़ता है
  • iov_iter_get_pages के अंदर अधिकांश time get_user_pages_fast में खर्च होता है
    • 128KiB buffer और 4KiB page के आधार पर कुल 32 pages लेने पड़ते हैं
    • pipe code implementation में एक बार में nr_pages = 16 के साथ call करता है और जरूरत हो तो repeat करता है, लेकिन कुल spliced page count 32 है
  • get_user_pages_fast CPU जैसा काम software में करते हुए page table walk करके struct page collect करता है
  • caller जब pages इस्तेमाल कर रहा हो, तब physical page reuse न हो, इसके लिए struct page का reference count बढ़ाना पड़ता है
    • बाद में put_page से reference count घटाना पड़ता है
  • शुरुआत में memset से buffer भरने पर page table entries पहले से बन जाती हैं और get_user_pages_fast के slow path से बचा जा सकता है
    • memset न करने पर उदाहरण में throughput 25.0GiB/s तक घट जाता है
    • huge page इस्तेमाल करने पर यह phenomenon उसी तरह नहीं दिखता

huge page से page handling cost घटाना

  • x86-64, 4KiB normal pages के अलावा 2MiB और 1GiB huge pages support करता है
    • आगे के experiments सिर्फ 2MiB huge page देखते हैं
    • 1GiB pages relatively rare हैं और इस काम के लिए overkill माने गए
  • huge page same memory range को fewer pages से represent करके management cost घटाता है
    • virtual address को physical address में translate करते समय page table level भी एक कम हो जाता है
    • CPU के TLB burden को कम करने में भी मदद कर सकता है
  • इस experiment का direct bottleneck hardware page table walk नहीं, बल्कि kernel का software path get_user_pages_fast है
  • Linux में 2MiB-aligned memory allocate करके और madvise(..., MADV_HUGEPAGE) call करके huge page use करने का अनुरोध किया जा सकता है
  • huge page लागू करने पर throughput 51.0GiB/s तक बढ़ता है
  • performance improvement का कारण यह नहीं है कि struct page सीधे एक 2MiB page को point करता है
    • kernel code आम तौर पर मानता है कि struct page current architecture के standard page size को point करता है
    • huge page को head struct page और कई tail struct page से represent किया जाता है
    • 2MiB huge page को 4KiB के आधार पर अधिकतम 512 struct page से represent किया जा सकता है
  • फिर भी पहली entry मिल जाने के बाद, आगे के struct page simple loop से generate किए जा सकते हैं, जिससे page table को बार-बार traverse करने की cost घटती है
  • Linux 5.17 के बाद kernels में head page को explicit रूप से identify करने वाला struct folio शामिल है, जिससे runtime head/tail checks की जरूरत कम करने वाला improvement है

busy loop से synchronization cost घटाना

  • huge page लागू करने के बाद perf में wait_for_space और __wake_up_common_lock time प्रमुख दिखता है
    • writable space का इंतज़ार करने की cost
    • read side को wake up करने की cost
  • इस synchronization cost से बचने के लिए vmsplice और splice में SPLICE_F_NONBLOCK इस्तेमाल किया जा सकता है
    • pipe में लिखा न जा सके तो तुरंत EAGAIN return करता है
    • caller तैयार होने तक busy loop चलाता है
  • busy loop लागू करने पर throughput 62.5GiB/s तक बढ़ता है
  • cost भी स्पष्ट है
    • vmsplice या splice ready होने का इंतज़ार करते समय CPU core पूरी तरह occupy रहता है
    • यह ज्यादा CPU usage के बदले latency या throughput पाने का तरीका है
  • अंत में यह synthetic benchmark लगभग 3.5GiB/s से लगभग 65GiB/s level तक improve हुआ

बचे हुए details और practical topics

  • optimization process perf output और Linux source code को साथ देखकर आगे बढ़ा
  • जिन topics को cover किया गया वे pipe और splicing से भी बड़े high-performance programming topics से जुड़े हैं

    • zero-copy operations

      • ring buffer
      • paging और virtual memory
      • synchronization overhead
      • real code में page table contention घटाने के लिए दो buffers अलग-अलग allocate किए जाते हैं
      • get_user_pages page table entries का reference count बढ़ाता है और put_page घटाता है
      • अगर दो buffers अलग-अलग page table entries इस्तेमाल करें तो reference count modification contention घटता है
      • test को taskset से ./write और ./read processes को दो cores पर pin करके run किया गया
      • repository में get_user_pages_fast के लिए synthetic benchmark भी शामिल है
      • huge page use करने या न करने के हिसाब से speed difference measure किया जा सकता है
      • splicing अब भी एक ambiguous और risky concept बना हुआ है, और related issues kernel developers पर लगातार बोझ बने रहते हैं

संबंधित पढ़ाई

1 टिप्पणियां

 
GN⁺ 2023-10-06
Hacker News की राय

  • अगर मैंने ठीक समझा है, तो vmsplice जब पढ़ने और लिखने वाले दोनों सिरों पर साथ-साथ इस्तेमाल किया जाए, तो यह दो processes के बीच छोटे shared memory mechanism जैसा दिखता है
    यानी दोनों processes को बेहद सावधान रहना पड़ता है कि buffer कब पढ़ना/लिखना है और इस्तेमाल के बाद उसे कैसे लौटाना है। यह तेज़ है, लेकिन साथ ही डरावना तरीका भी है, और यह बात भी अफ़सोसजनक है कि जो सीधा-सादा implementation हर कोई लिखेगा, वह संभव performance से 20 गुना धीमा है

    • अगर आप 20 गुना तेज़ version लिखने की कोशिश करेंगे, तो सहकर्मी इसे ज़रूरत से ज़्यादा जटिल बनाना और team player जैसा न होना मानेंगे
    • मुझे नहीं लगता कि vmsplice दो processes के बीच छोटा shared memory mechanism है। यह सिर्फ़ user memory से pipe तक zero-copy support करता है, और उलटी दिशा में copy होती है
      अधिक जानकारी के लिए https://mazzo.li/posts/fast-pipes.html#fn10 देखें

  • मैं सोच रहा हूँ कि क्या कोई data processing library है जो pipes, sockets, files और memory को abstract करते हुए ऐसी optimizations भी कर देती हो
    जानना चाहता हूँ कि C, C++, Rust या किसी दूसरी systems language में ऐसी कोई library है या नहीं। लेख में आए splice() और vmsplice() जैसे APIs से मैं परिचित नहीं हूँ, इसलिए low-level applications बनाते समय सोचने लगा कि क्या कोई library होगी जो जहाँ संभव हो वहाँ ऐसी optimizations अपने-आप इस्तेमाल कर ले। यह भी जानना चाहूँगा कि libuv, tokio, Netty Linux पर इसे automatically handle करते हैं या नहीं; थोड़ी-सी खोज से लगा कि शायद ऐसा हो सकता है

    • यह सामान्य flow से अलग हो सकता है, लेकिन यह portable नहीं है, इसलिए इसे abstract करने की value बहुत ज़्यादा नहीं है। संभावना है कि जहाँ ज़रूरत हो, वहाँ आप इसे खुद implement करेंगे
      उच्च-स्तरीय code ऐसे features बहुत कम इस्तेमाल करता है, क्योंकि ये काफ़ी special-purpose हैं और Linux के हिसाब से specialize करने पड़ते हैं। अगर आप data को देखे बिना सिर्फ़ Linux पर move कर रहे हैं, तो splice उपयोगी है। TCP/UDP proxy जैसे applications के लिए यह निश्चित रूप से चाहिए, लेकिन साधारण HTTP server के लिए यह उतना fit नहीं है। अगर आप ऐसा app बना रहे हैं, तो zero copy जैसे keywords आपको बार-बार मिलेंगे, और splice सबसे पहले दिखने वाले results में से एक होगा
    • tokio के लिए एक crate है। automatic नहीं है, लेकिन दिलचस्प हो सकता है: https://lib.rs/crates/tokio-splice
    • Cosh पर नज़र डालना उपयोगी हो सकता है। मैं अभी उसका paper पढ़ते हुए सोच रहा हूँ; यह ऐसा model है जो optimization की अनुमति देते हुए भी message-passing abstraction देता है
      research environment के बाहर यह बहुत प्रसिद्ध नहीं लगता, और efficient Cosh implementation लिखने में काफ़ी समय लग सकता है। संक्षेप में, इसके तीन transfer modes हैं: move, share, copy। उदाहरण के लिए, move transfer में sender अपने read/write अधिकार वाले data को receiver को पूरी तरह सौंप देता है, और इसे page table की virtual memory remapping से implement किया जा सकता है। साथ ही strong/weak properties भी हैं, जो बताती हैं कि क्या sender और receiver के सहयोग करने पर भरोसा किया जा सकता है, या virtual memory permission remapping से सख़्त isolation करना होगा। सच कहूँ तो, मुझे नहीं पता कि इसे इतना optimize किया जा सकता है कि यह बहुत ज़्यादा optimized pipe जैसी चीज़ से reliably टक्कर ले सके; यह “काफ़ी smart compiler” वाली समस्या भी बन सकती है। फिर भी मुझे लगता है कि इसे आज़माने लायक है
      [1] https://barrelfish.org/publications/trios14-baumann-cosh.pdf

  • 2022 से पहले की चर्चा: https://news.ycombinator.com/item?id=31592934

    • खोलकर देखने पर यह “How fast are Linux pipes anyway?” पर चर्चा थी, और जून 2022 में इस पर लगभग 200 comments आए थे: https://news.ycombinator.com/item?id=31592934

  • 4 साल पहले संयोग से पता चली एक हैरान करने वाली बात यह थी कि Linux pipes इस्तेमाल करने पर nondeterministic behavior हो सकता है
    https://www.gibney.org/the_output_of_linux_pipes_can_be_inde...

    • यह कोई हैरानी की बात नहीं है। बनाई गई pipe असल में echo किए गए data में से कुछ भी pass नहीं करती
      (echo red; echo green 1>&2) | echo blue | symbol के दोनों तरफ दो subshell बनाता है। subshell मौजूदा shell के child process होते हैं, इसलिए वे open file descriptor table जैसी अहम properties inherit करते हैं। दोनों subshell साथ-साथ चलते हैं, और parent shell बस सभी child processes के खत्म होने का wait() करता है। कौन-सा child पहले चलेगा, यह आम तौर पर predict नहीं किया जा सकता, और multicore system पर वे सचमुच एक साथ भी चल सकते हैं। बाएँ subshell का standard output pipe के write end से, और दाएँ subshell का standard input read end से जुड़ा होता है। लेकिन echo blue input पढ़ता नहीं, सिर्फ output करता है, इसलिए pipe से कुछ भी read नहीं होता। echo green >&2 standard output को pipe में नहीं, बल्कि जहाँ standard error point कर रहा है वहाँ भेजता है। आखिर में echo green और echo blue एक ही file, शायद terminal, में सीधे लिखते हैं, जिससे race condition बनती है, और order इस पर निर्भर करता है कि किसे पहले schedule किया गया
    • थोड़ा और गहराई से सोचें तो यह पूरी तरह स्वाभाविक है। pipeline के programs साथ-साथ चलते हैं
      वरना pipeline उपयोगी नहीं होगी। उदाहरण के लिए, curl से tar file download करके तुरंत extract करने वाली pipeline में, अगर curl खत्म होने तक इंतज़ार करके फिर tar चलाएँ, तो बड़ी intermediate tar file कहाँ store करें जैसी समस्या आएगी। buffer छोटा रखने और तेज चलने के लिए tar को curl के चलने के दौरान ही साथ चलना चाहिए। pipeline programs के बीच इकलौता control flow standard input और standard output से बनता है। उदाहरण में standard error पर लिखा जा रहा है, इसलिए वह जाहिर तौर पर deterministic control flow में शामिल नहीं है
    • अगर आपको Linux में तेज zero-copy I/O पसंद है, तो यह लेख भी देखने लायक है
      साथ ही, confusion से बचने के लिए: “Indeterministic” दर्शन का term है, और computer science का term “nondeterministic” है
      0. https://blog.superpat.com/zero-copy-in-linux-with-sendfile-a...
    • क्या यह वाकई इतना हैरान करने वाला है? कौन-सा output expected था और क्यों, यह पता हो तो confusion दूर करना आसान होगा
      यह command शायद जानबूझकर अजीब बनाई गई है, और code reviewer होता तो निश्चित ही शक करता। echo red है, लेकिन कहीं pass नहीं होता। यह “red herring” joke भी हो सकता है। echo green standard error पर जाता है, इसलिए वह तभी दिखता है जब echo blue से पहले खत्म हो। exact order output buffering पर निर्भर करता है, और यह इस बात पर बदलता है कि कौन-सा time slice पहले assign हुआ, साथ ही CPU की संख्या और load पर भी। इसलिए यह nondeterministic है, लेकिन उसी तरह जैसे top nondeterministic होता है
    • क्या ऐसी चीज़ें असल में problems पैदा करती हैं? सच कहूँ तो यह example काफी artificial लगता है

  • संक्षेप में, अगर मान लें कि दोनों programs को जितना संभव हो उतना optimal लिखा गया है, तो pipe की maximum speed system के एक core की read/write speed के करीब होती है
    मूल रूप से kernel एक program के standard output से दूसरे program के standard input में वही physical memory pages map करता है, इसलिए काम zero-copy हो जाता है, या कम optimal हालात में तेज single copy के करीब। यह जान लेने के बाद, shell scripts में pipe से दो या ज्यादा tools जोड़कर बेहद high-performance काम करना rewarding भी लगता है और थोड़ा मजेदार भी। यह toolbox के सबसे उपयोगी tools में से एक है

    • pipe zero-copy तभी होती है जब splice या vmsplice इस्तेमाल किए जाएँ। ये Linux-only system calls लिखने में कठिन हैं, खासकर vmsplice
      ज्यादातर programs और shell filters, pv जैसे notable exceptions को छोड़कर, इन्हें इस्तेमाल नहीं करते, इसलिए kernel memory में copy करने और फिर वापस निकालने की cost चुकाते हैं
    • मेरी समझ में pipe की एक गंभीर सीमा यह है कि x86 Linux पर यह सिर्फ 64KB / 16 pages buffer कर सकती है। आम तौर पर इसके core-memory bandwidth से धीमा होने की संभावना ज्यादा है
    • इसलिए threads उतने महत्वपूर्ण नहीं हैं जितना कई programmers सोचते हैं
      आप जो application बना रहे हैं, उसके load characteristics के हिसाब से pipe+process या green/user-space threads से ज्यादा साफ तरीके से implement हो सकती है। कम convenient हो सकता है, लेकिन message passing आम तौर पर deadlock hell से बेहतर होती है
    • मजेदार बात इसलिए है कि लोग या teams इससे खराब परिणाम पाने के लिए कई हफ्ते और काफी पैसा खर्च कर देते हैं
    • ऐसी system magic मुझे ठीक से नहीं पता, लेकिन क्या data को पूरा memory तक जाना पड़ता है? या cache वह round trip रोक देती है?

  • यह लेख Linux pipes को तेज बनाने के तरीके पर है, लेकिन shared memory या message queue जैसे दूसरे तरीके अब भी तेज हो सकते हैं
    जिन systems में बहुत सारा data तेजी से move करना होता है, वहाँ pipe का extra step speed कम कर सकता है। जब कई threads data share करते हैं, तब भी pipe दूसरे तरीकों की तुलना में ज्यादा problems पैदा कर सकती है। इसलिए लेख में बताए गए improvements शायद speed-critical real-world situations में बहुत मददगार न हों

    • क्या कोई example दे सकते हैं? data को batch करके process करते समय io_uring जैसी चीज़ चुनने पर फायदा होता है
      लेकिन bidirectional communication में किसी न किसी तरफ data ready होने की notification चाहिए। हो सकता है आप CPU जलाते हुए polling न करना चाहें, और मुझे साफ नहीं कि ऐसे options वह synchronization pipe से तेज कैसे handle करते हैं
    • message queue library इस्तेमाल करने का एक फायदा यह भी है कि multiple platforms के बीच incompatibility की चिंता कम करनी पड़ती है

  • page table जैसी चीज़ों के बारे में पता था, लेकिन इसे perf के जरिए performance analysis से जोड़कर देखने पर साफ हुआ कि throughput में यह कितना central है

  • pipes बेहतरीन हैं। दूसरा process किसी दूसरे CPU पर हो या दूसरी machine पर, सच कहूँ तो खास फर्क नहीं पड़ता
    https://github.com/nathants/s4/blob/master/examples/nyc_taxi...

  • pipes cat, sed, awk, cut, grep, uniq, jq आदि को बार-बार combine करने के लिए पर्याप्त तेज हैं