performance - أسرع خريطة C++؟




data-structures map (3)

تحذير هام: ما لم تقاس (ويشير سؤالك إلى أنك لم تقم بذلك) ، فإن أداء الخريطة يؤثر بشكل كبير على أداء التطبيق الخاص بك (نسبة كبيرة من الوقت الذي يتم إنفاقه على البحث وتحديث الخريطة) لا تهتم بجعله أسرع. عصا std::map (أو std::unordered_map أو أي تطبيق hash_map متاح). تسريع تطبيقك بنسبة 1٪ على الأرجح لن يكون مجديًا. جعلها خالية من الأخطاء بدلا من ذلك.

مرددا إجابة ريتشارد: قياس الأداء مع تنفيذ خريطة مختلفة باستخدام الطبقات الحقيقية والبيانات الحقيقية.

بعض الملاحظات الإضافية:

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

  • معرفة أين عنق الزجاجة الحقيقي هو. قد تكون تكلفة البحث في الخريطة ضئيلة مقارنة بتكلفة IO مثلاً.

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

في المثال الخاص بك (مفاتيح صحيحة 32 بت غير موقعة والتي يتم تجميعها بقوة ، على سبيل المثال يتم تعيينها بالتتابع) يمكنك استخدام المقاربة القائمة على أساس rad. مثال بسيط للغاية (قم بتهديده كتوضيح وليس جاهزًا لاستخدام الوصفة):

Item *sentinel[65536];  // sentinel page, initialized to NULLs.
Item (*pages[65536])[65536];  // list of pages,
                              // initialized so every element points to sentinel

ثم البحث هو بسيط مثل:

Item *value = pages[index >> 16][index & 0xFFFF];

عندما تحتاج إلى تعيين قيمة جديدة:

if (pages[index >> 16] == sentinel) {
  pages[index >> 16] = allocate_new_null_filled_page();
}
pages[index >> 16][index & 0xFFFF] = value;
  • قم بتعديل تطبيق خريطتك.

    • على سبيل المثال ، يحب كل hash_map معرفة العدد التقريبي للعناصر مقدمًا. يساعد على تجنب إعادة تخصيص غير ضرورية لجدول التجزئة و (ربما) إعادة صياغة جميع المفاتيح.

    • مع مثالي المتخصص أعلاه ، من المؤكد أنك ستحاول استخدام أحجام مختلفة للصفحة ، أو إصدار ثلاثة مستويات.

    • التحسين المشترك هو توفير مخصص الذاكرة المخصصة لتجنب تخصيصات متعددة من الكائنات الصغيرة.

صححني بأنني مخطئ ولكن std :: map هي خريطة مرتبة ، وهكذا في كل مرة أقوم بإدراج قيمة ، تستخدم الخريطة خوارزمية لفرز عناصرها داخليًا ، الأمر الذي يستغرق بعض الوقت.

يحصل طلبي على معلومات تتعلق ببعض العناصر على فاصل زمني ثابت.

يحتفظ هذا التطبيق بالخريطة التي يتم تعريفها على النحو التالي:

::std::map<DWORD, myItem*>

في البداية تعتبر كل العناصر "جديدة" للتطبيق. يتم تخصيص كائن "العنصر" وإضافته إلى هذه الخريطة ، مع ربط معرفه ومؤشر به.

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

في معظم الأحيان أحصل على التحديثات.

سؤالي هو:
هل هناك أي تنفيذ للخريطة أسرع أم يجب أن أستخدم هذا؟
هل من الأفضل استخدام unordered_map؟


هل من الأفضل استخدام unordered_map؟

ربما.

std:map توفر std:map أداءً ثابتًا في O (log n) لأنه يحتاج إلى التنفيذ كشجرة متوازنة. ولكن std:unordered_map سيتم تنفيذ std:unordered_map كجدول هاش قد يعطيك أداء O (1) (وظيفة هاش جيدة وتوزيع مفاتيح عبر دلاء التجزئة) ، ولكن يمكن أن يكون O (n) (كل شيء في دلو تجزئة واحد ويؤول إلى قائمة). يتوقع المرء عادة شيء ما بين هذه التطرف.

لذا يمكنك الحصول على أداء معقول (O (log n)) طوال الوقت ، أو تحتاج إلى التأكد من أن كل شيء يسير للحصول على أداء جيد مع التجزئة.

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


أولا ، عليك أن تتعلم التفكير مثل محامي اللغة.

مواصفات C ++ لا يشير إلى أي مترجم معين أو نظام التشغيل أو CPU. إنه يشير إلى آلة مجردة هي تعميم للأنظمة الفعلية. في عالم محامي اللغة ، وظيفة المبرمج هي كتابة الكود للجهاز التجريدي. وظيفة المترجم هي تفعيل هذا الرمز على آلة ملموسة. من خلال الترميز الصارم للمواصفات ، يمكنك التأكد من أن الكود الخاص بك سيتم تجميع وتشغيل بدون تعديل على أي نظام مع مترجم C ++ متوافق ، سواء اليوم أو 50 سنة من الآن.

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

بالطبع ، يمكنك كتابة رموز متعددة الخيوط في الممارسة لأنظمة خرسانة معينة - مثل pthreads أو Windows. ولكن لا توجد طريقة قياسية لكتابة تعليمة برمجية Multi-threaded لـ C ++ 98 / C ++ 03.

الجهاز التجريدي في C ++ 11 متعدد الخيوط حسب التصميم. كما أن لديها نموذج ذاكرة محددة جيدا. بمعنى ، ما يقوله المحول البرمجي وقد لا يفعل عندما يتعلق الأمر بالوصول إلى الذاكرة.

