เร็วกว่า C {n} เท่า

 (owen.cafe)
1 คะแนน โดย GN⁺ 2023-07-07 | 1 ความคิดเห็น | แชร์ทาง WhatsApp
  • แม้จะเป็นลูป C ขนาดเล็ก ผลลัพธ์จากคอมไพเลอร์ก็ไม่ได้ดีที่สุดเสมอไป และจากการปรับแต่งแอสเซมบลี x86_64 ด้วยมือ พบว่าเวอร์ชันที่ ตัด conditional branch ออก เร็วกว่าผลลัพธ์ของ clang 6.73 เท่า
  • ฟังก์ชันเป้าหมายประมวลผลสตริงโดยให้ 's' เป็น +1, 'p' เป็น -1, และ '\0' เป็นจุดสิ้นสุด โดยผลลัพธ์จาก clang 16 แบ่ง flow นี้ออกเป็น conditional branch 3 จุด
  • หลังจากเปลี่ยนลำดับ branch, จัดวาง basic block ใหม่ และแทน jump ด้วย arithmetic เวลาในการรันลดลงจาก 3.23 วินาทีเหลือ 2.87 วินาที และในขั้นนี้ทำความเร็วได้เท่ากับ GCC 12
  • เวอร์ชันที่เร็วที่สุดใช้ cmove เพื่อเลือกค่าที่จะบวกต่ออักขระเป็น 0, 1 หรือ -1 แล้วทำ add เสมอ ได้ผลที่ 0.48 วินาที และ throughput 1.94GiB/s
  • benchmark ทำบน AMD Ryzen 5 5625U และ Linux 6.1.33 โดยประมวลผลลิสต์อักขระสุ่ม 'p'/'s' จำนวน 1 ล้านตัว 1000 รอบ และใช้ผลลัพธ์ที่ดีที่สุดจากการรันหลายครั้ง

ฟังก์ชันทดลองและผลลัพธ์จากคอมไพเลอร์

  • ฟังก์ชันเป้าหมายเพิ่มตัวชี้สตริงทีละตัว และอัปเดตจำนวนเต็ม res ตามอักขระ
    • 's': res += 1
    • 'p': res -= 1
    • '\0': คืนค่า res
    • อักขระอื่น: ไม่เปลี่ยนแปลง
  • เริ่มต้นจากความคาดหวังว่า เนื่องจากฟังก์ชันมีขนาดเล็ก gcc หรือ clang น่าจะปรับให้เหมาะสมได้ค่อนข้างดี หรืออาจถึงขั้นดีที่สุด
  • แอสเซมบลีเริ่มต้นที่ clang สร้าง แบ่งกรณีทั้งสี่ออกเป็น conditional branch 3 จุด (je, je, jne)
    • เริ่มด้วย res = 0
    • อ่านอักขระแล้วตรวจสอบก่อนว่าเป็น '\0' หรือไม่
    • จากนั้นค่อยเปรียบเทียบกับ 'p', 's'
  • ผลลัพธ์เริ่มต้นของ clang
    • เวลาในการรัน: 3.23 วินาที
    • throughput: 295.26MiB/s
  • GCC สร้างโค้ดมากกว่าเล็กน้อย แต่เร็วกว่าเล็กน้อย

ตรวจสอบอักขระที่พบบ่อยก่อนเงื่อนไขสิ้นสุดที่พบได้น้อย

  • ลูปจะจบก็ต่อเมื่อเจออักขระ null terminator '\0' และในฟังก์ชันนี้ null terminator จะปรากฏได้มากที่สุดเพียงครั้งเดียว
  • ผลลัพธ์จาก clang ตรวจสอบ '\0' เป็นอย่างแรก ทำให้ทุกครั้งที่เจออักขระ 'p' และ 's' ต้องตรวจสอบเงื่อนไขสิ้นสุดก่อน
  • การแก้ด้วยมือครั้งแรกคือเปลี่ยนลำดับการเปรียบเทียบให้ ตรวจสอบ 'p' และ 's' ก่อน
  • ผลลัพธ์
    • เวลาในการรัน: 3.10 วินาที
    • ความเร็วเพิ่มขึ้น: 1.04 เท่า
    • throughput: 307.64MiB/s

