نظرة على التفاصيل: ميزة MessageQueue بدون قفل في Android 17

في Android 17، ستحصل التطبيقات التي تستهدف الإصدار 37 من حزمة SDK أو إصدارًا أحدث على تنفيذ جديد لـ MessageQueue بدون قفل. يؤدي التنفيذ الجديد إلى تحسين الأداء وتقليل عدد اللقطات المفقودة، ولكنّه قد يؤدي إلى تعطُّل البرامج التي تستخدم الحقول والطرق الخاصة في MessageQueue. لمزيد من المعلومات حول التغيير في السلوك وكيفية الحدّ من تأثيره، اطّلِع على مستندات التغيير في سلوك MessageQueue. يقدّم منشور المدوّنة الفني هذا نظرة عامة على إعادة تصميم MessageQueue وكيفية تحليل مشاكل التنافس على القفل باستخدام Perfetto.

يتحكّم Looper في سلسلة واجهة المستخدم لكل تطبيق Android. فهي تسحب العمل من MessageQueue، وترسله إلى Handler، وتكرر ذلك. على مدار عقدين من الزمن، استخدمت MessageQueue قفل شاشة واحدًا (أي مجموعة رموز synchronized) لحماية حالتها.

يقدّم Android 17 تحديثًا مهمًا لهذا المكوّن: تنفيذ بدون قفل يُسمى DeliQueue.

يشرح هذا المنشور كيف تؤثر عمليات القفل في أداء واجهة المستخدم، وكيفية تحليل هذه المشاكل باستخدام Perfetto، والخوارزميات وعمليات التحسين المحدّدة المستخدَمة لتحسين سلسلة التعليمات الرئيسية في Android.

المشكلة: تنازع القفل وعكس الأولوية

كانت واجهة برمجة التطبيقات MessageQueue القديمة تعمل كقائمة انتظار ذات أولوية محمية بدالة استبعاد متبادل واحدة. إذا نشر مؤشر ترابط في الخلفية رسالة أثناء إجراء مؤشر الترابط الرئيسي صيانة لقائمة الانتظار، يحظر مؤشر الترابط في الخلفية مؤشر الترابط الرئيسي.

عندما يتنافس مؤشران أو أكثر على الاستخدام الحصري للقفل نفسه، يُطلق على ذلك اسم تنازع القفل. ويمكن أن يؤدي هذا التنافس إلى انعكاس الأولوية، ما يؤدي إلى حدوث مشاكل في واجهة المستخدم ومشاكل أخرى في الأداء.

يمكن أن تحدث مشكلة "قلب الأولويات" عندما تضطر سلسلة تعليمات ذات أولوية عالية (مثل سلسلة واجهة المستخدم) إلى انتظار سلسلة تعليمات ذات أولوية منخفضة. لنفترض التسلسل التالي:

1. يحصل مؤشر ترابط في الخلفية ذو أولوية منخفضة على قفل MessageQueue لنشر نتيجة العمل الذي قام به.
2. يصبح مؤشر ترابط متوسط الأولوية قابلاً للتشغيل ويخصّص له برنامج جدولة النواة وقت وحدة المعالجة المركزية، ما يؤدي إلى استباق مؤشر الترابط المنخفض الأولوية.
3. تُنهي سلسلة واجهة المستخدم ذات الأولوية العالية مهمتها الحالية وتحاول القراءة من قائمة الانتظار، ولكن يتم حظرها لأنّ سلسلة التعليمات ذات الأولوية المنخفضة تحتفظ بدالة الاستبعاد المتبادل.

تحظر سلسلة التعليمات ذات الأولوية المنخفضة سلسلة واجهة المستخدم، ويؤدي العمل ذو الأولوية المتوسطة إلى تأخيرها أكثر.

تحليل التنافس باستخدام Perfetto

يمكنك تشخيص هذه المشاكل باستخدام Perfetto. في عملية التتبُّع العادية، يدخل سلسلة التعليمات المحظورة على قفل الشاشة في حالة السكون، وتعرض أداة Perfetto شريحة تشير إلى مالك القفل.

عند طلب بيانات التتبُّع، ابحث عن الشرائح التي تحمل الاسم "monitor contention with …" (مراقبة التنافس مع …) متبوعة باسم سلسلة التعليمات التي تملك القفل وموقع الرمز الذي تم الحصول على القفل منه.

