Geekly articles weekly

Mengganti Equals dan GetHashCode. Tetapi apakah itu perlu?

Jika Anda terbiasa dengan C #, kemungkinan besar Anda tahu bahwa Anda harus selalu mengesampingkan Equals , serta GetHashCode , untuk menghindari GetHashCode kinerja. Tetapi apa yang akan terjadi jika ini tidak dilakukan? Hari ini, kami membandingkan kinerja dengan dua opsi penyetelan dan mempertimbangkan alat untuk membantu menghindari kesalahan.



Seberapa serius masalah ini?


Tidak setiap masalah kinerja potensial mempengaruhi runtime aplikasi. Metode Enum.HasFlag tidak terlalu efisien (*), tetapi jika Anda tidak menggunakannya pada sepotong kode sumber daya intensif, maka tidak akan ada masalah serius dalam proyek. Ini juga merupakan kasus dengan salinan yang diproteksi yang dibuat oleh tipe struct yang tidak bisa dibaca dalam konteks readonly. Masalahnya ada, tetapi tidak mungkin terlihat dalam aplikasi biasa.

(*) Tetap di NET Inti 2.1, dan, seperti yang saya sebutkan dalam publikasi sebelumnya , dan sekarang dapat diatasi dengan menggunakan HasFlag mereka sendiri disesuaikan untuk versi.

Tetapi masalah yang akan kita bicarakan hari ini adalah spesial. Jika metode Equals dan GetHashCode tidak dibuat dalam struktur, maka versi standar mereka dari System.ValueType . Dan mereka dapat secara signifikan mengurangi kinerja aplikasi akhir.

Mengapa versi standar lambat?


Para penulis CLR melakukan yang terbaik untuk membuat versi standar Equals dan GetHashCode seefisien mungkin untuk tipe nilai. Tetapi ada beberapa alasan mengapa metode ini hilang dalam keefektifan versi pengguna, ditulis untuk jenis tertentu secara manual (atau dihasilkan oleh kompiler).

1. Distribusi konversi kemasan. CLR dirancang sedemikian rupa sehingga setiap panggilan ke elemen yang didefinisikan dalam tipe System.ValueType atau System.Enum memicu transformasi pembungkus (**).

(**) Jika metode ini tidak mendukung kompilasi JIT. Misalnya, dalam Core CLR 2.1, kompiler JIT mengenali metode Enum.HasFlag dan menghasilkan kode yang sesuai yang tidak mulai membungkus.

2. Potensi konflik dalam versi standar dari metode GetHashCode . Saat menerapkan fungsi hash, kita menghadapi dilema: untuk membuat distribusi fungsi hash baik atau cepat. Dalam beberapa kasus, Anda bisa melakukan keduanya, tetapi dalam tipe ValueType.GetHashCode , ini biasanya sulit.

Fungsi hash tradisional tipe struct "menggabungkan" kode hash dari semua bidang. Tetapi satu-satunya cara untuk mendapatkan kode hash bidang dalam metode ValueType adalah dengan menggunakan refleksi. Itu sebabnya penulis CLR memutuskan untuk mengorbankan kecepatan demi distribusi, dan versi standar GetHashCode hanya mengembalikan kode hash dari bidang non-nol pertama dan "merusaknya" dengan pengenal tipe (***) (untuk lebih jelasnya lihat RegularGetValueTypeHashCode di coreclr repo on github).

(***) Dilihat dari komentar dalam repositori CoreCLR, situasinya mungkin berubah di masa depan.

 public readonly struct Location { public string Path { get; } public int Position { get; } public Location(string path, int position) => (Path, Position) = (path, position); } var hash1 = new Location(path: "", position: 42).GetHashCode(); var hash2 = new Location(path: "", position: 1).GetHashCode(); var hash3 = new Location(path: "1", position: 42).GetHashCode(); // hash1 and hash2 are the same and hash1 is different from hash3

