يتم توجيه انتباهك إلى نظرة عامة صغيرة على إمكانات توجيه الخوارزميات في .NET Framework و .NETCORE. الغرض من هذه المقالة هو تقديم هذه التقنيات لأولئك الذين لم يعرفوها على الإطلاق وإظهار أن .NET لا يتخلف كثيراً عن اللغات "الحقيقية المترجمة" للمواطن الأصلي.
التنمية.
لقد بدأت للتو في تعلم أساليب التحويل ، لذلك إذا وجهني شخص من المجتمع إلى حالة غير صريحة أو قدم نسخًا محسنة من الخوارزميات الموضحة أدناه ، فسوف أكون سعيدًا جدًا.
قليلا من التاريخ
في .NET ، ظهر SIMD لأول مرة في عام 2015 مع إصدار .NET Framework 4.6. ثم تمت إضافة أنواع 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 بايت يمكننا وضعه في ناقل. إذا تم استخدام تسريع الأجهزة ، فإن هذه القيمة توضح عدد الأرقام التي يمكن وضعها في سجل SIMD بأربع أرقام. في الحقيقة ، يُظهر عدد عناصر هذا النوع التي يمكن تشغيلها بالتوازي ؛
- accVector - متجه تتراكم فيه نتيجة الوظيفة ؛
var v = ناقل جديد <int> (array، i)؛ - يتم تحميل البيانات في متجه v جديد ، من الصفيف ، بدءًا من الفهرس i. سيتم تحميل بيانات vectorSize بالضبط. - accVector = Vector.Add (accVector، v)؛ - يتم إضافة متجهين.
على سبيل المثال ، يتم تخزين أرقام الصفيف 8: {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:
الجوهرية 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; } }
نتيجة الاختبار على جهاز الكمبيوتر الخاص بي:
أعتقد أن كل الشفرة الخاصة بهذه الطرق مفهومة ، باستثناء سطرين في Intrinsics:
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 عنصرًا في المتجه. يمكن العثور على الكود الكاذب هنا .
وبالتالي ، إذا لم تتطابق بعض البايتات في va و vb ، فعندها تكون البايتات المقابلة هي 0 ، وبالتالي فإن البتات الأكثر أهمية في هذه البايتات ستكون 0 أيضًا ، مما يعني أن البتات المقابلة في استجابة Avx2.MoveMask ستكون أيضًا 0 وستكون المقارنة أيضًا 0 مع equalsMask لن تعمل.
دعنا نحلل مثالًا صغيرًا ، على افتراض أن طول الموجه 8 بايت (لكتابته كان أقل):
- اسمحوا va = {100 ، 10 ، 20 ، 30 ، 100 ، 40 ، 50 ، 100} ، و vb = {100 ، 20 ، 10 ، 30 ، 100 ، 40 ، 80 ، 90} ؛
- ثم تكون Equal مساوية لـ {255، 0، 0، 255، 255، 255، 0، 0}؛
- ستُرجع طريقة MoveMask 10011100b ، والتي ستحتاج إلى مقارنة مع القناع 11111111b ، لأن نظرًا لأن هذه الأقنعة غير متساوية ، فقد تبين أن المتجهات va و vb غير متساوية.
حساب عدد مرات حدوث عنصر في المجموعة
في بعض الأحيان يكون من الضروري حساب عدد المرات التي يتم فيها العثور على عنصر معين في مجموعة ما ، على سبيل المثال ، ints ، يمكن أيضًا تسريع هذه الخوارزمية. دعنا نكتب بعض الطرق للمقارنة ، سنبحث عن عنصر العنصر في صفيف الصفيف.
الأكثر وضوحا:
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;
نتيجة الاختبار على جهاز الكمبيوتر الخاص بي:
تتشابه طرق المتجهات والأصالة في المنطق تمامًا ، والاختلافات هي فقط في تنفيذ عمليات محددة. الفكرة ككل هي:
- يتم إنشاء ناقل متجه يتم فيه تخزين العدد المطلوب في كل عنصر ؛
- يتم تحميل جزء من المصفوفة في المتجه v ومقارنته مع القناع ، ثم يتم تعيين جميع البتات في عناصر متساوية في Equal ، لأن areEqual عبارة عن متجه من ints ، ثم إذا قمت بتعيين جميع وحدات بت عنصر واحد ، فسنحصل على -1 في هذا العنصر ((int) (1111_1111_1111_1111_1111_1111_1111_1111b) == -1) ؛
- the vector areEqual يتم طرحها من accVector وبعد ذلك سيكون accVector هو مجموع عدد المرات التي حدث فيها عنصر العنصر في جميع المتجهات v لكل موقف (ناقص min يعطي زائد).
يمكن العثور على جميع التعليمات البرمجية من المقال على جيثب
الخاتمة
لقد درست جزءًا صغيرًا جدًا من الاحتمالات التي يوفرها .NET لحسابات البيانات. للحصول على قائمة كاملة وحديثة من العناصر الداخلية المتاحة في .NETCORE تحت x86 ، يمكنك الرجوع إلى التعليمات البرمجية المصدر . من المريح أنه في ملفات C # في ملخص كل مضمن ، يوجد اسم خاص به من عالم C ، مما يبسط فهم الغرض من هذا المضمون وترجمة خوارزميات C ++ / C الحالية إلى .NET. وثائق System.Numerics.Vector متاحة في msdn .
في رأيي ، .NET لديه ميزة كبيرة على C ++ ، لأنه يتم تجميع JIT بالفعل على جهاز العميل ، ثم يمكن للمترجم تحسين الكود لمعالج عميل معين ، مما يوفر أقصى أداء. في الوقت نفسه ، يمكن أن يظل مبرمج لكتابة التعليمات البرمجية السريعة في إطار لغة واحدة والتكنولوجيا.
محدث (09/15/2019):
كان هناك عضادة في المعاييرفي المقاييس ، استخدمت IterationSetup ، والتي ، كما اتضح فيما بعد ، يمكن أن تؤثر بشكل كبير على أداء المعايير التي تنجح في أقل من 100 مللي ثانية. إذا أعدتها على GlobalSetup ، فستكون النتائج هكذا.
مجموع عناصر الصفيف:
مقارنة مجموعتين:
عدد تكرارات عنصر في صفيف