ข่าวสารเกี่ยวกับผลิตภัณฑ์

เบื้องหลัง: MessageQueue แบบไม่มีการล็อกของ Android 17

ใช้เวลาอ่าน 16 นาที
ดูโปรไฟล์ของ Charles Munger ดูโปรไฟล์ของ Shai Barack
Charles Munger และ Shai Barack

ใน Android 17 แอปที่กำหนดเป้าหมายเป็น SDK 37 ขึ้นไปจะได้รับการติดตั้งใช้งาน MessageQueue ใหม่ซึ่งไม่มีการล็อก การใช้งานใหม่นี้จะช่วยปรับปรุงประสิทธิภาพและลดเฟรมที่ขาดหายไป แต่อาจทำให้ไคลเอ็นต์ที่แสดงผลในช่องและเมธอดส่วนตัวของ MessageQueue เสียหาย ดูข้อมูลเพิ่มเติมเกี่ยวกับการเปลี่ยนแปลงลักษณะการทำงานและวิธีลดผลกระทบได้ที่เอกสารประกอบเกี่ยวกับการเปลี่ยนแปลงลักษณะการทำงานของ MessageQueue บล็อกโพสต์ทางเทคนิคนี้แสดงภาพรวมของสถาปัตยกรรมใหม่ของ MessageQueue และวิธีวิเคราะห์ปัญหาการแย่งชิงล็อกโดยใช้ Perfetto

Looper จะขับเคลื่อนเธรด UI ของแอปพลิเคชัน Android ทุกแอป โดยจะดึงงานจาก MessageQueue ส่งไปยัง Handler และทำซ้ำ เป็นเวลา 2 ทศวรรษที่ MessageQueue ใช้การล็อกจอภาพเดียว (เช่น บล็อกโค้ด synchronized) เพื่อปกป้องสถานะของตนเอง

Android 17 มีการอัปเดตที่สำคัญสำหรับคอมโพเนนต์นี้ ซึ่งก็คือการติดตั้งใช้งานแบบไม่มีการล็อกที่ชื่อว่า DeliQueue

โพสต์นี้จะอธิบายว่าการล็อกส่งผลต่อประสิทธิภาพของ UI อย่างไร วิธีวิเคราะห์ปัญหาเหล่านี้ด้วย Perfetto รวมถึงอัลกอริทึมและการเพิ่มประสิทธิภาพที่เฉพาะเจาะจงซึ่งใช้เพื่อปรับปรุงเทรดหลักของ Android

ปัญหา: การแย่งชิงล็อกและการกลับลำดับความสำคัญ

MessageQueue เดิมทำหน้าที่เป็นคิวที่มีลำดับความสำคัญซึ่งได้รับการปกป้องโดยการล็อกเพียงครั้งเดียว หากเทรดเบื้องหลังโพสต์ข้อความขณะที่เทรดหลักดำเนินการบำรุงรักษาคิว เทรดเบื้องหลังจะบล็อกเทรดหลัก

เมื่อเทรดอย่างน้อย 2 เทรดแข่งขันกันเพื่อใช้ล็อกเดียวกันแต่เพียงผู้เดียว เราจะเรียกว่าการแย่งชิงล็อก การแย่งชิงนี้อาจทำให้เกิดการกลับลำดับความสำคัญ ซึ่งนำไปสู่ความกระตุกของ UI และปัญหาด้านประสิทธิภาพอื่นๆ

การกลับลำดับความสำคัญอาจเกิดขึ้นเมื่อเธรดที่มีลำดับความสำคัญสูง (เช่น เธรด UI) ต้องรอเธรดที่มีลำดับความสำคัญต่ำ ลองพิจารณาลำดับต่อไปนี้

  1. เทรดเบื้องหลังที่มีลำดับความสำคัญต่ำจะได้รับล็อก MessageQueue เพื่อโพสต์ผลลัพธ์ของงานที่ทำ
  2. เทรดลำดับความสำคัญปานกลางจะทำงานได้ และตัวจัดตารางเวลาของเคอร์เนลจะจัดสรรเวลา CPU ให้กับเทรดดังกล่าว โดยจะแย่งสิทธิ์เทรดที่มีลำดับความสำคัญต่ำ
  3. เธรด UI ที่มีลำดับความสำคัญสูงทำงานปัจจุบันเสร็จและพยายามอ่านจากคิว แต่ถูกบล็อกเนื่องจากเธรดที่มีลำดับความสำคัญต่ำถือล็อกอยู่

เธรดที่มีลำดับความสำคัญต่ำจะบล็อกเธรด UI และงานที่มีลำดับความสำคัญปานกลางจะทำให้เธรด UI ล่าช้าออกไปอีก

perfetto1.png

การวิเคราะห์การช่วงชิงทรัพยากรด้วย Perfetto

คุณสามารถวินิจฉัยปัญหาเหล่านี้ได้โดยใช้ Perfetto ในการติดตามมาตรฐาน เทรดที่ถูกบล็อกในการล็อกมอนิเตอร์จะเข้าสู่สถานะพัก และ Perfetto จะแสดงส่วนที่ระบุเจ้าของการล็อก

เมื่อค้นหาข้อมูลการติดตาม ให้มองหา Slice ที่ชื่อ "monitor contention with …" ตามด้วยชื่อของชุดข้อความที่เป็นเจ้าของล็อกและเว็บไซต์โค้ดที่ได้รับล็อก

กรณีศึกษา: Launcher ขัดข้อง

เราจะวิเคราะห์การติดตามที่ผู้ใช้พบอาการกระตุกขณะไปยังหน้าแรกในโทรศัพท์ Pixel ทันทีหลังจากถ่ายภาพในแอปกล้องถ่ายรูป ด้านล่างนี้คือภาพหน้าจอของ Perfetto ที่แสดงเหตุการณ์ที่นำไปสู่เฟรมที่พลาดไป