Ini adalah algoritma yang masuk akal sampai terjadi kesalahan. Tetapi jika Anda kurang beruntung dan nilai bidang pertama dari tipe struct Anda adalah sama di sebagian besar kasus, maka fungsi hash akan selalu menghasilkan hasil yang sama. Seperti yang mungkin sudah Anda duga, jika Anda menyimpan instance ini dalam hash set atau hash table, maka kinerja akan anjlok.

3. Kecepatan implementasi berdasarkan refleksi rendah. Sangat rendah Refleksi adalah alat yang ampuh jika digunakan dengan benar. Tetapi konsekuensinya akan mengerikan jika Anda menjalankannya pada sepotong kode sumber daya-intensif.

Mari kita lihat bagaimana fungsi hash yang gagal, yang mungkin hasil dari (2) dan implementasi berbasis refleksi, mempengaruhi kinerja:

 public readonly struct Location1 { public string Path { get; } public int Position { get; } public Location1(string path, int position) => (Path, Position) = (path, position); } public readonly struct Location2 { // The order matters! // The default GetHashCode version will get a hashcode of the first field public int Position { get; } public string Path { get; } public Location2(string path, int position) => (Path, Position) = (path, position); } public readonly struct Location3 : IEquatable<Location3> { public string Path { get; } public int Position { get; } public Location3(string path, int position) => (Path, Position) = (path, position); public override int GetHashCode() => (Path, Position).GetHashCode(); public override bool Equals(object other) => other is Location3 l && Equals(l); public bool Equals(Location3 other) => Path == other.Path && Position == other.Position; } private HashSet<Location1> _locations1; private HashSet<Location2> _locations2; private HashSet<Location3> _locations3; [Params(1, 10, 1000)] public int NumberOfElements { get; set; } [GlobalSetup] public void Init() { _locations1 = new HashSet<Location1>(Enumerable.Range(1, NumberOfElements).Select(n => new Location1("", n))); _locations2 = new HashSet<Location2>(Enumerable.Range(1, NumberOfElements).Select(n => new Location2("", n))); _locations3 = new HashSet<Location3>(Enumerable.Range(1, NumberOfElements).Select(n => new Location3("", n))); _locations4 = new HashSet<Location4>(Enumerable.Range(1, NumberOfElements).Select(n => new Location4("", n))); } [Benchmark] public bool Path_Position_DefaultEquality() { var first = new Location1("", 0); return _locations1.Contains(first); } [Benchmark] public bool Position_Path_DefaultEquality() { var first = new Location2("", 0); return _locations2.Contains(first); } [Benchmark] public bool Path_Position_OverridenEquality() { var first = new Location3("", 0); return _locations3.Contains(first); } 


  Method | NumOfElements | Mean | Gen 0 | Allocated | -------------------------------- |------ |--------------:|--------:|----------:| Path_Position_DefaultEquality | 1 | 885.63 ns | 0.0286 | 92 B | Position_Path_DefaultEquality | 1 | 127.80 ns | 0.0050 | 16 B | Path_Position_OverridenEquality | 1 | 47.99 ns | - | 0 B | Path_Position_DefaultEquality | 10 | 6,214.02 ns | 0.2441 | 776 B | Position_Path_DefaultEquality | 10 | 130.04 ns | 0.0050 | 16 B | Path_Position_OverridenEquality | 10 | 47.67 ns | - | 0 B | Path_Position_DefaultEquality | 1000 | 589,014.52 ns | 23.4375 | 76025 B | Position_Path_DefaultEquality | 1000 | 133.74 ns | 0.0050 | 16 B | Path_Position_OverridenEquality | 1000 | 48.51 ns | - | 0 B |

Jika nilai bidang pertama selalu sama, maka secara default fungsi hash mengembalikan nilai yang sama untuk semua elemen dan set hash secara efektif dikonversi ke daftar tertaut dengan operasi penyisipan dan pencarian O (N) dan pencarian. Jumlah operasi untuk mengisi koleksi menjadi O (N ^ 2) (di mana N adalah jumlah sisipan dengan kompleksitas O (N) untuk setiap sisipan). Ini berarti bahwa menyisipkan ke dalam kumpulan 1000 elemen akan menghasilkan hampir 500.000 panggilan ke ValueType.Equals . Berikut adalah konsekuensi dari metode yang menggunakan refleksi!

Seperti yang ditunjukkan dalam tes, kinerja akan dapat diterima jika Anda beruntung dan elemen pertama dari struktur ini unik (dalam kasus Position_Path_DefaultEquality ). Tetapi jika tidak demikian, maka produktivitas akan sangat rendah.

Masalah nyata


Saya pikir sekarang Anda bisa menebak masalah apa yang baru-baru ini saya temui. Beberapa minggu yang lalu saya menerima pesan kesalahan: runtime aplikasi yang saya kerjakan meningkat dari 10 menjadi 60 detik. Untungnya, laporan itu sangat rinci dan berisi acara Tracing untuk Windows, sehingga area masalah ditemukan dengan cepat - ValueType.Equals dimuat 50 detik.

Setelah melihat sekilas kode tersebut, menjadi jelas apa masalahnya:

 private readonly HashSet<(ErrorLocation, int)> _locationsWithHitCount; readonly struct ErrorLocation { // Empty almost all the time public string OptionalDescription { get; } public string Path { get; } public int Position { get; } }

Saya menggunakan tuple yang berisi tipe struct kustom dengan versi standar Equals . Dan sayangnya, ia memiliki bidang pertama opsional, yang hampir selalu menyamai String.equals . Produktivitas tetap tinggi sampai jumlah elemen dalam set meningkat secara signifikan. Dalam hitungan menit, koleksi dengan puluhan ribu elemen telah diinisialisasi.

Apakah implementasi ValueType.Equals/GetHashCode default selalu berjalan lambat?


ValueType.Equals dan ValueType.GetHashCode memiliki metode optimasi khusus. Jika jenisnya tidak memiliki "pointer" dan itu dikemas dengan benar (saya akan menunjukkan contoh dalam satu menit), maka versi dioptimalkan digunakan: iterasi GetHashCode dilakukan pada blok contoh, XOR dari 4 byte digunakan, metode memcmp membandingkan dua contoh menggunakan memcmp .

 // Optimized ValueType.GetHashCode implementation static INT32 FastGetValueTypeHashCodeHelper(MethodTable *mt, void *pObjRef) { INT32 hashCode = 0; INT32 *pObj = (INT32*)pObjRef; // this is a struct with no refs and no "strange" offsets, just go through the obj and xor the bits INT32 size = mt->GetNumInstanceFieldBytes(); for (INT32 i = 0; i < (INT32)(size / sizeof(INT32)); i++) hashCode ^= *pObj++; return hashCode; } // Optimized ValueType.Equals implementation FCIMPL2(FC_BOOL_RET, ValueTypeHelper::FastEqualsCheck, Object* obj1, Object* obj2) { TypeHandle pTh = obj1->GetTypeHandle(); FC_RETURN_BOOL(memcmp(obj1->GetData(), obj2->GetData(), pTh.GetSize()) == 0); }

Pemeriksaan itu sendiri dilakukan di ValueTypeHelper::CanCompareBits , itu disebut baik dari iterasi ValueType.Equals dan dari iterasi ValueType.GetHashCode .

Tetapi optimisasi adalah hal yang sangat berbahaya.

Pertama, sulit dipahami ketika dihidupkan; bahkan perubahan kecil pada kode dapat menghidupkan dan mematikannya:

 public struct Case1 { // Optimization is "on", because the struct is properly "packed" public int X { get; } public byte Y { get; } } public struct Case2 { // Optimization is "off", because struct has a padding between byte and int public byte Y { get; } public int X { get; } }

Untuk informasi lebih lanjut tentang struktur memori, lihat blog saya, "Elemen Internal Objek yang Dikelola, Bagian 4. Struktur Lapangan" .

Kedua, membandingkan memori tidak selalu memberi Anda hasil yang benar. Ini adalah contoh sederhana:

 public struct MyDouble { public double Value { get; } public MyDouble(double value) => Value = value; } double d1 = -0.0; double d2 = +0.0; // True bool b1 = d1.Equals(d2); // False! bool b2 = new MyDouble(d1).Equals(new MyDouble(d2));

-0,0 dan +0,0 sama, tetapi memiliki representasi biner yang berbeda. Ini berarti bahwa Double.Equals benar dan MyDouble.Equals salah. Dalam kebanyakan kasus, perbedaannya tidak signifikan, tetapi bayangkan berapa jam yang Anda habiskan untuk memperbaiki masalah yang disebabkan oleh perbedaan ini.

Bagaimana cara menghindari masalah serupa?


Bisakah Anda bertanya kepada saya bagaimana hal di atas dapat terjadi dalam situasi nyata? Salah satu cara yang jelas untuk memulai metode Equals dan GetHashCode di jenis struct - menggunakan FxCop aturan CA1815 . Tetapi ada satu masalah: ini adalah pendekatan yang terlalu ketat.

Aplikasi yang kinerjanya sangat penting dapat memiliki ratusan tipe struct yang belum tentu digunakan dalam kumpulan hash atau kamus. Oleh karena itu, pengembang aplikasi dapat menonaktifkan aturan, yang akan menimbulkan konsekuensi yang tidak menyenangkan jika tipe struct menggunakan fungsi yang dimodifikasi.

Pendekatan yang lebih tepat adalah untuk memperingatkan pengembang jika struct tipe "tidak pantas" dengan nilai elemen default yang sama (didefinisikan dalam aplikasi atau perpustakaan pihak ketiga) disimpan dalam hash set. Tentu saja saya berbicara tentang ErrorProne.NET dan aturan yang saya tambahkan di sana segera setelah saya mengalami masalah ini:



Versi ErrorProne.NET tidak sempurna dan akan "menyalahkan" kode yang benar jika penyelesai kesetaraan khusus digunakan dalam konstruktor:



Tapi saya masih berpikir itu layak peringatan jika struct dengan elemen yang sama secara default tidak digunakan ketika sedang diproduksi. Misalnya, ketika saya memeriksa aturan saya, saya menyadari bahwa struktur System.Collections.Generic.KeyValuePair <TKey, TValue> yang didefinisikan dalam mscorlib tidak menimpa Equals dan GetHashCode . Tidak mungkin ada orang yang akan mendefinisikan variabel seperti HashSet <KeyValuePair<string, int>> hari ini, tapi saya percaya bahkan BCL dapat melanggar aturan. Karena itu, ada baiknya menemukan ini sebelum terlambat.

Kesimpulan


  • Menerapkan kesetaraan default untuk tipe struct dapat memiliki konsekuensi serius untuk aplikasi Anda. Ini masalah nyata, bukan teoretis.
  • Elemen kesetaraan default untuk tipe nilai didasarkan pada refleksi.
  • Distribusi yang dilakukan oleh GetHashCode versi standar akan sangat buruk jika bidang pertama dari banyak instance memiliki nilai yang sama.
  • Ada versi yang dioptimalkan untuk metode Equals dan GetHashCode standar, tetapi Anda tidak harus bergantung pada mereka, karena bahkan perubahan kode kecil dapat mematikannya.
  • Gunakan aturan FxCop untuk memastikan bahwa setiap tipe struct mengabaikan elemen kesetaraan. Namun, lebih baik untuk mencegah masalah dengan penganalisis jika struktur "tidak tepat" disimpan dalam set hash atau dalam tabel hash.

Sumber Daya Tambahan


Source: https://habr.com/ru/post/id418515/

More articles:


All Articles