كيف يعمل Realloc و memcpy؟

Question

لدي سؤالان.

1. يفعل realloc() و memcpy() انسخ الإدخالات الموجودة في مصفوفة إلى أخرى بطريقة أسرع من مجرد التكرار على كل عنصر O(N) ؟إذا كانت الإجابة بنعم فما هو التعقيد في نظرك؟

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

Answer 1

1 - لا.يقومون بنسخ كتلة في وقت واحد.يرى http://www.embedded.com/design/configurable-systems/4024961/Optimizing-Memcpy-improves-speed لتحليل جيد جدا.

2- هذا يعتمد على التنفيذ.يرى http://www.gnu.org/software/libtool/manual/libc/Changing-Block-Size.html للحصول على تفاصيل glibc."في العديد من تطبيقات التخصيص، يتطلب تصغير الكتلة أحيانًا نسخها"

Answer 2

دعونا نلقي نظرة فاحصة قليلا memcpy وأثناء قيامنا بذلك، عند علامة "big O" أو تدوين Landau.

أولاً، كبير-O.كما تحدثت في مكان آخر، من الجدير أن نتذكر تعريف Big O، وهو أن بعض الوظائف ز (ن) يقال أنه يا (و (ن)) عندما يكون هناك ثابت ك لأي منهم ز (ن) ≤ كف (ن).ما يفعله الثابت هو أنه يتيح لك تجاهل التفاصيل الصغيرة لصالح الجزء المهم.وكما لاحظ الجميع، memcpy ل ن سوف يكون بايت على) في أي بنية عادية تقريبًا، لأنه بغض النظر عما يتعين عليك نقله ن بايت، قطعة واحدة في كل مرة.لذا، أول تنفيذ ساذج لـ memcpy في C يمكن كتابتها

unsigned char *
memcpy(unsigned char * s1, unsigned char * s2, long size){
    long ix;
    for(ix=0; ix < size; ix++)
        s1[ix] = s2[ix];
    return s1;
}

هذا في الواقع على), ، وقد يجعلك تتساءل عن سبب اهتمامنا بروتين المكتبة.ومع ذلك، فإن الشيء المتعلق libc الوظائف هي أنها المكان الذي تتم فيه كتابة الأدوات المساعدة الخاصة بالمنصة؛إذا كنت ترغب في تحسين البنية، فهذا أحد الأماكن التي يمكنك القيام فيها بذلك.لذا، اعتمادا على الهندسة المعمارية, قد تكون هناك خيارات تنفيذ أكثر كفاءة؛على سبيل المثال، في بنية IBM 360، يوجد MOVL التعليمات التي تنقل البيانات عبارة عن أجزاء كبيرة تستخدم رمزًا صغيرًا محسّنًا للغاية.لذا، بدلاً من تلك الحلقة، قد يبدو تطبيق memcpy 360 بدلاً من ذلك

LR 3,S1      LOAD S1 ADDR in Register 3
LR 4,S2      
MOVL 3,4,SIZE

(بالمناسبة، لا توجد ضمانات بأن كود 360 صحيح تمامًا، ولكنه سيكون بمثابة توضيح.) هذا التنفيذ تبدو مثل بدلا من القيام به ن خطوات حول الحلقة كما فعل كود C، فهو ينفذ فقط 3 تعليمات.

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

ولهذا السبب يمكنك الاستفادة منه بشكل جيد memcpy -- إنه ليس أسرع بشكل مقارب، ولكن التنفيذ يتم بأسرع ما يمكن لأي شخص القيام به على تلك العمارة بالذات.

Answer 3

1. لا توجد طريقة على الإطلاق لنسخ العناصر N بشكل أسرع من O(N).ومع ذلك، قد يكون قادرًا على نسخ عناصر متعددة مرة واحدة، أو استخدام تعليمات خاصة للمعالج - لذلك قد يظل أسرع مما يمكنك القيام به بنفسك.
2. لا أعرف على وجه اليقين، ولكن أفترض أن الذاكرة قد أعيد تخصيصها بالكامل.هذا هو الافتراض الأكثر أمانًا، وربما يعتمد على التنفيذ على أي حال.

Answer 4

1. اداء ال memcpy لا يمكن أن يكون حقًا أفضل من O(N) ولكن يمكن تحسينه بحيث يتفوق على النسخ اليدوي؛على سبيل المثال، قد يكون قادرًا على نسخ 4 بايت في الوقت الذي يستغرقه نسخ بايت واحد.كثير memcpy تتم كتابة التطبيقات مجمعة باستخدام تعليمات محسنة يمكنها نسخ عناصر متعددة في وقت واحد وهو عادة أسرع من نسخ البيانات بايت واحد في المرة الواحدة.

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

Answer 5

1. يمكن تخمين أنه يمكن كتابة memcpy بحيث يتحرك عدد كبير من البتات.على سبيل المثالمن الممكن تمامًا نسخ البيانات باستخدام تعليمات SSE، إذا كان ذلك مفيدًا.

كما قال آخرون، لن يكون أسرع من O(n)، لكن أنظمة الذاكرة غالبًا ما يكون لها حجم كتلة مفضل، ومن الممكن أيضًا، على سبيل المثال، كتابة حجم سطر ذاكرة التخزين المؤقت في المرة الواحدة.

Answer 6

بافتراض أنك تتحدث عن glibc، وبما أن أسئلتك تعتمد على التنفيذ، فمن الأفضل التحقق من المصدر فقط:

malloc.c

memcpy.c

من الطريقة التي قرأتها، ستكون الإجابات:

1. O(N) --- لا توجد طريقة لنسخ العناصر في وقت أفضل من الزمن الخطي.
2. في بعض الأحيان، سيتم نسخ العناصر الكبيرة عند استخدام realloc() لتقليصها.

Answer 7

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

تلك المستخدمة لنسخ الذاكرة هي movsb/movsw مع تعليمات مندوب.

CMPS/MOVS/SCAS/STOS
REP, REPE, REPNE, REPNZ, REPZ

يسجل الإعداد باستخدام عناوين src/trg وعدد int وتذهب بعيدًا.

Answer 8

بعض النقاط المهمة المتعلقة بإعادة التخصيص (تحقق من dev c++):void *realloc(void *ptr, size_t size);

1. يجب على وظيفة realloc() تغيير حجم كائن الذاكرة المشار إليه بواسطة ptr إلى الحجم المحدد حسب الحجم.

2. ويجب أن تظل محتويات القطعة دون تغيير حتى الحجم الأصغر من الحجم الجديد والقديم.

3. إذا كان الحجم الجديد أكبر، تكون محتويات الجزء المخصص حديثًا من الكائن غير محددة.

4. إذا كان الحجم 0 ولم يكن ptr مؤشرًا فارغًا، فسيتم تحرير الكائن المشار إليه.

5. إذا كان ptr مؤشرًا فارغًا، فيجب أن يكون realloc() مكافئًا لـ malloc() بالحجم المحدد.

6. إذا لم يتطابق ptr مع المؤشر الذي تم إرجاعه مسبقًا بواسطة calloc() أو malloc() أو realloc() أو إذا تم إلغاء تخصيص المساحة مسبقًا عن طريق استدعاء free() أو realloc()، يكون السلوك غير محدد.