เพิ่มประสิทธิภาพโค้ด 4 เท่าด้วย if ที่ไร้ประโยชน์

 (purplesyringa.moe)
1 คะแนน โดย GN⁺ 3 시간 전 | 1 ความคิดเห็น | แชร์ทาง WhatsApp
  • เพิ่ม เงื่อนไขเพียงหนึ่งจุด ในลูปที่ไล่ตามเส้นทางการเข้ารหัสที่เหมาะที่สุดของตัวบีบอัดเฉพาะโดเมน ทำให้เวลาในการรัน benchmark แบบสังเคราะห์ลดจาก 320µs เหลือ 80µs
  • เนื่องจากในแต่ละรอบ ที่อยู่หน่วยความจำขึ้นกับ j จากรอบก่อนหน้า แม้แต่คำสั่ง mov เพียงคำสั่งเดียวก็ยังติดอยู่กับ latency ของการเข้าถึงหน่วยความจำ โดยไม่สามารถใช้ประโยชน์จาก instruction-level parallelism ได้
  • หากนำคุณสมบัติที่ว่า next_j[i][j] ส่วนใหญ่มีค่าเท่ากับ j เดิมไปสะท้อนในการทำนายสาขา CPU จะสามารถข้าม dependency ระหว่างรอบ และ speculative execution หลายรอบได้
  • ใช้การ cast เป็น volatile เพื่อไม่ให้คอมไพเลอร์ลบ if ที่ในเชิงความหมายไม่จำเป็นออกไป ใน LLVM การใช้ [[unlikely]] หรือ __builtin_expect(..., 0) ก็ใช้ได้เช่นกัน แต่ volatile สร้างโค้ดที่ดีกว่าและ GCC ก็รองรับด้วย
  • ในการทดลองที่สมจริง ได้ ประสิทธิภาพเพิ่มขึ้นประมาณ 2 เท่า ซึ่งอาจเกิดจากการสร้างโค้ดที่ยังไม่เหมาะที่สุดของ LLVM และหากทำนาย j ได้ยาก สามารถใช้ pshufb ที่มี latency 1 cycle เป็นทางเลือกได้

การไล่ตามเส้นทางที่เหมาะที่สุดของตัวบีบอัด

  • ต้องแบ่งสตริงอินพุตออกเป็นหลาย chunk และเลือกการเข้ารหัสที่มีขนาดเล็กที่สุดสำหรับแต่ละ chunk
    • การเข้ารหัสแต่ละแบบบีบอัดอักขระที่ถนัดได้ต่างกัน จึงตัดสินขอบเขต chunk ได้ยากในทันที
    • อัลกอริทึมใน บทความก่อนหน้า แปลงปัญหานี้ให้เป็น การค้นหาเส้นทางสั้นที่สุด บนกริด
  • แต่ละเซลล์จะบันทึกเซลล์ที่เหมาะที่สุดถัดไปที่จะย้ายไป
    • หากไล่ตาม reference จากเซลล์แรกไปจนถึงเซลล์สุดท้าย จะได้ลำดับการเข้ารหัสที่เหมาะที่สุด
  • ลูปแรกที่เติมค่า next_j ถูกปรับแต่งด้วย SIMD ไว้แล้ว
    • bottleneck จริงคือ ลูปไล่ตามเส้นทางแบบง่าย ๆ ต่อไปนี้
uint8_t encoding[n_symbols];
uint8_t j = 0;

for (int i = 0; i < n_symbols; i++) {
    j = next_j[i][j];
    encoding[i] = j;
}
  • การทำงานหลัก j = next_j[i][j] หากไม่รวมการเขียน จะถูกคอมไพล์เป็นคำสั่ง mov เพียงคำสั่งเดียว

Dependency ที่ทำให้แม้คำสั่งเดียวก็ช้าลง

  • CPU สมัยใหม่ใช้ instruction-level parallelism เพื่อรันหลายคำสั่งและงานจากรอบลูปที่ต่างกันพร้อมกัน
    • นี่คือเหตุผลที่ในลูปทั่วไป ค่าใช้จ่ายของการตรวจ i < n_symbols และ i++ ไม่ได้ขัดขวางงานอื่น
  • แต่ คำสั่งที่พึ่งพากัน ไม่สามารถรันพร้อมกันได้
    • การคำนวณที่อยู่หน่วยความจำ next_j[i][j] ของรอบปัจจุบันต้องใช้ j ที่ได้จากรอบก่อนหน้า
    • รอบถัดไปจึงเริ่มไม่ได้จนกว่าผลลัพธ์ของรอบก่อนหน้าจะออกมา ทำให้ได้รับผลจาก latency ของการเข้าถึงหน่วยความจำ แม้ข้อมูลจะอยู่ใน cache ก็ตาม