จัดวาง basic block ใหม่และลด jump

  • กรณีที่พบบ่อยทั้งสองคือ 'p' และ 's' ต่างก็ jump กลับไปที่จุดเริ่มลูป ดังนั้นสามารถลด branch ได้ด้วยการวางบล็อกหนึ่งไว้เหนือลูป
  • หากวางบล็อก 's' ไว้ก่อนลูปทันที หลังประมวลผล 's' แล้วจะไหลเข้าสู่ลูปได้โดยไม่ต้องมี jump แยก
  • แต่แลกกับการต้อง jump เข้าลูปหนึ่งครั้งตอนเริ่มฟังก์ชัน เพื่อข้ามบล็อก 's'
    • jump ตอนเริ่มฟังก์ชันเกิดขึ้นเพียงครั้งเดียว
    • ส่วนอักขระ 's' อาจพบหลายครั้ง จึงถือเป็น trade-off ที่ยอมรับได้
  • ผลลัพธ์
    • เวลาในการรัน: 2.98 วินาที
    • ความเร็วเพิ่มขึ้นโดยรวม: 1.08 เท่า
    • throughput: 320.02MiB/s

ใช้ arithmetic เพื่อตัด unconditional jump หนึ่งจุด

  • ใช้ arithmetic เพื่อลบ unconditional jmp ที่กลับไปลูปในบล็อก p:
  • การลดค่า 1 ครั้งสามารถให้ผลเดียวกันได้ด้วย sub eax, 2 แล้วตามด้วย inc eax จึงทำให้หลังประมวลผล 'p' แล้วไหลต่อไปยังบล็อก 's'
  • วิธีนี้ตัด คำสั่ง branch ออกไปได้อีกหนึ่งจุด
  • ผลลัพธ์
    • เวลาในการรัน: 2.87 วินาที
    • ความเร็วเพิ่มขึ้นโดยรวม: 1.12 เท่า
    • throughput: 332.29MiB/s
  • ประสิทธิภาพ ณ จุดนี้เท่ากับโค้ดที่ GCC 12 สร้าง
    • โค้ด GCC 12 ก็รันใน 2.87 วินาที
    • เวอร์ชันเขียนด้วยมือมี 13 คำสั่ง
    • ผลลัพธ์จาก GCC มี 19 คำสั่ง
    • โค้ด GCC ดูเหมือนจะ unroll ลูปและนำ case block บางส่วนกลับมาใช้ซ้ำ

แทน conditional branch ด้วย cmove

  • หาก conditional branch เป็นคอขวด ก็สามารถตัด conditional branch เองออกได้โดยไม่ต้องพึ่ง branch predictor
  • เวอร์ชันที่เร็วที่สุดใช้ cmove หรือ conditional move เมื่อเท่ากัน
  • กฎการทำงานเรียบง่าย
    • ค่าเริ่มต้นคือ 0
    • ถ้าอักขระปัจจุบันเป็น 's' ให้เป็น 1
    • ถ้าอักขระปัจจุบันเป็น 'p' ให้เป็น -1
    • ในแต่ละรอบ ให้นำค่าที่เลือกได้ไปบวกกับ res เสมอ
  • วิธีนี้ตัดลูกศรจำนวนมากออกจาก control flow graph
  • ผลลัพธ์
    • เวลาในการรัน: 0.48 วินาที
    • ความเร็วเพิ่มขึ้นโดยรวม: 6.73 เท่า
    • throughput: 1.94GiB/s
  • ในแอสเซมบลีของลูป C แบบแน่นที่เขียนเอง การปรับแต่งที่คอมไพเลอร์ไม่ได้ทำอัตโนมัติสามารถเพิ่มความเร็วได้ในระดับ 6 เท่า