launcherJ.png
  • อาการ: เทรดหลักของ Launcher ไม่ทันกำหนดเวลาเฟรม โดยบล็อกเป็นเวลา 18 มิลลิวินาที ซึ่งเกินกำหนดเวลา 16 มิลลิวินาทีที่จำเป็นสำหรับการแสดงผล 60Hz
  • การวินิจฉัย: Perfetto แสดงเทรดหลักที่ถูกบล็อกในล็อก MessageQueue เทรด "BackgroundExecutor" เป็นเจ้าของล็อก
  • สาเหตุของปัญหา: BackgroundExecutor ทำงานที่ Process.THREAD_PRIORITY_BACKGROUND (ลำดับความสำคัญต่ำมาก) เนื่องจากกำลังทำงานที่ไม่เร่งด่วน (ตรวจสอบขีดจำกัดการใช้งานแอป) ในขณะเดียวกัน เทรดที่มีลำดับความสำคัญปานกลางก็ใช้เวลา CPU ในการประมวลผลข้อมูลจากกล้อง ตัวจัดตารางเวลาของระบบปฏิบัติการได้แย่งสิทธิ์เทรด BackgroundExecutor เพื่อเรียกใช้เทรดกล้อง

ลำดับนี้ทำให้เธรด UI ของ Launcher (ลำดับความสำคัญสูง) ถูกบล็อกโดยอ้อมจากเทรดผู้ปฏิบัติงานของกล้อง (ลำดับความสำคัญปานกลาง) ซึ่งทำให้เธรดเบื้องหลังของ Launcher (ลำดับความสำคัญต่ำ) ไม่สามารถปลดล็อกได้

การค้นหาการติดตามด้วย PerfettoSQL

คุณสามารถใช้ PerfettoSQL เพื่อค้นหาข้อมูลการติดตามสำหรับรูปแบบที่เฉพาะเจาะจงได้ ซึ่งจะเป็นประโยชน์หากคุณมีคลังการติดตามขนาดใหญ่จากอุปกรณ์ของผู้ใช้หรือการทดสอบ และคุณกำลังค้นหาการติดตามที่เฉพาะเจาะจงซึ่งแสดงให้เห็นปัญหา

ตัวอย่างเช่น การค้นหานี้จะค้นหาการแย่งชิงทรัพยากร MessageQueue ที่เกิดขึ้นพร้อมกับเฟรมที่หายไป (กระตุก)

INCLUDE PERFETTO MODULE android.monitor_contention;
INCLUDE PERFETTO MODULE android.frames.jank_type;

SELECT
  process_name,
  -- Convert duration from nanoseconds to milliseconds
  SUM(dur) / 1000000 AS sum_dur_ms,
  COUNT(*) AS count_contention
FROM android_monitor_contention
WHERE is_blocked_thread_main
AND short_blocked_method LIKE "%MessageQueue%" 

-- Only look at app processes that had jank
AND upid IN (
  SELECT DISTINCT(upid)
  FROM actual_frame_timeline_slice
  WHERE android_is_app_jank_type(jank_type) = TRUE
)
GROUP BY process_name
ORDER BY SUM(dur) DESC;

ในตัวอย่างที่ซับซ้อนยิ่งขึ้นนี้ ให้รวมข้อมูลการติดตามที่ครอบคลุมหลายตารางเพื่อระบุการแย่งชิง MessageQueue ระหว่างการเริ่มต้นแอป

INCLUDE PERFETTO MODULE android.monitor_contention; 
INCLUDE PERFETTO MODULE android.startup.startups; 

-- Join package and process information for startups
DROP VIEW IF EXISTS startups; 
CREATE VIEW startups AS 
SELECT startup_id, ts, dur, upid 
FROM android_startups 
JOIN android_startup_processes USING(startup_id); 

-- Intersect monitor contention with startups in the same process.
DROP TABLE IF EXISTS monitor_contention_during_startup; 
CREATE VIRTUAL TABLE monitor_contention_during_startup 
USING SPAN_JOIN(android_monitor_contention PARTITIONED upid, startups PARTITIONED upid); 

SELECT 
  process_name, 
  SUM(dur) / 1000000 AS sum_dur_ms, 
  COUNT(*) AS count_contention 
FROM monitor_contention_during_startup 
WHERE is_blocked_thread_main 
AND short_blocked_method LIKE "%MessageQueue%" 
GROUP BY process_name 
ORDER BY SUM(dur) DESC;

คุณสามารถใช้ LLM ที่คุณชื่นชอบเพื่อเขียนการค้นหา PerfettoSQL เพื่อค้นหารูปแบบอื่นๆ ได้

ที่ Google เราใช้ BigTrace เพื่อเรียกใช้การค้นหา PerfettoSQL ในการติดตามหลายล้านรายการ ซึ่งทำให้เรายืนยันได้ว่าสิ่งที่เห็นจากเรื่องราวที่เล่าต่อกันมานั้นเป็นปัญหาเชิงระบบจริงๆ ข้อมูลแสดงให้เห็นว่าการแย่งชิงล็อกของ MessageQueue ส่งผลกระทบต่อผู้ใช้ทั่วทั้งระบบนิเวศ ซึ่งเป็นการยืนยันถึงความจำเป็นในการเปลี่ยนแปลงสถาปัตยกรรมพื้นฐาน

โซลูชัน: การทำงานพร้อมกันแบบไม่มีการล็อก