ใช้ branch prediction เป็น value speculation

  • ตัวบีบอัดนี้คาดว่าจะมีจำนวน chunk ไม่มาก ดังนั้นกรณีที่ next_j[i][j] เท่ากับ j เดิมจึงเป็นส่วนใหญ่
  • เราไม่สามารถสั่ง CPU โดยตรงให้ทำนายที่อยู่ว่า j จะคงเดิมได้ แต่สามารถใช้ branch prediction เพื่อสร้างผลลัพธ์แบบเดียวกันได้
for (int i = 0; i < n_symbols; i++) {
    if (j != next_j[i][j]) {
        j = next_j[i][j];
    }
    encoding[i] = j;
}
  • หาก CPU ทำนายว่าจะไม่รัน body ของ if ก็จะมองว่าไม่มี dependency ระหว่างรอบที่อัปเดต j และจะ speculative execute หลายรอบ
  • หากเงื่อนไขเป็นจริงจริง ๆ จะเกิด การกู้คืนจาก branch misprediction
    • ยกเลิกการเขียนที่ทำไปจากการทำนายผิด
    • เริ่มรันใหม่โดยใช้ j ที่ถูกต้อง
  • ระหว่างที่ j แทบไม่เปลี่ยน bottleneck ของลูปจะเปลี่ยนจาก latency ไปเป็น throughput

ป้องกันไม่ให้คอมไพเลอร์ลบ if

  • จากมุมมองของคอมไพเลอร์ โค้ดที่เพิ่มเงื่อนไขกับโค้ดเดิมมีความหมายเหมือนกัน
    • หาก j อยู่ในหน่วยความจำ อาจหลีกเลี่ยงการเขียนที่ไม่จำเป็นหรือการเขียนลงหน่วยความจำแบบอ่านอย่างเดียวได้ แต่ในที่นี้เป็น ค่าของรีจิสเตอร์
    • การ optimize เช่น common subexpression elimination (CSE) อาจลบเงื่อนไขและการเข้าถึงซ้ำได้
  • compiler hint ทั่วไปมักใช้เพื่อลด branch แต่ในที่นี้กลับต้อง คงโค้ดแบบมี branch ไว้ ไม่ให้กลายเป็นโค้ดไร้ branch
  • ใช้การ cast เป็น volatile ฝั่ง assignment เพื่อให้การเข้าถึงหน่วยความจำของการตรวจเงื่อนไขและการกำหนดค่าดูเหมือนเป็นอิสระจากกัน
for (int i = 0; i < n_symbols; i++) {
    if (j != next_j[i][j]) {
        j = *(uint8_t volatile *)&next_j[i][j];
    }
    encoding[i] = j;
}
  • จากการตรวจสอบเพิ่มเติมวันที่ 13 กรกฎาคม เช่นเดียวกับวิธีที่ ibookstein พบ การใช้ [[unlikely]] หรือ __builtin_expect(..., 0) ก็ให้ผลแบบเดียวกันใน LLVM ได้
  • วิธี volatile สร้างโค้ดที่ดีกว่าและ ทำงานได้ใน GCC ด้วย

การเปลี่ยนแปลงประสิทธิภาพที่พบใน benchmark

  • ใน benchmark แบบสังเคราะห์ เวลาในการรันลูปลดจาก 320µs เหลือ 80µs ทำให้เร็วขึ้น 4 เท่า
    • ความต่างของเวลาต่อการรันหนึ่งครั้งอาจเล็ก แต่ในกระบวนการบีบอัด ลูปนี้ถูกเรียกหลายครั้ง จึงสะสมเป็นต้นทุนรวม
  • ในการทดลองที่สมจริงกว่า บันทึกได้ว่า ประสิทธิภาพเพิ่มขึ้นประมาณ 2 เท่า
    • อาจเป็นผลจากการที่ LLVM สร้างโค้ดได้ไม่เหมาะที่สุด แต่ก็ยังคุ้มค่าพอที่จะนำไปใช้