ความพยายามประหยัด register และการทดลองเพิ่มเติมที่ไม่สำเร็จ

  • ยังได้ลองเวอร์ชันที่ใช้ sete ของ x86_64 เพื่อตั้งค่า register ขนาด 1 ไบต์เป็น 0 หรือ 1 แบบมีเงื่อนไข
  • เวอร์ชันนี้ตัดการใช้ r8d ออก แต่ช้ากว่าเวอร์ชันที่ใช้เฉพาะ cmov
  • ผลลัพธ์
    • เวลาในการรัน: 0.51 วินาที
    • ความเร็วเพิ่มขึ้นโดยรวม: 6.33 เท่า
    • throughput: 1.83GiB/s
  • การใช้ register น้อยลง หรือใช้การคำนวณ 8 บิตแทน 32 บิต ไม่ได้ทำให้เร็วขึ้น
  • การทดลองเพิ่มเติมก็ทำให้ประสิทธิภาพลดลงเช่นกัน
    • unroll ลูปของเวอร์ชันที่ดีที่สุด: ช้าลง
    • จัดตำแหน่งจุดเริ่มลูปให้อยู่บนขอบเขต 16 ไบต์: ช้าลง
    • ใน GNU assembler หากใส่ .align <bytes> ไว้หน้าป้ายกำกับ จะสามารถแทรก nop ได้