เราแก้ไขปัญหาการแย่งชิงทรัพยากรของ MessageQueue โดยใช้โครงสร้างข้อมูลแบบไม่มีการล็อก โดยใช้การดำเนินการหน่วยความจำแบบอะตอมแทนการล็อกแบบเอกสิทธิ์เฉพาะบุคคลเพื่อซิงค์การเข้าถึงสถานะที่แชร์ โครงสร้างข้อมูลหรืออัลกอริทึมจะไม่มีการล็อกหากมีเทรดอย่างน้อย 1 เทรดที่ทำงานได้เสมอ ไม่ว่าลักษณะการกำหนดเวลาของเทรดอื่นๆ จะเป็นอย่างไร โดยทั่วไปแล้ว คุณสมบัตินี้ทำได้ยาก และมักไม่คุ้มค่าที่จะดำเนินการกับโค้ดส่วนใหญ่

องค์ประกอบพื้นฐานแบบอะตอม

ซอฟต์แวร์ที่ไม่มีการล็อกมักจะอาศัยพื้นฐานการอ่าน-แก้ไข-เขียนแบบอะตอมที่ฮาร์ดแวร์มีให้

ใน CPU ARM64 รุ่นเก่า อะตอมิกใช้ลูป Load-Link/Store-Conditional (LL/SC) CPU จะโหลดค่าและทำเครื่องหมายที่อยู่ หากเทรดอื่นเขียนไปยังที่อยู่นั้น การจัดเก็บจะล้มเหลว และลูปจะลองอีกครั้ง เนื่องจากเทรดสามารถพยายามต่อไปและดำเนินการสำเร็จได้โดยไม่ต้องรอเทรดอื่น การดำเนินการนี้จึงไม่มีการล็อก

ARM64 LL/SC loop example
retry:
    ldxr    x0, [x1]        // Load exclusive from address x1 to x0
    add     x0, x0, #1      // Increment value by 1
    stxr    w2, x0, [x1]    // Store exclusive.
                            // w2 gets 0 on success, 1 on failure
    cbnz    w2, retry       // If w2 is non-zero (failed), branch to retr

(ดูใน Compiler Explorer)

สถาปัตยกรรม ARM ที่ใหม่กว่า (ARMv8.1) รองรับ Large System Extensions (LSE) ซึ่งรวมถึงวิธีการในรูปแบบ Compare-And-Swap (CAS) หรือ Load-And-Add (แสดงด้านล่าง) ใน Android 17 เราได้เพิ่มการรองรับคอมไพเลอร์ Android Runtime (ART) เพื่อตรวจหาเมื่อระบบรองรับ LSE และส่งคำสั่งที่เพิ่มประสิทธิภาพแล้ว

/ ARMv8.1 LSE atomic example
ldadd   x0, x1, [x2]    // Atomic load-add.
                        // Faster, no loop required.

ในการเปรียบเทียบของเรา โค้ดที่มีการแย่งชิงทรัพยากรสูงซึ่งใช้ CAS จะมีความเร็วเพิ่มขึ้นประมาณ 3 เท่าเมื่อเทียบกับตัวแปร LL/SC

ภาษาโปรแกรม Java มีองค์ประกอบพื้นฐานแบบอะตอมผ่าน java.util.concurrent.atomic ซึ่งอาศัยคำสั่ง CPU เฉพาะเหล่านี้และคำสั่งอื่นๆ

โครงสร้างข้อมูล: DeliQueue

วิศวกรของเราได้ออกแบบโครงสร้างข้อมูลแบบใหม่ที่เรียกว่า DeliQueue เพื่อนำการแย่งชิงล็อกออกจาก MessageQueue DeliQueue จะแยกการแทรก Message ออกจากการประมวลผล Message ดังนี้

  1. รายการของ Messages (Treiber stack): สแต็กที่ไม่มีการล็อก ชุดข้อความใดๆ สามารถพุช Messages ใหม่ที่นี่ได้โดยไม่มีการแย่งชิงทรัพยากร
  2. คิวที่มีลำดับความสำคัญ (Min-heap): กอง Messages ที่ต้องจัดการ ซึ่งเป็นของเทรด Looper โดยเฉพาะ (จึงไม่จำเป็นต้องมีการซิงค์หรือล็อกเพื่อเข้าถึง)

Enqueue: pushing to a Treiber stack

รายการ Messages จะเก็บไว้ในสแต็ก Treiber [1] ซึ่งเป็นสแต็กแบบไม่มีล็อกที่ใช้ลูป CAS เพื่ออัปเดตตัวชี้ส่วนหัว

public class TreiberStack <E> {
    AtomicReference<Node<E>> top =
            new AtomicReference<Node<E>>();
    public void push(E item) {
        Node<E> newHead = new Node<E>(item);
        Node<E> oldHead;
        do {
            oldHead = top.get();
            newHead.next = oldHead;
        } while (!top.compareAndSet(oldHead, newHead));
    }

    public E pop() {
        Node<E> oldHead;
        Node<E> newHead;
        do {
            oldHead = top.get();
            if (oldHead == null) return null;
            newHead = oldHead.next;
        } while (!top.compareAndSet(oldHead, newHead));
        return oldHead.item;
    }
}

ซอร์สโค้ดที่อิงตาม Java Concurrency in Practice [2] พร้อมใช้งานออนไลน์และเผยแพร่เป็นสาธารณสมบัติ

ผู้ผลิตสามารถพุช Message ใหม่ไปยังสแต็กได้ทุกเมื่อ ซึ่งคล้ายกับการดึงตั๋วที่เคาน์เตอร์อาหารสำเร็จรูป โดยหมายเลขของคุณจะกำหนดตามเวลาที่คุณมาถึง แต่ลำดับที่คุณได้รับอาหารไม่จำเป็นต้องตรงกัน เนื่องจากเป็นสแต็กที่ลิงก์กัน Message ทุกรายการจึงเป็นสแต็กย่อย คุณสามารถดูว่าคิว Message เป็นอย่างไร ณ จุดใดก็ได้โดยการติดตามส่วนหัวและทำซ้ำไปข้างหน้า คุณจะไม่เห็น Message ใหม่ที่พุชไว้ด้านบน แม้ว่าจะมีการเพิ่มในระหว่างการข้ามผ่านก็ตาม

