فيما يلي نظرة سريعة على إمكانيات تحويل الخوارزميات في .NET Framework و .NET Core. هذه المقالة مخصصة لأولئك الذين لا يعرفون شيئًا عن هذه التقنيات. سأُظهر أيضًا أن .NET لا يتخلف عن اللغات "المترجمة الحقيقية" للتنمية الأصلية.
أنا بدأت للتو في تعلم تقنيات مكافحة ناقلات الأمراض. لذا ، سأكون ممتنًا إذا وجد أفراد المجتمع أخطاء واضحة أو اقترحوا تحسينات على الخوارزميات الموصوفة.
بعض التاريخ
ظهر SIMD في .NET Framework 4.6 في عام 2015. عند إضافة أنواع Matrix3x2 و Matrix4x4 و Plane و Quaternion و Vector2 و Vector3 و Vector4. سمحوا الحسابات الموجه. التالي هو نوع Vector <T> الذي أعطى المزيد من الفرص لتوجيه الخوارزميات. ومع ذلك ، لا يزال العديد من المبرمجين غير راضين لأن هذه الأنواع قيدت تدفقات أفكار المبرمجين ولم تسمح باستخدام السعة الكاملة لتعليمات SIMD في المعالجات الحديثة. الآن في .NET Core 3.0 Preview ، لدينا مساحة اسم System.Runtime.Intrinsics توفر حرية كبيرة في اختيار التعليمات. للحصول على أقصى سرعة ، تحتاج إلى استخدام RyuJit واللجوء إما إلى x64 التجميع أو إيقاف تشغيل Prefer 32 بت واختيار التجميع AnyCPU. ركضت جميع المعايير على كمبيوتر Intel Core i7-6700 3.40 جيجاهرتز (Skylake).
جمع عناصر الصفيف
قررت أن أبدأ بمهمة كلاسيكية عادةً ما تأتي أولاً إذا كان هناك توجيه. إنه يتعامل مع إيجاد مجموع عناصر الصفيف. دعنا نكتب أربعة تطبيقات لهذه المهمة لتلخيص عناصر Array.
التنفيذ الأكثر وضوحا:
public int Naive() { int result = 0; foreach (int i in Array) { result += i; } return result; }
التنفيذ القائم على LINQ:
public long LINQ() => Array.Aggregate<int, long>(0, (current, i) => current + i);
التنفيذ على أساس المتجهات من System.Numerics:
public int Vectors() { int vectorSize = Vector<int>.Count; var accVector = Vector<int>.Zero; int i; var array = Array; for (i = 0; i <= array.Length - vectorSize; i += vectorSize) { var v = new Vector<int>(array, i); accVector = Vector.Add(accVector, v); } int result = Vector.Dot(accVector, Vector<int>.One); for (; i < array.Length; i++) { result += array[i]; } return result; }
تطبيق يستند إلى رمز من مساحة الاسم System.Runtime.Intrinsics:
public unsafe int Intrinsics() { int vectorSize = 256 / 8 / 4; var accVector = Vector256<int>.Zero; int i; var array = Array; fixed (int* ptr = array) { for (i = 0; i <= array.Length - vectorSize; i += vectorSize) { var v = Avx2.LoadVector256(ptr + i); accVector = Avx2.Add(accVector, v); } } int result = 0; var temp = stackalloc int[vectorSize]; Avx2.Store(temp, accVector); for (int j = 0; j < vectorSize; j++) { result += temp[j]; } for (; i < array.Length; i++) { result += array[i]; } return result; }
لقد حددت هذه الطرق الأربع على جهاز الكمبيوتر الخاص بي وحصلت على النتائج التالية:
من الواضح أن الحلول مع Vectors و Intrinsics أسرع بكثير من الحلول الواضحة والمستندة إلى LINQ. الآن نحن بحاجة إلى معرفة ما يجري في هاتين الطريقتين.
دعونا ننظر في طريقة المتجهات عن كثب:
ناقلات public int Vectors() { int vectorSize = Vector<int>.Count; var accVector = Vector<int>.Zero; int i; var array = Array; for (i = 0; i <= array.Length - vectorSize; i += vectorSize) { var v = new Vector<int>(array, i); accVector = Vector.Add(accVector, v); } int result = Vector.Dot(accVector, Vector<int>.One); for (; i < array.Length; i++) { result += array[i]; } return result; }
- int vectorSize = Vector <int> .Count؛ - كمية أرقام 4 بايت التي يمكن أن نضعها في ناقل. إذا تم استخدام تسريع الأجهزة ، فإن هذه القيمة توضح عدد الأرقام المكونة من 4 بايت التي يمكننا وضعها في سجل SIMD واحد. في الواقع ، يُظهر عدد عناصر هذا النوع التي يمكن التعامل معها بشكل متزامن ؛
- accVector عبارة عن ناقل يقوم بتجميع نتيجة الوظيفة ؛
- var v = ناقل جديد <int> (array، i)؛ - يتم تحميل البيانات من الصفيف في ناقل v جديد ، بدءًا من i index. سيتم تحميل vectorSize البيانات بالضبط ؛
- accVector = Vector.Add (accVector، v)؛ - لخص متجهين.
على سبيل المثال ، هناك 8 أرقام في Array: {0 ، 1 ، 2 ، 3 ، 4 ، 5 ، 6 ، 7} و vectorSize == 4.
ثم خلال دورة التكرار الأولى من accVector = {0 ، 0 ، 0 ، 0} ، v = {0 ، 1 ، 2 ، 3} وبعد الإضافة ، سيتم تثبيت accVector: {0 ، 0 ، 0 ، 0} + {0 ، 1 ، 2 ، 3} = {0 ، 1 ، 2 ، 3}.
أثناء التكرار الثاني v = {4، 5، 6، 7} وبعد الإضافة accVector = {0، 1، 2، 3} + {4، 5، 6، 7} = {4، 6، 8، 10}. - الآن نحن بحاجة فقط للحصول على مجموع جميع العناصر المتجهة. للقيام بذلك ، يمكننا استخدام الضرب العددي بواسطة ناقل متجه بأخرى: int result = Vector.Dot (accVector، Vector <int> .One)؛
ثم نحصل على: {4 ، 6 ، 8 ، 10} * {1 ، 1 ، 1 ، 1} = 4 * 1 + 6 * 1 + 8 * 1 + 10 * 1 = 28. - إذا لزم الأمر ، سيتم تلخيص تلك الأرقام التي لا تناسب المتجه الأخير في النهاية.
دعنا ننظر إلى رمز Intrinsics:
Intrinsics public unsafe int Intrinsics() { int vectorSize = 256 / 8 / 4; var accVector = Vector256<int>.Zero; int i; var array = Array; fixed (int* ptr = array) { for (i = 0; i <= array.Length - vectorSize; i += vectorSize) { var v = Avx2.LoadVector256(ptr + i); accVector = Avx2.Add(accVector, v); } } int result = 0; var temp = stackalloc int[vectorSize]; Avx2.Store(temp, accVector); for (int j = 0; j < vectorSize; j++) { result += temp[j]; } for (; i < array.Length; i++) { result += array[i]; } return result; }
يمكننا أن نرى أنه يشبه المتجهات مع استثناء واحد:
مقارنة اثنين من المصفوفات
نحن بحاجة إلى مقارنة صفيفين من بايت. إنها بالضبط هذه المهمة التي دفعتني إلى دراسة SIMD في .NET. مرة أخرى ، دعنا نكتب عدة طرق لقياس ومقارنة صفيفين: ArrayA و ArrayB.
الحل الأكثر وضوحا:
public bool Naive() { for (int i = 0; i < ArrayA.Length; i++) { if (ArrayA[i] != ArrayB[i]) return false; } return true; }
الحل القائم على LINQ:
public bool LINQ() => ArrayA.SequenceEqual(ArrayB);
الحل يعتمد على وظيفة MemCmp:
[DllImport("msvcrt.dll", CallingConvention = CallingConvention.Cdecl)] static extern int memcmp(byte[] b1, byte[] b2, long count); public bool MemCmp() => memcmp(ArrayA, ArrayB, ArrayA.Length) == 0;
الحل القائم على ناقلات من System.Numerics:
public bool Vectors() { int vectorSize = Vector<byte>.Count; int i = 0; for (; i <= ArrayA.Length - vectorSize; i += vectorSize) { var va = new Vector<byte>(ArrayA, i); var vb = new Vector<byte>(ArrayB, i); if (!Vector.EqualsAll(va, vb)) { return false; } } for (; i < ArrayA.Length; i++) { if (ArrayA[i] != ArrayB[i]) return false; } return true; }
الحل القائم على الجوهرية:
public unsafe bool Intrinsics() { int vectorSize = 256 / 8; int i = 0; const int equalsMask = unchecked((int) (0b1111_1111_1111_1111_1111_1111_1111_1111)); fixed (byte* ptrA = ArrayA) fixed (byte* ptrB = ArrayB) { for (; i <= ArrayA.Length - vectorSize; i += vectorSize) { var va = Avx2.LoadVector256(ptrA + i); var vb = Avx2.LoadVector256(ptrB + i); var areEqual = Avx2.CompareEqual(va, vb); if (Avx2.MoveMask(areEqual) != equalsMask) { return false; } } for (; i < ArrayA.Length; i++) { if (ArrayA[i] != ArrayB[i]) return false; } return true; } }
نتائج تشغيل المعيار على جهاز الكمبيوتر الخاص بي:
أعتقد أن رمز هذه الطرق واضح ، فيما عدا سطرين في العناصر الداخلية:
var areEqual = Avx2.CompareEqual(va, vb); if (Avx2.MoveMask(areEqual) != equalsMask) { return false; }
في السطر الأول ، يتم مقارنة متجهين من أجل المساواة ويتم حفظ النتيجة في متجه متساوي يتم فيه ضبط كل وحدات البت في العنصر في موضع معين على 1 إذا كانت العناصر المقابلة في va و vb متساوية. لذلك ، اتضح أنه إذا كانت موجهات البايتة va و vb متساوية ، فيجب أن تساوي جميع العناصر الموجودة في المعادلات 255 (11111111b). نظرًا لأن Avx2.CompareEqual عبارة عن غلاف يحتوي على _mm256_cmpeq_epi8 ، يمكننا الانتقال إلى موقع Intel على الويب ورؤية الكود الكاذب لهذه العملية:
أسلوب MoveMask يجعل رقم 32 بت من ناقل. البتات العليا لكل 32 عنصر من عناصر onebyte في المتجه هي قيم البتات في نتيجة MoveMask. الكود الكاذب متاح هنا .
وبالتالي ، إذا لم تتطابق بعض وحدات البايت في va و vb ، فستكون البايتات المقابلة في القيمة هي 0. وبالتالي ، فإن البتات العليا لهذه البايتات ستكون 0 أيضًا. هذا يعني أن البتات المقابلة في استجابة Avx2.MoveMask ستكون أيضًا 0 ولن تكون Equal متساوية مع equalsMask.
دعونا نلقي نظرة على مثال واحد على افتراض أن طول المتجه 8 بايت (لكتابة أقل):
- دع va = {100 ، 10 ، 20 ، 30 ، 100 ، 40 ، 50 ، 100} و vb = {100 ، 20 ، 10 ، 30 ، 100 ، 40 ، 80 ، 90}.
- بعد ذلك ستكون الأعداد {255 ، 0 ، 0 ، 255 ، 255 ، 255 ، 0 ، 0}.
- سيعود الأسلوب MoveMask 10011100b الذي يجب مقارنته مع قناع 11111111b. نظرًا لأن هذه الأقنعة ليست متساوية ، فإن متجهات va و vb ليست متساوية أيضًا.
حساب عدد مرات حدوث عنصر في مجموعة.
في بعض الأحيان تحتاج إلى حساب تكرارات عنصر معين ، على سبيل المثال أعداد صحيحة ، في مجموعة. يمكننا تسريع هذه الخوارزمية أيضا. للمقارنة ، دعونا نكتب عدة طرق للبحث في عنصر العنصر في Array.
الأكثر وضوحا:
public int Naive() { int result = 0; foreach (int i in Array) { if (i == Item) { result++; } } return result; }
باستخدام LINQ:
public int LINQ() => Array.Count(i => i == Item);
باستخدام المتجهات من System.Numerics.Vectors:
public int Vectors() { var mask = new Vector<int>(Item); int vectorSize = Vector<int>.Count; var accResult = new Vector<int>(); int i; var array = Array; for (i = 0; i <= array.Length - vectorSize; i += vectorSize) { var v = new Vector<int>(array, i); var areEqual = Vector.Equals(v, mask); accResult = Vector.Subtract(accResult, areEqual); } int result = 0; for (; i < array.Length; i++) { if (array[i] == Item) { result++; } } result += Vector.Dot(accResult, Vector<int>.One); return result; }
باستخدام الجوهرية:
public unsafe int Intrinsics() { int vectorSize = 256 / 8 / 4; var temp = stackalloc int[vectorSize]; for (int j = 0; j < vectorSize; j++) { temp[j] = Item; } var mask = Avx2.LoadVector256(temp); var accVector = Vector256<int>.Zero; int i; var array = Array; fixed (int* ptr = array) { for (i = 0; i <= array.Length - vectorSize; i += vectorSize) { var v = Avx2.LoadVector256(ptr + i); var areEqual = Avx2.CompareEqual(v, mask); accVector = Avx2.Subtract(accVector, areEqual); } } int result = 0; Avx2.Store(temp, accVector); for(int j = 0; j < vectorSize; j++) { result += temp[j]; } for(; i < array.Length; i++) { if (array[i] == Item) { result++; } } return result; }
نتائج تشغيل المعيار على جهاز الكمبيوتر الخاص بي:
تتطابق طرق المتجهات والداخل في المنطق تمامًا ولكنها تختلف في تنفيذ عمليات معينة. الفكرة هي ما يلي:
- إنشاء قناع متجه يتم فيه تخزين العدد المطلوب في كل عنصر ؛
- تحميل جزء من مجموعة في ناقلات v ومقارنة هذا الجزء مع قناع. نتيجة لذلك ، سيتم تعيين كافة وحدات البت في عناصر متساوية في القيمة. نظرًا لأن Equal عبارة عن صفيف من الأعداد الصحيحة ، فإذا قمنا بتعيين جميع وحدات بت عنصر واحد ، فسنحصل على -1 في هذا العنصر ((int) (1111_1111_1111_1111_1111_1111_1111_1111b) == -1) ؛
- طرح هي ناقلات متساوية من accVector. بعد ذلك ، سيحتفظ accVector بعدد المرات التي حدث فيها عنصر العنصر في جميع المتجهات v لكل موقف (ناقص بواسطة ناقص زائد).
الكود كله من المقال موجود على جيثب .
استنتاج
لقد وصفت جزءًا صغيرًا فقط من إمكانيات .NET من أجل حساب التحويل. للاطلاع على قائمة محدّثة كاملة بجميع العناصر الداخلية المتوفرة في .NET Core ضمن الإصدار x86 ، انتقل إلى الكود المصدري . من الملائم أن ملخص كل مضمن في ملفات C # يحتوي على اسمه في عالم C. هذا يساعد إما على فهم الغرض من هذه الخوارزمية ونقل خوارزميات C ++ / C الموجودة إلى .NET. وثائق System.Numerics.Vector متاحة على msdn .
أعتقد أن .NET لديه ميزة كبيرة على C ++. نظرًا لأن التحويل البرمجي لـ JIT يحدث بالفعل على جهاز عميل ، يمكن للمترجم تحسين التعليمات البرمجية لمعالج عميل معين ، مما يوفر أقصى أداء. في الوقت نفسه ، يمكن للمبرمج البقاء داخل لغة واحدة ونفس التقنيات لكتابة رمز سريع.