สภาพแวดล้อม benchmark และโค้ด

  • รายการโค้ดอยู่บน GitHub
  • สภาพแวดล้อม benchmark
    • OS: Linux 6.1.33
    • CPU: AMD Ryzen 5 5625U with Radeon Graphics
    • CPU family 25, 6 คอร์, 2 เธรดต่อคอร์, 1 ซ็อกเก็ต
    • clang: 16.0.1
    • gcc: 12.2.0
  • เวอร์ชัน C ถูกคอมไพล์ด้วย -march=native เพื่อให้สร้างโค้ดที่เหมาะกับ CPU เฉพาะได้
  • benchmark ใช้ลิสต์อักขระ 1 ล้านตัวที่ประกอบด้วย 'p' และ 's' แบบสุ่ม
    • ฟังก์ชันแต่ละเวอร์ชันประมวลผลลิสต์นี้ 1000 รอบ
    • แต่ละเวอร์ชันถูกรันหลายครั้ง แล้วเลือกผลลัพธ์ที่ดีที่สุด
  • มีบทความต่อเนื่องลิงก์ไปยัง part two

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

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

 
GN⁺ 2023-07-07
ความเห็นจาก Hacker News

  • ข้อสรุปที่ถูกต้องไม่ใช่ แอสเซมบลีเขียนมือเร็วกกว่า C 6 เท่า แต่ใกล้เคียงกับ การกระโดดคำสั่งอาจช้ากว่าการคำนวณแบบมีเงื่อนไขมาก มากกว่า
    ใน C เอง ถ้าไม่ใช้ switch แล้วจัดการด้วย if แค่หนึ่งหรือสองอัน ก็ให้ผลแบบเดียวกันได้ง่าย ๆ พอเปลี่ยนฟังก์ชัน C ให้เป็น ถ้า s ก็เพิ่ม, ถ้า p ก็ลด, ถ้า \0 ก็จบ เร็วขึ้น 5.5 เท่า และในการรันตัวอย่างลดจาก 3.58 วินาทีเหลือ 0.65 วินาที

    • ดีเลย ภาค 2 เขียน C ใหม่แล้วได้ เร็วขึ้น 12 เท่า: https://owen.cafe/posts/the-same-speed-as-c/
      อย่างที่คนอื่นพูดกัน หลังจากปรับอินพุตแล้วก็ยังสามารถทำอัลกอริทึมให้เป็นเวกเตอร์ได้ด้วย ฉันมองนี่เป็นแบบฝึกหัดเชิงการสอน และหวังจริง ๆ ว่าคนจะไม่ไล่ลงไปเขียนแอสเซมบลีโดยไม่มีเหตุผลที่ดีพอ
    • คำว่า การกระโดดช้ากว่าการคำนวณแบบมีเงื่อนไข จะจริงเมื่อการกระโดดนั้นคาดเดาไม่ได้ ถ้าการกระโดดคาดเดาได้ การกระโดดจะเร็วกว่า
      Linus ก็เคยเขียนยาวไว้ก่อนหน้านี้เหมือนกันว่า cmov ไม่ค่อยมีประโยชน์กับ branch ที่คาดเดาได้: https://yarchive.net/comp/linux/cmov.html
    • สงสัยว่าใช้ GCC เวอร์ชัน อะไร ทั้งบน Ubuntu และ Windows ได้ประสิทธิภาพเท่ากัน และบน gcc (Ubuntu 9.4.0-1ubuntu1~20.04.1) 9.4.0 ทั้ง lone กับ ltwo ใช้เวลาประมาณ 3.58 วินาทีเท่ากัน
    • สงสัยว่าการเปลี่ยน switch เป็น if หลายอันจะเร็วกว่าตลอดไหม และตั้งแต่จำนวนกรณีประมาณไหน switch จะเริ่มเร็วกว่า ถ้ามันสม่ำเสมอ ก็น่าจะเป็นเรื่องที่ควรเข้าไปอยู่ใน compiler optimization
    • รู้สึกว่าคอมไพเลอร์เองก็น่าจะทำการแปลงระดับนี้ได้ไม่ใช่หรือ

  • มองว่าโค้ดเดิมไม่ได้เขียนมาให้เป็นมิตรกับคอมไพเลอร์เท่าไร ถ้าเขียนแบบ result += *s == 's'; result -= *s == 'p'; คอมไพเลอร์จะสร้าง โค้ด sete/cmov แบบไร้ branch ที่เหมาะสมให้ และความเร็วจะออกมาแทบเท่ากับแอสเซมบลีที่ปรับแต่งในบทความ
    แต่ก็ยังไม่ทำ loop unrolling หรือ vectorization ถ้าส่งขนาดสตริงแยกเข้ามาแล้ววนโดยรู้ size คอมไพเลอร์จะรู้ขนาดลูป จึง unroll ได้ และถ้าเป็นไปได้ก็จะใช้คำสั่ง AVX-512 ด้วย สำหรับอินพุตใหญ่จะเร็วกว่ามาก แต่ขี้เกียจทำ benchmark เอง ถ้าเป็นโปรแกรมเมอร์ C ที่ไม่ติดตามความยาวสตริงก็เชิญตามสบาย แต่ฉันว่าไม่ควรทำแบบนั้นจริง ๆ: https://godbolt.org/z/rde51zMd8

    • เวอร์ชันที่เป็นมิตรกับคอมไพเลอร์มีอยู่ในภาค 2: https://owen.cafe/posts/the-same-speed-as-c/
      เวอร์ชันนั้นทำได้ 3.88GiB/s ตั้งใจไม่พาไปถึงขั้น vectorization เพื่อให้ขอบเขตปัญหายังเล็ก และอยากโชว์ทิปกับลูกเล่นแอสเซมบลีในบทความ ยังพอมีช่องให้เขียนต่อภายหลังเรื่อง padding สตริงอินพุตและทำอัลกอริทึมให้เป็นเวกเตอร์
    • ในโค้ดขาดไปหนึ่งบรรทัดสำคัญ: /* DON’T REFACTOR THIS FOR READABILITY IT WILL SLOW DOWN */
    • ใน Nim ก็ดูเหมือนจะกระตุ้นได้เหมือนกันถ้าทำแบบนี้: เปิด {.overflowChecks:off.} แล้ววน input โดยถ้า 's' == c ก็เพิ่ม ถ้า 'p' == c ก็ลด
      บน Apple M1 เร็วขึ้นประมาณ 5 เท่า และถ้าเปิดตรวจ overflow ไว้ ความเร็วจะมากกว่าเวอร์ชัน C พื้นฐานได้แค่ราว 2 เท่าเท่านั้น การรู้แพตเทิร์นที่ดีสำหรับชักนำ SIMD optimization ไว้ก็มีประโยชน์เสมอ
    • ที่บอกว่า “ไม่ควรทำแบบนั้นจริง ๆ” หมายถึงไม่ควรละเลยการติดตามความยาวสตริงใช่ไหม?

  • ถ้ามองจากฝั่งที่เกือบเป็นผู้เชี่ยวชาญด้าน optimization ฉันคงแก้ปัญหานี้คนละแบบไปเลย บนเครื่องฉัน C เวอร์ชันแรกทำได้ 389MB ต่อวินาที และถ้าแอสเซมบลีในบทความให้ผลดีขึ้น 6.2 เท่าเท่ากัน ก็จะได้ราว 2.4GB ต่อวินาที
    สำหรับบัฟเฟอร์ยาว ๆ เวอร์ชัน C++ นี้บนเครื่องฉันเกิน 24GB/s: https://gist.github.com/Const-me/3ade77faad47f0fbb0538965ae7...
    โดยไม่ต้องเขียนแอสเซมบลี ใช้แค่ AVX2 intrinsic ก็เร็วกว่าเวอร์ชันเดิม 61 เท่า

    • น่าสนใจ ดูเหมือนว่าจะใช้ movemask กับ popcnt เพื่อทำเวกเตอร์ให้กับ prologue ได้ แทนการเก็บตัวนับไว้ในรีจิสเตอร์ ymm
      ยังเป็นโค้ดที่ไม่ได้ทดสอบเลยจึงต้อง benchmark แต่ก็ดูเหมือนจะทำได้ด้วยการสร้าง mask ของ s, p, \0 แล้วใช้ tzcnt, bzhi นับบิตก่อนถึงท้ายสตริง
    • อยากรู้ด้วยความสงสัยว่าแบบนี้ทำผ่าน std::experimental::simd ได้ไหม: https://en.cppreference.com/w/cpp/experimental/simd
    • น่าจะดีถ้าเขียนอันนี้ใหม่ให้เข้ากันได้กับ repository ของ @414owen
    • อยากรู้ว่ามีแหล่งเรียนและฝึก AVX ที่ดีไหม

  • โค้ดนี้ดูเหมาะกับ SIMD มากจริง ๆ ถ้าเปลี่ยน prototype ให้รับความยาวแบบระบุชัดได้ ก็จะอ่านและประมวลผลทีละ 16 ไบต์ได้ง่าย
    เอาผลการเปรียบเทียบมาบวกและลบตรง ๆ ได้เลย และแค่เรียก strlen() ตอนเริ่มฟังก์ชันเพื่อเอาความยาวแบบ explicit ก็น่าจะคุ้มแล้ว

  • ลองทำ implementation แบบ vectorized บน RISC-V อย่างเร็ว ๆ ดูแล้ว ใช้ rvv อ่านสตริง หา位置ของ \0 แล้วนับจำนวน s กับ p ด้วย vcpop
    บน Mangopi MQ Pro (C906, rv64gc + rvv 0.7.1, ความยาวเวกเตอร์ 128 บิต) switch ได้ 0.19 Bytes/Cycle, C implementation แบบ table ได้ 0.17 Bytes/Cycle, ส่วน rvv ได้ 1.57 Bytes/Cycle และหลังประมาณ 30KiB จะลดลงไปที่ 1.35 ถ้าจัด pointer ให้ตรงหน้า page และให้ vl ไม่ใหญ่กว่าขนาด page ก็ทำได้ถึง 2/1.7 Bytes/Cycle

    • ถ้าจะให้ถูกต้องสมบูรณ์ การโหลดควรเป็น fault-only-first load rvv มีฟีเจอร์นี้อยู่ ไม่อย่างนั้นอาจพังได้เมื่อ null byte อยู่ชิดก่อนจุดสิ้นสุดของหน่วยความจำที่ถูกจัดสรร

  • นี่น่าจะเป็น คุณสมบัติเฉพาะของสถาปัตยกรรม x86 ค่าใช้จ่ายของการไม่ทำ branch มันถูกมาก เลยทำให้ branch ดูแพงเมื่อเทียบกัน: https://wordsandbuttons.online/challenge_your_performance_in...
    แต่บนโปรเซสเซอร์แบบอื่นอาจไม่เป็นแบบนั้น: https://wordsandbuttons.online/using_logical_operators_for_l...
    คำถามที่ใหญ่กว่าคือ โดยทั่วไปแล้วทำไมต้องใช้ C ถ้าจะจูนด้วยมือให้รันได้ดีที่สุดบนฮาร์ดแวร์เฉพาะตัวหนึ่ง C ก็คือเครื่องมือที่ผิด และคุณต้องการ assembly กับระบบ macro ที่ดี เป้าหมายดั้งเดิมของ C คือทำให้โค้ดระดับระบบย้ายจากแพลตฟอร์มหนึ่งไปอีกแพลตฟอร์มหนึ่งได้ง่ายขึ้น และการสูญเสียประสิทธิภาพระหว่างทางก็เป็นสิ่งที่คาดไว้อยู่แล้ว มันคล้ายกับการเขียนกลอนเป็น Esperanto เพื่อให้แปลอัตโนมัติไปเป็นภาษาที่ต้องการ แทนที่จะเขียนบทกวีภาษาฮินดีแล้วแปลเป็นภาษาอูรดู คุณจะไม่ได้บทกวีชั้นยอดสองบท แต่จะได้งานแปลคุณภาพต่ำสองชิ้นอย่างรวดเร็ว และนั่นคือบทบาทของ C

  • ถ้าคอมไพล์ด้วย FDO/PGO ก็มีโอกาสสูงที่จะเกิดการจัดเรียง branch และ block ใหม่ เพราะถ้าไม่มี FDO คอมไพเลอร์จะไม่รู้ว่าแต่ละ branch ถูกเลือกบ่อยแค่ไหน ในบางกรณี FDO ยังอาจเปิดใช้ cmov ได้ด้วย
    แต่ cmov จะดีกว่า test/jump แบบปกติหรือไม่ ขึ้นอยู่มากว่าการทำนาย branch ทำได้แม่นแค่ไหน และโดยทั่วไป cmov จะทำงานดีกว่าเมื่อ branch คาดเดาได้ยากมาก ถ้า cmov ทำให้เร็วขึ้น 6 เท่า ก็เดาได้ว่าข้อมูลทดสอบน่าจะเป็นสตริงสุ่มที่เกือบทั้งหมดมีแต่ s กับ p ไม่ได้ผิดอะไร แต่ก็เป็นการอาศัยคุณสมบัติของข้อมูลที่ไม่ได้พูดถึงมาปรับ benchmark ให้เฉพาะทาง เลยทำให้บทความดูชวนให้เข้าใจผิดนิดหน่อย

    • โค้ดทดสอบอยู่ที่นี่: https://github.com/414owen/blog-code/blob/master/02-the-same...
      มันสุ่มเลือก 's' หรือ 'p' และอักขระที่เป็นไปได้ก็มีแค่ 's', 'p', กับ null terminator เท่านั้น ถ้ารู้คุณสมบัติของอินพุตนี้ ก็ทำ optimization แบบฉลาดเกินไปอย่าง result += (1 | *s++) - 'r'; ได้เหมือนกัน มันเป็นโค้ดที่เจ้าเล่ห์มาก แต่ก็แสดงประเด็นเรื่องการใช้คุณสมบัติของข้อมูลได้ชัดเจน
    • ภายในสตริงจะเจอ '\0' ได้มากสุดครั้งเดียวเพราะฟังก์ชันจะคืนค่าทันที แต่ตัวอักษรอื่นอาจเจอได้หลายครั้ง ข้อมูลนี้ดูเหมือนเป็นสิ่งที่คอมไพเลอร์เข้าถึงได้แม้ไม่มี PGO
      แน่นอนว่า PGO ช่วยได้ และบนเครื่องผมมันได้ 2.80 วินาที ซึ่งดีกว่าโค้ดท้ายส่วน Rearranging blocks อินพุตถูกอธิบายไว้ใน Benchmarking setup และก็อยู่ใน repository ด้วย: https://github.com/414owen/blog-code/blob/master/01-six-time...
      ในภาค 2 ที่ลิงก์ไว้ท้ายบทความ ผู้เขียนทำโค้ด C ให้เร็วที่สุดจนชนะ assembly ทั้งหมดในบทความนี้ ผมไม่เคยบอกว่าการเขียน assembly เป็นความคิดที่ดีเสมอไป แค่มองว่าการ optimize และการแกะความหมายผลลัพธ์จากคอมไพเลอร์เป็นโจทย์ที่น่าสนใจและเป็นโอกาสเรียนรู้ที่ดี

  • ผมคิดว่าน่าจะทำให้เร็วกว่าในบทความและบทความต่อเนื่องได้ แต่ก็ต้องแลกกับการเจาะจงกรณีที่สตริงประกอบด้วยแค่ 's' และ 'p'
    ตัว benchmark เองก็ทดสอบเฉพาะสตริงที่มีแต่ 's' กับ 'p' อยู่แล้ว เลยมองว่ายุติธรรม ประเด็นหลักคือ เราอยากเพิ่ม res ทีละ 1 เมื่ออักขระถัดไปเป็น s แต่ res += c - 'r' ใช้ไม่ได้ เพราะแม้กับ s จะได้ 1 แต่กับ p จะได้ -2 อย่างไรก็ตาม ถ้ามอง 'p' - 'r' เป็นจำนวนเต็มแบบ unsigned มันจะ underflow และตั้งค่า carry flag จากนั้น adc ของ x64 จะบวกรีจิสเตอร์สองตัวพร้อม carry flag ได้ ดังนั้นจึงแทน cmp, cmov สองชุดด้วย sub, adc ชุดเดียวได้ เวอร์ชันนี้เร็วกว่าเวอร์ชัน C ในบทความต่อ 1.08 เท่า และเร็วกว่า x64-7 เดิม 1.66 เท่า แน่นอนว่าถ้าใช้ SWAR/SIMD ก็ยังน่าจะปรับได้อีก

    • เป็นแนวทางที่น่าสนใจ ผมน่าจะเขียนให้ชัดว่า assembly ที่ค่อนข้างเรียบง่ายใน 02-the-same-speed-as-c/loop-5.x64.s คือเวอร์ชันที่เร็วที่สุดที่ผมมี

      บนเครื่องผม loop-5.x64.s ใช้เวลา 0.244 วินาที ส่วน implementation ข้างบนได้ 0.422 วินาที ผมเองก็ไม่แน่ใจนักว่าทำไมถึงต่างกันแบบนี้ เพราะดูเผิน ๆ implementation ข้างบนเหมือนจะเร็วกว่า ดังนั้นควร benchmark บนฮาร์ดแวร์ที่จะใช้รันจริงเสมอ

    • ถ้าจะให้ง่ายกว่านั้น ก็รวมค่าของสมาชิกทุกตัวใน array ก่อน แล้วค่อยลบ 'p' * len ทิ้งตอนท้าย แล้วหารด้วย ('s' - 'p') เพื่อหาจำนวน s จำนวน p ก็คือ len - s_count
      ขั้นรวมค่าเริ่มต้นก็ vectorize ได้ง่ายเช่นกัน ถ้าไม่ได้พลาดอะไร มันก็น่าจะทำงานได้ ปัญหาเดียวคือความเป็นไปได้ที่ผลรวมสะสมจะ overflow ผมไม่ค่อยมีแรงจูงใจจะ benchmark เอง แก้ไข: ผมลืมไปว่าตอนเจอ s ค่ามันลดลง ดังนั้นผลลัพธ์สุดท้ายคือ p_count - s_count

  • strlen() น่าจะถูก implement มาให้เร็วพอสมควรอยู่แล้ว และถ้ารู้ขนาดบัฟเฟอร์ คอมไพเลอร์ก็สามารถ auto-vectorize ลูปด้านในได้
    จริง ๆ แล้ว โค้ด len = strlen(buf) แล้วตามด้วยลูป for ที่บวก (buf[i] == 's') - (buf[i] == 'p') สามารถ auto-vectorize ได้: https://gcc.godbolt.org/z/qYfadPYoq

  • เมื่อก่อนผมเคยเขียน Common Lisp UTF-8 decoder สำหรับ SBCL มีตัวถอดรหัสในตัวอยู่แล้ว เลยทำเป็นแบบฝึกหัด
    ถ้าไม่นับ optimization ง่าย ๆ ที่เห็นชัดอยู่แล้ว เกือบทุกการปรับปรุงประสิทธิภาพมาจากการจัดโครงสร้างโค้ดให้คอมไพเลอร์สร้างคำสั่ง cmov* แทน branch

    • อยากเห็นตัวอย่างว่าคุณเปลี่ยนโค้ดยังไงบ้าง และก็สงสัยด้วยว่าคุณ disassemble ฟังก์ชันซ้ำ ๆ เพื่อดูว่ามันใช้คำสั่งที่ถูกต้องหรือเปล่า หรือเช็กการดีขึ้นจาก benchmark จริง ๆ
    • ถ้า branch ถูกทำนายได้ถูกต้อง มันก็มีโอกาสจะเร็วกว่าการย้ายแบบมีเงื่อนไข เพราะ branch ไม่ได้เพิ่มความยาวของ critical path
      ตัวถอดรหัส UTF-8 มักถูกรันกับอินพุตที่เป็น ASCII ล้วน เลยอยากรู้ว่าคุณ benchmark ด้วยอินพุตแบบไหน