حول تنفيذ بنية بيانات الخريطة في V8

معيار ECMAScript 2015 ، والمعروفة باسم ES6، هناك العديد من الجديدة جافا سكريبت مجموعات مثل Map، Set، WeakMapو WeakSet. يبدو أنها إضافة رائعة لإمكانيات JavaScript القياسية. يتم استخدامها على نطاق واسع في العديد من المكتبات ، في التطبيقات ، في جوهر Node.js. سنتحدث اليوم عن المجموعة Map، ونحاول معرفة تفاصيل تنفيذها في V8 واستخلاص بعض الاستنتاجات العملية بناءً على المعرفة المكتسبة.



لا يوفر معيار ES6 مؤشرًا واضحًا للنهج الذي يجب اتباعه لتنفيذ دعم بنية البيانات Map. إنه يعطي فقط بعض التلميحات حول الطرق الممكنة لتنفيذه. يحتوي أيضًا على معلومات حول المتوقع منMapمقاييس الأداء:



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



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



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



قبل أن نبدأ ، أود أن أشير إلى أن ما سيتم مناقشته أدناه يشير إلى محرك V8 8.4 ، المدمج في نسخة مطورة جديدة من Node.js (بتعبير أدق ، نحن نتحدث عن الالتزام 238104c). لا تحتاج إلى توقع أي شيء خارج المواصفات.

الخوارزمية الأساسية لتطبيق الخريطة

بادئ ذي بدء ، سأقول أن هياكل البيانات Mapتستند إلى جداول التجزئة. أدناه أفترض أنك تعرف كيف تعمل جداول التجزئة. إذا لم تكن على دراية بجداول التجزئة ، فعليك أولاً أن تقرأ عنها ( هنا ، على سبيل المثال) ثم متابعة قراءة هذه المقالة فقط.



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



يستخدم V8 ما يسمى " جداول التجزئة الحتمية " التي اقترحها Tyler Close. يوضح الكود الكاذب التالي ، المستند إلى TypeScript ، هياكل البيانات الأساسية المستخدمة لتنفيذ جداول التجزئة هذه:

interface Entry {
    key: any;
    value: any;
    chain: number;
}
 
interface CloseTable {
    hashTable: number[];
    dataTable: Entry[];
    nextSlot: number;
    size: number;
}

هنا CloseTableتمثل الواجهة جدول تجزئة. يحتوي على مصفوفة hashTableحجمها يعادل عدد حاويات التجزئة. Nيتوافق عنصر المصفوفة مع الفهرس مع Nحاوية التجزئة -th ويخزن فهرس عنصر رأسه الموجود في المصفوفة dataTable. وتحتوي هذه المصفوفة على سجلات الجدول بالترتيب الذي أُدرجت فيه. يتم تقديم الإدخالات بواسطة الواجهة Entry. أخيرًا ، يحتوي كل إدخال على خاصية chainتشير إلى الإدخال التالي في سلسلة إدخالات حاوية التجزئة (أو بشكل أكثر دقة ، في قائمة مرتبطة بشكل فردي).



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



عند إزالة سجل من الجدول، يتم إزالته من dataTable(على سبيل المثال، عن طريق الكتابة إلى خصائصه keyو valueالقيم undefined). ثم يتم ربط الإدخال الذي يسبقه والمدخل الذي يليه ببعضهما البعض مباشرة. كما لاحظت ، هذا يعني أن جميع الإدخالات المحذوفة تستمر في شغل مساحة في ملف dataTable.



الآن للحصول على آخر قطعة من اللغز لدينا. عندما يمتلئ الجدول بالسجلات (الحالية والمحذوفة) ، يجب إعادة تجزئته (إعادة بنائه) مع زيادة حجمه. يمكن تغيير حجم الجدول إلى أسفل.



باستخدام هذا النهج ، يكون اجتياز بنية البيانات هو Mapنفسه اجتياز المصفوفة dataTable. وهذا يضمن الحفاظ على الترتيب الذي يتم به إدراج السجلات في الجدول واستيفاء المعيار. مع وضع ذلك في الاعتبار ، أتوقع أن تستخدم معظم محركات JS (إن لم يكن كلها) جداول التجزئة الحتمية كواحدة من آليات التنفيذ الأساسية Map.

البحث العملي للخوارزمية

دعنا نلقي نظرة على بعض الأمثلة لمساعدتنا على استكشاف الخوارزمية في الممارسة العملية. لنفترض أن لدينا CloseTableحاويتين تجزئة ( hastTable.length) ، تبلغ سعتها الإجمالية 4 عناصر ( dataTable.length). هذا الجدول مليء بالمحتوى التالي:

