程序代写代做代考 graph Java COMP0020: Functional Programming

COMP0020: Functional Programming
Example Programs
COMP0020 Functional Programming Lecture 20
Garbage Collection Techniques
Christopher D. Clack (University College London)
COMP0020: Functional Programming
Academic Year 2018-2019 26 / 58

COMP0020: Functional Programming
Example Programs
Contents
Motivation Mark-scan Two-space copying Reference counting Comparison
Christopher D. Clack (University College London)
COMP0020: Functional Programming
Academic Year 2018-2019 27 / 58

COMP0020: Functional Programming
Example Programs
Motivation
Beta reduction in Miranda can cause heap cells to become detached from the program graph Similar eects in Java
Fixed heap size – limited resources
How do we reuse (recycle) memory ?
Christopher D. Clack (University College London)
COMP0020: Functional Programming
Academic Year 2018-2019 28 / 58

COMP0020: Functional Programming
Example Programs
Motivation
We need to :
I Find which cells are no longer required by the program I Make those cells available to the memory allocator
Unreferenced cells are called GARBAGE
Key technique : “GARBAGE COLLECTION” Three popular variants :
I Mark-scan
I Two-space (or “semi-space”) copying I Reference counting
Christopher D. Clack (University College London)
COMP0020: Functional Programming
Academic Year 2018-2019 29 / 58

COMP0020: Functional Programming
Example Programs
1. Mark-scan
Triggered when program has used >80% of heap Evaluation suspended until collector finished
May happen many times during program Mark :
I Follow pointers from root cell of program and mark all reachable cells (set “mark bit” to 1)
Scan :
I All cells in the heap
F if marked, set mark bit to 0 (ready for next mark) F else attach cell to free list
Christopher D. Clack (University College London)
COMP0020: Functional Programming
Academic Year 2018-2019 30 / 58

COMP0020: Functional Programming
Example Programs
1. Mark-scan
Mark-scan uses a FREE LIST for allocation
I A linked list of cells which are available for use by the program I Before program starts, ALL cells are on free list
F Then program is loaded F Then program is run
I Scanner re-creates the free list by linking all unused cells I Cells are unlinked from free list when allocated
Christopher D. Clack (University College London)
COMP0020: Functional Programming
Academic Year 2018-2019 31 / 58

COMP0020: Functional Programming
Example Programs
2. Two-space copying
The two-space collector must :
I Follow pointers from the root cell of the program in FROM space, COPY each cell into TO-space and update any pointers to that cell so they now point to the copy in TO-space.
I Swap the names/roles of FROM-space and TO-space I Allow evaluation to proceed
Garbage is “left behind” after copying Allocation is by simple (fast) pointer-increment
Christopher D. Clack (University College London)
COMP0020: Functional Programming
Academic Year 2018-2019 32 / 58

COMP0020: Functional Programming
Example Programs
3. Reference Counting
Each cell is extended with a reference count field
The reference count keeps track of how many pointers are pointing to this cell :
I Each new pointer to this cell causes its reference count to be incremented
I Each deletion of a pointer to this cell causes its reference count to be decremented
Any cell with a reference count of 0 is garbage. All cells with reference count 0 are on FREE LIST
Christopher D. Clack (University College London)
COMP0020: Functional Programming
Academic Year 2018-2019 33 / 58

COMP0020: Functional Programming
Example Programs
Comparison
Overheads :
I iMark-scan :
F 1 bit per cell
F + a stack for traversal (or use pointer-reversal) I Copying :
F 100% space overhead I Reference count :
F typically 32 bits per cell
F + time overhead (when copy/delete pointer, must also read in and modify the cell it points to !)
Christopher D. Clack (University College London)
COMP0020: Functional Programming
Academic Year 2018-2019 34 / 58

COMP0020: Functional Programming
Example Programs
Comparison
Compaction/fragmentation
I Mark-scan :
F Must run separate compactor (during scan phase) to reduce fragmentation
I Copying :
F Inherently compacting
F No fragmentation immediately after copy (BUT remember 100% overhead) I Reference counting :
F Must run separate compactor to reduce fragmentation
Christopher D. Clack (University College London)
COMP0020: Functional Programming
Academic Year 2018-2019 35 / 58

COMP0020: Functional Programming
Example Programs
Comparison
Small program in big heap :
I Mark-scan : visits ALL heap cells (slow)
I Copying : only visits program cells (fast)
I Reference count : only visits cells in use (fast)
Large program (nearly fills heap) :
I Mark-scan : performance degrades I Copying : performance degrades
I Reference count : unaected
Christopher D. Clack (University College London)
COMP0020: Functional Programming
Academic Year 2018-2019 36 / 58

COMP0020: Functional Programming
Example Programs
Comparison
Cyclic structures in heap :
I Mark-scan : unaected
I Copying : unaected
I Reference count : needs special attention !
Christopher D. Clack (University College London)
COMP0020: Functional Programming
Academic Year 2018-2019 37 / 58

COMP0020: Functional Programming
Example Programs
Summary
Summary
Motivation Mark-scan Two-space copying Reference counting Comparison
Christopher D. Clack (University College London)
COMP0020: Functional Programming
Academic Year 2018-2019 38 / 58

COMP0020: Functional Programming
Example Programs
Summary
END OF LECTURE
Christopher D. Clack (University College London)
COMP0020: Functional Programming
Academic Year 2018-2019 39 / 58