ทางเลือกเป็นการแทนค่าด้วย bitmask

  • ในอัลกอริทึมนี้ next_j[i][j] มีได้เพียงหนึ่งในสองค่า
    • ส่วนใหญ่คือ j ปัจจุบัน
    • ที่เหลือเป็นค่าที่ไม่เกี่ยวกับ j และขึ้นกับ i เท่านั้น
  • สามารถเปลี่ยนอาร์เรย์ next_j[i] ที่มี 8 องค์ประกอบให้เป็นคู่ของค่าทดแทนกับ bitmask ได้
    • ในการแทนค่านี้ if มีความจำเป็นในเชิงความหมาย จึงไม่ต้องใช้ทางอ้อมด้วย volatile
    • อย่างไรก็ตาม บน x86 การตรวจ bit ที่ตำแหน่งแปรผันอาจช้ากว่าการเปรียบเทียบ จึงมีความเป็นไปได้ที่ประสิทธิภาพรวมจะลดลงแทน

เมื่อทำนาย j ไม่ได้

  • บทความเรื่องการเร่งการไล่ตาม linked list ด้วย value speculation ก็กล่าวถึงวิธีเพิ่มประสิทธิภาพด้วยแนวทางเดียวกัน
  • หากทำนาย j ได้ยาก สามารถใช้ pshufb ซึ่งเป็นคำสั่ง vector index ได้
    • pshufb มี latency 1 cycle จึงลดให้ต่ำกว่านี้ได้ยากหากไม่มี speculative execution
    • สามารถคำนวณเส้นทางของค่าเริ่มต้น j ที่เป็นไปได้แต่ละค่าแบบขนานด้วย vector operation
    • ยังสามารถแบ่งงานไปหลาย thread แล้วนำผลลัพธ์มารวมกันได้ด้วย

บทความที่เกี่ยวข้อง

1 ความคิดเห็น

 
GN⁺ 3 시간 전
ความคิดเห็นจาก Lobste.rs

  • ดูเหมือนว่าแค่ใส่ แอตทริบิวต์ [[unlikely]] ของ C++20 ไว้กับคำสั่ง if ก็เพียงพอที่จะทำให้ clang ไม่สามารถตัดโค้ดส่วนนั้นทิ้งได้: https://clang.godbolt.org/z/r4xYWfPfe
    ยังไม่ได้ตรวจสอบกับคอมไพเลอร์ตัวอื่น

    • พอตรวจอีกครั้งพบว่าใน LLVM มันใช้งานได้จริง และน่าจะเป็นเพราะตอนแรกลองผิดกับ GCC ที่ไม่มีผล
      อย่างไรก็ตาม [[unlikely]] จะ ย้ายโค้ดออกไปไว้นอก fast path ทำให้ LLVM สร้างโค้ดที่ค่อนข้างไม่มีประสิทธิภาพแบบด้านล่าง 
              cmp     r8b, dl  
        jne     not_equal  
continue:  
        ...  
not_equal:  
        mov     ecx, edx  
        jmp     continue
      รูปแบบต่อไปนี้ดูสมเหตุสมผลกว่า 
              cmp     r8b, dl  
        je      skip  
        mov     ecx, edx  