Dequeue: bulk transfer to a min-heap

หากต้องการค้นหา Message ถัดไปที่จะจัดการ Looper จะประมวลผล Message ใหม่จากสแต็ก Treiber โดยเดินผ่านสแต็กโดยเริ่มจากด้านบนและทำซ้ำจนกว่าจะพบ Message สุดท้ายที่ประมวลผลก่อนหน้านี้ เมื่อ Looper เคลื่อนที่ลงไปตามสแต็ก ระบบจะแทรก Message ลงในฮีปต่ำสุดที่เรียงตามกำหนดเวลา เนื่องจาก Looper เป็นเจ้าของฮีปแต่เพียงผู้เดียว จึงจัดลำดับและประมวลผล Message โดยไม่มีการล็อกหรืออะตอมมิก

dequeue.png

เมื่อเดินลงไปตามสแต็ก Looper จะสร้างลิงก์จาก Message ที่ซ้อนกันกลับไปยังรายการก่อนหน้าด้วย จึงทำให้เกิดรายการที่ลิงก์ซ้อนกัน การสร้างรายการที่ลิงก์นั้นปลอดภัยเนื่องจากระบบจะเพิ่มลิงก์ที่ชี้ลงไปยังสแต็กผ่านอัลกอริทึมสแต็ก Treiber ที่มี CAS และลิงก์ที่ชี้ขึ้นไปยังสแต็กจะอ่านและแก้ไขโดยเทรด Looper เท่านั้น จากนั้นระบบจะใช้ลิงก์ย้อนกลับเหล่านี้เพื่อนำ Message ออกจากจุดที่กำหนดเองในสแต็กในเวลา O(1)

การออกแบบนี้ให้การแทรก O(1) สำหรับผู้ผลิต (ชุดข้อความที่โพสต์งานไปยังคิว) และการประมวลผล O(log N) ที่ตัดจำหน่ายสำหรับผู้ใช้ (Looper)

การใช้ Min-Heap เพื่อจัดลำดับ Message ยังช่วยแก้ไขข้อบกพร่องพื้นฐานใน MessageQueue เดิม ซึ่งเก็บ Message ไว้ในรายการที่ลิงก์แบบเดี่ยว (มีรากอยู่ที่ด้านบน) ในการติดตั้งใช้งานแบบเดิม การนำออกจากส่วนหัวคือ O(1) แต่การแทรกมีกรณีที่แย่ที่สุดคือ O(N) ซึ่งปรับขนาดได้ไม่ดีสำหรับคิวที่โอเวอร์โหลด ในทางกลับกัน การแทรกและการนำออกจาก Min-Heap จะปรับขนาดแบบลอการิทึม ซึ่งให้ประสิทธิภาพเฉลี่ยที่แข่งขันได้ แต่โดดเด่นมากในเรื่องเวลาในการตอบสนองแบบ Tail


 
เวอร์ชันเดิม (ล็อก) MessageQueueDeliQueue
แทรกO(N)

O(1) สำหรับชุดข้อความการโทร

O(logN) สำหรับเทรด Looper

นำออกจากศีรษะO(1)O(logN)

ในการใช้งานคิวแบบเดิม ผู้ผลิตและผู้บริโภคใช้การล็อกเพื่อประสานงานการเข้าถึงรายการที่ลิงก์แบบเดี่ยวที่สำคัญโดยเฉพาะ ใน DeliQueue สแต็ก Treiber จะจัดการการเข้าถึงพร้อมกัน และผู้ใช้รายเดียวจะจัดการการจัดลำดับคิวงาน

การนำออก: ความสอดคล้องกันผ่าน Tombstone

DeliQueue เป็นโครงสร้างข้อมูลแบบผสมที่รวมสแต็ก Treiber แบบไม่มีล็อกเข้ากับมินฮีปแบบเทรดเดียว การซิงค์โครงสร้างทั้ง 2 แบบนี้โดยไม่มีการล็อกส่วนกลางทำให้เกิดความท้าทายที่ไม่เหมือนใคร นั่นคือข้อความอาจปรากฏในสแต็ก แต่ถูกนำออกจากคิวในทางตรรกะ

เพื่อแก้ปัญหานี้ DeliQueue ใช้เทคนิคที่เรียกว่า "Tombstoning" โดย Message แต่ละรายการจะติดตามตำแหน่งของตนเองในสแต็กผ่านตัวชี้ไปข้างหลังและไปข้างหน้า ดัชนีในอาร์เรย์ของฮีป และแฟล็กบูลีนที่ระบุว่ามีการนำออกหรือไม่ เมื่อ Message พร้อมที่จะทำงาน เทรด Looper จะ CAS แฟล็กที่นำออก จากนั้นนำออกจากฮีปและสแต็ก