خذ بعين الاعتبار المثال التالي ، حيث يتم الوصول إلى زوج من المتغيرات العمومية بشكل متزامن بواسطة اثنين من مؤشرات الترابط:

           Global
           int x, y;

Thread 1            Thread 2
x = 17;             cout << y << " ";
y = 37;             cout << x << endl;

ما قد الناتج 2 الخيط؟

تحت C ++ 98 / C ++ 03 ، هذا ليس حتى السلوك غير المعرّف؛ السؤال نفسه لا معنى له لأن المعيار لا يتأمل أي شيء يسمى "الخيط".

تحت C ++ 11 ، تكون النتيجة سلوك غير محدد ، لأن الأحمال والمخازن لا يجب أن تكون ذرية بشكل عام. التي قد لا تبدو مثل الكثير من التحسن ... وفي حد ذاته ، ليس كذلك.

ولكن مع C ++ 11 ، يمكنك كتابة هذا:

           Global
           atomic<int> x, y;

Thread 1                 Thread 2
x.store(17);             cout << y.load() << " ";
y.store(37);             cout << x.load() << endl;

الآن أصبحت الأمور أكثر إثارة. بادئ ذي بدء ، يتم تعريف السلوك هنا. يمكن الآن قراءة مؤشر الترابط 2 0 0 (إذا كان يعمل قبل مؤشر الترابط 1) ، 37 17 (إذا كان يعمل بعد مؤشر ترابط 1) أو 0 17 (إذا كان يعمل بعد تعيين خيط 1 إلى x ولكن قبل تعيينها إلى y).

ما لا يمكن طباعته هو 37 0 ، لأن الوضع الافتراضي للأحمال / المخازن الذرية في C ++ 11 هو فرض الاتساق التتابعي . هذا يعني أن جميع الأحمال والمخازن يجب أن تكون "كما لو" ، فقد حدث بالترتيب الذي كتبته في كل موضوع ، في حين أن العمليات بين سلاسل الرسائل يمكن تشذيرها على الرغم من أن النظام يحبها. لذا فإن السلوك الافتراضي للذرات يوفر كل من الذرية وترتيب الأحمال والمخازن.

الآن ، على وحدة المعالجة المركزية الحديثة ، يمكن أن يكون ضمان الاتساق التسلسلي مكلفًا. على وجه الخصوص ، من المرجح أن ينبعث المترجم حواجز ذاكرة كاملة بين كل وصول هنا. ولكن إذا كانت خوارزميتك قادرة على تحمل الأحمال والمخازن غير المنتظمة ؛ بمعنى ، إذا كانت تتطلب ذرية ولكن لا تطلب ؛ بمعنى ، إذا كان بإمكانه تحمل 37 0 كإخراج من هذا البرنامج ، فيمكنك كتابة هذا:

           Global
           atomic<int> x, y;

Thread 1                            Thread 2
x.store(17,memory_order_relaxed);   cout << y.load(memory_order_relaxed) << " ";
y.store(37,memory_order_relaxed);   cout << x.load(memory_order_relaxed) << endl;

وكلما كانت وحدة المعالجة المركزية أكثر حداثة ، زادت احتمالية أن يكون هذا أسرع من المثال السابق.

أخيرًا ، إذا كنت تحتاج فقط إلى الاحتفاظ بأحمال ومخازن معينة بالترتيب ، فيمكنك كتابة:

           Global
           atomic<int> x, y;

Thread 1                            Thread 2
x.store(17,memory_order_release);   cout << y.load(memory_order_acquire) << " ";
y.store(37,memory_order_release);   cout << x.load(memory_order_acquire) << endl;

هذا يعيدنا إلى الأحمال والمخازن المطلوبة - لذلك لم يعد 37 0 مخرجًا محتملًا - ولكنه يفعل ذلك مع الحد الأدنى من الحمل. (في هذا المثال التافه ، تكون النتيجة هي نفس الاتساق التسلسلي الكامل ؛ في برنامج أكبر ، لن تكون كذلك).

بالطبع ، إذا كانت النواتج الوحيدة التي ترغب في مشاهدتها هي 0 0 أو 37 17 ، فيمكنك فقط التفاف كائن كتيب حول الرمز الأصلي. ولكن إذا كنت قد قرأت هذا الآن ، أراهن أنك تعرف بالفعل كيف يعمل هذا ، وهذه الإجابة هي بالفعل أطول مما كنت أقصد :-).

لذا ، بيت القصيد. Mutexes كبيرة ، و C ++ 11 يقيس لهم. ولكن في بعض الأحيان لأسباب تتعلق بالأداء تريد الأوليات الأولية (مثل نمط القفل الكلاسيكي المزدوج الفحص ). يوفر المعيار الجديد أدوات عالية المستوى مثل كائنات mutexes ومتغيرات الحالة ، كما يوفر أدوات ذات مستوى منخفض مثل الأنواع الذرية والنكهات المتنوعة لحاجز الذاكرة. حتى الآن ، يمكنك كتابة روتينات متزامنة عالية الأداء ومتزامنة تمامًا مع اللغة التي يحددها المعيار ، ويمكنك التأكد من أن التعليمة البرمجية الخاصة بك سيتم تجميعها وتشغيلها دون تغيير على كل من أنظمة اليوم وغدًا.

على الرغم من كونك صريحًا ، إلا إذا كنت خبيرًا وتعمل على بعض الشفرات الخطيرة ذات المستوى المنخفض ، فيجب عليك التمسك بمتغيري الكائنات المتغيرة والمتغيرات الشرطية. هذا ما أنوي فعله

لمزيد من المعلومات عن هذه الأشياء ، راجع مشاركة المدونة هذه .





c++ performance data-structures map