لماذا يعتبر أداء مضاعفات المصفوفة هذه مختلفة تمامًا؟

Question

لقد كتبت فئتين من المصفوفة في جافا فقط لمقارنة أداء مضاعفات المصفوفة. متاجر فئة واحدة (MAT1) double[][] A عضو حيث الصف i من المصفوفة A[i]. متاجر الفئة الأخرى (MAT2) A و T أين T هو تحويل A.

دعنا نقول أن لدينا مصفوفة مربعة M ونريد منتج M.mult(M). اتصل بالمنتج P.

عندما يكون M مثيل MAT1 ، كانت الخوارزمية المستخدمة هي الواردة المباشرة:

P[i][j] += M.A[i][k] * M.A[k][j]
    for k in range(0, M.A.length)

في الحالة التي تستخدم فيها m mat2:

P[i][j] += M.A[i][k] * M.T[j][k]

وهو نفس الخوارزمية بسبب T[j][k]==A[k][j]. على 1000 × 1000 مصفوفات ، تستغرق الخوارزمية الثانية حوالي 1.2 ثانية على الجهاز الخاص بي ، بينما تستغرق الأولى ما لا يقل عن 25 ثانية. كنت أتوقع أن يكون الثاني أسرع ، ولكن ليس بهذا القدر. والسؤال هو ، لماذا هذا أسرع بكثير؟

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

سألت شخصًا ما واعتقد أنه بسبب أنماط الوصول إلى الذاكرة الودية (أي أن الإصدار الثاني سيؤدي إلى عدد أقل من الأخطاء الناعمة TLB). لم أفكر في هذا على الإطلاق ، لكن يمكنني أن أرى نوعًا ما كيف ينتج عنه عدد أقل من أخطاء TLB.

إذن ، ما هو؟ أم أن هناك سببًا آخر لفرق الأداء؟

Answer 1

هذا بسبب موقع بياناتك.

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

هذا يعني أنه إذا كنت تصل إلى عنصر في الموضع x,y سوف يحسب x*row_length + y وسيكون هذا هو الإزاحة المستخدمة للإشارة إلى العنصر في الموضع المحدد.

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

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

(لقد قمت بتبسيط التفسير كله ، إنه فقط أعطيك الفكرة الأساسية حول هذه المشكلة)

على أي حال ، لا أعتقد أن هذا ناتج عن JVM في حد ذاته. ربما يتعلق الأمر بكيفية إدارة نظام التشغيل الخاص بك بذكرى عملية Java ..

Answer 2

فرضيات ذاكرة التخزين المؤقت و TLB معقولة ، لكنني أرغب في رؤية الكود الكامل لقياسك ... وليس فقط قصاصات الكود الزائفة.

الاحتمال الآخر هو أن فرق الأداء هو نتيجة لتطبيقك باستخدام ذاكرة إضافية بنسبة 50 ٪ لمصفوفات البيانات في الإصدار مع Transpose. إذا كان حجم كومة JVM صغيرًا ، فمن المحتمل أن يؤدي ذلك إلى تشغيل GC كثيرًا. قد يكون هذا نتيجة لاستخدام حجم الكومة الافتراضي. (ثلاثة الكثير من 1000 x 1000 x 8 البايتات ~ 24 ميجابايت)

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

Answer 3

من السهل تخمين أن المشكلة قد تكون محلية ، وربما هي كذلك ، لكن هذا لا يزال تخمينًا.

ليس من الضروري تخمين. قد تمنحك تقنيتان الإجابة - خطوة واحدة وتوقف مؤقتًا.

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

إذا كان في الواقع يتجول في الحلقة الداخلية بدون أي حركة نفايات ، فإن الإيقاف العشوائي سيعطيك معلومات. نظرًا لأن البطيء يستغرق 20 مرة أطول من The Fast One ، فإن هذا يعني 95 ٪ من الوقت الذي يقوم به شيئًا لا يجب أن يكون عليه. لذا انظر ما هو عليه. في كل مرة تتوقف فيها ، تكون الفرصة هي 95 ٪ التي سترى ما هو ولماذا.

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

Answer 4

قد تحاول مقارنة الأداء بين JDK6 و OpenJDK7 ، بالنظر إلى هذا مجموعة من النتائج...