เมื่อชุดข้อความอื่นต้องการนำ Message ออก ระบบจะไม่ดึงข้อมูลออกจากโครงสร้างข้อมูลทันที แต่จะทำตามขั้นตอนต่อไปนี้แทน

  1. การนำออกเชิงตรรกะ: เทรดใช้ CAS เพื่อตั้งค่าแฟล็กการนำออกของ Message จากเท็จเป็นจริงโดยอัตโนมัติ Message จะยังคงอยู่ในโครงสร้างข้อมูลเพื่อเป็นหลักฐานว่ากำลังรอนำออก ซึ่งเรียกว่า "Tombstone" เมื่อมีการแจ้งว่าต้องการนำ Message ออก DeliQueue จะถือว่าไม่มีข้อมูลดังกล่าวอยู่ในคิวอีกต่อไปเมื่อใดก็ตามที่พบข้อมูลนั้น
  2. การล้างข้อมูลที่เลื่อนออกไป: การนำออกจากโครงสร้างข้อมูลจริงเป็นความรับผิดชอบของเทรด Looper และจะเลื่อนออกไปจนกว่าจะถึงภายหลัง เธรดตัวนำออกจะเพิ่ม Message ไปยังสแต็กรายการว่างแบบไม่มีการล็อกอีกรายการหนึ่ง แทนที่จะแก้ไขสแต็กหรือฮีป
  3. การนำออกเชิงโครงสร้าง: เฉพาะ Looper เท่านั้นที่โต้ตอบกับฮีปหรือนำองค์ประกอบออกจากสแต็กได้ เมื่อตื่นขึ้นมา ระบบจะล้างรายการที่ว่างและประมวลผล Message ที่มีอยู่ จากนั้นระบบจะยกเลิกการลิงก์ Message แต่ละรายการจากสแต็กและนำออกจากฮีป  

วิธีนี้จะทำให้การจัดการฮีปทั้งหมดเป็นแบบเทรดเดียว ซึ่งจะช่วยลดจำนวนการดำเนินการที่เกิดขึ้นพร้อมกันและอุปสรรคด้านหน่วยความจำที่จำเป็น ทำให้เส้นทางวิกฤตเร็วขึ้นและง่ายขึ้น

การข้าม: การแย่งชิงข้อมูลโมเดลหน่วยความจำ Java ที่ไม่เป็นอันตราย

API การทำงานพร้อมกันส่วนใหญ่ เช่น Future ในไลบรารีมาตรฐานของ Java หรือ Job และ Deferred ของ Kotlin มีกลไกในการยกเลิกงานก่อนที่จะเสร็จสมบูรณ์ อินสแตนซ์ของคลาสใดคลาสหนึ่งเหล่านี้จะจับคู่แบบ 1:1 กับหน่วยงานที่เกี่ยวข้อง และการเรียกใช้ cancel ในออบเจ็กต์จะยกเลิกการดำเนินการที่เฉพาะเจาะจงซึ่งเชื่อมโยงกับออบเจ็กต์เหล่านั้น

อุปกรณ์ Android ในปัจจุบันมี CPU แบบหลายคอร์และเครื่องมือเก็บหน่วยความจำแอปตามรุ่นที่ทำงานพร้อมกัน แต่เมื่อ Android ได้รับการพัฒนาขึ้นเป็นครั้งแรก การจัดสรรออบเจ็กต์ 1 รายการสำหรับงานแต่ละหน่วยนั้นมีค่าใช้จ่ายสูงเกินไป ด้วยเหตุนี้ Handler ของ Android จึงรองรับการยกเลิกผ่านการโอเวอร์โหลดจำนวนมากของ removeMessages แทนที่จะนำ Message ที่เฉพาะเจาะจงออก ระบบจะนำ Message ทั้งหมดที่ตรงกับเกณฑ์ที่ระบุออก ในทางปฏิบัติ คุณจะต้องทำซ้ำผ่าน Message ทั้งหมดที่แทรกไว้ก่อนที่จะเรียกใช้ removeMessages และนำรายการที่ตรงกันออก

เมื่อทำซ้ำไปข้างหน้า เทรดต้องการการดำเนินการแบบอะตอมมิกที่มีการจัดลำดับเพียงรายการเดียวเพื่ออ่านส่วนหัวปัจจุบันของสแต็ก หลังจากนั้น ระบบจะใช้การอ่านฟิลด์แบบธรรมดาเพื่อค้นหา Message ถัดไป หากเทรด Looper แก้ไขช่อง next ขณะนำ Message ออก การเขียนของ Looper และการอ่านของเทรดอื่นจะไม่ซิงค์กัน ซึ่งเรียกว่าการแย่งใช้ข้อมูล โดยปกติแล้ว การแย่งใช้ข้อมูลเป็นข้อบกพร่องร้ายแรงที่อาจทำให้เกิดปัญหาใหญ่ในแอป เช่น การรั่วไหล, การวนซ้ำไม่สิ้นสุด, ข้อขัดข้อง, อาการค้าง และอื่นๆ อย่างไรก็ตาม ภายใต้เงื่อนไขที่จำกัดบางอย่าง การแย่งชิงข้อมูลอาจไม่เป็นอันตรายภายในโมเดลหน่วยความจำของ Java สมมติว่าเราเริ่มด้วยกองไพ่ต่อไปนี้

headMessage.png

เราทำการอ่านแบบอะตอมมิกของส่วนหัวและเห็น A ตัวชี้ถัดไปของ A ชี้ไปที่ B ในขณะเดียวกันกับที่เราประมวลผล B ตัววนซ้ำอาจนำ B และ C ออกโดยอัปเดต A ให้ชี้ไปยัง C แล้วจึงชี้ไปยัง D

headMessage2.png

แม้ว่า B และ C จะถูกนำออกตามตรรกะ แต่ B ยังคงเก็บตัวชี้ถัดไปไว้ที่ C และ C ไปยัง D เทรดการอ่านจะยังคงข้ามผ่านโหนดที่ถูกนำออกซึ่งแยกออกมา และในที่สุดจะกลับเข้าร่วมสแต็กที่ใช้งานอยู่ ณ D 

การออกแบบ DeliQueue ให้จัดการกับการแข่งขันระหว่างการข้ามและการนำออกช่วยให้เราสามารถทำซ้ำได้อย่างปลอดภัยโดยไม่ต้องล็อก

กำลังออก: Refcount แบบเนทีฟ

