ฟังก์ชัน tolower() ที่ทำด้วย AVX-512

 (dotat.at)
1 คะแนน โดย GN⁺ 2024-07-30 | 1 ความคิดเห็น | แชร์ทาง WhatsApp
  • นี่คือการทดลองใช้ AVX-512-BW ประมวลผลครั้งละ 64 ไบต์ในการคัดลอกสตริงพร้อมแปลง ASCII ตัวพิมพ์ใหญ่เป็นตัวพิมพ์เล็ก เพื่อดึงประสิทธิภาพ SIMD ออกมาได้แม้กับสตริงขนาดเล็ก
  • แกนหลักของการทำงานคือการเปรียบเทียบว่าแต่ละไบต์อยู่ในช่วง 'A' ถึง 'Z' หรือไม่ จากนั้นใช้ การดำเนินการแบบมาสก์ที่บวกค่า 'a' - 'A' เฉพาะตำแหน่งนั้น
  • ส่วนท้ายที่เหลือของทั้งสตริงสั้นและสตริงยาวจัดการด้วย masked load/store เพื่อลดต้นทุนการจัดการชิ้นส่วนเล็ก ๆ ที่โค้ด SIMD มักเจอ
  • จากการวัดการคัดลอกขนาดราว 1MiB บน Clang 16, Debian 11 และ AMD Ryzen 9 7950X โดยใช้ชังก์ตั้งแต่ 1 ไบต์ถึง 1KiB พบว่า tolower64 อยู่ในกลุ่มที่ทำงานได้เร็วอย่างสม่ำเสมอเมื่อเทียบกับตัวอื่น
  • บน Zen 4 นั้น AVX-512-BW ดูเหมาะกับงานประมวลผลสตริงมาก แต่ยังไม่ได้ตรวจสอบ ARM SVE และ RISC-V Vector extension แบบละเอียดด้วยตัวเอง

สร้าง tolower() แบบ 64 ไบต์ด้วย AVX-512-BW

  • เป้าหมายคือการทำ เคอร์เนล tolower() แบบ SIMD ที่คัดลอกสตริงไปพร้อมกับแปลงอักขระ ASCII ตัวพิมพ์ใหญ่เป็นตัวพิมพ์เล็ก
  • AVX-512-BW เป็นส่วนขยายที่รองรับการคำนวณระดับไบต์และเวิร์ด ซึ่งใช้งานได้บนโปรเซสเซอร์ AMD Zen รุ่นใหม่
    • AVX-512 แบ่งเป็นหลายส่วนขยาย ทำให้สถานะการรองรับค่อนข้างซับซ้อน
    • ฝั่ง Intel ถูกมองว่าการรองรับนั้นไม่สม่ำเสมอเป็นพิเศษ
  • ARM SVE ก็มี masked load/store ระดับไบต์ ที่เหมาะกับงานประมวลผลสตริงเช่นกัน
    • ใช้งานได้บนคอร์ big-ARM Neoverse รุ่นใหม่ เช่น Amazon Graviton
    • แต่ใช้ไม่ได้บน Apple Silicon
  • RISC-V Vector extension ก็มีสไตล์ใกล้เคียงกับ ARM SVE และใช้งานได้บนคอมพิวเตอร์บอร์ดเดี่ยวขนาดเล็กหลายรุ่น

วิธีทำงานของ tolower64()

  • tolower64() เป็นเคอร์เนลที่อิง AVX-512 และประมวลผล 64 ไบต์ ต่อครั้ง
  • ขั้นแรกจะเติมค่าอ้างอิงลงในเวกเตอร์รีจิสเตอร์ที่บรรจุ 64 ไบต์
    • 'A'
    • 'Z'
    • 'a' - 'A'
  • จากนั้นนำเวกเตอร์อักขระอินพุต c ไปเปรียบเทียบกับ 'A' และ 'Z' เพื่อสร้างมาสก์ขนาด 64 บิตแต่ละตัว
    • ตำแหน่งที่ c >= 'A'
    • ตำแหน่งที่ c <= 'Z'
  • นำมาสก์ทั้งสองมารวมกันด้วย _kand_mask64() เพื่อสร้างมาสก์ is_upper ที่ระบุเฉพาะ ตำแหน่งตัวพิมพ์ใหญ่
  • ขั้นสุดท้ายใช้ _mm512_mask_add_epi8()
    • ไบต์ที่ is_upper เป็น false จะคงค่า c เดิมไว้
    • ไบต์ที่ is_upper เป็น true จะกลายเป็น c + ('a' - 'A')