skip:  
        ...
      นอกจากนี้มันยังเพิ่มคำสั่งอีกหนึ่งตัวในลูปร้อนเพื่อให้ปรับแต่งไม่ต้องอ่านค่าจากหน่วยความจำหลายรอบ ดังนั้น เทคนิคที่ใช้ volatile ก็ยังมีประโยชน์อยู่ แต่ก็น่ายินดีที่โค้ดเดิมเองก็ยังทำงานได้เช่นกัน

  • เทคนิคนี้ที่อื่นเรียกว่า value speculation: https://mazzo.li/posts/value-speculation.html

    • หลังจากคิดวิธีนี้ขึ้นมาใหม่ ตอนแรกผมคิดว่าน่าจะเอาไปใช้กับ linked list ที่เก็บไว้ใน arena ได้ด้วย แต่บทความที่ลิงก์ไว้พูดถึงเรื่องนั้นตรง ๆ อยู่แล้ว เลยเพิ่มลิงก์นั้นเข้าไปในบทความของผมด้วย

  • อีก 2–3 ปีข้างหน้า นักพัฒนาน่าจะยิ่งไม่สนใจผลลัพธ์ของ LLM มากขึ้นเรื่อย ๆ เลยสงสัยว่าพวกเขาจะยังสนใจบล็อกโพสต์แนวนี้อยู่ไหม

    • แม้แต่ตอนนี้คนที่สนใจก็มีน้อยมาก และถ้ามองทั้งวงการโปรแกรมมิงก็ถือเป็น ความรู้เฉพาะทาง
      ถึงอย่างนั้นสำหรับคนที่สนใจ มันก็ยังเป็นบทความที่มีประโยชน์และดีมาก
    • Godbolt ได้รับความนิยมมาก เวลานักพัฒนาที่หมกมุ่นกับ LLM ถูกวิจารณ์เรื่องนิสัยไม่อ่านโค้ด ก็มักยก “ดูถึงระดับแอสเซมบลีเลยเหรอ?” ขึ้นมาเหมือนเป็นคำโต้แย้งสำคัญ แต่ในความเป็นจริงก็มีคน ตรวจดูแอสเซมบลี อยู่และจะทำต่อไป
      นักพัฒนาที่คิดว่ารายละเอียดไม่สำคัญยากจะเป็นนักพัฒนาที่ดีได้ เหมือนวิศวกรโยธาที่ยอดเยี่ยมต้องใส่ใจตั้งแต่น็อตและโบลต์ของโครงการใหญ่ นักพัฒนาที่เก่งก็ต้องขุดลงไปถึงรายละเอียดเล็ก ๆ เช่นกัน เพราะภาพรวมถูกสร้างขึ้นจากรายละเอียด และถ้าคุณให้ความสำคัญกับสิ่งที่ตัวเองสร้าง ก็หลีกเลี่ยงเรื่องนี้ไม่ได้
    • ผมมองว่ามันไม่ได้ต่างจากตอนนี้ในระดับรากฐาน ทุกวันนี้คนส่วนใหญ่ก็ไม่ได้สนใจ ผลลัพธ์จากคอมไพเลอร์ ของโค้ดที่มนุษย์เขียนอยู่แล้ว
      คนที่จะไปดูผลลัพธ์จากคอมไพเลอร์ของโค้ดที่ AI เขียนอาจมีน้อยลงอีก แต่โครงสร้างพื้นฐานของเรื่องนี้คงไม่เปลี่ยน
    • สิ่งที่จะเปลี่ยนน่าจะไม่ใช่ว่ามีความสนใจหรือไม่ แต่เป็น การจัดลำดับความสำคัญของการปรับแต่งใหม่ มากกว่า
      เมื่อ 10 ปีก่อน ถ้า Bash script ช้าลงนิดหน่อย ก็คงไม่ได้เริ่มคิดจาก instruction-level parallelism หรือการทำนาย branch ของ CPU ก่อนอยู่แล้ว มักจะมีส่วนสำคัญด้านประสิทธิภาพที่เขียนด้วยภาษาที่คอมไพล์และปรับแต่งได้ ภายในนั้นก็มี hot path ที่ควรดูละเอียด และข้างในอีกทีก็อาจมี hot loop อยู่หนึ่งหรือสองจุดที่คุ้มจะตรวจดูเรื่อง vectorization หรือความต่างของพฤติกรรมบน CPU รุ่นใหม่
      ต่อให้ใช้ LLM จุดที่ร้อนที่สุดด้านประสิทธิภาพก็ยังอาจคุ้มค่าที่จะตรวจด้วยตัวเองเป็นกรณีพิเศษ คุณอาจยอมรับคุณภาพที่ต่ำกว่าของผลลัพธ์อย่างตั้งใจ หรือใช้ LLM ทำ 70% แล้วแก้ที่เหลือ 30% ด้วยมือจนดีขึ้นเป็น 85:15 ได้ แต่บทความนี้ก็ยังถือว่าพูดถึง พื้นที่รายละเอียดระดับ top 1% อยู่ดี
    • ผมไม่ได้เขียน C++ ดังนั้นในแง่นั้นมันก็ไม่ใช่เรื่องที่ผมสนใจโดยตรงอยู่แล้ว แต่ก็ยังอ่านได้อย่างน่าสนใจ และคิดว่า อีก 2–3 ปีข้างหน้า เนื้อหาแบบนี้ก็น่าจะยังสนุกอยู่เหมือนเดิม