لماذا عادة ما يكون لها هياكل البيانات بحجم 2^n؟

https://stackoverflow.com/questions/1816727

08-07-2019
|

سؤال

هل هناك سبب تاريخي أو شيء من هذا القبيل؟ لقد رأيت عدة مرات مثل شيء مثل char foo[256]; أو #define BUF_SIZE 1024. حتى أنني أفعل في الغالب فقط 2^ن المخازن المؤقتة ذات الحجم ، في الغالب لأنني أعتقد أنه يبدو أكثر أناقة وبهذه الطريقة لا يجب أن أفكر في رقم محدد. لكنني لست متأكدًا مما إذا كان هذا هو السبب في أن معظم الناس يستخدمونها ، فسيتم تقدير مزيد من المعلومات.

المحلول

قد يكون هناك عدد من الأسباب ، على الرغم من أن الكثير من الناس سوف يفعلون ذلك فقط يفعلون ذلك من العادة.

أحد الأماكن التي يكون فيها مفيدًا للغاية في التنفيذ الفعال للمخازن المؤقتة الدائرية ، وخاصة على البنية حيث يكون مشغل ٪ مكلفًا (أولئك الذين ليس لديهم تقسيم للأجهزة - في المقام الأول 8 بت - التحكم الدقيق). باستخدام المخزن المؤقت 2^n في هذه الحالة ، فإن Modulo ، هو مجرد حالة من أجهزة التخزين العليا ، أو في حالة قول مخزن مؤقت للبايت 256 ، ببساطة باستخدام فهرس 8 بت والسماح له باللف.

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

نصائح أخرى

عادة ما تكون خطوط ذاكرة التخزين المؤقت بعضًا من 2 (غالبًا 32 أو 64). البيانات التي هي مضاعف لا يتجزأ من هذا الرقم ستكون قادرة على الملاءمة (والاستفادة الكاملة) العدد المقابل لخطوط ذاكرة التخزين المؤقت. كلما زاد عدد البيانات التي يمكنك حزمها في ذاكرة التخزين المؤقت الخاصة بك ، كان الأداء أفضل .. لذلك أعتقد أن الأشخاص الذين يصممون هياكلهم بهذه الطريقة يتحسنون لذلك.

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

أعتقد في النهاية أن السبب الهائل في معظم الحالات هو أن المبرمجين يحبون قوى اثنين.

جداول التجزئة ، تخصيص الصفحات

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

بالنظر إلى كتاب Intel I386 القديم ، and هي دورتين و div هو 40 دورة. يستمر التباين اليوم بسبب التعقيد الأساسي الأكبر بكثير للانقسام ، على الرغم من أن أوقات الدورة الإجمالية التي تبلغ 1000x أسرع تميل إلى إخفاء تأثير أبطأ الآلة.

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

وكما لاحظ آخرون ، فإن المبرمجين يحبون قوى اثنين.

أستطيع أن أفكر في بعض الأسباب خارج رأسي:

2^n هي قيمة شائعة جدًا في جميع أحجام الكمبيوتر. يرتبط هذا بشكل مباشر بالطريقة التي يتم تمثيل البتات في أجهزة الكمبيوتر (قيمتان محتملين) ، مما يعني أن المتغيرات تميل إلى أن يكون لها نطاقات من القيم التي تكون حدودها 2^n.
بسبب النقطة المذكورة أعلاه ، ستجد في كثير من الأحيان القيمة 256 باعتبارها حجم المخزن المؤقت. هذا لأنه أكبر عدد يمكن تخزينه في بايت. لذا ، إذا كنت ترغب في تخزين سلسلة مع حجم السلسلة ، فستكون أكثر كفاءة إذا قمت بتخزينها على النحو التالي: SIZE_BYTE+ARRAY, ، حيث يخبرك بايت الحجم بحجم الصفيف. هذا يعني أن الصفيف يمكن أن يكون أي حجم من 1 إلى 256.
في كثير من الأحيان ، يتم اختيار الأحجام استنادًا إلى الأشياء المادية (على سبيل المثال ، حجم الذاكرة الذي يمكن أن يختاره نظام التشغيل من بينه بحجم سجلات وحدة المعالجة المركزية وما إلى ذلك) وستكون أيضًا كمية محددة من بت. بمعنى ، فإن مقدار الذاكرة التي يمكنك استخدامها عادة ما تكون قيمة 2^n (لنظام 32 بت ، 2^32).
قد تكون هناك قضايا فوائد الأداء/المحاذاة لمثل هذه القيم. يمكن لمعظم المعالجات الوصول إلى كمية معينة من البايتات في وقت واحد ، لذلك حتى لو كان لديك متغير يكون حجمه هو أن نقول) 20 بت ، سيظل معالج 32 بت قراءة 32 بت ، بغض النظر عن ما. لذلك غالبًا ما يكون أكثر كفاءة في جعل المتغير 32 بت. أيضا ، بعض المعالجات يتطلب المتغيرات التي يجب محاذاة مع كمية معينة من البايتات (لأنها لا تستطيع قراءة الذاكرة ، على سبيل المثال ، عناوين في الذاكرة غريبة). بالطبع ، في بعض الأحيان لا يتعلق الأمر بمواقع ذاكرة فردية ، ولكن المواقع التي تتراوح بين 4 أو 6 من 8 ، وما إلى ذلك ، في هذه الحالات ، من المفيد صنع المخازن المؤقتة فقط دائماً تكون محاذاة.

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