دراسة حالة: بطء مشغّل التطبيقات

للتوضيح، دعنا نحلل تتبعًا حيث واجه المستخدم مشكلة في التنقل إلى الصفحة الرئيسية على هاتف Pixel مباشرة بعد التقاط صورة في تطبيق الكاميرا. أدناه نرى لقطة شاشة لـ Perfetto تعرض الأحداث التي أدت إلى الإطار المفقود:

• المشكلة: لم يلتزم سلسلة التعليمات الرئيسية في مشغّل التطبيقات بالموعد النهائي للإطار. تم حظرها لمدة 18 ملي ثانية، وهو ما يتجاوز الموعد النهائي البالغ 16 ملي ثانية المطلوب للعرض بمعدل 60 هرتز.
• التشخيص: أظهرت أداة Perfetto أنّ سلسلة التعليمات الرئيسية محظورة بسبب قفل MessageQueue. كان مؤشر ترابط "BackgroundExecutor" يملك القفل.
• السبب الأساسي: يتم تشغيل BackgroundExecutor في Process.THREAD_PRIORITY_BACKGROUND (أولوية منخفضة جدًا). نفّذ مهمة غير عاجلة (التحقّق من المدة القصوى لاستخدام التطبيقات). في الوقت نفسه، كانت سلاسل المحادثات ذات الأولوية المتوسطة تستخدم وقت وحدة المعالجة المركزية لمعالجة البيانات من الكاميرا. أوقف برنامج جدولة نظام التشغيل سلسلة مهام BackgroundExecutor لتشغيل سلاسل مهام الكاميرا.

أدّى هذا التسلسل إلى حظر سلسلة واجهة المستخدم في 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;

يمكنك استخدام نموذجك اللغوي الكبير المفضّل لكتابة طلبات PerfettoSQL للعثور على أنماط أخرى.

في Google، نستخدم BigTrace لتشغيل طلبات بحث PerfettoSQL على ملايين عمليات التتبُّع. ومن خلال ذلك، تأكّدنا من أنّ ما لاحظناه بشكل فردي كان في الواقع مشكلة في النظام. وكشفت البيانات أنّ تنازع القفل في MessageQueue يؤثر في المستخدمين في جميع أنحاء المنظومة المتكاملة، ما يؤكد الحاجة إلى تغيير أساسي في البنية.

الحلّ: التزامن بدون قفل

لقد عالجنا مشكلة التنافس في MessageQueue من خلال تنفيذ بنية بيانات خالية من القفل، وذلك باستخدام عمليات الذاكرة الذرية بدلاً من الأقفال الحصرية لمزامنة الوصول إلى الحالة المشتركة. تكون بنية البيانات أو الخوارزمية خالية من القفل إذا كان بإمكان سلسلة محادثات واحدة على الأقل إحراز تقدّم دائمًا بغض النظر عن سلوك جدولة سلاسل المحادثات الأخرى. يصعب تحقيق هذه الخاصية بشكل عام، ولا تستحق عادةً السعي لتحقيقها في معظم الرموز البرمجية.

الأساسيات الذرية

غالبًا ما تعتمد البرامج الخالية من القفل على أساسيات القراءة والتعديل والكتابة الذرية التي توفرها الأجهزة.

في الجيل القديم من وحدات المعالجة المركزية ARM64، كانت العمليات الذرية تستخدم حلقة Load-Link/Store-Conditional (LL/SC). تحمّل وحدة المعالجة المركزية قيمة وتضع علامة على العنوان. إذا كتب مؤشر ترابط آخر إلى هذا العنوان، يفشل المتجر، وتتم إعادة محاولة الحلقة. بما أنّ سلاسل التعليمات يمكنها مواصلة المحاولة والنجاح بدون انتظار سلسلة تعليمات أخرى، فإنّ هذه العملية خالية من القفل.

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) مع إضافات النظام الكبيرة (LSE) التي تتضمّن تعليمات في شكل "المقارنة والتبديل" (CAS) أو "التحميل والإضافة" (الموضّحة أدناه). في Android 17، أضفنا إمكانية استخدام برنامج تجميع "وقت تشغيل Android" ‏(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 تعتمد على هذه التعليمات وغيرها من تعليمات وحدة المعالجة المركزية المتخصّصة.

بنية البيانات: DeliQueue

لإزالة تنازع القفل من MessageQueue، صمّم مهندسونا بنية بيانات جديدة تُسمى DeliQueue. يفصل DeliQueue بين إدراج Message ومعالجة Message:

1. قائمة Messages (مكدّس Treiber): مكدّس بدون قفل. يمكن لأي سلسلة محادثات إرسال Messages جديد هنا بدون أي تعارض.
2. قائمة الانتظار ذات الأولوية (كومة الحد الأدنى): كومة من 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]، متاحة على الإنترنت وتم إصدارها للنطاق العام