การจัดการสตริงยาวและสตริงสั้น

  • สำหรับสตริงยาว ส่วนใหญ่จะประมวลผลด้วย vector load/store แบบไม่ต้องจัดแนว ตามปกติ
    • _mm512_loadu_epi8()
    • tolower64()
    • _mm512_storeu_epi8()
  • สำหรับสตริงสั้นและชิ้นส่วนท้ายที่เหลือของสตริงยาว จะใช้ masked unaligned load/store
  • มาสก์ถูกสร้างให้เปิดเฉพาะ len บิตด้านล่าง
    • uint64_t len_bits = (~0ULL) >> (64 - len)
    • นำขึ้นไปเป็น SIMD mask register ด้วย _cvtu64_mask64(len_bits)
  • _mm512_maskz_loadu_epi8() จะเติม 0 ลงในตำแหน่งของรีจิสเตอร์ปลายทางที่มาสก์ปิดอยู่
  • _mm512_mask_storeu_epi8() จะบันทึกเฉพาะตำแหน่งที่มาสก์เปิดอยู่
  • วิธีนี้คือหัวใจสำคัญที่ทำให้จัดการชิ้นส่วนสตริงขนาดเล็กได้รวดเร็ว

เงื่อนไขเบนช์มาร์กและตัวที่ใช้เปรียบเทียบ

  • เบนช์มาร์กรันบน Clang 16, Debian 11 และ AMD Ryzen 9 7950X
  • สิ่งที่วัดคือการคัดลอกข้อมูลราว 1MiB โดยเปลี่ยนความยาวของชังก์ตั้งแต่ 1 ไบต์ถึง 1KiB
  • เพื่อสะท้อนความต่างด้านการจัดแนวของสตริงต้นทางและปลายทาง จึงเว้นไม่กี่ไบต์ไว้ระหว่างสตริงแต่ละชุด ซึ่งไบต์เหล่านี้ไม่นับรวมในปริมาณการวัด 1MiB
  • เนื่องจาก Ryzen 9 7950X มี L2 cache ขนาด 1MiB ต่อคอร์ จึงคาดว่าแต่ละการทดสอบจะลามไปถึง L3 cache
  • แต่ละฟังก์ชันถูกคอมไพล์แยกกันเพื่อหลีกเลี่ยงผลรบกวนจากการ inline และการย้ายโค้ด
    • แต่ในโค้ดจริงมีแนวโน้มว่าจะส่งเสริมการ inline มากกว่าป้องกัน

ผลลัพธ์: ประสิทธิภาพที่ลื่นไหลของ tolower64

  • tolower64 สีชมพู โดยรวมแล้วอยู่ใกล้กลุ่ม ที่เร็วที่สุด ในบรรดาฟังก์ชันที่ทดสอบอย่างสม่ำเสมอ
    • เมื่อความยาวเป็น 65 ไบต์ จะตกลงเล็กน้อยจากการข้ามไปยังเวกเตอร์ตัวที่สอง
    • หลังจากนั้นก็ไต่ขึ้นอย่างรวดเร็วและไม่มีร่องประสิทธิภาพลึก ๆ แสดงว่า masked load/store มีประสิทธิภาพในการจัดการชิ้นส่วนสตริงสั้น
  • copybytes64 สีเขียว เป็น memcpy เวอร์ชันที่ใช้ AVX-512 ในลักษณะคล้ายกัน
    • ไม่ได้เร็วกว่่า tolower64 มากนัก
    • Clang รุ่นใหม่เข้าใจความหมายของฟังก์ชันนี้และเขียนใหม่ทั้งหมด จึงใช้ Clang 11 คอมไพล์
  • copybytes1 สีส้ม เป็น memcpy แบบไบต์ต่อไบต์
    • คอมไพล์ด้วย Clang 11
    • แสดงให้เห็นว่า heuristic สำหรับ auto-vectorization ของ Clang 11 ค่อนข้างไม่ดีนักกับชิ้นส่วนสตริงที่เล็กกว่า 256 ไบต์
  • tolower สีแดง เป็น baseline ที่เรียก tolower() มาตรฐานจาก <ctype.h> และช้ามาก
  • tolower1 สีม่วง เป็น tolower() แบบไบต์ต่อไบต์ที่คอมไพล์ด้วย Clang 16
    • auto-vectorization ของ Clang 16 ดีขึ้นมากเมื่อเทียบกับ Clang 11
    • แต่ก็ยังช้ากว่าเวอร์ชันที่เขียนด้วยมือ และสร้าง โค้ดที่ซับซ้อนกว่ามาก
    • การจัดการชิ้นส่วนสตริงสั้นยังไม่ดีเท่า tolower64 ทำให้กราฟประสิทธิภาพแกว่งเป็นยอดแหลม
  • tolower8 สีน้ำตาล เป็น SWAR tolower() จากบทความก่อนหน้า
    • Clang พยายามทำ auto-vectorization แต่ฟังก์ชันซับซ้อนเกินไปจนผลลัพธ์ไม่ดี
    • แม้คอมไพล์ด้วย Clang 16 ก็ยังเห็นหน้าผาประสิทธิภาพที่ 256 ไบต์แบบเดียวกับสไตล์ Clang 11
  • memcpy สีน้ำเงิน เรียกใช้ memcpy ของ glibc
    • ช่วงแรกทำได้เร็ว แต่มีบางช่วงที่ตกลงไปเหลือประมาณครึ่งหนึ่งของความเร็ว copybytes64
    • ยังไม่ทราบสาเหตุ

