CSE 373 Lecture Notes - Lecture 5: Locality Of Reference, Linked List
17 May 2018
School
Department
Course
Professor
CSE 373 Lecture 5
Implementing Tree Map
- Putting into a tree
o Traversing, then hit null → create a new node
- AVL inbalance cases:
Check for + fix inbalances:
Memory architecture
- More memory a layer can store, slower it is
- Accessing disk is very slow
- Balance between speed and space
Locality
Document Summary
Putting into a tree: traversing, then hit null create a new node. More memory a layer can store, slower it is. Spatial partition memory you are likely to use close by: arrays + fields, leveraging special locality, bring more in than you need. Temporal computers assume memory you just accessed will be likely accessed in the near future: leveraging temporal locality, once something is loaded into ram or cache, keep it around for a while. Amount of memory moved from disk to ram: called a block/page, ~4kb (smallest unit of data on disk) Amount of memory moved from ram to cache: called a cache line, ~64 bytes. Operating system is boss: controls page and cache line size, decides when to move or evict data. Progra(cid:373) asks ja(cid:448)a virtual machi(cid:374)e (cid:894)jvm(cid:895) for (cid:373)ore (cid:373)e(cid:373)ory fro(cid:373) the (cid:862)heap(cid:863) (cid:894)pile of recently used memory) If necessary, jvm asks operating system for more memory.
