Saya memiliki pohon keputusan biner yang sangat penting untuk kinerja, dan saya ingin memfokuskan pertanyaan ini pada satu baris kode. Kode untuk iterator pohon biner ada di bawah ini dengan hasil dari menjalankan analisis kinerja terhadapnya.
public ScTreeNode GetNodeForState(int rootIndex, float[] inputs)
{
0.2% ScTreeNode node = RootNodes[rootIndex].TreeNode;
24.6% while (node.BranchData != null)
{
0.2% BranchNodeData b = node.BranchData;
0.5% node = b.Child2;
12.8% if (inputs[b.SplitInputIndex] <= b.SplitValue)
0.8% node = b.Child1;
}
0.4% return node;
}
BranchData adalah bidang, bukan properti. Saya melakukan ini untuk mencegah risiko tidak sebaris.
Kelas BranchNodeData adalah sebagai berikut:
public sealed class BranchNodeData
{
/// <summary>
/// The index of the data item in the input array on which we need to split
/// </summary>
internal int SplitInputIndex = 0;
/// <summary>
/// The value that we should split on
/// </summary>
internal float SplitValue = 0;
/// <summary>
/// The nodes children
/// </summary>
internal ScTreeNode Child1;
internal ScTreeNode Child2;
}
Seperti yang Anda lihat, while loop / null check sangat berpengaruh pada kinerja. Pohonnya besar, jadi saya berharap mencari daun akan memakan waktu cukup lama, tetapi saya ingin memahami jumlah waktu yang tidak proporsional yang dihabiskan untuk satu baris itu.
Saya sudah mencoba:
- Memisahkan cek Null dari sementara - cek Null itulah yang menjadi hit.
- Menambahkan bidang boolean ke objek dan memeriksanya, tidak ada bedanya. Tidak peduli apa yang dibandingkan, masalahnya adalah perbandingan.
Apakah ini masalah prediksi cabang? Jika ya, apa yang dapat saya lakukan? Jika ada?
Saya tidak akan berpura-pura memahami CIL , tetapi saya akan mempostingnya untuk semua orang sehingga mereka dapat mencoba mengambil beberapa informasi darinya.
.method public hidebysig
instance class OptimalTreeSearch.ScTreeNode GetNodeForState (
int32 rootIndex,
float32[] inputs
) cil managed
{
// Method begins at RVA 0x2dc8
// Code size 67 (0x43)
.maxstack 2
.locals init (
[0] class OptimalTreeSearch.ScTreeNode node,
[1] class OptimalTreeSearch.BranchNodeData b
)
IL_0000: ldarg.0
IL_0001: ldfld class [mscorlib]System.Collections.Generic.List`1<class OptimalTreeSearch.ScRootNode> OptimalTreeSearch.ScSearchTree::RootNodes
IL_0006: ldarg.1
IL_0007: callvirt instance !0 class [mscorlib]System.Collections.Generic.List`1<class OptimalTreeSearch.ScRootNode>::get_Item(int32)
IL_000c: ldfld class OptimalTreeSearch.ScTreeNode OptimalTreeSearch.ScRootNode::TreeNode
IL_0011: stloc.0
IL_0012: br.s IL_0039
// loop start (head: IL_0039)
IL_0014: ldloc.0
IL_0015: ldfld class OptimalTreeSearch.BranchNodeData OptimalTreeSearch.ScTreeNode::BranchData
IL_001a: stloc.1
IL_001b: ldloc.1
IL_001c: ldfld class OptimalTreeSearch.ScTreeNode OptimalTreeSearch.BranchNodeData::Child2
IL_0021: stloc.0
IL_0022: ldarg.2
IL_0023: ldloc.1
IL_0024: ldfld int32 OptimalTreeSearch.BranchNodeData::SplitInputIndex
IL_0029: ldelem.r4
IL_002a: ldloc.1
IL_002b: ldfld float32 OptimalTreeSearch.BranchNodeData::SplitValue
IL_0030: bgt.un.s IL_0039
IL_0032: ldloc.1
IL_0033: ldfld class OptimalTreeSearch.ScTreeNode OptimalTreeSearch.BranchNodeData::Child1
IL_0038: stloc.0
IL_0039: ldloc.0
IL_003a: ldfld class OptimalTreeSearch.BranchNodeData OptimalTreeSearch.ScTreeNode::BranchData
IL_003f: brtrue.s IL_0014
// end loop
IL_0041: ldloc.0
IL_0042: ret
} // end of method ScSearchTree::GetNodeForState
Sunting: Saya memutuskan untuk melakukan tes prediksi cabang, saya menambahkan identik jika dalam beberapa saat, jadi kita punya
while (node.BranchData != null)dan
if (node.BranchData != null)di dalam itu. Saya kemudian menjalankan analisis kinerja terhadapnya, dan butuh enam kali lebih lama untuk menjalankan perbandingan pertama seperti yang dilakukan untuk mengeksekusi perbandingan kedua yang selalu mengembalikan true. Jadi sepertinya ini memang masalah prediksi cabang - dan saya rasa tidak ada yang bisa saya lakukan ?!
Edit lainnya
Hasil di atas juga akan terjadi jika node.BranchData harus dimuat dari RAM untuk pemeriksaan while - kemudian akan di-cache untuk pernyataan if.
Ini adalah pertanyaan ketiga saya tentang topik serupa. Kali ini saya fokus pada satu baris kode. Pertanyaan saya yang lain tentang hal ini adalah:
sumber
BranchNodeproperti. Silakan coba gantinode.BranchData != nullReferenceEquals(node.BranchData, null). Apakah ada bedanya?while(true) { /* current body */ if(node.BranchData == null) return node; }. Apakah itu mengubah sesuatu?while(true) { BranchNodeData b = node.BranchData; if(ReferenceEquals(b, null)) return node; node = b.Child2; if (inputs[b.SplitInputIndex] <= b.SplitValue) node = b.Child1; }Ininode. BranchDatahanya akan diambil sekali.Jawaban:
Sejauh ini, hal termahal yang pernah dilakukan prosesor bukanlah menjalankan instruksi, melainkan mengakses memori. Inti eksekusi modern CPU adalah banyak kali lebih cepat dari bus memori. Masalah yang berkaitan dengan jarak , semakin jauh sinyal listrik harus berjalan, semakin sulit untuk mendapatkan sinyal tersebut dikirim ke ujung lain kabel tanpa merusaknya. Satu-satunya obat untuk masalah itu adalah membuatnya lebih lambat. Masalah besar dengan kabel yang menghubungkan CPU ke RAM di mesin Anda, Anda dapat membuka casing dan melihat kabelnya.
Prosesor memiliki solusi untuk masalah ini, mereka menggunakan cache , buffer yang menyimpan salinan byte dalam RAM. Yang penting adalah L1 cache , biasanya 16 kilobyte untuk data dan 16 kilobyte untuk instruksi. Kecil, memungkinkannya mendekati mesin eksekusi. Membaca byte dari cache L1 biasanya membutuhkan 2 atau 3 siklus CPU. Selanjutnya adalah cache L2, lebih besar dan lebih lambat. Prosesor kelas atas juga memiliki cache L3, lebih besar dan lebih lambat. Ketika teknologi proses meningkat, buffer tersebut mengambil lebih sedikit ruang dan secara otomatis menjadi lebih cepat saat mereka semakin dekat ke inti, alasan besar mengapa prosesor yang lebih baru lebih baik dan bagaimana mereka mengelola untuk menggunakan jumlah transistor yang semakin meningkat.
Namun cache tersebut bukanlah solusi yang sempurna. Prosesor akan tetap berhenti pada akses memori jika data tidak tersedia di salah satu cache. Itu tidak dapat berlanjut sampai bus memori yang sangat lambat telah menyediakan data. Kehilangan ratusan siklus CPU dimungkinkan dalam satu instruksi.
Struktur pohon merupakan masalah, mereka tidak ramah cache. Node mereka cenderung tersebar di seluruh ruang alamat. Cara tercepat untuk mengakses memori adalah dengan membaca dari alamat berurutan. Unit penyimpanan untuk L1 cache adalah 64 byte. Atau dengan kata lain, setelah prosesor membaca satu byte, 63 byte berikutnya sangat cepat karena mereka akan ada di cache.
Yang membuat array sejauh ini menjadi struktur data yang paling efisien. Juga alasan bahwa kelas .NET List <> bukanlah daftar sama sekali, ia menggunakan array untuk penyimpanan. Hal yang sama untuk jenis koleksi lainnya, seperti Kamus, secara struktural tidak mirip dengan array, tetapi diimplementasikan secara internal dengan array.
Jadi, pernyataan while () Anda kemungkinan besar akan terganggu oleh CPU yang macet karena itu mendereferensi penunjuk untuk mengakses bidang BranchData. Pernyataan berikutnya sangat murah karena pernyataan while () sudah melakukan pekerjaan berat dalam mengambil nilai dari memori. Menetapkan variabel lokal itu murah, prosesor menggunakan buffer untuk menulis.
Bukan masalah sederhana untuk dipecahkan, meratakan pohon Anda menjadi susunan kemungkinan besar tidak praktis. Tidak sedikit karena Anda biasanya tidak dapat memprediksi urutan simpul pohon yang akan dikunjungi. Pohon merah-hitam mungkin membantu, tidak jelas dari pertanyaannya. Jadi kesimpulan sederhana untuk ditarik adalah bahwa itu sudah berjalan secepat yang Anda bisa harapkan. Dan jika Anda membutuhkannya untuk bekerja lebih cepat maka Anda memerlukan perangkat keras yang lebih baik dengan bus memori yang lebih cepat. DDR4 akan menjadi mainstream tahun ini.
sumber
Untuk melengkapi jawaban hebat Hans tentang efek cache memori, saya menambahkan diskusi tentang memori virtual ke terjemahan memori fisik dan efek NUMA.
Dengan komputer memori virtual (semua komputer saat ini), saat melakukan akses memori, setiap alamat memori virtual harus diterjemahkan ke alamat memori fisik. Ini dilakukan oleh perangkat keras manajemen memori menggunakan tabel terjemahan. Tabel ini dikelola oleh sistem operasi untuk setiap proses dan disimpan dalam RAM. Untuk setiap halaman memori virtual, ada entri dalam tabel terjemahan ini yang memetakan halaman virtual ke halaman fisik. Ingat diskusi Hans tentang akses memori yang mahal: jika setiap terjemahan virtual ke fisik memerlukan pencarian memori, semua akses memori akan menelan biaya dua kali lipat. Solusinya adalah memiliki cache untuk tabel terjemahan yang disebut buffer tepi tampilan terjemahan(TLB singkatnya). TLB tidak besar (12 hingga 4096 entri), dan ukuran halaman tipikal pada arsitektur x86-64 hanya 4 KB, yang berarti bahwa ada paling banyak 16 MB yang dapat langsung diakses dengan klik TLB (mungkin bahkan kurang dari itu, Sandy Bridge yang memiliki ukuran TLB 512 item ). Untuk mengurangi jumlah TLB yang terlewat, Anda dapat memiliki sistem operasi dan aplikasi yang bekerja sama untuk menggunakan ukuran halaman yang lebih besar seperti 2 MB, yang mengarah ke ruang memori yang jauh lebih besar yang dapat diakses dengan klik TLB. Halaman ini menjelaskan bagaimana menggunakan halaman besar dengan Java yang dapat sangat mempercepat akses memori .
Jika komputer Anda memiliki banyak soket, kemungkinan itu adalah arsitektur NUMA . NUMA berarti Akses Memori Non-Seragam. Dalam arsitektur ini, beberapa akses memori biaya lebih dari yang lain. Sebagai contoh, dengan komputer 2 soket dengan RAM 32 GB, setiap soket mungkin memiliki RAM 16 GB. Pada komputer contoh ini, akses memori lokal lebih murah daripada akses ke memori soket lain (akses jarak jauh 20 hingga 100% lebih lambat, bahkan mungkin lebih). Jika di komputer seperti itu, pohon Anda menggunakan 20 GB RAM, setidaknya 4 GB data Anda ada di node NUMA lainnya, dan jika akses 50% lebih lambat untuk memori jarak jauh, akses NUMA memperlambat akses memori Anda sebesar 10%. Selain itu, jika Anda hanya memiliki memori kosong pada satu node NUMA, semua proses yang membutuhkan memori pada node yang kelaparan akan dialokasikan memori dari node lain yang aksesnya lebih mahal. Lebih buruk lagi, sistem operasi dapat berpikir bahwa menukar bagian memori dari node yang kelaparan adalah ide yang bagus,yang akan menyebabkan akses memori lebih mahal . Hal ini dijelaskan secara lebih rinci dalam Masalah "swap insanity" MySQL dan efek dari arsitektur NUMA di mana beberapa solusi diberikan untuk Linux (menyebarkan akses memori pada semua node NUMA, mengatasi masalah pada akses NUMA jarak jauh untuk menghindari pertukaran). Saya juga dapat memikirkan untuk mengalokasikan lebih banyak RAM ke soket (24 dan 8 GB daripada 16 dan 16 GB) dan memastikan program Anda dijadwalkan pada simpul NUMA yang lebih besar, tetapi ini membutuhkan akses fisik ke komputer dan obeng ;-) .
sumber
Ini bukan jawaban semata melainkan penekanan pada apa yang ditulis Hans Passant tentang penundaan dalam sistem memori.
Perangkat lunak berkinerja sangat tinggi - seperti game komputer - tidak hanya dibuat untuk mengimplementasikan game itu sendiri, tetapi juga diadaptasi sedemikian rupa sehingga kode dan struktur data memanfaatkan cache dan sistem memori secara maksimal, yaitu memperlakukannya sebagai sumber daya yang terbatas. Ketika saya menangani masalah cache, saya biasanya berasumsi bahwa L1 akan mengirimkan dalam 3 siklus jika data ada di sana. Jika tidak dan saya harus pergi ke L2 saya asumsikan 10 siklus. Untuk L3 30 siklus dan untuk memori RAM 100.
Ada tindakan terkait memori tambahan yang - jika Anda perlu menggunakannya - memberikan hukuman yang lebih besar dan itu adalah kunci bus. Kunci bus disebut bagian penting jika Anda menggunakan fungsionalitas Windows NT. Jika Anda menggunakan varietas yang ditanam sendiri, Anda mungkin menyebutnya spinlock. Apa pun namanya yang disinkronkan ke perangkat master bus paling lambat dalam sistem sebelum kunci dipasang. Perangkat bus-mastering paling lambat mungkin adalah kartu PCI 32-bit klasik yang tersambung @ 33MHz. 33MHz adalah seperseratus frekuensi dari CPU x86 biasa (@ 3,3 GHz). Saya berasumsi tidak kurang dari 300 siklus untuk menyelesaikan kunci bus tetapi saya tahu mereka bisa memakan waktu berkali-kali selama itu jadi jika saya melihat 3000 siklus saya tidak akan terkejut.
Pengembang perangkat lunak multi-threading pemula akan menggunakan kunci bus di semua tempat dan kemudian bertanya-tanya mengapa kode mereka lambat. Triknya - seperti semua yang berkaitan dengan memori - adalah menghemat akses.
sumber