Looper ได้รับการสนับสนุนโดยการจัดสรรแบบเนทีฟที่ต้องเพิ่มพื้นที่ว่างด้วยตนเองเมื่อ Looper ออกแล้ว หากชุดข้อความอื่นกำลังเพิ่ม Message ขณะที่ Looper กำลังออก ชุดข้อความดังกล่าวอาจใช้การจัดสรรแบบเนทีฟหลังจากที่ว่างแล้ว ซึ่งเป็นการละเมิดความปลอดภัยของหน่วยความจำ เราป้องกันปัญหานี้โดยใช้ tagged refcount ซึ่งจะใช้ 1 บิตของอะตอมเพื่อระบุว่า Looper กำลังจะปิดหรือไม่

ก่อนใช้การจัดสรรแบบเนทีฟ เทรดจะอ่านอะตอมมิก refcount หากมีการตั้งค่าบิตการออก ระบบจะแสดงผลว่า Looper กำลังออกและต้องไม่ใช้การจัดสรรแบบเนทีฟ หากไม่เป็นเช่นนั้น ระบบจะพยายามใช้ CAS เพื่อเพิ่มจำนวนชุดข้อความที่ใช้งานอยู่โดยใช้การจัดสรรแบบเนทีฟ หลังจากทำสิ่งที่ต้องทำแล้ว ระบบจะลดจำนวนลง หากมีการตั้งค่าบิตการออกหลังจากเพิ่มขึ้นแต่ก่อนลดลง และตอนนี้จำนวนเป็น 0 ระบบจะปลุกเทรด Looper

เมื่อเทรด Looper พร้อมที่จะออก เทรดจะใช้ CAS เพื่อตั้งค่าบิตการออกในอะตอม หาก refcount เป็น 0 ระบบจะดำเนินการต่อเพื่อเพิ่มพื้นที่ว่างในการจัดสรรแบบเนทีฟได้ ไม่เช่นนั้น ระบบจะพักตัวเองไว้ โดยรู้ว่าจะถูกปลุกเมื่อผู้ใช้รายสุดท้ายของการจัดสรรแบบเนทีฟลดจำนวนการอ้างอิง แนวทางนี้หมายความว่าเทรด Looper จะรอความคืบหน้าของเทรดอื่นๆ แต่จะรอเฉพาะเมื่อกำลังจะออกเท่านั้น ซึ่งจะเกิดขึ้นเพียงครั้งเดียวและไม่ส่งผลต่อประสิทธิภาพ และจะเก็บโค้ดอื่นๆ ไว้เพื่อใช้การจัดสรรแบบเนทีฟโดยไม่มีการล็อกอย่างสมบูรณ์

atomicLayout.png

ยังมีเคล็ดลับและความซับซ้อนอื่นๆ อีกมากมายในการติดตั้งใช้งาน ดูข้อมูลเพิ่มเติมเกี่ยวกับ DeliQueue ได้โดยการตรวจสอบซอร์สโค้ด

การเพิ่มประสิทธิภาพ: การเขียนโปรแกรมแบบไม่มี Branch

ในระหว่างการพัฒนาและทดสอบ DeliQueue ทีมได้ทำการเปรียบเทียบหลายครั้งและวิเคราะห์โค้ดใหม่อย่างรอบคอบ ปัญหาหนึ่งที่พบจากการใช้เครื่องมือ simpleperf คือการล้างไปป์ไลน์ที่เกิดจากโค้ดตัวเปรียบเทียบ Message

ตัวเปรียบเทียบมาตรฐานจะใช้การข้ามแบบมีเงื่อนไข โดยมีเงื่อนไขในการตัดสินใจว่า Message ใดจะมาก่อนตามที่อธิบายไว้ด้านล่าง

static int compareMessages(@NonNull Message m1, @NonNull Message m2) {
    if (m1 == m2) {
        return 0;
    }

    // Primary queue order is by when.
    // Messages with an earlier when should come first in the queue.
    final long whenDiff = m1.when - m2.when;
    if (whenDiff > 0) return 1;
    if (whenDiff < 0) return -1;

    // Secondary queue order is by insert sequence.
    // If two messages were inserted with the same `when`, the one inserted
    // first should come first in the queue.
    final long insertSeqDiff = m1.insertSeq - m2.insertSeq;
    if (insertSeqDiff > 0) return 1;
    if (insertSeqDiff < 0) return -1;

    return 0;
}

โค้ดนี้จะคอมไพล์เป็นการข้ามแบบมีเงื่อนไข (คำสั่ง b.le และ cbnz) เมื่อ CPU พบ Branch แบบมีเงื่อนไข ก็จะไม่ทราบว่ามีการใช้ Branch หรือไม่จนกว่าจะมีการคำนวณเงื่อนไข จึงไม่ทราบว่าควรอ่านคำสั่งใดต่อไป และต้องเดาโดยใช้เทคนิคที่เรียกว่าการคาดคะเน Branch ในกรณีอย่างการค้นหาแบบไบนารี ทิศทางของสาขาจะแตกต่างกันอย่างคาดเดาไม่ได้ในแต่ละขั้นตอน ดังนั้นจึงเป็นไปได้ว่าการคาดคะเนครึ่งหนึ่งจะผิดพลาด การคาดคะเนสาขามักไม่มีประสิทธิภาพในอัลกอริทึมการค้นหาและการจัดเรียง (เช่น อัลกอริทึมที่ใช้ใน Min-Heap) เนื่องจากต้นทุนของการเดาผิดมีมากกว่าการปรับปรุงจากการเดาถูก เมื่อตัวคาดการณ์สาขาคาดเดาผิด ตัวคาดการณ์จะต้องทิ้งงานที่ทำหลังจากสมมติค่าที่คาดการณ์ไว้ และเริ่มใหม่อีกครั้งจากเส้นทางที่ใช้จริง ซึ่งเรียกว่าการล้างไปป์ไลน์