// ,    -, 
// ,     ,   function hashCode(n) { return n; }
table.set(0, 'a'); // => - 0 (0 % 2)
table.set(1, 'b'); // => - 1 (1 % 2)
table.set(2, 'c'); // => - 0 (2 % 2)

قد يبدو التمثيل الداخلي للجدول الذي تم الحصول عليه في هذا المثال كما يلي:

const tableInternals = {
    hashTable: [0, 1],
    dataTable: [
        {
            key: 0,
            value: 'a',
            chain: 2 //  <2, 'c'>
        },
        {
            key: 1,
            value: 'b',
            chain: -1 // -1    
        },
        {
            key: 2,
            value: 'c',
            chain: -1
        },
        //  
    ],
    nextSlot: 3, //    
    size: 3
}

إذا قمت بحذف سجل باستخدام الطريقة table.delete(0)، فسيبدو جدول التجزئة كما يلي:

const tableInternals = {
    hashTable: [0, 1],
    dataTable: [
        {
            key: undefined, //  
            value: undefined,
            chain: 2 
        },
        {
            key: 1,
            value: 'b',
            chain: -1
        },
        {
            key: 2,
            value: 'c',
            chain: -1
        },
        //  
    ],
    nextSlot: 3,
    size: 2 //  
}

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



يمكن تطبيق نفس النهج عند تنفيذ هياكل البيانات Set. الاختلاف الوحيد هو أن هياكل البيانات هذه لا تحتاج إلى خاصية value.



الآن بعد أن اكتشفنا ما وراء الكائنات Mapفي V8 ، نحن على استعداد للمضي قدمًا.

تفاصيل التنفيذ

تتم كتابة تنفيذ بنية البيانات Mapفي V8 بلغة C ++ ، وبعد ذلك يتم منح كود JS إمكانية الوصول إلى الآليات المقابلة. معظم الكود المرتبط Mapموجود في الفصول OrderedHashTableو OrderedHashMap. نحن نعلم بالفعل كيف تعمل هذه الفئات. إذا كنت تريد أن نلقي نظرة على نفسك مدوناتها، ثم يمكنك العثور عليها هنا ، هنا و هنا .



نظرًا لأننا مهتمون بشكل خاص بالتفاصيل العملية للتنفيذ Mapفي V8 ، نحتاج أولاً إلى فهم كيفية تعيين سعة الجدول.

سعة الجدول

في V8 ، تكون سعة جدول التجزئة (بنية البيانات Map) دائمًا قوة اثنين. إذا تحدثنا عن معدل استخدام حاويات التجزئة ، فسيتم تمثيلها دائمًا بالرقم 2. أي أن السعة القصوى للجدول 2 * number_of_bucketsهي ضعف عدد حاويات التجزئة. عند إنشاء كائن فارغ ، Mapتوجد حاويتا تجزئة في جدول التجزئة الداخلي الخاص به. نتيجة لذلك ، فإن سعة هذا الكائن تساوي 4 سجلات.



هناك قيود على السعة القصوى للكائنات Map. في أنظمة 64 بت ، سيكون هذا حوالي 16.7 مليون سجل. يرجع هذا القيد إلى خصائص تمثيل هياكل البيانات Mapفي الكومة. سنتحدث عنها لاحقا.



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



للتأكد من أن ما رأيته في الكود المصدري يعمل تمامًا كما فهمته ، قمت بتعديل رمز محرك V8 المدمج في Node.js ، مما جعله يحتوي على Mapخاصية جديدة bucketsمعلومات حول عدد حاويات التجزئة. يمكنك العثور على نتائج هذا التعديل هنا... في هذا التجميع الخاص لـ Node.js ، يمكن تشغيل البرنامج النصي التالي:

const map = new Map();
let prevBuckets = 0;
for (let i = 0; i < 100; i++) {
  if (prevBuckets !== map.buckets) {
    console.log(`size: ${i}, buckets: ${map.buckets}, capacity: ${map.buckets * 2}`);
    prevBuckets = map.buckets;
  }
  map.set({}, {});
}

يقوم هذا البرنامج النصي ببساطة بإدراج Map100 سجل في بنية البيانات . هذا ما يتم عرضه في الكونسول بعد تشغيله:

$ ./node /home/puzpuzpuz/map-grow-capacity.js
size: 0, buckets: 2, capacity: 4
size: 5, buckets: 4, capacity: 8
size: 9, buckets: 8, capacity: 16
size: 17, buckets: 16, capacity: 32
size: 33, buckets: 32, capacity: 64
size: 65, buckets: 64, capacity: 128

كما ترى ، عندما يمتلئ الجدول ، فإنه مع كل تغيير في حجمه ، يزيد بمقدار الضعف. لنحاول الآن تقليص الجدول بإزالة العناصر منه:

const map = new Map();
for (let i = 0; i < 100; i++) {
  map.set(i, i);
}
console.log(`initial size: ${map.size}, buckets: ${map.buckets}, capacity: ${map.buckets * 2}`);
 