บทสรุปและโค้ด

  • AVX-512-BW เหมาะมากกับการจัดการสตริง โดยเฉพาะ สตริงสั้น
  • บน Zen 4 มันเร็วมาก และ intrinsic functions ก็ใช้งานค่อนข้างง่าย
  • จุดเด่นที่สุดคือ ประสิทธิภาพที่ลื่นไหล
    • แทบไม่เห็นร่องประสิทธิภาพที่เกิดจาก auto-vectorization สลับไปใช้โค้ดสเกลาร์เมื่อเจอชิ้นส่วนสตริงเล็ก ๆ
  • เนื่องจากไม่สามารถเข้าถึงอุปกรณ์ที่รองรับ ARM SVE หรือ RISC-V Vector extension ได้สะดวก จึงยังไม่ได้ศึกษาส่วนขยายทั้งสองนี้อย่างละเอียด
  • สามารถดูโค้ดได้ที่ git repository ของเว็บไซต์

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

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

 
GN⁺ 2024-07-30
ความคิดเห็นจาก Hacker News

  • ทริก “unsafe read beyond of death” นั้น แม้ฮาร์ดแวร์จะยอมให้ทำได้ แต่ในโมเดลหน่วยความจำของ Rust และ LLVM จะถือว่าเป็นพฤติกรรมที่ไม่ถูกกำหนดไว้
    เช่นเดียวกับพฤติกรรมที่ไม่ถูกกำหนดไว้อื่น ๆ คอมไพเลอร์อาจสมมติระหว่างการทำ optimization ได้ว่า “เรื่องแบบนั้นไม่เกิดขึ้น” จึงอาจทำให้เกิดผลลัพธ์ที่คาดไม่ถึง และถ้าจะเลี่ยงก็ต้องใช้อินไลน์แอสเซมบลี
    https://github.com/ogxd/gxhash/issues/82

    • ในกรณีแบบนี้ น่าจะดีถ้ามีทางเลือกที่ไม่ใช่แอสเซมบลี
      โหลดแบบ “อ่านค่าที่เกินขอบเขตการจัดสรรเป็นองค์ประกอบที่ไม่ระบุค่า และให้เป็นพฤติกรรมที่ไม่ถูกกำหนดไว้เฉพาะตอนที่ฮาร์ดแวร์รับไม่ได้” ดูเหมือนไม่น่าจะรองรับยากนัก และต่อให้ภายในเป็นเพียงชื่อเรียกอีกชื่อของการเรียกแอสเซมบลีดังกล่าวก็ยังเพียงพอ
      ถัดจากนั้นไปอีก ถ้าสามารถรับประกันได้ว่าหลังการจัดสรรทุกชนิด เช่น malloc, สแตก, ค่าคงที่ ฯลฯ จะมีแอดเดรสที่ไม่ก่อให้เกิด fault อย่างน้อยราว 64 ไบต์ ก็คงดี แต่เรื่องนี้ต้องอาศัยความร่วมมือจากหลายองค์ประกอบจึงซับซ้อนกว่ามาก
      ใน custom allocator นี่เป็นเรื่องเล็กน้อย แต่ในกรณีนั้นก็จะใช้โค้ด SIMD กับข้อมูลที่อยู่นอก custom heap ได้ยาก และยังต้องผูกติดกับความเป็นไปได้เล็กน้อยที่จะเกิด segfault
      sanitizer หรือ Valgrind ก็ยังมีประโยชน์อยู่ เพราะสามารถติดตามค่าที่ออกนอกขอบเขตในฐานะค่าที่ยังไม่กำหนด และแจ้งข้อผิดพลาดเมื่อมีการใช้งานจริงได้
    • ก็สงสัยว่าในระดับฮาร์ดแวร์มันจริงแค่ไหนเหมือนกัน
      อยากรู้ว่าถ้าอ่านจากเพจที่ไม่ได้แมปหรือหน่วยความจำที่ถูกป้องกันไว้จะเกิดอะไรขึ้น และยังไม่ได้ดูโค้ดจึงไม่รู้ว่าการรับประกันเรื่อง alignment ช่วยหลีกเลี่ยงจุดนี้ได้หรือไม่
    • คำอธิบายที่ว่า “ถ้าเป็นพฤติกรรมที่ไม่ถูกกำหนดไว้ คอมไพเลอร์ก็สามารถสมมติได้ว่าเรื่องนั้นจะไม่เกิดขึ้น” นั้นไม่ถูกต้อง
      พฤติกรรมที่ไม่ถูกกำหนดไว้เป็นคำศัพท์เฉพาะทางในมาตรฐาน C ดังนั้นการเหมารวมแบบนี้จึงดูแปลก และ ANSI C ก็ไม่ได้อนุญาตให้ตั้งสมมติฐานเช่นนั้นไว้อย่างชัดเจน ส่วน ISO C แม้จะเปิดกว้างกว่า แต่ก็ไม่ได้ให้เหตุผลรองรับสมมติฐานนี้อย่างเป็นรูปธรรม
      คำอธิบายแนว “UB = สมมติว่าเกิดขึ้นไม่ได้” นั้น สำหรับผมถือว่าใกล้เคียงกับการขู่ให้กลัวแบบไม่ค่อยซื่อตรงพอสมควร

  • พอเห็นโค้ดที่สะอาดและประสิทธิภาพดีในบทความนี้ ก็เริ่มสงสัยว่าการติดตั้งใช้งาน AVX512 ของ AMDกับ AVX10 ที่ Intel วางแผนไว้จะสู้กันอย่างไร
    ดูเหมือนแก่นหลักของ AVX10 จะอยู่ที่การแก้ปัญหาสถานการณ์ P-core/E-core ของ Intel ขณะที่ AMD เลือกแนวทางที่ดีกว่า คือใช้ทั้งการติดตั้งใช้งานแบบเต็มความกว้างใน Zen5 หรือแบบประมวลผล 256 บิต 2 รอบใน Zen4 และ Zen5 Mobile ตามความเหมาะสม โดยยังคง API ให้ลื่นไหล
    ผลการเพิ่มประสิทธิภาพครั้งใหญ่ในบทความนี้ก็มาจากคอร์ Zen4 ทั้งหมด และ AVX512 มีข้อดีมากมาย จึงน่าหงุดหงิดที่ Intel จำกัดมันมากเกินไปเพื่อแบ่งส่วนตลาด จนแทบปิดกั้นการนำไปใช้ในโค้ดไคลเอนต์ทั่วไปโดยปริยาย

    • ถ้า Intel ใส่ AVX10/256 ลงใน CPU ทุกรุ่นที่จะออกจากนี้จริง สุดท้ายก็คงชนะเพราะการเข้าถึงที่แพร่หลายกว่า
      ตลาดปฏิเสธแนวทางแยกเส้นทางโค้ดตาม CPU มาตลอด และในทางปฏิบัติ SIMD implementation ที่สำคัญก็มักยึดตัวหารร่วมต่ำสุด
      AVX10.1/256 กับ AVX512VL มีส่วนย่อยร่วมกัน ดังนั้นเมื่อเวลาผ่านไปนานพอจน CPU ส่วนใหญ่รองรับ ผู้คนก็น่าจะหันไปเจาะจงส่วนย่อยนั้น
      AMD คงยังเก็บชัยชนะแบบง่าย ๆ ได้ต่อไปในแอป benchmark บางตัวที่อัปเดตรองรับ AVX512 แล้ว แต่ถ้า Intel ยังเดินตามแผน AVX10 ต่อ AMD เองก็น่าจะลงเอยด้วยการใช้ SIMD pipeline แบบประมวลผล 2 รอบอย่างเต็มรูปแบบ เพื่อรองรับ AVX10/256 ได้อย่างมีประสิทธิภาพ โดยยังคงความเข้ากันได้กับ AVX512
      Intel ตัดสินใจพลาดมามากในสิบปีที่ผ่านมา แต่การแบ่งตลาดด้วย instruction set น่าจะเป็นหนึ่งในการตัดสินใจที่แย่ที่สุด เท่ากับเป็นการทำลายแรงส่งและความสนใจต่อการพัฒนาสมัยใหม่ด้วยตัวเอง และสิ่งที่สำคัญกว่าความกว้างจริง ๆ ก็คือฟีเจอร์อย่างการทำงานกับ mask ดังนั้นหวังว่าจะใส่ AVX10/256 ลงมาทั้งไลน์ผลิตภัณฑ์
    • การติดตั้งใช้งาน AVX512 ของ Zen 4 ไม่ใช่แบบประมวลผล 2 รอบ (double-pumped) และนักข่าวสายเทคนิคก็ควรเลิกเรียกแบบนั้นได้แล้ว
      คำนี้มีความหมายเฉพาะ แต่ไม่ตรงกับการทำงานจริง
      Zen 4 เพียงแค่ดีโค้ดการทำงานของ ZMM register ออกเป็นหลาย micro-op แล้วจัดตารางไปยังหน่วย 256 บิตที่ว่างอยู่ ส่วน shuffle แบบเต็มความกว้าง 512 บิตก็ใช้ฮาร์ดแวร์เฉพาะจัดการเป็นกรณีพิเศษเพื่อหลีกเลี่ยงการจำลองที่มีต้นทุนสูง
      เพราะอย่างนั้น Zen 4 ที่มีหน่วย SIMD 256 บิต 4 หน่วยจึงทำงานได้ราวกับเป็นคอร์ 2×512 บิตที่ทรงพลัง และการติดตั้งใช้งานนี้ก็ไม่ได้เป็นวิธีราคาถูกเลย แถมอาจเป็นรูปแบบที่ดีที่สุดในฮาร์ดแวร์ฝั่งผู้บริโภคจนถึงตอนนี้ด้วยซ้ำ
    • ไม่เข้าใจว่าทำไม Intel ถึงไม่แก้ปัญหานี้ด้วยการใส่ AVX512 แบบประมวลผล 2 รอบ ลงใน E-core หรือไม่ก็ทำ CPU เดสก์ท็อปที่มีแต่ P-core อย่างที่ควรจะเป็นตั้งแต่แรก
      พวกเขามีเวลาจะแก้เรื่องนี้มาหลายปีแล้ว และแม้ AMD จะรองรับ แต่ก็ยังไม่ได้รับการยอมรับเพราะส่วนแบ่งตลาด ซึ่งน่ารำคาญมาก ส่วน AVX10 ก็น่าเสียดายที่ดูจะทำให้ Intel ยื้อโลกนี้ไว้ได้นานขึ้น
      สำหรับเดสก์ท็อป ผมอยากเห็นคอร์ที่ดีกว่า จำนวนคอร์ที่มากกว่า และ instruction set ที่กำหนดมาตรฐานมาดี เปิดใช้ฟีเจอร์ที่มีประโยชน์อย่าง SIMD ที่กว้างขึ้น, float16, gather/scatter และ AMD ก็กำลังทำได้ค่อนข้างดี
      ในทางกลับกัน Intel กลับเอาคอร์อ่อนมาแปะข้างคอร์ที่พอใช้ได้ แล้วก็จำกัดคอร์ที่พอใช้ได้นั้นให้ต้องเข้ากับคอร์อ่อน ออก CPU ที่มีจำนวนคอร์เท่าเดิมอยู่หลายเจเนอเรชัน ทำให้ดูเหมือนมีคอร์มากด้วยการเติมคอร์อ่อนเข้ามา ออก instruction set ย่อยมากมายจนแทบสร้างชุดร่วมที่มีประโยชน์ได้ยาก และยังทิ้งการรองรับคำสั่งที่ตัวเองเคยทำเหมือนให้สัญญาไว้
      ความนิยมของผู้ประกอบเครื่องเดสก์ท็อปคือ Intel ในยุค 90, AMD ช่วงต้นยุค 2000, Intel อีกครั้งในช่วงปลายยุค 2000 และทศวรรษ 2010 ส่วนตอนนี้กลับมาเป็น AMD แล้ว สงสัยว่า Intel จะทำอะไรเพื่อสร้างฐานกลับคืนมานอกจากคอยขัดขาคู่แข่ง และการแข่งขันก็ควรดำเนินต่อไปเพื่อไม่ให้อีกฝ่ายสบายเกินไป

  • เอกสารที่อ่านเล่นได้สนุก: http://www.unicode.org/Public/3.1-Update1/CaseFolding-4.txt

    • ยังมีเรื่องแบบนี้ด้วย: ถ้าแปลง ß ของภาษาเยอรมัน เป็นตัวพิมพ์ใหญ่ ความยาวของสตริงจะเปลี่ยน
      ตัวอย่างเช่น "straße".upper() จะกลายเป็น 'STRASSE'
      อีกทั้งถ้าไม่กำหนด locale เวลาแปลง i ไม่มีจุดของกลุ่มภาษาตุรกีไปกลับระหว่างตัวพิมพ์ใหญ่/เล็ก 'ı'.upper().lower() จะกลายเป็น 'i' ทำให้เพี้ยน
    • โชคดีที่โค้ดนี้มาจากงาน DNS จึงเป็นแบบ ASCII เท่านั้น และไม่ต้องรับมือกับความซับซ้อนพวกนั้น
      มีโปรโตคอลที่ไม่แยกตัวพิมพ์ใหญ่เล็กแบบ ASCII อยู่หลายตัว และมักเจอบ่อยใน hot path ของเซิร์ฟเวอร์จำนวนมาก
    • สตริงที่ใช้ภายในเหมือน ID กับข้อความที่มนุษย์ป้อนนั้นต่างกัน
      แบบแรกมักใช้ pure ASCII ในการเข้ารหัส 8 บิตก็พอ แต่แบบหลังจะซับซ้อนขึ้น
      ที่อยู่ DNS เป็นตัวอย่างง่าย ๆ ซึ่งในทางเทคนิคเก็บ Unicode ได้แทบทั้งหมด แต่ตอน resolve DNS จริงจะถูกแปลงเป็น subset ของ ASCII ที่จำกัดมาก และกระบวนการ resolve นั้นไม่แยกตัวพิมพ์ใหญ่เล็ก
      แน่นอนว่าก็มีภาษาโปรแกรมที่รองรับระบบอักขระทั้งหมดของ Unicode แต่ยังมี identifier ที่ไม่แยกตัวพิมพ์ใหญ่เล็กด้วย ถ้าคุณกำลังจัดการของแบบนั้นอยู่ ก็ขอแสดงความเสียใจด้วย
    • สำหรับตัวอย่างที่ maße กลายเป็น MASSE นั้น ภาษาเยอรมันก็มี Eszett ตัวพิมพ์ใหญ่คือ ẞ ด้วย
      แม้จะยังไม่แพร่หลายมากและมีฟอนต์ที่รองรับไม่มากนัก แต่ในทางทฤษฎีตอนนี้มันมีอยู่แล้ว

  • รู้สึกว่าคำอธิบายเรื่อง “การบวก mask” ในบทความอาจจะผิดหรือเปล่า
    น่าจะต้องบวกตอน is_upper เป็น false และคัดลอกเดิมไว้ตอนเป็น true หรือไม่

    • อ้อ เพิ่งมารู้ทีหลังว่าชื่อตัวแปร to_upper กลับด้าน ควรเรียกว่า to_lower มากกว่า
      ขอบคุณที่ชี้จุดที่ทำให้งง ตอนนี้แก้ทั้งบทความและโค้ดแล้ว
    • การทำงานนี้คือ tolower
      ตัวพิมพ์ใหญ่ A คือ 0x40 และตัวพิมพ์เล็กคือ 0x60 ดังนั้นการ บวก 0x20 ต้องเกิดตอน is_upper เป็น true

  • การปรับแต่งแบบ SWAR นี้มักมีประโยชน์เฉพาะเมื่อสตริงถูกจัดแนวกับแอดเดรส 8 ไบต์
    ถ้านำอัลกอริทึม SWAR ไปใช้กับสตริงที่ไม่จัดแนว ก็มักจะช้ากว่าอัลกอริทึมเดิม
    ถ้าแยกเป็น 3 ขั้นตอนคือ จัดการช่วงต้นจนถึงแอดเดรสที่จัดแนว, จัดการส่วนเนื้อหาที่จัดแนวแล้ว, และจัดการส่วนท้ายที่สั้นกว่า 8 ไบต์ จำนวนคำสั่งจะยิ่งเพิ่มขึ้น
    มีกรณีคล้ายกันพร้อมเบนช์มาร์กเกี่ยวกับคำกล่าวที่ผิดว่า utf8.IsValid ใน Go เร็วกว่าอยู่ที่นี่: https://github.com/sugawarayuuta/charcoal/pull/1

    • การทำงาน SIMD แบบ mask ของ AVX-512 และ ARM SVE ออกมาเพื่อแก้ปัญหานั้น
      งานด้านหน่วยความจำยังคงทำแบบจัดแนวและใช้ขนาดเวกเตอร์เต็มเสมอ แต่สามารถใส่ mask เฉพาะ element ที่ใช้ได้จริง
      ต่อให้การทำงานหน่วยความจำของเวกเตอร์แบบ masked จะไม่จัดแนว หรือคร่อมหน้าเพจที่ไม่ได้แมปหรือถูกป้องกันไว้ หาก lane นั้นถูกปิดด้วย mask ก็จะไม่เกิด fault
      ยังมีคำสั่ง load พิเศษที่ลดความยาวเวกเตอร์ลงจนถึงก่อน element แรกที่จะทำให้เกิด fault สำหรับงานอย่าง strlen() ที่ไม่รู้ความยาวล่วงหน้าด้วย

  • การบวกแบบมาสก์ดูเท่มาก คงจะดีถ้าใน .NET intrinsic สามารถจัดการมาสก์รีจิสเตอร์ของ AVX512 ได้โดยตรง แต่ตอนนี้ต้องพึ่ง “รูปแบบสำนวนที่คอมไพเลอร์รู้จัก”
    ถ้าวิเคราะห์ลูปแกนหลักที่ผู้เขียนทำไว้ด้วย uiCA(CQA/MAQAO) โดยอิง Ice Lake จะได้ประมาณ 32B/cycle และถ้าคิดเป็น 3GHz ก็จะได้เกือบ 96GiB/s หากสมมติว่าไม่มีคอขวดด้านหน่วยความจำ แน่นอนว่าสำหรับอัลกอริทึมแบบนี้ การเข้าถึงหน่วยความจำคือคอขวดเสมอ
    แต่ก็ดูเหมือนยังไม่ใกล้เคียงการใช้ประโยชน์ได้เต็มที่นัก และถ้าใช้ Clang ก็จะได้ผลการ unroll ที่คลี่ออกได้ดีกว่าและมีการเลือกคำสั่งที่ดีกว่า จนไปถึง 42.67B/cycle แม้ L2 cache ก็น่าจะรักษา throughput ระดับนั้นได้ยาก แต่ก็น่าสนใจที่การแปลงตัวพิมพ์เล็ก/ใหญ่ของสตริงความยาวปานกลางจบลงในเวลาพอๆ กับที่แสงจากหน้าจอไปถึงกระจกตา
    เมื่อไม่กี่เดือนก่อนผมเคยทำการแปลงตัวพิมพ์ใหญ่/เล็ก ASCII ภายใน UTF-8 แบบคล้ายกันด้วย C#: https://github.com/U8String/U8String/blob/main/Sources/U8Str...
    เพราะสตริงสั้นครองโค้ดเบสส่วนใหญ่ การแปลงแบบ unroll สำหรับกรณีที่สั้นกว่าความยาวเวกเตอร์จึงสำคัญ และ switch จะถูกคอมไพล์เป็น jump table กับ branchless fall-through
    ตอนนี้ใช้แค่ 256 บิต เพราะในกรณีอย่าง Zen 3 หรือ 4 ที่มีเพียง SIMD unit แบบ 256×4 ก็อิ่มตัวอยู่แล้ว มีตัวอย่างเปรียบเทียบกับเวอร์ชัน C แบบวางคู่กันอยู่ที่นี่: https://godbolt.org/z/eTGYhTPan
    บน AVX512 ดูเหมือนว่าน่าจะเปลี่ยนคำสั่ง 3 ตัวด้วย vpternlogd ได้ และตอนที่ยังใช้ฮาร์ดแวร์ AVX512 ได้ .NET ก็เคย optimize แบบนั้นด้วยความกว้าง 256 บิต + AVX512VL แต่ตอนนี้แปลกตรงที่ทำซ้ำด้วยความกว้าง 512 บิตไม่ได้
    น่าจะเห็นความพยายาม SWAR ที่ล้มเหลวฝั่ง switch dispatch ด้วย อยากรู้ว่าไลเซนส์ของบทความนี้เป็นแบบไหน ถ้าผ่าน test suite ก็อยากหยิบไปใช้

    • Clang กับ GCC จัดการ intrinsic คนละแบบ และโดยเฉพาะกับคำสั่ง AVX-512 นั้น Clang มีแนวโน้มมากกว่า GCC ที่จะหลุดจาก opcode และอัลกอริทึมที่ Intel guide ระบุไว้
      ถ้ามองจากโครงสร้างของคอมไพเลอร์ทั้งสองก็พอเข้าใจได้ แต่บางครั้งผลลัพธ์ก็ดีขึ้น บางครั้งก็แย่ลง
      หลายปีก่อนผมเคยทำโปรเจกต์ที่ vectorize หนักมากและต้องคอมไพล์ได้ทั้งสองตัว สุดท้ายเลยต้องเก็บ inline assembly สำหรับเป้าหมายเฉพาะพร้อมกับเวอร์ชันอ้างอิง C และไฟล์ .S ไว้ในรีโพซิทอรี
      Makefile ก็เละขึ้น แถมต้องใส่ benchmark เข้าไปใน test suite ด้วย ทำให้ภาระการดูแลรักษาสูงมาก เลยสรุปว่าการใช้ intrinsic เป็นเครื่องมือระดับล่างที่ดีกว่า auto-vectorization นั้นต้องทำอย่างระมัดระวังมาก
      ตัวอย่าง: ที่ https://godbolt.org/z/T4Pjhrz5d output ของ GCC เป็นไปตามคาด แต่ output ของ Clang น่าตกใจและช้ากว่าจริง พอจับรันในลูป ตาม uiCA แล้ว GCC ใช้ 4 cycle เทียบกับ 7 cycle และยังเห็นได้จาก benchmark ของแอปจริงที่ฟังก์ชันนี้ถูกรันหลายพันล้านครั้งในอัลกอริทึม brute-force
      พอลองไปดูในโค้ดเบสของ LLVM ก็จำได้ว่าเคยเห็นปัญหาว่า Clang 16 อาจปล่อยคำสั่ง mask AVX-512 บางตัวออกมาไม่ได้เลยเพราะ internal refactoring
    • การวิเคราะห์มีประโยชน์มาก
      ไม่ได้ตั้งเป้าหมายจะรีดประสิทธิภาพสูงสุดตั้งแต่แรก ตอนแรกแค่อยากดูว่ามันทำงานได้ไหม แต่กลายเป็นว่าความพยายามครั้งแรกออกมาดีเกินคาดเป็นโบนัส
      สิ่งที่สนใจหลักคือ สตริงที่สั้นกว่าเวกเตอร์รีจิสเตอร์ และการกำจัดร่องต่ำในกราฟ throughput
      ถ้าตามลิงก์โค้ดท้ายบล็อกโพสต์ไปจะมีข้อมูลไลเซนส์อยู่ โดยยกเว้นส่วน MPL-2.0 ที่เดิมเขียนไว้สำหรับ BIND แล้ว ส่วนที่เหลือเป็น 0BSD หรือ MIT-0
    • ดูจากก้อนแอสเซมบลีใหญ่ๆ อย่างเดียวอาจไม่ชัด แต่ Clang เขียน (x >= 'a' && x <= 'z') ใหม่เป็น รูปแบบ (x - 'a') < ... เพื่อลดคำสั่งลงหนึ่งตัว
      บางครั้งยังลดได้ถึงขั้นไม่ต้องโหลดรีจิสเตอร์ด้วยเพราะการเข้ารหัส opcode ที่แปลกๆ

  • ไม่รู้ว่า swar คืออะไร

    • เป็นตัวย่อของ “SIMD Within A Register”
      ปกติหมายถึงเทคนิคที่ pack หลายรายการไว้ในรีจิสเตอร์เดียว แล้วใช้งานให้คล้าย SIMD โดยไม่ต้องมีคำสั่ง SIMD แบบ explicit
      ตัวอย่างเช่น ถ้าใส่เลข 31 บิตกับ 32 บิตไว้ในรีจิสเตอร์ 64 บิตและเหลือ 1 บิตไว้สำหรับ carry คุณก็ทำการบวกสองครั้งได้ด้วยการบวก 64 บิตครั้งเดียว
      ในวงการเกมก็ใช้ทริกแบบนี้กับกราฟิกมานานแล้ว โดย pack ค่า RGB(A) ไว้ในจำนวนเต็ม 32 บิต และใน ScummVM ก็มีโค้ดที่อินเตอร์โพเลตพิกเซล RGB 16 บิต 2 พิกเซล รวมทั้งหมด 6 คอมโพเนนต์ภายในค่า 32 บิต: https://github.com/scummvm/scummvm/blob/master/graphics/scal...
    • แปลว่า SIMD ภายในรีจิสเตอร์

  • หลังจาก Unicode ปรากฏขึ้น แนวคิดเรื่องตัวพิมพ์ใหญ่และตัวพิมพ์เล็กก็กลายเป็นบึงโคลนไปแล้ว
    ถ้าจะทำให้ถูกต้องจริงๆ ต้องใช้ข้อมูลจำนวนมาก
    ถ้าคุณกำลังทำงานที่การเสร็จทันเวลาขึ้นอยู่กับความเร็วในการรัน ASCII tolower ก็ควรเปลี่ยนเกมและเปลี่ยนสมมติฐานไปเลยดีกว่า

  • เมื่อก่อนผมเคยใส่ขอบสีดำรอบภาพเพื่อหลีกเลี่ยงปัญหาการอ่านเลยบัฟเฟอร์ของ SIMD แบบหมดจด
    มันทำงานได้ดีมาก และในแง่ความเร็วก็เอาชนะ implementation บางตัวของ OpenCV ได้ แต่ก็ใช่ว่าจะควบคุมอินพุตได้สมบูรณ์แบบแบบนั้นเสมอไป

  • สงสัยว่าเคยลองทำแบบนี้ไหม ผลของ auto-vectorization ดูค่อนข้างสะอาดทีเดียว
    https://godbolt.org/z/1c5joKK5n

    • อันนั้นโดยพื้นฐานก็เหมือน tolower1 ดู bullet ด้านล่างของกราฟได้