Locality of Reference

দুই রূপ। Temporal locality — যা এইমাত্র access হয়েছে তা আবার শীঘ্রই লাগবে (loop counter, accumulator, বারবার call হওয়া function)। Spatial locality — যা access হয়েছে তার কাছাকাছি ঠিকানার ডেটাও শীঘ্রই লাগবে (array traversal, struct field access)।

কেন না থাকলে hierarchy অকেজো: [[cache]] শুধু কাজ করে কারণ ছোট, দ্রুত storage-এ সাম্প্রতিক/কাছাকাছি ডেটা রাখলে বেশিরভাগ access hit পায়। Access সত্যিই random হলে প্রতিটাই [[cache-miss]] হতো — hierarchy-র কোনো লাভ থাকত না।

হার্ডওয়্যার উৎস: base+offset addressing mode (array/struct access-এর জন্য ব্যবহৃত) স্বয়ংক্রিয়ভাবে spatially local ঠিকানা তৈরি করে — arr[i]-এর পরপর ঠিকানা মাত্র element_size বাইট দূরে।

পরিমাপযোগ্য প্রমাণ: array বনাম linked-list traversal — দুটোই Θ(n) (mathematics/asymptotic-notation), তবু array ১০-৫০× দ্রুত, কারণ array-তে spatial locality আছে (একটা [[cache-line]] আনলেই একসাথে অনেক element), linked-list-এ নেই (প্রতিটা node এলোমেলো heap address)।