Matematika generik tidak aman dalam C #

Sayangnya, tidak mudah untuk secara memadai menerjemahkan nama keburukan yang saya mulai ke dalam bahasa Rusia. Saya terkejut menemukan bahwa dokumentasi resmi MSDN menyebut "generics" "templates" (mirip dengan templat C++ , saya kira). Dalam edisi ke-4 "CLR via C# " yang menarik perhatian saya , Jeffrey Richter , yang diterjemahkan oleh Peter , obat generik disebut "generalisasi," yang mencerminkan konsep itu jauh lebih baik. Artikel ini akan berbicara tentang operasi matematika umum yang tidak aman di C# . Menimbang bahwa C# tidak dimaksudkan untuk komputasi berkinerja tinggi (walaupun, tentu saja, ia mampu melakukan ini, tetapi tidak dapat bersaing dengan C/C++ ), operasi matematika di BCL tidak terlalu diperhatikan. Mari kita coba untuk menyederhanakan pekerjaan dengan tipe aritmatika dasar menggunakan C# dan CLR .

Pernyataan masalah

Penafian : artikel ini akan berisi banyak fragmen kode, beberapa di antaranya akan saya ilustrasikan dengan tautan ke sumber daya luar biasa SharpLab ( Gi r tHub ) oleh Andrey Shchekin .

Sebagian besar perhitungan dengan satu atau lain cara mengarah ke operasi dasar. Penambahan, pengurangan (inversi, negasi), perkalian dan pembagian dapat ditambah dengan operasi perbandingan dan memeriksa kesetaraan. Tentu saja, semua tindakan ini dapat dengan mudah dan sederhana dilakukan pada variabel tipe aritmatika dasar C# . Satu-satunya masalah adalah bahwa C# harus tahu pada waktu kompilasi bahwa operasi dilakukan pada tipe tertentu, dan tampaknya menulis metode yang sama-sama efisien (dan transparan) menambahkan dua bilangan bulat dan dua angka floating-point tidak mungkin.

Mari kita tentukan keinginan kita untuk metode umum hipotetis yang melakukan beberapa operasi matematika sederhana:

1. Metode harus memiliki batasan tipe umum yang melindungi kita dari upaya menambahkan (atau mengalikan, membagi) dua tipe arbitrer. Kami membutuhkan beberapa batasan tipe generik.
2. Untuk kemurnian percobaan, jenis yang diterima dan dikembalikan harus sama. Misalnya, operator biner harus memiliki tanda tangan dari formulir (T, T) => T
3. Metode ini setidaknya harus dioptimalkan sebagian. Misalnya, tinju di mana-mana tidak dapat diterima.

Dan bagaimana dengan tetangga?

Mari kita lihat F# . Saya tidak kuat di F# , tetapi sebagian besar pembatasan C# ditentukan oleh batasan CLR , yang berarti F# menderita masalah yang sama. Anda dapat mencoba mendeklarasikan metode penambahan umum yang eksplisit dan metode penambahan yang biasa dan lihat apa yang dikatakan sistem inferensi tipe F# :

 let add_gen (x : 'a) (y : 'a) = x + y let add xy = x + y add_gen 5.0 6.0 |> ignore add 5.0 6.0 |> ignore 

Dalam hal ini, kedua metode akan berubah menjadi non-umum, dan kode yang dihasilkan akan sama. Dengan kekakuan sistem tipe F# , di mana tidak ada konversi implisit dari bentuk int -> double , setelah panggilan pertama metode ini dengan parameter tipe double (dalam istilah C# ), metode panggilan dengan parameter jenis lain (bahkan dengan kemungkinan hilangnya akurasi karena konversi jenis) lebih lanjut akan gagal.