เราพบปัญหานี้จากการทำโปรไฟล์การเปรียบเทียบโดยใช้ตัวนับประสิทธิภาพ branch-misses ซึ่งจะบันทึกสแต็กเทรซที่ตัวคาดการณ์สาขาคาดเดาผิด จากนั้นเราจึงแสดงผลลัพธ์ด้วย Google pprof ดังที่แสดงด้านล่าง

flame2.png

โปรดทราบว่าโค้ด MessageQueue เดิมใช้รายการที่ลิงก์แบบเดี่ยวสำหรับคิวที่เรียงลำดับ การแทรกจะข้ามรายการตามลำดับการจัดเรียงเป็นการค้นหาเชิงเส้น โดยหยุดที่องค์ประกอบแรกที่ผ่านจุดแทรกและลิงก์ Message ใหม่ไว้ข้างหน้า หากต้องการถอดออกจากหัว เพียงยกเลิกการลิงก์หัว ในขณะที่ DeliQueue ใช้ Min-Heap ซึ่งการเปลี่ยนแปลงต้องมีการจัดเรียงองค์ประกอบบางอย่างใหม่ (การเลื่อนขึ้นหรือลง) ด้วยความซับซ้อนแบบลอการิทึมในโครงสร้างข้อมูลที่สมดุล ซึ่งการเปรียบเทียบใดๆ มีโอกาสเท่ากันในการกำหนดทิศทางการข้ามไปยังโหนดลูกด้านซ้ายหรือโหนดลูกด้านขวา อัลกอริทึมใหม่จะทำงานได้เร็วขึ้นแบบอะซิมโทติก แต่จะแสดงจุดคอขวดใหม่เนื่องจากโค้ดการค้นหาหยุดทำงานเมื่อเกิด Branch Miss ครึ่งหนึ่งของเวลาทั้งหมด

เมื่อตระหนักว่าการพลาดสาขาทำให้โค้ดฮีปช้าลง เราจึงเพิ่มประสิทธิภาพโค้ดโดยใช้การเขียนโปรแกรมแบบไม่มีสาขา

// Branchless Logic
static int compareMessages(@NonNull Message m1, @NonNull Message m2) {
    final long when1 = m1.when;
    final long when2 = m2.when;
    final long insertSeq1 = m1.insertSeq;
    final long insertSeq2 = m2.insertSeq;

    // signum returns the sign (-1, 0, 1) of the argument,
    // and is implemented as pure arithmetic:
    // ((num >> 63) | (-num >>> 63))
    final int whenSign = Long.signum(when1 - when2);
    final int insertSeqSign = Long.signum(insertSeq1 - insertSeq2);

    // whenSign takes precedence over insertSeqSign,
    // so the formula below is such that insertSeqSign only matters
    // as a tie-breaker if whenSign is 0.
    return whenSign * 2 + insertSeqSign;
}

หากต้องการทำความเข้าใจการเพิ่มประสิทธิภาพ ให้ถอดแยกตัวอย่างทั้ง 2 รายการใน Compiler Explorer และใช้ LLVM-MCA ซึ่งเป็นเครื่องจำลอง CPU ที่สามารถสร้างไทม์ไลน์โดยประมาณของรอบ CPU

The original code:
Index     01234567890123
[0,0]     DeER .    .  .   sub  x0, x2, x3
[0,1]     D=eER.    .  .   cmp  x0, #0
[0,2]     D==eER    .  .   cset w0, ne
[0,3]     .D==eER   .  .   cneg w0, w0, lt
[0,4]     .D===eER  .  .   cmp  w0, #0
[0,5]     .D====eER .  .   b.le #12
[0,6]     . DeE---R .  .   mov  w1, #1
[0,7]     . DeE---R .  .   b    #48
[0,8]     . D==eE-R .  .   tbz  w0, #31, #12
[0,9]     .  DeE--R .  .   mov  w1, #-1
[0,10]    .  DeE--R .  .   b    #36
[0,11]    .  D=eE-R .  .   sub  x0, x4, x5
[0,12]    .   D=eER .  .   cmp  x0, #0
[0,13]    .   D==eER.  .   cset w0, ne
[0,14]    .   D===eER  .   cneg w0, w0, lt
[0,15]    .    D===eER .   cmp  w0, #0
[0,16]    .    D====eER.   csetm        w1, lt
[0,17]    .    D===eE-R.   cmp  w0, #0
[0,18]    .    .D===eER.   csinc        w1, w1, wzr, le
[0,19]    .    .D====eER   mov  x0, x1
[0,20]    .    .DeE----R   ret

โปรดสังเกตสาขาแบบมีเงื่อนไข 1 สาขา b.le ซึ่งหลีกเลี่ยงการเปรียบเทียบช่อง insertSeq หากทราบผลลัพธ์จากการเปรียบเทียบช่อง when แล้ว

The branchless code:
Index     012345678
[0,0]     DeER .  .   sub       x0, x2, x3
[0,1]     DeER .  .   sub       x1, x4, x5
[0,2]     D=eER.  .   cmp       x0, #0
[0,3]     .D=eER  .   cset      w0, ne
[0,4]     .D==eER .   cneg      w0, w0, lt
[0,5]     .DeE--R .   cmp       x1, #0
[0,6]     . DeE-R .   cset      w1, ne
[0,7]     . D=eER .   cneg      w1, w1, lt
[0,8]     . D==eeER   add       w0, w1, w0, lsl #1
[0,9]     .  DeE--R   ret

ในกรณีนี้ การใช้งานแบบไม่มี Branch จะใช้รอบและคำสั่งน้อยกว่าเส้นทางที่สั้นที่สุดผ่านโค้ดแบบมี Branch ซึ่งดีกว่าในทุกกรณี การติดตั้งใช้งานที่รวดเร็วขึ้นและการกำจัด Branch ที่คาดการณ์ผิดพลาดส่งผลให้การเปรียบเทียบประสิทธิภาพบางรายการของเราดีขึ้นถึง 5 เท่า