يمكن لأي منتج دفع Messages جديدة إلى المكدس في أي وقت. يشبه ذلك سحب تذكرة من عدّاد الأطعمة الجاهزة، حيث يتم تحديد رقمك حسب وقت حضورك، ولكن ليس بالضرورة أن يتطابق الترتيب الذي تحصل فيه على طعامك. بما أنّها حزمة مرتبطة، فإنّ كل Message هو حزمة فرعية، ويمكنك معرفة شكل قائمة انتظار Message في أي وقت من خلال تتبُّع الرأس والتكرار للأمام، ولن تظهر لك أي Message جديدة في الأعلى، حتى إذا تمت إضافتها أثناء التنقّل.

Dequeue: bulk transfer to a min-heap

للعثور على Message التالي المطلوب معالجته، يعالج Looper Messages الجديد من حزمة Treiber من خلال الانتقال إلى الحزمة بدءًا من الأعلى والتكرار حتى يعثر على آخر Message تمت معالجته سابقًا. عندما ينتقل Looper إلى أسفل الحزمة، يُدرج Message في الكومة الصغرى المرتبة حسب الموعد النهائي. بما أنّ Looper يملك الكومة حصريًا، فإنّه يرتّب ويعالج Message بدون أقفال أو عمليات ذرية.

عند الانتقال إلى أسفل الحزمة، ينشئ Looper أيضًا روابط من Messages المكدّسة إلى العناصر السابقة، وبالتالي يشكّل قائمة مرتبطة بشكل مزدوج. يُعد إنشاء القائمة المرتبطة آمنًا لأن الروابط التي تشير إلى أسفل المكدس تتم إضافتها عبر خوارزمية مكدس Treiber مع CAS، ولا تتم قراءة الروابط الموجودة أعلى المكدس وتعديلها إلا بواسطة سلسلة المحادثات Looper. بعد ذلك، يتم استخدام هذه الروابط الخلفية لإزالة Message من نقاط عشوائية في الحزمة في وقت O(1).

يوفّر هذا التصميم إدراج O(1) للمنتجين (سلاسل المحادثات التي تنشر العمل في قائمة الانتظار) ومعالجة O(log N) مُستهلَكة للمستهلك (Looper).

إنّ استخدام كومة الحد الأدنى لترتيب Message يعالج أيضًا عيبًا أساسيًا في MessageQueue القديم، حيث تم الاحتفاظ بـ Message في قائمة مرتبطة بشكل فردي (متجذرة في الأعلى). في التنفيذ القديم، كانت الإزالة من الرأس O(1)، ولكن الإدراج كان في أسوأ حالاته O(N)، ما أدى إلى تراجع الأداء في قوائم الانتظار المزدحمة. في المقابل، يتم قياس الإدراج والإزالة من الكومة الصغرى بشكل لوغاريتمي، ما يوفر متوسط أداء تنافسي ولكنه يتفوق حقًا في زمن الاستجابة في الذيل.

في تنفيذ قائمة الانتظار القديمة، استخدم المنتجون والمستهلك قفلًا لتنسيق الوصول الحصري إلى القائمة المرتبطة بشكل فردي. في DeliQueue، يتعامل مكدس Treiber مع الوصول المتزامن، ويتعامل المستهلك الفردي مع طلب قائمة انتظار العمل الخاصة به.

الإزالة: الاتساق من خلال علامات الحذف

