Bingung antara lokalitas Temporal dan Spasial dalam kode kehidupan nyata

Pertama, referensi ke var bisa lokal sementara atau lokal spasial bukan lokalitas sementara, yang merupakan tata bahasa yang tidak tepat. Poin kecil.

Sekarang, ke pertanyaan Anda.

1. Prinsip Lokalitas temporal menyatakan bahwa dua instruksi mereferensikan lokasi yang sama dalam jangka waktu yang relatif singkat. Misalnya, dalam kode yang diberikan, a[i] sering direferensikan, dengan instruksi seperti a[i] = a[i] * 2 dan a[i] = a[i] * 3 dieksekusi sangat berdekatan. Jika kita melihat cakupan ini, kita dapat mengatakan bahwa referensi ke j dan a[i] bersifat lokal sementara. Referensi ke i juga bersifat lokal sementara, karena i direferensikan setiap kali a[i] ada. Namun, jika baris terakhir kode yang diberikan berbunyi seperti a[j] = a[j] * j, maka referensi ke i tidak akan bersifat lokal sementara, setidaknya dalam cakupan loop dalam^[1].

2. Prinsip Lokalitas spasial menyatakan bahwa dua instruksi mereferensikan lokasi memori yang berdekatan. Referensi ke a[i] adalah contoh bagus untuk hal ini, karena orang dapat berasumsi (sebagian besar waktu) bahwa a[0] dan a[1] akan bersebelahan dalam memori.

3. Dua yang pertama pada dasarnya mencakup hal ini, tetapi teks yang dikutip benar, dan kode tersebut juga menunjukkan lokalitas spasial.

[1] - Secara umum, ketika Anda berbicara tentang lokalitas, itu akan berada dalam konteks tingkat tertentu dalam hierarki memori, apakah itu RAM atau cache L1 atau apa pun yang Anda miliki. Dalam semua hal kecuali dalam arti yang paling terbatas, referensi ke i dan j bersifat lokal sementara.

Menulis jawaban ini karena saya tidak mengerti bahkan setelah membaca jawaban lain pada pertanyaan ini, beberapa pertanyaan lain dan wikipedia (itu lebih membingungkan.)

Saya rasa kami menghabiskan banyak waktu dan energi untuk memahami terminologi yang agak membingungkan/rumit dalam kasus ini. Saya merasa lebih mudah untuk memahaminya ketika saya tidak memperhatikan istilah 'spasial' dan 'temporal'.

Mari kita mulai dengan dasar-dasarnya.

Mari kita coba memahami apa itu cache - tempat yang lebih cepat diakses dibandingkan memori utama. Itu keren. Tapi tempat ini terbatas dan mahal, jadi sebaiknya gunakan dengan bijak. Namun bagaimana Anda (atau OS) memutuskan apa yang akan dimasukkan ke dalam cache dan apa yang tidak akan dimasukkan? Seharusnya ada cara untuk mengetahui apa yang kita butuhkan di masa depan.. ah prediksi masa depan! (Laporan Minoritas! Bunyikan loncengnya?).

Harus ada cara untuk menentukan kebutuhan program di masa depan. Dengan menggunakan akal sehat dan kodenya, kita dapat mengatakan bahwa beberapa bagian kode bersifat berulang - contoh - loop! Jika ada variabel i di dalam satu lingkaran, Anda tahu variabel itu akan diakses berulang kali dalam waktu dekat. Inilah prinsip di balik lokalitas temporal. saya dapat dibawa ke cache karena bersifat lokal sementara.

Di area lain jika kode menggunakan struktur data linier (contoh: Array) dan itu juga dalam satu lingkaran dengan kenaikan indeks, maka mudah untuk melihat bahwa meskipun kebutuhan saat ini hanya lokasi ke-3 (misalnya) dari struktur data ini, lokasi berikutnya juga akan segera diperlukan karena indeks meningkat sebesar 1 untuk struktur data linier tersebut. Jadi alangkah baiknya jika kita membawa datanya di beberapa lokasi berikutnya juga. Inilah prinsip di balik lokalitas spasial. Beberapa lokasi berikutnya dapat dimasukkan ke dalam cache karena bersifat lokal secara spasial.

Konsep lokalitas pada dasarnya adalah mengidentifikasi data dan instruksi untuk memasukkan cache sehingga kita dapat mengurangi kesalahan cache dan memanfaatkan tempat khusus ini secara efektif.

Lingkaran luar adalah contoh lokalitas spasial. Ini secara berurutan menambah alamat panggilan for-loop bagian dalam.

Lingkaran dalam menunjukkan lokalitas temporal. Alamat memori yang sama diakses sepuluh kali berturut-turut, dan dikalikan dengan j setiap kali.

Adapun dua pertanyaan pertama Anda, i dan j (penghitung loop) adalah contoh yang sangat baik dari lokalitas temporal.

Lokalitas adalah ukuran yang diterapkan oleh cache untuk meminimalkan panggilan ke memori. Jika suatu instruksi perlu mengetahui nilai alamat memori yang belum ada dalam cache, maka instruksi tersebut akan mengakses memori dan menyimpan semua lokasi memori di sekitarnya dalam cache juga.

Mari kita mulai dengan mendefinisikan Lokalitas Temporal dan Spasial.

Lokalitas Temporal - Lokalitas temporal berarti data atau instruksi terkini yang sedang diambil mungkin diperlukan segera. Jadi kita harus menyimpan data atau instruksi tersebut dalam memori cache sehingga kita dapat menghindari pencarian data yang sama lagi di memori utama dan dengan demikian menghemat waktu.

Lokalitas Spasial - Lokalitas spasial berarti instruksi atau data yang dekat dengan lokasi memori saat ini yang sedang diambil, mungkin diperlukan segera dalam waktu dekat.

sum = 0;
for (i = 0; i < arr.length; i++)
  sum += arr[i];
return sum;

Sekarang lihat contoh ini, Di sini jumlah variabel digunakan berulang kali yang menunjukkan Lokalitas Temporal dan kemudian nilai array arr diakses secara berurutan yaitu arr[0], arr[1], arr [2] ,... dan seterusnya dan yang menampilkan Lokalitas spasial karena array merupakan blok memori Berdekatan(berdekatan) sehingga data yang dekat dengan lokasi memori saat ini diambil.

Sekarang lihat contoh ini

for(i = 0; i < 20; i++)
    for(j = 0; j < 10; j++)
        a[i] = a[i]*j;

Di sini kita melihat lokalitas temporal sebagai a[i] di loop kedua digunakan berulang kali dan kemudian variabel j diakses untuk menunjukkan Lokalitas Spasial.