من تقرير المطور الكبير سيرجي موريليوف ، يمكنك التعرف على الحاوية الترابطية متعددة الخيوط للمكتبة القياسية ، والتي يتم تطويرها كجزء من WG21. تحدث سيرجي عن إيجابيات وسلبيات الحلول الشائعة لهذه المشكلة والمسار الذي اختاره المطورون.
- ربما تكون قد خمنت بالفعل من العنوان الذي سيكون عليه تقرير اليوم حول كيفية قيامنا ، في إطار مجموعة العمل 21 ، بتكوين حاوياتنا على غرار std :: unordered_map ، ولكن من أجل بيئة متعددة الخيوط.
في العديد من لغات البرمجة - Java و C # و Python - هذا موجود بالفعل ويستخدم على نطاق واسع. لكن في C ++ الحبيبة ، الأسرع والأكثر إنتاجية ، لم يحدث هذا. لكننا استشرنا وقررنا فعل شيء من هذا القبيل.
قبل إضافة شيء ما إلى المعيار ، تحتاج إلى التفكير في كيفية استخدام الناس له. ثم لجعل واجهة أكثر صحة ، والتي من المرجح أن تعتمدها اللجنة - ويفضل دون أي تعديلات. وهكذا في النهاية لن يكون هناك شيء فعلوه بشيء ، لكن اتضح أنه شيء آخر.
الخيار الأكثر شهرة والمستخدمة على نطاق واسع هو التخزين المؤقت الحوسبة الثقيلة الكبيرة. هناك خدمة Memcached معروفة إلى حد ما تقوم ببساطة بتخزين استجابات خادم الويب في الذاكرة. من الواضح أنه يمكنك القيام بنفس الشيء تقريبًا على جانب التطبيق الخاص بك ، إذا كان لديك حاوية ترابطية تنافسية. كلا النهجين لهما إيجابيات وسلبيات. ولكن إذا لم يكن لديك مثل هذه الحاوية ، فسيتعين عليك إما صنع دراجتك الخاصة أو استخدام نوع من Memcached.
حالة الاستخدام الشائعة الأخرى هي إلغاء البيانات المكررة للحدث. أعتقد أن الكثيرين في هذه الغرفة يكتبون جميع أنواع الأنظمة الموزعة ويعرفون أن قوائم الانتظار الموزعة تستخدم في كثير من الأحيان للتواصل بين المكونات ، مثل Apache Kafka و Amazon Kinesis. تتميز هذه الميزة بأنها يمكن أن ترسل رسالة واحدة إلى مستهلك واحد عدة مرات. يتم استدعاء هذا مرة واحدة على الأقل للتسليم ، مما يعني ضمان التسليم مرة واحدة على الأقل: أكثر ممكن ، وأقل غير ممكن.
النظر في هذا من حيث الحياة الحقيقية. تخيل أن لدينا بعض الخلفية لبعض غرف الدردشة أو الشبكة الاجتماعية حيث تحدث الرسائل. يمكن أن يؤدي هذا إلى حقيقة أن شخصًا ما كتب رسالة وتلقى أحدهم إشعارًا لاحقًا على هواتفهم المحمولة عدة مرات. من الواضح أنه إذا رأى المستخدمون هذا ، فلن يكونوا سعداء بذلك. يقال أنه يمكن حل هذه المشكلة مع حاوية رائعة متعددة الخيوط.
الحالة التالية الأقل استخدامًا هي عندما نحتاج فقط إلى حفظ شيء ما في جانب الخادم ، وبعض البيانات التعريفية للمستخدم. على سبيل المثال ، يمكننا توفير الوقت الذي تمت مصادقة المستخدم آخر مرة فيه ، لفهم متى يجب أن يُطلب منه في المرة القادمة اسم المستخدم وكلمة المرور الخاصة به.
الخيار الأخير في هذه الشريحة هو الإحصاءات. من تطبيقات الحياة الحقيقية ، يمكن تقديم مثال للاستخدام في جهاز افتراضي من Facebook. لقد صنعوا آلة افتراضية كاملة لتحسين PHP وفي أجهزتهم الافتراضية ، حاولوا تدوين الوسيطات التي تم استدعاؤهم في جدول تجزئة متعدد الخيوط لجميع الوظائف المدمجة. وإذا كانت لديهم نتيجة في ذاكرة التخزين المؤقت ، فإنهم يحاولون إعطاؤها فورًا وعدم حساب أي شيء.
إضافة شيء كبير ومعقد إلى المعيار ليس سهلاً وليس سريعًا. كقاعدة عامة ، إذا تمت إضافة شيء كبير ، فإنه يمر بالمواصفات الفنية. حاليًا ، يتحرك المعيار كثيرًا لتوسيع دعم تعدد مؤشرات الترابط في المكتبة القياسية. وبالتحديد ، فإن الاقتراح P0260R3 حول قوائم الانتظار ذات مؤشرات الترابط المتعددة يتم الآن هناك. يتعلق هذا الاقتراح بهيكل بيانات مشابه جدًا لنا ، وقراراتنا للتصميم متشابهة جدًا من نواح كثيرة.
في الواقع ، أحد المفاهيم الأساسية لتصميمها هو أن واجهتها مختلفة عن قائمة الانتظار القياسية. ما هي النقطة؟ إذا نظرت إلى قائمة الانتظار القياسية ، ثم لاستخراج عنصر منها ، يلزمك إجراء عمليتين. ما عليك القيام به عملية أمامية لحساب ، وعملية البوب للحذف. إذا عملنا في ظل ظروف تعدد مؤشرات ترابط ، فقد يكون لدينا نوع من العمليات على قائمة الانتظار بين هاتين المكالمتين ، وقد يحدث أن نفكر في عنصر واحد ونحذف عنصرًا آخر ، والذي يبدو غير صحيح من الناحية المفاهيمية. لذلك ، تم استبدال هاتين المكالمتين هناك بواحدة ، وتمت إضافة عدد قليل من المكالمات من فئة try push و try pop. لكن الفكرة العامة هي أن الحاوية متعددة الخيوط لن تكون هي نفس الواجهة العادية.
تحتوي قوائم الانتظار متعددة مؤشرات الترابط أيضًا على العديد من التطبيقات المختلفة التي تحل العديد من المهام المختلفة. المهمة الأكثر شيوعًا هي مهمة المنتجين والمستهلكين ، عندما يكون لدينا بعض مؤشرات الترابط التي تنتج بعض المهام وهناك بعض مؤشرات الترابط التي تأخذ المهام من قائمة الانتظار ومعالجتها.
الحالة الثانية هي عندما نحتاج فقط إلى وجود قائمة انتظار متزامنة. في حالة المصنعين والمستهلكين ، نحصل على قائمة انتظار تقتصر على الجزء العلوي والسفلي. إذا حاولنا ، من الناحية النسبية ، الاستخراج من قائمة انتظار فارغة ، فسنذهب إلى حالة الانتظار. ونفس الشيء يحدث تقريبًا إذا حاولنا إضافة شيء لا يلائم قائمة الانتظار في الحجم.
أيضًا في هذا الاقتراح ، تم توضيح أنه لدينا واجهة منفصلة بشكل منفصل تتيح لنا التمييز بين التنفيذ الذي لدينا داخل القفل ، أو القفل المجاني. حقيقة أنه هنا في كل مكان في الاقتراح هو مكتوب قفل الحرة ، في الواقع ، هو مكتوب في كتب كما الانتظار مجانا. هذا يعني أن خوارزمية لدينا تعمل لعدد ثابت من العمليات. قفل مجاني يعني اختلافًا بسيطًا ، لكن هذا ليس هو الموضوع.
دعونا نلقي نظرة على رسم تخطيطي نموذجي لكيفية تنفيذ جدول التجزئة الخاص بنا إذا كان قد تم حظره. لدينا مقسمة إلى عدد من القطاعات. كل قطعة ، كقاعدة عامة ، تحتوي على نوع من القفل ، مثل Mutex ، Spinlock ، أو أي شيء أكثر صعوبة. بالإضافة إلى Mutex أو Spinlock ، فإنه يحتوي أيضًا على جدول التجزئة المعتاد ، والذي يحميه هذا العمل.
في هذه الصورة ، لدينا جدول تجزئة ، مصنوع في القوائم. في الواقع ، في تطبيقنا المرجعي ، كتبنا جدول تجزئة بعناوين مفتوحة لأسباب تتعلق بالأداء. اعتبارات الأداء هي في الأساس نفس السبب الذي يجعل std :: vector أسرع من std :: list لأن المتجه ، متحدثًا نسبيًا ، يتم تخزينه بالتتابع في الذاكرة. عندما نمضي قدماً ، لدينا وصول متسلسل ، يتم تخزينه بشكل جيد. إذا استخدمنا نوعًا من الأوراق ، فسنواجه جميع أنواع القفزات بين أقسام مختلفة من الذاكرة. وكل شيء ، كقاعدة عامة ، ينتهي بحقيقة أننا نفقد الإنتاجية.
في البداية ، عندما نريد العثور على شيء في جدول التجزئة هذا ، نأخذ رمز التجزئة من المفتاح. يمكنك أن تأخذها modulo وتفعل شيئًا آخر معها حتى نحصل على رقم القطعة ، وفي المقطع الذي نبحث عنه ، كما هو الحال في جدول تجزئة منتظم ، ولكن في نفس الوقت ، بالطبع ، نأخذ القفل.
الأفكار الرئيسية لتصميمنا. بالطبع ، لقد صنعنا أيضًا واجهة لا تتطابق مع std :: unordered_map. السبب هو هذا. على سبيل المثال ، في الأمراض المنقولة جنسياً :: unordered_map العادية ، لدينا شيء رائع مثل التكرارات. أولاً ، لا يمكن لجميع التطبيقات دعمها بشكل طبيعي. وتلك التي يمكن أن تدعم ، كقاعدة عامة ، هي نوع من التطبيقات الخالية من الأقفال التي تتطلب إما مجموعة من البيانات المهملة أو نوعًا من المؤشرات الذكية التي تقوم بتنظيف الذاكرة الموجودة خلفها.
بالإضافة إلى ذلك ، هناك عدة أنواع أخرى من العمليات التي طردناها. في الواقع ، التكرار ، هم في أماكن كثيرة. على سبيل المثال ، هم في جافا. ولكن ، كقاعدة ، الغريب ، أنها لا تتزامن هناك. وإذا حاولت القيام بشيء ما معهم من خيوط مختلفة ، فيمكنهم بسهولة الدخول في حالة غير صالحة ، ويمكنك الحصول على استثناء في Java ، وإذا كتبت هذا على الإيجابيات ، فسيكون هذا على الأرجح سلوكًا غير محدد ، وهو أمر أسوأ . وبالمناسبة ، فيما يتعلق بموضوع السلوك غير المحدد: في رأيي ، فإن الرفاق من فيسبوك في حماقة مكتبتهم ، والذي تم نشره في المصادر المفتوحة على جيثب ، فعلوا ذلك تمامًا. فقط انسخ الواجهة مع Java وحصلت على هذه التكرارات الرائعة.
ليس لدينا أيضًا شكوى تتعلق بالذاكرة ، أي إذا أضفنا شيئًا إلى الحاوية وأخذنا ذاكرة لها ، فلن نردها ، حتى لو حذفنا كل شيء. ومن المتطلبات الأخرى لهذا القرار أن يكون لدينا طاولة تجزئة مع معالجة مفتوحة من الداخل. إنه يعمل على بنية بيانات خطية ، مثل المتجهات لا تعيد الذاكرة.
اللحظة المفاهيمية التالية هي أنه في أي ظرف من الظروف لن نعطي أي شخص روابط خارجية ومؤشرات للأشياء الداخلية. تم القيام بذلك على وجه التحديد لمنع الحاجة إلى جمع القمامة ، وليس لفرض مؤشرات ذكية. من الواضح أننا إذا قمنا بتخزين بعض الأشياء الكبيرة بما فيه الكفاية ، فإن تخزينها حسب القيمة في الداخل لن يكون مربحًا. ولكن ، في هذه الحالة ، يمكننا دائمًا تغليفها بنوع من المؤشرات الذكية التي نختارها. وإذا أردنا ، على سبيل المثال ، القيام بنوع من المزامنة على القيم ، فيمكننا لفها في نوع من التعزيز :: synchronized_value.
نظرنا إلى حقيقة أنه منذ بعض الوقت ، تمت إزالة class_ptr class من الطريقة التي أرجعت عدد الروابط النشطة إلى هذا الكائن. وقد توصلنا إلى استنتاج مفاده أننا نحتاج أيضًا إلى التخلص من العديد من الوظائف ، وهي الحجم والعدد والفرز والباطل ، عدد مرات الظهور ، لأنه بمجرد أن نرجع هذه القيمة من الوظيفة ، فإنها تتوقف على الفور عن أن تكون صالحة ، لأن أي شخص يمكنه تغيير نفس اللحظة.
في أحد اجتماعاتنا السابقة ، طلبوا منا إضافة نوع من الوضع حتى نتمكن من الوصول إلى الحاوية الخاصة بنا في وضع الخيوط المفردة ، مثل std :: unordered_map العادية. مثل هذه الدلالات تسمح لنا بالتمييز بوضوح بين المكان الذي نعمل فيه في وضع متعدد مؤشرات الترابط وأين لا. ولتجنب بعض المواقف غير السارة عندما يأخذ الناس حاوية متعددة الخيوط ، توقع أن كل شيء سيكون على ما يرام معهم ، يأخذهم على التكرار ، ومن ثم فجأة اتضح أن كل شيء سيء.
في هذا الاجتماع في هاواي ، تم كتابة اقتراح كامل ضدنا. :) قيل لنا أن مثل هذه الأشياء ليس لها مكان في المعيار ، لأن هناك العديد من الطرق لجعل الحاوية الترابطية متعددة الخيوط.
لكل منها إيجابيات وسلبيات - وليس من الواضح كيفية استخدام ما نجحنا فيه في النهاية. كقاعدة عامة ، يتم استخدامه عندما تحتاج إلى نوع من الأداء الشديد. ويبدو أن حلنا المعبأ غير مناسب ، فمن الضروري تحسينه لكل حالة محددة.
النقطة الثانية من هذا الاقتراح هي أن واجهتنا لا تتوافق مع حقيقة أن Facebook نشر على GitHub من مكتبته القياسية.
في الواقع ، لم تكن هناك مشاكل خاصة هناك. كان هناك ببساطة سؤال من فئة "أنا لم أقرأ ، لكنني أدين". نظروا للتو - الواجهة مختلفة ، مما يعني أنها غير متوافقة.
كانت فكرة الاقتراح أيضًا أنه ينبغي حل المهام المماثلة بمساعدة ما يسمى بالتصميم المستند إلى السياسة ، عندما يكون من الضروري إنشاء معلمة قالب إضافية يمكنك من خلالها تمرير قناع بت مع الميزات التي نريد تمكينها وإيقافها. في الواقع ، يبدو هذا متوحشًا قليلاً ويؤدي إلى حقيقة أننا نحصل على حوالي 2 ^ n من التطبيقات ، حيث n هو عدد الميزات المختلفة.
في الكود ، يبدو شيء من هذا القبيل. لدينا نوع من المعلمة وبعض عدد الثوابت المحددة مسبقًا والتي يمكن تمريرها هناك. الغريب ، تم رفض هذا الاقتراح.
لأنه في الواقع ، اتخذت اللجنة بالفعل موقفًا مفاده أن مثل هذه الأمور يجب أن تكون عندما تنتقل قائمة الانتظار المتعددة الخيوط إلى لجنة الدراسات 1. لم يكن هناك حتى تصويت على هذه المسألة. لكن تم طرح سؤالين للتصويت.
أول واحد. أراد الكثير من الناس لنا إلى جانب تنفيذ مرجعنا لدعم القراءة دون اتخاذ أي أقفال. بحيث يكون لدينا قراءة غير قابلة للحظر تمامًا. من المنطقي حقًا: كقاعدة عامة ، حالة المستخدم الأكثر شيوعًا هي التخزين المؤقت. ومن المفيد جدًا أن تكون لدينا قراءة سريعة.
اللحظة الثانية. سمع الجميع الكثير من الصديق السابق الذي تحدث عن التصميم القائم على السياسة. كان لدى الجميع فكرة - ولكن ماذا ، دعني أتحدث عن فكرتي أيضًا! وصوت الجميع على أن يكون التصميم القائم على السياسة. على الرغم من أنه يجب أن يقال ، فإن هذه القصة برمتها مستمرة لبعض الوقت ، وكان زملاء إنتل ، آرت روبنسون وأنتون مالاخوف يفعلون ذلك من قبلنا. وكان لديهم بالفعل العديد من المقترحات حول هذا الموضوع. لقد عرضوا فقط إضافة تطبيق تأمين مجاني يستند إلى خوارزمية
SeepOrderedList . وكان لديهم أيضًا تصميم قائم على السياسة مع شكوى الذاكرة.
وهذا الاقتراح لم يعجبه مجموعة عمل Evolution Library. تم اختتامه لسبب أننا ببساطة سنحصل على زيادة غير محدودة في عدد الكلمات في المعيار. سيكون من المستحيل ببساطة معاينة كافية وتنفيذها ببساطة في التعليمات البرمجية.
ليس لدينا أي تعليقات على الأفكار نفسها. لدينا تعليقات ، بالنسبة للجزء الأكبر ، على التنفيذ المرجعي. وبالطبع ، لدينا بعض الأفكار التي يمكن تقديمها لجعلها أكثر وضوحًا. لكن في الأساس ، في المرة القادمة سنذهب مع نفس الاقتراح. نأمل مخلصين ألا يكون لدينا ، كما هو الحال مع الوحدات ، خمس مكالمات بنفس الاقتراح. نحن نؤمن بإخلاص في أنفسنا ، وأنهم سيسمحون لنا بالانتقال إلى المكالمة التالية ، وأن مجموعة العمل على تطوير المكتبات ستصر مع ذلك على رأينا ولن تسمح لنا بدفع التصميم القائم على السياسة. لأن خصمنا لا يتوقف. قرر أن يثبت للجميع أنه ضروري. ولكن كما يقولون ، فإن الوقت سوف اقول. لدي كل شيء ، شكرا لك على اهتمامك.