‫DeliQueue هي بنية بيانات مختلطة تجمع بين مكدّس Treiber بدون قفل وكومة صغرى أحادية السلسلة. إنّ الحفاظ على مزامنة هذين الهيكلَين بدون قفل عام يمثّل تحديًا فريدًا: قد تكون الرسالة موجودة فعليًا في المكدّس ولكن تمت إزالتها منطقيًا من قائمة الانتظار.

لحلّ هذه المشكلة، يستخدم DeliQueue أسلوبًا يُسمّى "tombstoning". يتتبّع كل Message موضعه في الحزمة من خلال المؤشرات الخلفية والأمامية، وفهرسه في مصفوفة الكومة، وعلامة منطقية تشير إلى ما إذا تمت إزالته. عندما يكون Message جاهزًا للتشغيل، سيقوم سلسلة التعليمات Looper بإجراء CAS على علامة الإزالة، ثم إزالته من الكومة والمكدس.

عندما يحتاج مؤشر ترابط آخر إلى إزالة Message، لا يتم استخراجه على الفور من بنية البيانات. بدلاً من ذلك، يتم تنفيذ الخطوات التالية:

1. الإزالة المنطقية: يستخدم سلسلة التعليمات CAS لضبط علامة إزالة Message من خطأ إلى صحيح بشكل ذري. يبقى Message في بنية البيانات كدليل على إزالته في انتظار المراجعة، وهو ما يُعرف باسم "شاهد القبر". بعد وضع علامة على Message لإزالته، يتعامل DeliQueue معه كما لو أنّه لم يعُد موجودًا في قائمة الانتظار كلما تم العثور عليه.
2. التنظيف المؤجَّل: تقع مسؤولية الإزالة الفعلية من بنية البيانات على عاتق سلسلة المحادثات Looper، ويتم تأجيلها إلى وقت لاحق. بدلاً من تعديل المكدّس أو الذاكرة المؤقتة، يضيف مؤشر ترابط الإزالة Message إلى مكدّس قائمة حرة آخر غير مقفل.
3. الإزالة الهيكلية: يمكن فقط لـ Looper التفاعل مع الكومة أو إزالة العناصر من المكدس. وعندما يستأنف نشاطه، يمحو القائمة الحرة ويعالج Message التي تحتوي عليها. بعد ذلك، يتم إلغاء ربط كل Message من الحزمة وإزالته من الذاكرة المؤقتة.  

يحافظ هذا النهج على إدارة كومة الذاكرة المؤقتة في سلسلة تعليمات واحدة. ويقلل من عدد العمليات المتزامنة وحواجز الذاكرة المطلوبة، مما يجعل المسار الحرج أسرع وأبسط.

Traversal: benign Java memory model data races

تتضمّن معظم واجهات برمجة التطبيقات المتزامنة، مثل Future في مكتبة Java العادية أو Job وDeferred في Kotlin، آلية لإلغاء العمل قبل اكتماله. يتطابق مثيل إحدى هذه الفئات بنسبة 1:1 مع وحدة من العمل الأساسي، ويؤدي استدعاء cancel على عنصر إلى إلغاء العمليات المحدّدة المرتبطة به.

تحتوي أجهزة Android الحالية على وحدات معالجة مركزية متعددة النواة وتتيح جمع البيانات المُهمَلة حسب الأجيال بشكل متزامن. ولكن عندما تم تطوير Android لأول مرة، كان من المكلف للغاية تخصيص كائن واحد لكل وحدة عمل. وبالتالي، تتيح فئة Handler في Android إلغاء الإشعارات من خلال العديد من عمليات التحميل الزائد لـ removeMessages، فبدلاً من إزالة Message محدّد، تتم إزالة جميع Message التي تتطابق مع المعايير المحدّدة. من الناحية العملية، يتطلّب ذلك تكرار جميع Message التي تم إدراجها قبل استدعاء removeMessages وإزالة العناصر المطابقة.