อย่างไรก็ตาม เทคนิคนี้อาจใช้ไม่ได้เสมอไป โดยทั่วไปแล้ว วิธีการแบบไม่มี Branch จะต้องทำงานที่จะถูกทิ้ง และหาก Branch คาดเดาได้เกือบตลอดเวลา งานที่เสียเปล่านั้นอาจทำให้โค้ดทำงานช้าลง นอกจากนี้ การนำสาขาออกมักจะทำให้เกิดการขึ้นต่อกันของข้อมูล CPU สมัยใหม่จะดำเนินการหลายอย่างต่อรอบ แต่จะดำเนินการตามคำสั่งไม่ได้จนกว่าอินพุตจากคำสั่งก่อนหน้าจะพร้อม ในทางตรงกันข้าม CPU สามารถคาดเดาเกี่ยวกับข้อมูลในสาขา และทำงานล่วงหน้าได้หากคาดการณ์สาขาได้อย่างถูกต้อง

การทดสอบและการตรวจสอบ

การตรวจสอบความถูกต้องของอัลกอริทึมแบบ Lock-Free เป็นเรื่องที่ยากมาก

นอกเหนือจาก Unit Test มาตรฐานสำหรับการตรวจสอบความถูกต้องอย่างต่อเนื่องในระหว่างการพัฒนาแล้ว เรายังเขียนการทดสอบความเครียดที่เข้มงวดเพื่อยืนยันค่าคงที่ของคิวและพยายามกระตุ้นให้เกิดสภาวะการแย่งชิงทรัพยากรหากมี ในห้องปฏิบัติการทดสอบ เราสามารถเรียกใช้อินสแตนซ์ทดสอบหลายล้านรายการในอุปกรณ์จำลองและในฮาร์ดแวร์จริง

ด้วยการใช้เครื่องมือ Java ThreadSanitizer (JTSan) เราสามารถใช้การทดสอบเดียวกันเพื่อตรวจหาการแย่งชิงข้อมูลในโค้ดได้ด้วย JTSan ไม่พบการแย่งใช้ทรัพยากรข้อมูลที่เป็นปัญหาใน DeliQueue แต่ที่น่าประหลาดใจคือตรวจพบบั๊กการทำงานพร้อมกัน 2 รายการในเฟรมเวิร์ก Robolectric ซึ่งเราได้แก้ไขทันที

เราได้สร้างเครื่องมือวิเคราะห์ใหม่เพื่อปรับปรุงความสามารถในการแก้ไขข้อบกพร่อง ด้านล่างนี้คือตัวอย่างที่แสดงปัญหาในโค้ดแพลตฟอร์ม Android ซึ่งเทรดหนึ่งโอเวอร์โหลดอีกเทรดหนึ่งด้วย Message ทำให้เกิดงานค้างจำนวนมาก ซึ่งมองเห็นได้ใน Perfetto ด้วยฟีเจอร์การวัด MessageQueue ที่เราเพิ่มเข้ามา

workspace.png

หากต้องการเปิดใช้การติดตาม MessageQueue ในกระบวนการ system_server ให้ใส่ข้อมูลต่อไปนี้ในการกำหนดค่า Perfetto

data_sources {
  config {
    name: "track_event"
    target_buffer: 0  # Change this per your buffers configuration
    track_event_config {
      enabled_categories: "mq"
    }
  }
}

ผลกระทบ

DeliQueue ช่วยปรับปรุงประสิทธิภาพของระบบและแอปโดยการนำการล็อกออกจาก MessageQueue

  • การเปรียบเทียบประสิทธิภาพแบบสังเคราะห์: การแทรกแบบหลายเธรดลงในคิวที่มีการใช้งานสูงจะเร็วขึ้นสูงสุด 5,000 เท่าเมื่อเทียบกับ MessageQueue เดิม เนื่องจากมีการปรับปรุงการทำงานพร้อมกัน (Treiber Stack) และการแทรกที่เร็วขึ้น (Min-heap)
  • ในการติดตาม Perfetto ที่ได้จากผู้ทดสอบเวอร์ชันเบต้าภายใน เราพบว่าเวลาที่เทรดหลักของแอปใช้ในการแย่งชิงล็อกลดลง 15%
  • ในอุปกรณ์ทดสอบเดียวกัน การแย่งชิงล็อกที่ลดลงส่งผลให้ประสบการณ์ของผู้ใช้ดีขึ้นอย่างมาก เช่น
    • เฟรมที่พลาดในแอปลดลง 4%
    • เฟรมที่หายไปลดลง 7.7% ในการโต้ตอบกับ UI ของระบบและ Launcher
    • เวลาตั้งแต่เริ่มต้นแอปจนถึงเฟรมแรกที่วาดลดลง 9.1% ที่เปอร์เซ็นไทล์ที่ 95

ขั้นตอนถัดไป

DeliQueue จะเปิดตัวในแอปใน Android 17 นักพัฒนาแอปควรอ่านบทความเรื่องการเตรียมแอปให้พร้อมสำหรับMessageQueueแบบใหม่ที่ไม่มีการล็อกในบล็อกของนักพัฒนาแอป Android เพื่อดูวิธีทดสอบแอปของตน

ข้อมูลอ้างอิง

[1] Treiber, R.K., 1986. การเขียนโปรแกรมระบบ: การรับมือกับความขนาน International Business Machines Incorporated, Thomas J. Watson Research Center

[2] Goetz, B., Peierls, T., Bloch, J., Bowbeer, J., Holmes, D., และ Lea, D. (2006). Java Concurrency in Practice Addison-Wesley Professional

เขียนโดย
อ่านต่อ