ClementBera uploaded a new version of VMMaker to project VM Maker: http://source.squeak.org/VMMaker/VMMaker.oscog-cb.2378.mcz
==================== Summary ====================
Name: VMMaker.oscog-cb.2378 Author: cb Time: 27 April 2018, 10:07:17.97412 am UUID: 4dc47e41-2815-44b2-9c16-23caeb9df018 Ancestors: VMMaker.oscog-cb.2377
Improved compactor comments.
Introduced SpurTrackingCompactor (Work in progress) which emulates Garbage First compaction behavior.
Added SpurAnalysingSweeper as common superclass of SelectiveCompactor and TrackingCompactor. SpurAnalysingSweeper includes APIs to sweep the heap and compute occupation of each segment at the same time, which is used by Selective and Tracking compactors (they compact only the least used segments).
=============== Diff against VMMaker.oscog-cb.2377 ===============
Item was added: + SpurSweeper subclass: #SpurAnalysingSweeper + instanceVariableNames: '' + classVariableNames: '' + poolDictionaries: '' + category: 'VMMaker-SpurMemoryManager'! + + !SpurAnalysingSweeper commentStamp: 'cb 4/27/2018 09:45' prior: 0! + Abstract class, in addition to SpurSweeper, while sweeping the heap I annotate segments with occupation rate. This can be used by a compacting algorithm to compact only segments which are not used a lot.!
Item was added: + ----- Method: SpurAnalysingSweeper>>globalSweepAndSegmentOccupationAnalysis (in category 'sweep phase') ----- + globalSweepAndSegmentOccupationAnalysis + self internalGlobalSweepAndSegmentOccupationAnalysis. + manager checkFreeSpace: GCModeFull. + manager unmarkSurvivingObjectsForCompact.!
Item was added: + ----- Method: SpurAnalysingSweeper>>internalGlobalSweepAndSegmentOccupationAnalysis (in category 'sweep phase') ----- + internalGlobalSweepAndSegmentOccupationAnalysis + "Iterate over old space, free unmarked objects, annotate each segment with each occupation" + | currentEntity nextBridge start segmentIndex currentUsed currentUnused | + currentEntity := manager firstObject. + nextBridge := manager segmentManager bridgeAt: 0. + segmentIndex := currentUnused := currentUsed := 0. + [self oop: currentEntity isLessThan: manager endOfMemory] whileTrue: + [currentEntity = nextBridge + ifTrue: + ["End of segment, set occupation" + self + setOccupationAtIndex: segmentIndex + used: currentUsed + unused: currentUnused. + currentUnused := currentUsed := 0. + segmentIndex := segmentIndex + 1. + self unmark: currentEntity. + nextBridge := manager segmentManager bridgeAt: segmentIndex] + ifFalse: + ["In-segment, sweep and compute occupation" + (self canUseAsFreeSpace: currentEntity) + ifTrue: + ["bulkFreeChunkFrom: may change a 1 word header + object to a double word header object" + start := manager startOfObject: currentEntity. + self bulkFreeChunkFrom: currentEntity. + currentEntity := manager objectStartingAt: start. + currentUnused := currentUnused + (manager numSlotsOfAny: currentEntity)] + ifFalse: + [self unmark: currentEntity. + currentUsed := currentUsed + (manager numSlotsOfAny: currentEntity)]]. + currentEntity := manager objectAfter: currentEntity limit: manager endOfMemory]. + "set last segment (last bridge = endOfMemory)" + self + setOccupationAtIndex: segmentIndex + used: currentUsed + unused: currentUnused.!
Item was added: + ----- Method: SpurAnalysingSweeper>>occupationOf: (in category 'segment access') ----- + occupationOf: segInfo + self subclassResponsibility!
Item was added: + ----- Method: SpurAnalysingSweeper>>setOccupationAtIndex:used:unused: (in category 'segment access') ----- + setOccupationAtIndex: segmentIndex used: used unused: unused + self subclassResponsibility!
Item was changed: CogClass subclass: #SpurCompactor instanceVariableNames: 'manager scavenger coInterpreter' classVariableNames: '' poolDictionaries: 'SpurMemoryManagementConstants VMBasicConstants VMSpurObjectRepresentationConstants' category: 'VMMaker-SpurMemoryManager'!
+ !SpurCompactor commentStamp: 'cb 4/27/2018 09:38' prior: 0! + Abstract common superclass of all compactors to define apis and simulation variables. - !SpurCompactor commentStamp: 'cb 4/26/2018 13:53' prior: 0! - Common superclass of all compactors to define apis and simulation variables.
- IMPORTANT: This defines APIs only, subclassing is prohibited on auxiliary classes (Slang compiler won't find inherited methods). - The full GC in Spur is split in two, the marking phase and the compactor phase. The subclasses of SpurCompactor are implementations of the second phase, so they are called once the marking phase is finished. SpurCompactor is reponsible for: - freeing unmarked objects - compacting the live old space objects (though each subclass define what it does, some spurCompactor may not compact) - unmarking all objects remaining live - updating oops directly referred by the VM when they are moved (remapObj:/shouldRemapObj: thingy)
The main apis are the following: - biasForGC/biasForSnapshot: tells the compactor if the GC is performed for snapshots or not, in general we want to compact more aggressively for snapshots to avoid saving large files with many unused space. - compact: main API, should free the unmarked object, unmark the objects remaining live and potentially compact the heap - remapObj:/shouldRemapObj: => Not really sure what this does, it seems it has to do with updating oops directly referred by the VM when they are moved. + - postSwizzleAction: if you want to do something at start-up after swizzle phase (typically useful if your compaction algo uses segInfos)
- Instance Variables coInterpreter: <StackInterpreter> + scavenger: <SpurGenerationScavenger> - compactedCopySpace: <SpurNewSpaceSpace> manager: <SpurMemoryManager>!
Item was changed: + SpurAnalysingSweeper subclass: #SpurSelectiveCompactor - SpurSweeper subclass: #SpurSelectiveCompactor instanceVariableNames: 'segmentToFill' classVariableNames: 'MaxOccupationForCompaction' poolDictionaries: '' category: 'VMMaker-SpurMemoryManager'!
+ !SpurSelectiveCompactor commentStamp: 'cb 4/27/2018 09:50' prior: 0! - !SpurSelectiveCompactor commentStamp: 'cb 4/26/2018 13:59' prior: 0! SpurSelectiveCompactor compacts memory by selecting the memory segments with the most free space and compacting only those, to limit fragmentation while being really quick to perform. The algorithm is fast mostly because it does not update pointers: they are updated lazily during the next marking phase, so there is no need to read the fields of objects in other memory segments that the one compacted.
The algorithm works as follow. First, a global sweep pass iterates over the memory linearly, changing unmarked objects to free chunks and concatenating free chunks. During the global sweep phase, the segments of the heap are analysed to determine the percentage of occupation. Second, the least occupied segments are compacted by copying the remaining live objects into an entirely free segment, called regionToFill (we detail later in the paragraph where regionToFill comes from), changing their values to forwarding objects and marking the free chunks as unavailable (removed from free list and marked as data objects). Third, the next marking phase removes all forwarders. Fourth, at the beginning of the next compaction phase the compacted segments from the previous GC can be entirely marked as free space (No need to check anything inside, there were only forwarders and trash data). One of the compacted segment is then selected as the segmentToFill, others are just marked as free chunks.
The compaction is effectively partial, compacting only the most critical segments of the heap to limit fragmentation. Compaction time is crazy low, since a low number of objects are moved and pointer updated is lazily done during the next marking phase, while still preventing memory fragmentation.
Now this works well when biasForGC is true, but when performing a snapshot, the compactor is just total crap (we need to figure out a solution).
- IMPORTANT: I could not figure out to make inheritance work so I copied methods from SpurSweeper here. - segmentToFill <SegInfo> the segment that will be filled through the copying algorithm
+ ------------------------ + + Segment abuse: + The swizzle field of segInfo is abused by using the low 8 bits for occupation and the 9th bit as isBeingCompacted bit. + !
Item was removed: - ----- Method: SpurSelectiveCompactor>>globalSweepAndSegmentOccupationAnalysis (in category 'sweep phase') ----- - globalSweepAndSegmentOccupationAnalysis - self internalGlobalSweepAndSegmentOccupationAnalysis. - manager checkFreeSpace: GCModeFull. - manager unmarkSurvivingObjectsForCompact.!
Item was removed: - ----- Method: SpurSelectiveCompactor>>internalGlobalSweepAndSegmentOccupationAnalysis (in category 'sweep phase') ----- - internalGlobalSweepAndSegmentOccupationAnalysis - "Iterate over old space, free unmarked objects, annotate each segment with each occupation" - | currentEntity nextBridge start segmentIndex currentUsed currentUnused | - currentEntity := manager firstObject. - nextBridge := manager segmentManager bridgeAt: 0. - segmentIndex := currentUnused := currentUsed := 0. - [self oop: currentEntity isLessThan: manager endOfMemory] whileTrue: - [currentEntity = nextBridge - ifTrue: - ["End of segment, set occupation" - self - setOccupationAtIndex: segmentIndex - used: currentUsed - unused: currentUnused. - currentUnused := currentUsed := 0. - segmentIndex := segmentIndex + 1. - self unmark: currentEntity. - nextBridge := manager segmentManager bridgeAt: segmentIndex] - ifFalse: - ["In-segment, sweep and compute occupation" - (self canUseAsFreeSpace: currentEntity) - ifTrue: - ["bulkFreeChunkFrom: may change a 1 word header - object to a double word header object" - start := manager startOfObject: currentEntity. - self bulkFreeChunkFrom: currentEntity. - currentEntity := manager objectStartingAt: start. - currentUnused := currentUnused + (manager numSlotsOfAny: currentEntity)] - ifFalse: - [self unmark: currentEntity. - currentUsed := currentUsed + (manager numSlotsOfAny: currentEntity)]]. - currentEntity := manager objectAfter: currentEntity limit: manager endOfMemory]. - "set last segment (last bridge = endOfMemory)" - self - setOccupationAtIndex: segmentIndex - used: currentUsed - unused: currentUnused.!
Item was changed: ----- Method: SpurSelectiveCompactor>>isSegmentBeingCompacted: (in category 'segment access') ----- isSegmentBeingCompacted: segInfo <var: 'segInfo' type: #'SpurSegmentInfo *'> + "Swizzle is abused bit 8 isBeingCompacted bits 0-7 occupation" - "Swizzle is abused bit 8 isClaimed bits 0-7 occupation" ^ segInfo swizzle anyMask: 1 << 8!
Item was changed: ----- Method: SpurSelectiveCompactor>>markSegmentAsBeingCompacted: (in category 'segment access') ----- markSegmentAsBeingCompacted: segInfo <var: 'segInfo' type: #'SpurSegmentInfo *'> + "Swizzle is abused bit 8 isBeingCompacted bits 0-7 occupation" - "Swizzle is abused bit 8 isClaimed bits 0-7 occupation" segInfo swizzle: (segInfo swizzle bitOr: 1 << 8)!
Item was changed: ----- Method: SpurSelectiveCompactor>>occupationOf: (in category 'segment access') ----- occupationOf: segInfo <var: 'segInfo' type: #'SpurSegmentInfo *'> + "Swizzle is abused bit 8 isBeingCompacted bits 0-7 occupation" - "Swizzle is abused bit 8 isClaimed bits 0-7 occupation" ^segInfo swizzle bitAnd: 16rFF!
Item was removed: - ----- Method: SpurSelectiveCompactor>>setOccupation:used:unused: (in category 'segment access') ----- - setOccupation: segInfo used: used unused: unused - <var: 'segInfo' type: #'SpurSegmentInfo *'> - "Swizzle is abused bit 8 isClaimed bits 0-7 occupation - Setting occupation resets the claim bit" - | occupation | - occupation := used * 255 // (used + unused). - segInfo swizzle: occupation!
Item was changed: ----- Method: SpurSelectiveCompactor>>setOccupationAtIndex:used:unused: (in category 'segment access') ----- setOccupationAtIndex: segmentIndex used: used unused: unused + "WARNING: Resets the isCompacted bit" + "Swizzle is abused bit 8 isBeingCompacted bits 0-7 occupation - "Swizzle is abused bit 8 isClaimed bits 0-7 occupation Setting occupation resets the claim bit" | occupation segInfo | <var: 'segInfo' type: #'SpurSegmentInfo *'> segInfo := self addressOf: (manager segmentManager segments at: segmentIndex). occupation := used * 255 // (used + unused). segInfo swizzle: occupation!
Item was changed: SpurCompactor subclass: #SpurSweeper instanceVariableNames: 'biasForGC' classVariableNames: '' poolDictionaries: '' category: 'VMMaker-SpurMemoryManager'!
+ !SpurSweeper commentStamp: 'cb 4/27/2018 09:43' prior: 0! - !SpurSweeper commentStamp: 'cb 10/2/2017 11:34' prior: 0! SpurSweeper is a sweep-only algorithm, setting the compactor to SpurSweeper effectively changes the fullGC to a mark-sweep non-moving algorithm.
+ SpurSweeper is a reference implementation if one wants to evaluate GC performance and compare it to a Mark-Sweep. It's also the only non-moving GC available right now which can be convenient for some experiments. One of the main reason why it was implemented is because advanced compaction algorithm includes a sweep phase (See SelectiveCompactor for example) and SpurSweeper allows to debug the sweep phase separatedly. + ! - SpurSweeper has two main purposes: - 1. SpurSelectiveCompactor includes a sweep algorithm, inherited from SpurSweeper, and SpurSweeper allows to debug it separatedly. - 2. SpurSweeper is a non-moving GC which can be convenient in some cases (For example when accessing objects from C in a concurrent thread called with ThreadedFFI, the C code can access the objects during fullGC since there won't be conflict with object fields being updated while being read). - - For snapshots a non-compacting algortihm does not make sense, hence a more aggressive compactor is called instead (see #compact).!
Item was added: + SpurAnalysingSweeper subclass: #SpurTrackingCompactor + instanceVariableNames: '' + classVariableNames: '' + poolDictionaries: '' + category: 'VMMaker-SpurMemoryManager'! + + !SpurTrackingCompactor commentStamp: 'cb 4/27/2018 09:58' prior: 0! + SpurTrackingCompactor is a derived simplified implementation of Garbage First (G1) algorithm (Java 9 default GC). + + SpurTrackingCompactor compacts memory by selecting the memory segments with the most free space and compacting only those, to limit fragmentation while being really quick to perform. To update efficiently the references to moved objects, SpurTrackingCompactor uses a per segment remembered table in the form with a card marking scheme, hence when compacting segments, instead of scanning all the heap for pointer updates, it scans only the moved objects and the objects remembered for the segment. Since segments compacted are almost free segments, the remembered table is small upon compaction. + + This algorithm requires extra GC write barriers and higher aligment in segments for efficient write barrier (bits in the pointer are used to know to which segment an object belongs). + + !