عند التكرار للأمام، يتطلب مؤشر الترابط عملية ذرية مرتبة واحدة فقط، لقراءة الرأس الحالي للمكدس. بعد ذلك، يتم استخدام قراءات الحقول العادية للعثور على Message التالي. إذا عدّل مؤشر ترابط Looper حقول next أثناء إزالة Message، لن تتم مزامنة عملية كتابة Looper وعملية قراءة مؤشر ترابط آخر، وهذا ما يُعرف باسم سباق البيانات. عادةً ما يكون سباق البيانات خطأً خطيرًا يمكن أن يسبب مشاكل كبيرة في تطبيقك، مثل التسريبات والحلقات اللانهائية والأعطال وحالات التجميد والمزيد. ومع ذلك، في ظل ظروف ضيقة معينة، يمكن أن تكون سباقات البيانات حميدة ضمن نموذج ذاكرة Java. لنفترض أنّنا بدأنا بمجموعة من:

ننفّذ قراءة ذرية للرأس، ونرى A. يشير مؤشر A التالي إلى B. في الوقت نفسه الذي نعالج فيه B، قد يزيل المتكرر B وC، عن طريق تحديث A للإشارة إلى C ثم D.

على الرغم من إزالة B وC منطقيًا، يحتفظ B بمؤشره التالي إلى C، وC إلى D. يواصل مؤشر القراءة التنقّل عبر العُقد التي تمت إزالتها وفصلها، ثم ينضم مجددًا إلى الحزمة النشطة في D. 

من خلال تصميم DeliQueue للتعامل مع حالات السباق بين التنقّل والإزالة، نسمح بالتكرار الآمن بدون قفل.

Quitting: Native refcount

يتم دعم Looper من خلال تخصيص أصلي يجب إخلاؤه يدويًا بعد إنهاء Looper. إذا كان هناك سلسلة محادثات أخرى تضيف Messages أثناء إنهاء Looper، يمكن أن تستخدم التخصيص الأصلي بعد إخلاء المساحة، وهو ما يمثّل انتهاكًا لأمان الذاكرة. نمنع ذلك باستخدام عدد مراجع مُصنَّف، حيث يتم استخدام جزء واحد من الذرة للإشارة إلى ما إذا كان Looper سيتم إنهاؤه.

قبل استخدام التخصيص الأصلي، يقرأ سلسلة التعليمات عدد المراجع الذري. إذا تم ضبط وحدة بت الإيقاف، يتم عرض أنّ Looper قيد الإيقاف ويجب عدم استخدام التخصيص الأصلي. وإذا لم يكن الأمر كذلك، فإنه يحاول استخدام CAS لزيادة عدد سلاسل المحادثات النشطة باستخدام التخصيص الأصلي. بعد تنفيذ ما يحتاج إليه، يقلل العدد. إذا تم ضبط وحدة بت الإنهاء بعد زيادتها ولكن قبل إنقاصها، وكان العدد الآن صفرًا، فسيتم تنشيط سلسلة المحادثات Looper.

عندما يكون سلسلة المحادثات Looper جاهزًا للخروج، يستخدم CAS لضبط بت الخروج في الذرة. إذا كان عدد المراجع 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). عندما تواجه وحدة المعالجة المركزية فرعًا شرطيًا، لا يمكنها معرفة ما إذا كان سيتم اتخاذ الفرع حتى يتم حساب الشرط، لذلك لا تعرف التعليمات التي يجب قراءتها بعد ذلك، وعليها التخمين باستخدام تقنية تسمى توقُّع الفرع. في حالة مثل البحث الثنائي، سيكون اتجاه الفرع مختلفًا بشكل غير متوقع في كل خطوة، لذلك من المحتمل أن تكون نصف التوقعات خاطئة. غالبًا ما يكون التنبؤ بالفرع غير فعال في خوارزميات البحث والفرز (مثل تلك المستخدمة في الكومة الصغرى)، لأن تكلفة التخمين الخاطئ أكبر من التحسن الناتج عن التخمين الصحيح. عندما يخطئ متوقّع الفروع في تخمينه، عليه التخلّص من العمل الذي قام به بعد افتراض القيمة المتوقّعة، والبدء من جديد من المسار الذي تم اتّباعه فعليًا، ويُعرف ذلك باسم تفريغ المسار.

للعثور على هذه المشكلة، حدّدنا معاييرنا باستخدام عدّاد الأداء branch-misses الذي يسجّل تتبُّع تسلسل استدعاء الدوال البرمجية عندما يخطئ متوقّع الفروع. بعد ذلك، عرضنا النتائج باستخدام 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;
}

