จากระบบภายใน: MessageQueue ที่ไม่มีการล็อกของ Android 17

ใน 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 ล่าช้าออกไปอีก

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

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

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

กรณีศึกษา: ความหน่วงของ Launcher

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

• อาการ: เทรดหลักของ 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 รุ่นเก่ากว่านี้ Atomics จะใช้ลูป 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 จะเร็วกว่าตัวแปร LL/SC ประมาณ 3 เท่า

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

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

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

1. รายการ Messages (Treiber stack): สแต็กที่ไม่มีการล็อก เธรดใดก็ได้สามารถส่ง Messages ใหม่มาที่นี่ได้โดยไม่มีการแย่งชิง
2. คิวลำดับความสำคัญ (Min-heap): 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: โอนไปยัง Min-Heap จำนวนมาก

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

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

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

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

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

การนำออก: ความสอดคล้องผ่านป้ายหลุมศพ

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

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

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

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

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

การข้าม: การแข่งขันข้อมูลในโมเดลหน่วยความจำ 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 และการอ่านของเธรดอื่นจะไม่ได้ซิงค์กัน ซึ่งถือเป็นการแข่งขันด้านข้อมูล โดยปกติแล้ว Data Race เป็นข้อบกพร่องร้ายแรงที่อาจทำให้เกิดปัญหาใหญ่ในแอป เช่น การรั่วไหล ลูปที่ไม่มีที่สิ้นสุด ข้อขัดข้อง การหยุดทำงาน และอื่นๆ อย่างไรก็ตาม ภายใต้เงื่อนไขที่จำกัดบางอย่าง การแข่งขันของข้อมูลอาจไม่เป็นอันตรายภายในโมเดลหน่วยความจำของ Java สมมติว่าเราเริ่มต้นด้วยกองซ้อนของ

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

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

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

การออก: Native refcount

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

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

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

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

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

ขณะพัฒนาและทดสอบ 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 พบการแยกสาขาแบบมีเงื่อนไข CPU จะไม่ทราบว่าควรใช้สาขาใดจนกว่าจะมีการคำนวณเงื่อนไข จึงไม่ทราบว่าจะอ่านคำสั่งใดต่อไปและต้องคาดเดาโดยใช้เทคนิคที่เรียกว่าการคาดคะเนการแยกสาขา ในกรณีเช่นการค้นหาแบบไบนารี ทิศทางของกิ่งก้านจะแตกต่างกันอย่างคาดเดาไม่ได้ในแต่ละขั้นตอน ดังนั้นจึงมีแนวโน้มที่การคาดคะเนครึ่งหนึ่งจะผิด การคาดการณ์กิ่งมักไม่มีประสิทธิภาพในอัลกอริทึมการค้นหาและการจัดเรียง (เช่น อัลกอริทึมที่ใช้ในกองขั้นต่ำ) เนื่องจากต้นทุนของการคาดการณ์ที่ผิดนั้นสูงกว่าการปรับปรุงจากการคาดการณ์ที่ถูกต้อง เมื่อตัวคาดการณ์กิ่งก้านคาดการณ์ผิด ก็จะต้องทิ้งงานที่ทำหลังจากสมมติค่าที่คาดการณ์ไว้ และเริ่มใหม่จากเส้นทางที่ใช้จริง ซึ่งเรียกว่าการล้างไปป์ไลน์

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

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

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

// 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

โปรดสังเกตสาขาแบบมีเงื่อนไข 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

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

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

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

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

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

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

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

หากต้องการเปิดใช้การติดตาม 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

• การทดสอบประสิทธิภาพสังเคราะห์: การแทรกแบบหลายเธรดลงในคิวที่มีการใช้งานสูงเร็วกว่า MessageQueue รุ่นเดิมถึง 5,000 เท่า เนื่องจากมีการปรับปรุงการทำงานพร้อมกัน (สแต็ก Treiber) และการแทรกที่เร็วขึ้น (กองข้อมูลแบบมินฮีป)
• ในการติดตาม 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

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