Perlu dicatat bahwa jika Anda mengganti operator + dengan operator persamaan = , gambar menjadi sedikit berbeda : kedua metode berubah menjadi digeneralisasi (dari sudut pandang C# ), dan metode pembantu khusus, tersedia dalam F# dipanggil untuk melakukan perbandingan.

 let eq_gen (x : 'a) (y : 'a) = x = y let eq xy = x = y eq_gen 5.0 6.0 |> ignore eq_gen 5 6 |> ignore eq 5.0 6.0 |> ignore eq 5 6 |> ignore 

Bagaimana dengan Java ?

Sulit bagi saya untuk berbicara tentang Java , tetapi, sejauh yang saya tahu, tipe-tipe penting tidak ada dalam bentuk yang biasa bagi kita, tetapi masih ada tipe- tipe primitif . Untuk bekerja dengan primitif di Java ada pembungkus (misalnya, referensi Long untuk primitif oleh-nilai long ), yang memiliki Number kelas basis umum. Dengan demikian, Anda dapat menggeneralisasi sebagian operasi menggunakan Number , tetapi ini adalah jenis referensi, yang tidak mungkin memiliki efek positif pada kinerja.

Koreksi saya jika saya salah.

C++ ?

C++ adalah bahasa untuk curang.
C++ membuka jalan bagi fitur yang oleh beberapa orang dianggap ... tidak alami .
Templat (alias templat), berbeda dengan generalisasi (generik), dalam arti harfiah, templat . Saat mendeklarasikan templat, Anda dapat secara eksplisit membatasi jenis templat yang tersedia. Karena alasan ini, dalam C++ , misalnya, kode berikut ini valid:

 #include <iostream> template<typename T, std::enable_if_t<std::is_arithmetic<T>::value>* = nullptr> T Add (T left, T right) { return left + right; } int main() { std::cout << Add(5, 6) << std::endl; std::cout << Add(5.0, 6.0) << std::endl; // std::cout << Add("a", "b") << std::endl; Does not compile } 

is_arithmetic , sayangnya, memungkinkan char dan bool sebagai parameter. Di sisi lain, char dapat setara dengan sbyte dalam terminologi C# , meskipun ukuran sebenarnya dari tipe integer tergantung pada fase platform / kompiler / bulan.

Bahasa Pengetikan Dinamis

Akhirnya, pertimbangkan beberapa bahasa yang diketik secara dinamis (dan ditafsirkan ), dipertajam oleh perhitungan. Dalam bahasa seperti itu, biasanya generalisasi perhitungan tidak menimbulkan masalah: jika jenis parameter cocok untuk dieksekusi, kondisional, penambahan, maka operasi akan dilakukan, jika tidak maka akan gagal dengan kesalahan.

Dengan Python (3.7.3 x64):

 def add (x, y): return x + y type(add(5, 6)) # <class 'int'> type(add(5.0, 6.0)) # <class 'float'> type(add('a', 'b') # <class 'str'> 

Dalam R (3.6.1 x64)

 add <- function(x, y) x + y # Or typeof() vctrs::vec_ptype_show(add(5, 6)) # Prototype: double vctrs::vec_ptype_show(add(5L, 6L)) # Prototype: integer vctrs::vec_ptype_show(add("5", "6")) # Error in x + y : non-numeric argument to binary operator 

Sebaliknya, di dunia C #: kami membatasi jenis fungsi matematika yang umum

Sayangnya, kami tidak dapat melakukan ini. Di C# tipe primitif adalah tipe menurut nilai, mis. struktur yang, meskipun diwarisi dari System.Object (dan System.ValueType ), tidak memiliki banyak kesamaan. Keterbatasan alami dan logis adalah di where T : struct . Dimulai dengan C# 7.3 kita memiliki di where T : unmanaged constraint, yang berarti bahwa T adalah , null . Selain tipe aritmatika primitif yang kita butuhkan, char , bool , decimal , setiap Enum dan struktur apa pun yang semua bidangnya memiliki tipe unmanaged sama memenuhi persyaratan ini. Yaitu tipe ini akan lulus ujian:

 public struct Coords<T> where T : unmanaged { public TX; public TY; } 

Jadi, kita tidak dapat menulis fungsi umum yang hanya menerima tipe aritmatika yang diinginkan. Karenanya Unsafe dalam judul artikel - kita harus bergantung pada pemrogram menggunakan kode kita. Upaya untuk memanggil metode umum hipotetis T Add<T>(T left, T right) where T : unmanaged akan menyebabkan hasil yang tidak terduga jika pemrogram melewati objek dari tipe yang tidak kompatibel sebagai argumen.

Eksperimen pertama, naif: dynamic

dynamic adalah alat pertama dan jelas yang dapat membantu kita memecahkan masalah kita. Tentu saja, menggunakan dynamic untuk perhitungan sama sekali tidak berguna - dynamic setara dengan object , dan metode yang disebut dengan variabel dynamic diubah menjadi refleksi mengerikan oleh kompiler. Sebagai bonus - mengemas / membongkar jenis menurut nilai kami. Berikut ini sebuah contoh :

 public class Class { public static void Method() { var x = Add(5, 6); var y = Add(5.0, 6.0); } private static dynamic Add(dynamic left, dynamic right) => left + right; } 

Lihat saja IL metode Method :

 .method public hidebysig static void Method () cil managed { // Method begins at RVA 0x2050 // Code size 53 (0x35) .maxstack 8 IL_0000: ldc.i4.5 IL_0001: box [System.Private.CoreLib]System.Int32 IL_0006: ldc.i4.6 IL_0007: box [System.Private.CoreLib]System.Int32 IL_000c: call object Class::Add(object, object) IL_0011: pop IL_0012: ldc.r8 5 IL_001b: box [System.Private.CoreLib]System.Double IL_0020: ldc.r8 6 IL_0029: box [System.Private.CoreLib]System.Double IL_002e: call object Class::Add(object, object) IL_0033: pop IL_0034: ret } // end of method Class::Method 

Dimuat 5 , dikemas , dimuat 6 , dikemas, disebut object Add(object, object) .
Opsi jelas tidak cocok untuk kita.

Percobaan kedua, "di dahi"

Ya, dynamic bukan untuk kita, tetapi jumlah tipe kita terbatas, dan mereka sudah diketahui sebelumnya. Mari kita mempersenjatai diri kita dengan linggis cabang dan menuliskannya: jika tipe kita adalah , mari kita hitung sesuatu, jika tidak - inilah pengecualian.

 public static T Add<T>(T left, T right) where T : unmanaged { if(left is int i32Left && right is int i32Right) { // ??? } // ... throw new NotSupportedException(); } 

III, di sini kita menemukan masalah. Jika Anda memahami jenis apa yang kami kerjakan, Anda masih dapat menerapkan operasi untuk mereka juga, maka int kondisional yang dihasilkan perlu dikonversi ke tipe T tidak diketahui dan ini tidak terlalu sederhana. Opsi return (T)(i32Left + i32Right) tidak dapat dikompilasi - tidak ada jaminan bahwa T adalah int (walaupun kita tahu itu adalah). Anda dapat mencoba pengembalian konversi ganda return (T)(object)(i32Left + i32Right) . Pertama, jumlahnya dikemas, lalu dibongkar dalam T Ini hanya akan berfungsi jika jenisnya cocok sebelum pengemasan dan setelah pengemasan. Anda tidak dapat mengemas int , tetapi membukanya double , bahkan jika ada konversi implisit int -> double . Masalah dengan kode ini adalah percabangan raksasa dan banyaknya paket yang dibongkar, bahkan dalam kondisi sekalipun. Opsi ini juga tidak bagus.

Refleksi dan Metadata

Nah, bermainlah dan itu sudah cukup. Semua orang tahu bahwa ada operator di C# yang dapat diganti. Di sana, ada + , - , == , == != Dan seterusnya. Yang perlu kita lakukan adalah mengeluarkan metode tipe T statis yang sesuai dengan operator, misalnya, penambahan - itu saja. Ya, sekali lagi beberapa paket, tetapi tidak ada percabangan dan tidak ada masalah. Semuanya bisa di-cache oleh tipe T dan umumnya mempercepat proses dengan segala cara, mengurangi satu operasi matematika untuk memanggil metode refleksi tunggal. Nah, kira-kira seperti ini:

 public static T Add<T>(T left, T right) where T : unmanaged { // Simple example without cache. var method = typeof(T) .GetMethod(@"op_Addition", new [] {typeof(T), typeof(T)}) ?.CreateDelegate(typeof(Func<T, T, T>)) as Func<T, T, T>; return method?.Invoke(left, right) ?? throw new InvalidOperationException(); } 

Sayangnya ini tidak berhasil . Faktanya adalah bahwa tipe aritmatika (tetapi tidak decimal ) tidak memiliki metode statis. Semua operasi diimplementasikan melalui operasi IL , seperti add . Refleksi normal tidak menyelesaikan masalah kita.

System.Linq.Ekspresi

Solusi berbasis Expressions dijelaskan di blog John Skeet di sini (oleh Marc Gravell).
Idenya cukup sederhana. Misalkan kita memiliki tipe T yang mendukung operasi + . Mari kita membuat ekspresi seperti ini:

 (x, y) => x + y; 

Setelah itu, setelah di-cache, kita akan menggunakannya. Membangun ekspresi seperti itu cukup mudah. Kami membutuhkan dua parameter dan satu operasi. Jadi mari kita tuliskan.

 private static readonly Dictionary<(Type Type, string Op), Delegate> Cache = new Dictionary<(Type Type, string Op), Delegate>(); public static T Add<T>(T left, T right) where T : unmanaged { var t = typeof(T); // If op is cached by type and function name, use cached version if (Cache.TryGetValue((t, nameof(Add)), out var del)) return del is Func<T, T, T> specificFunc ? specificFunc(left, right) : throw new InvalidOperationException(nameof(Add)); var leftPar = Expression.Parameter(t, nameof(left)); var rightPar = Expression.Parameter(t, nameof(right)); var body = Expression.Add(leftPar, rightPar); var func = Expression.Lambda<Func<T, T, T>>(body, leftPar, rightPar).Compile(); Cache[(t, nameof(Add))] = func; return func(left, right); } 

Informasi yang berguna tentang pohon ekspresi dan delegasi diterbitkan di hub

Secara teknis, ekspresi memungkinkan kita untuk menyelesaikan semua masalah kita - operasi dasar apa pun dapat direduksi menjadi memanggil metode umum. Operasi yang lebih kompleks dapat ditulis dengan cara yang sama, menggunakan ekspresi yang lebih kompleks. Ini hampir cukup.

Kami melanggar semua aturan

Apakah mungkin untuk mencapai sesuatu yang lain menggunakan kekuatan CLR/C# ? Mari kita lihat tahun berapa kode dihasilkan oleh metode penambahan untuk berbagai jenis :

 public class Class { public static double Add(double x, double y) => x + y; public static int Add(int x, int y) => x + y; // Decimal only to show difference public static decimal Add(decimal x, decimal y) => x + y; } 

Kode IL sesuai berisi serangkaian instruksi yang sama:

 ldarg.0 ldarg.1 add ret 

Ini adalah kode op sangat add ke mana dikompilasi jenis aritmatika primitif dikompilasi. decimal di tempat ini memanggil static decimal decimal.op_Addition(decimal, decimal) . Tetapi bagaimana jika kita menulis metode yang akan digeneralisasi, tetapi mengandung persis kode- IL ini? Yah, John Skeet memperingatkan bahwa ini tidak sepadan . Dalam kasusnya, ia mempertimbangkan semua jenis (termasuk decimal ), serta analog yang dapat dibatalkan. Ini akan membutuhkan operasi IL cukup non-trivial dan tentu akan menyebabkan kesalahan. Tetapi kita masih dapat mencoba menerapkan operasi dasar.

Yang mengejutkan saya, Visual Studio tidak mengandung template untuk proyek IL dan file IL . Anda tidak bisa hanya mengambil dan menjelaskan bagian dari kode di IL dan memasukkannya ke dalam perakitan Anda. Secara alami, open source membantu kami. Proyek ILSupport berisi template untuk proyek IL , serta serangkaian instruksi yang dapat ditambahkan ke *.csproj untuk memasukkan kode IL dalam proyek. Tentu saja, untuk menggambarkan semuanya dalam IL cukup sulit, sehingga penulis proyek menggunakan atribut MethodImpl dengan bendera ForwardRef . Atribut ini memungkinkan Anda untuk mendeklarasikan metode sebagai extern dan tidak menggambarkan tubuh metode. Itu terlihat seperti ini:

 [MethodImpl(MethodImplOptions.ForwardRef)] public static extern T Add<T>(T left, T right) where T : unmanaged; 

Langkah selanjutnya adalah menulis implementasi metode dalam file *.il dengan kode IL :

 .method public static hidebysig !!T Add<valuetype .ctor (class [mscorlib]System.ValueType modreq ([mscorlib]System.Runtime.InteropServices.UnmanagedType)) T>(!!T left, !!T right) cil managed { .param type [1] .custom instance void System.Runtime.CompilerServices.IsUnmanagedAttribute::.ctor() = (01 00 00 00 ) ldarg.0 ldarg.1 add ret } 

Tidak ada tempat yang secara eksplisit merujuk pada tipe !!T , kami menyarankan CLR untuk menambahkan dua argumen dan mengembalikan hasilnya. Tidak ada pemeriksaan tipe, dan semuanya ada di hati nurani pengembang. Anehnya, ia bekerja, dan relatif cepat.

Sedikit patokan

Mungkin, tolok ukur yang jujur ​​akan dibangun di atas ekspresi yang agak rumit, perhitungan yang "langsung" akan dibandingkan dengan metode IL -berbahaya ini. Saya menulis algoritma sederhana yang merangkum kuadrat angka yang sebelumnya dihitung dan disimpan dalam array double dan membagi jumlah akhir dengan jumlah angka. Untuk melakukan operasi, saya menggunakan C# + , * dan / operator, seperti yang dilakukan orang sehat, fungsi yang dibangun dengan Expressions , dan fungsi IL .

 BenchmarkDotNet=v0.12.0, OS=Windows 10.0.18362 Intel Core i7-2700K CPU 3.50GHz (Sandy Bridge), 1 CPU, 8 logical and 4 physical cores .NET Core SDK=3.1.100 [Host] : .NET Core 3.1.0 (CoreCLR 4.700.19.56402, CoreFX 4.700.19.56404), X64 RyuJIT Job-POXTAH : .NET Core 3.1.0 (CoreCLR 4.700.19.56402, CoreFX 4.700.19.56404), X64 RyuJIT Runtime=.NET Core 3.1 

Kode tidak aman kami sekitar 2.5 kali lebih lambat (dalam satu operasi). Ini dapat dikaitkan dengan fakta bahwa dalam kasus perhitungan "dahi", kompiler mengkompilasi a + b ke dalam kode add op, dan dalam kasus metode yang tidak aman, fungsi statis disebut, yang secara alami lebih lambat, yang secara alami lebih lambat.

Alih-alih menyimpulkan: kapan true != true

Beberapa hari yang lalu, saya menemukan tweet dari Jared Parsons:

Ada kasus-kasus di mana yang berikut ini akan mencetak "false"
bool b = ...
if (b) Console.WriteLine (b.IsTrue ());

Ini adalah jawaban untuk entri ini , yang menunjukkan kode verifikasi bool untuk true , yang terlihat seperti ini:

 public static bool IsTrue(this bool b) { if (b == true) return true; else if (b == false) return false; else return !true && !false; } 

Cek sepertinya berlebihan, kan? Jared memberikan contoh tandingan yang menunjukkan beberapa fitur perilaku bool . Idenya adalah bahwa bool adalah byte ( sizeof(bool) == 1 ), sedangkan false cocok dengan 0 dan true match 1 . Selama Anda tidak mengayunkan pointer, bool berperilaku tidak ambigu dan dapat diprediksi. Namun, seperti yang diperlihatkan Jared, Anda dapat membuat bool menggunakan 2 sebagai nilai awal, dan bagian dari cek akan gagal dengan benar:

 bool b = false; byte* ptr = (byte*)&b; *ptr = 2; 

Kami dapat mencapai efek yang sama menggunakan operasi matematika kami yang tidak aman (ini tidak bekerja dengan Expressions ):

 var fakeTrue = Subtract<bool>(false, true); var val = *(byte*)&fakeTrue; if(fakeTrue) Assert.AreNotEqual(fakeTrue, true); else Assert.Fail("Clause not entered."); 

Ya, ya, kami memeriksa di dalam cabang yang true apakah kondisinya true , dan kami berharap pada kenyataannya itu tidak true . Kenapa begitu? Jika Anda mengurangi 0 ( =false ) 1 ( =true ) tanpa tanda centang, maka untuk byte ini akan sama dengan 255 . Secara alami, 255 ( fakeTrue kami) bukan 1 ( true nyata), jadi true dieksekusi. Bercabang bekerja secara berbeda.

if inversi terjadi: cabang bersyarat dimasukkan; jika kondisinya salah , maka transisi ke titik terjadi setelah akhir blok if . Validasi dilakukan oleh pernyataan brfalse / brfalse_S . Ini membandingkan nilai terakhir pada stack dengan nol . Jika nilainya nol, maka itu false , kita melangkahi blok if . Dalam kasus kami, fakeTrue tidak sama dengan nol, jadi pemeriksaan melewati dan eksekusi berlanjut di dalam blok if , di mana kami membandingkan fakeBool dengan nilai sebenarnya dan mendapatkan hasil negatif.

UPD01:
Setelah membahas dalam komentar dengan shai_hulud dan blowin , saya menambahkan metode lain ke tolok ukur yang mengimplementasikan cabang seperti if(typeof(T) == typeof(int)) return (T)(object)((int)(object)left + (int)(object)right); . Terlepas dari kenyataan bahwa JIT harus mengoptimalkan pemeriksaan, setidaknya ketika T adalah sebuah struct , metode tersebut masih bekerja dengan urutan yang lebih lambat. Tidak jelas apakah transformasi T -> int -> T dioptimalkan, atau apakah tinju / unboxing digunakan. Hasil benchmark MethodImpl dipengaruhi secara signifikan oleh flag MethodImpl .

UPD02:
xXxVano dalam komentar menunjukkan contoh menggunakan percabangan berdasarkan jenis dan melemparkan T <--> jenis tertentu menggunakan Unsafe.As<TFrom, TTo>() . Dengan analogi dengan percabangan dan kebiasaan melalui object , saya menulis tiga operasi (penambahan, perkalian dan pembagian) dengan percabangan untuk semua jenis aritmatika, setelah itu saya menambahkan tolok ukur lain ( UnsafeBranchSum ). Terlepas dari kenyataan bahwa semua metode (kecuali ekspresi) menghasilkan kode asm yang hampir identik (sejauh pengetahuan saya tentang assembler memungkinkan saya untuk menilai), untuk beberapa alasan yang tidak diketahui, kedua metode dengan percabangan sangat lambat dibandingkan dengan penjumlahan langsung ( DirectSum ) dan menggunakan obat generik dan kode IL . Saya tidak punya penjelasan untuk efek ini, fakta bahwa waktu yang dihabiskan tumbuh secara proporsional ke N menunjukkan bahwa ada semacam overhead konstan untuk setiap operasi, terlepas dari semua keajaiban JIT . Overhead ini hilang dari versi IL metode. , IL - , / / , 100% ( , ).
, , - .