لفهم عملية التحسين، فكِّك المثالَين في Compiler Explorer واستخدِم LLVM-MCA، وهو محاكي لوحدة المعالجة المركزية يمكنه إنشاء مخطط زمني تقديري لدورات وحدة المعالجة المركزية.

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 أضعاف في بعض معاييرنا!

ومع ذلك، لا يمكن تطبيق هذه الطريقة دائمًا. تتطلب الأساليب التي لا تحتوي على فروع بشكل عام القيام بعمل سيتم التخلص منه، وإذا كان الفرع قابلاً للتنبؤ به في معظم الأوقات، فقد يؤدي هذا العمل المهدر إلى إبطاء التعليمات البرمجية الخاصة بك. بالإضافة إلى ذلك، غالبًا ما تؤدي إزالة فرع إلى تبعية بيانات. تنفّذ وحدات المعالجة المركزية الحديثة عمليات متعددة في كل دورة، ولكن لا يمكنها تنفيذ تعليمات حتى تصبح مدخلاتها من تعليمات سابقة جاهزة. في المقابل، يمكن لوحدة المعالجة المركزية تخمين البيانات في الفروع، والعمل مسبقًا إذا تم توقّع فرع بشكل صحيح.

الاختبار والتحقّق من الصحة

يُعدّ التحقّق من صحة الخوارزميات الخالية من الأقفال أمرًا صعبًا للغاية.

بالإضافة إلى اختبارات الوحدات العادية للتحقّق المستمر أثناء التطوير، كتبنا أيضًا اختبارات ضغط صارمة للتحقّق من ثوابت قائمة الانتظار ومحاولة إحداث حالات سباق البيانات في حال وجودها. في مختبرات الاختبار، يمكننا تشغيل ملايين النُسخ الاختبارية على أجهزة محاكاة وأجهزة حقيقية.

باستخدام Java ThreadSanitizer (JTSan)، يمكننا استخدام الاختبارات نفسها لرصد بعض حالات السباق في الرمز البرمجي. لم تعثر أداة JTSan على أي حالات سباق بيانات في DeliQueue، ولكنها رصدت خطأين في التزامن في إطار عمل Robolectric، وقد تم إصلاحهما على الفور.

لتحسين إمكانات تصحيح الأخطاء، أنشأنا أدوات تحليل جديدة. في ما يلي مثال يوضّح مشكلة في رمز نظام Android الأساسي حيث يفرط أحد سلاسل المحادثات في تحميل سلسلة محادثات أخرى باستخدام Message، ما يتسبب في تراكم كبير، يظهر في 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.

• مقاييس الأداء الاصطناعية: عمليات الإدراج المتعدّدة في قوائم الانتظار المزدحمة أسرع بما يصل إلى 5,000 مرة من الإصدار القديم من MessageQueue، وذلك بفضل التزامن المحسّن (مكدّس Treiber) وعمليات الإدراج الأسرع (الكومة الصغرى).
• في عمليات تتبُّع Perfetto التي تم الحصول عليها من مختبِري الإصدار التجريبي الداخليين، نلاحظ انخفاضًا بنسبة %15 في الوقت الذي يقضيه سلسلة التعليمات الرئيسية للتطبيق في تنازع القفل.
• على أجهزة الاختبار نفسها، يؤدي تقليل تنازع القفل إلى تحسينات كبيرة في تجربة المستخدم، مثل:
  • ‫-4% من اللقطات المفقودة في التطبيقات
  • ‫-7.7% من اللقطات المفقودة في تفاعلات واجهة مستخدم النظام ومشغّل التطبيقات
  • ‫-9.1% في الوقت المستغرَق من بدء تشغيل التطبيق إلى رسم الإطار الأول، عند الشريحة المئوية 95

الخطوات التالية

يتم طرح DeliQueue في التطبيقات على Android 17. على مطوّري التطبيقات مراجعة مقالة "إعداد تطبيقك لاستخدام ميزة MessageQueue الجديدة التي لا تتطلّب قفل الجهاز" على مدوّنة مطوّري تطبيقات Android لمعرفة كيفية اختبار تطبيقاتهم.

المراجع

[1] Treiber, R.K., 1986. Systems programming: Coping with parallelism. International Business Machines Incorporated, Thomas J. مركز أبحاث واتسون.

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