let prevBuckets = 0;
for (let i = 0; i < 100; i++) {
  map.delete(i);
  if (prevBuckets !== map.buckets) {
    console.log(`size: ${map.size}, buckets: ${map.buckets}, capacity: ${map.buckets * 2}`);
    prevBuckets = map.buckets;
  }
}

هذا ما سيخرجه هذا البرنامج النصي:

$ ./node /home/puzpuzpuz/map-shrink-capacity.js
initial size: 100, buckets: 64, capacity: 128
size: 99, buckets: 64, capacity: 128
size: 31, buckets: 32, capacity: 64
size: 15, buckets: 16, capacity: 32
size: 7, buckets: 8, capacity: 16
size: 3, buckets: 4, capacity: 8
size: 1, buckets: 2, capacity: 4

هنا ، مرة أخرى ، يمكنك أن ترى أن حجم الجدول يتم تصغيره في كل مرة يحتوي على عدد أقل من number_of_buckets / 2العناصر.

دالة تجزئة

حتى الآن ، لم نتطرق إلى مسألة كيفية حساب V8 لرموز التجزئة للمفاتيح المخزنة في الكائنات Map. وهذا سؤال مهم.



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



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



وأخيرًا ، بالنسبة للكائنات ، يتم حساب التجزئة بناءً على رقم عشوائي ، ثم يتم تخزين ما يحدث مؤقتًا في الرأس الداخلي.

التعقيد الزمني للعمليات باستخدام كائنات الخريطة

تتطلب معظم العمليات التي يتم إجراؤها على هياكل البيانات Map، مثل setأو deleteتتطلب البحث من خلال هياكل البيانات هذه. كما هو الحال مع جداول التجزئة "الكلاسيكية" ، فإن التعقيد الزمني للبحث في حالتنا هو O(1).



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



من ناحية أخرى ، في أفضل سيناريو ، عندما يكون الجدول ممتلئًا ولا يوجد سوى سجلين في كل حاوية تجزئة ، فإن العثور على سجل يتطلب خطوتين فقط.



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

استهلاك الذاكرة

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





المصفوفة المستخدمة لتخزين هياكل بيانات الخريطة في الذاكرة



للأجزاء الفردية من المصفوفة الأغراض التالية:

• الرأس: يحتوي على معلومات عامة ، مثل عدد حاويات التجزئة أو عدد العناصر التي تمت إزالتها من Map.
• تفاصيل حاوية التجزئة: هذا هو المكان الذي نخزن فيه البيانات حول الحاويات التي تتوافق مع المصفوفة hashTableمن مثالنا.
• إدخالات جدول التجزئة: هذا هو المكان الذي يتم فيه تخزين البيانات المقابلة للمصفوفة dataTable. وهي تحتوي على معلومات حول إدخالات جدول التجزئة. يحتل كل سجل ثلاث خلايا في المصفوفة. أحدهما يخزن المفتاح ، والثاني يخزن القيمة ، والثالث يخزن "المؤشر" إلى السجل التالي في السلسلة.

إذا تحدثنا عن حجم المصفوفة ، فيمكن تقديرها تقريبًا كـ N * 3,5. هنا Nقدرة الجدول. لفهم ما يعنيه هذا من حيث استهلاك الذاكرة ، دعنا نتخيل أن لدينا نظام 64 بت وتم تعطيل ميزة ضغط المؤشر في V8 . في هذه الحالة ، هناك حاجة إلى 8 بايت لتخزين كل عنصر من عناصر المصفوفة. نتيجة لذلك Map، يلزم 29 ميغابايت من ذاكرة الكومة لتخزين بنية بيانات مع ما يقرب من مليون سجل.

النتيجة

في هذه المقالة ، قمنا بتغطية الكثير من الأشياء المتعلقة بهيكل البيانات Mapفي JavaScript. دعونا نلخص:

• Mapيستخدم V8 جداول التجزئة القطعية للتنفيذ . من المحتمل جدًا أن يتم تنفيذ بنية البيانات هذه أيضًا في محركات JS الأخرى.
• يتم تنفيذ الآليات التي تدعم العمل Mapفي C ++ ، وبعد ذلك يتم تقديمها كواجهة برمجة تطبيقات يمكن الوصول إليها من JavaScript.
• إذا تحدثنا عن التعقيد الزمني للعمليات التي يتم إجراؤها باستخدام الكائنات Map، فعندها يكون لها تعقيد ، وكذلك عند العمل مع جداول التجزئة "الكلاسيكية" O(1). في هذه الحالة ، يكون التعقيد الزمني لعملية التجزئة هو O(N).
• 64- Map 1 29 , .
• , , Set.

Map JavaScript-?