بسبب البساطة (اقرأ أيضا كلفة) من القاعدة 2 الحساب في الإلكترونيات: التحول اليسار (اضرب بمقدار 2) ، التحول اليمين (تقسيم على 2).

في مجال وحدة المعالجة المركزية ، تدور الكثير من التركيبات حول الحساب القاعدة 2. غالبًا ما يتم محاذاة Busses (التحكم والبيانات) للوصول إلى بنية الذاكرة على الطاقة 2. كلفة من تنفيذ المنطق في الإلكترونيات (EG CPU) يجعل من الحساب في قاعدة 2 مقنعة.

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

لمعلوماتك: سمات النظام الذي يجلس في الطبقة X هي نتيجة مباشرة لـ الخادم سمات الطبقة للنظام تجلس أسفل الطبقة <x. السبب في أنني أقول أن هذا ينبع من بعض التعليقات التي تلقيتها فيما يتعلق بنشراتي.

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

كنت سأستخدم حجة التحول ، لكنني كنت أفكر في سبب وجيه لتبريرها.

شيء واحد لطيف في المخزن المؤقت الذي يمثل قوة اثنين هو أن معالجة المخزن المؤقت الدائرية يمكن أن تستخدم Simple و Slars Sepls:

#define BUFSIZE 1024

++index;                // increment the index.
index &= BUFSIZE;       // Make sure it stays in the buffer.

إذا لم تكن قوة اثنين ، فسيكون ذلك ضروريًا. في الأيام الخوالي (وحاليا على رقائق صغيرة) التي تهم.

من الشائع أيضًا أن تكون الصفحات قوى 2.

في Linux ، أحب استخدام getPagesize () عند القيام بشيء مثل تقطيع المخزن المؤقت وكتابته إلى مأخذ توصيل أو واصف ملف.

إنه يصنع رقمًا مستديرًا لطيفًا في القاعدة 2. تمامًا حيث أن 10 أو 100 أو 1000000 لطيفة ، وأرقام مستديرة في القاعدة 10.

إذا لم تكن قوة 2 (أو أي شيء قريب مثل 96 = 64+32 أو 192 = 128+64) ، فيمكنك أن تتساءل عن سبب وجود دقة إضافية. لا يمكن أن يأتي الحجم المستدير من القاعدة 2 من قيود خارجية أو جهل مبرمج. سترغب في معرفة أي واحد هو.

أشارت الإجابات الأخرى إلى مجموعة من الأسباب الفنية التي تكون صالحة في الحالات الخاصة. لن أكرر أي منهم هنا.

في جداول التجزئة ، يجعل 2^n من السهل التعامل مع مجموعات المفاتيح بطريقة معينة. بشكل عام ، عندما يكون هناك مجموعة أساسية ، فإنك إما تصنع بنية أساسية ، على سبيل المثال قائمة ، من جميع الإدخالات ذات قيمة التجزئة نفسها ؛ أو تجد فتحة مجانية أخرى. يمكنك فقط إضافة 1 إلى فهرس الفتحة حتى تجد فتحة مجانية ؛ لكن هذه الاستراتيجية ليست مثالية ، لأنها تخلق مجموعات من الأماكن المحظورة. تتمثل الإستراتيجية الأفضل في حساب رقم التجزئة الثاني H2 ، بحيث GCD (N ، H2) = 1 ؛ ثم أضف H2 إلى فهرس الفتحة حتى تجد فتحة مجانية (مع التفاف). إذا كانت N قوة 2 ، فإن العثور على H2 يفي GCD (N ، H2) = 1 سهل ، كل رقم فردي سيفعله.

مرخصة بموجب: CC-BY-SA مع الإسناد

لا تنتمي إلى StackOverflow